自学内容网 自学内容网

Codeforces Round 962 (Div. 3) ABCDEF(思路+代码)

题目链接https://codeforc es.com/contest/1996

A. Legs

题意

一只鸡有两条腿,一只牛有四条腿,一共有 n n n( n n n是偶数)条腿,问最少多少只动物。

思路

全是牛的时候动物数量最多, 所以 a n s = ⌈ n 4 ⌉ ans = \lceil \frac{n}{4} \rceil ans=4n

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n;
    cin>>n;
    cout<<(n+3)/4<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B. Scale

题意

有一个01数组,请你缩小k倍,然后输出它。

例如:

1
6 3
000111
000111
000111
111000
111000
111000

缩小完变为

01
10

思路

循环输出,每次跳k格即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
char mp[1005][1005];
void solve(){
    int n,k;
    cin>>n>>k;
    rep(i,1,n){
        rep(j,1,n) cin>>mp[i][j];
    }
    for(int i =1;i<=n;i+=k){
        for(int j = 1;j<=n;j+=k){
            cout<<mp[i][j];
        }
        puts("");
    }
}
signed main(){
    // IO;
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C. Sort

题意

给你两个字符串 a , b a,b a,b , 进行 q q q次询问,每次询问 l , r l,r l,r 。 对于每次询问,你可以进行一些次数操作,每次可以使得一个字符变为任意另一个字符, 问最少多少次操作,能够使得 s o r t e d ( a [ l . . r ] ) = s o r t e d ( b [ l . . r ] ) sorted(a[l..r]) = sorted(b[l..r]) sorted(a[l..r])=sorted(b[l..r])

注意:每次询问的修改操作不影响之后的询问。

思路

因为我们会对这两个子串进行排序操作,所以我们就只需要考虑子串中每个字符出现的次数即可。

我们定义两个子串的差异度为 ∑ c h = a z ∣ c n t a [ c h ] − c n t b [ c h ] ∣ \sum_{ch = a}^z |cnta[ch]-cntb[ch]| ch=azcnta[ch]cntb[ch] ,即每种字符在两个子串中数量的差的总和。

我们每次操作可以将一个字符变为另一个字符,因此会使得二者的差异度减少2 。

所以我们总共的操作次数就是差异度除以2。 即 ∑ c h = a z ∣ c n t a [ c h ] − c n t b [ c h ] ∣ 2 \frac{\sum_{ch = a}^z |cnta[ch]-cntb[ch]|}{2} 2ch=azcnta[ch]cntb[ch]

于是我们需要解决的问题变为:如何更快地求出某一子串中所含有的字符数量: 前缀和 ,使用一个sum[N][26] 数组来记录每个字符出现的次数。于是对于某一子串 a [ l . . r ] a[l..r] a[l..r] , 字符 c h ch ch , 出现的次数为sum[r][ch-'a'] - sum[l-1][ch-'a']

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int cnt1[200005][27];
int cnt2[200005][27];
void solve(){
    int n,q;
    cin>>n>>q;
    string a,b;
    cin>>a>>b; a = ' ' + a; b = ' ' + b;
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<26;j++){
            cnt1[i][j] = cnt1[i-1][j] + (a[i] == 'a' + j);
            cnt2[i][j] = cnt2[i-1][j] + (b[i] == 'a' + j);
        }
    }
    while(q--){
        int l, r;
        cin>>l>>r;
        int ans = 0;
        for(int j = 0;j<26;j++){
            ans += abs((cnt1[r][j] - cnt1[l-1][j])-(cnt2[r][j] - cnt2[l-1][j]));
        }
        cout<<ans/2<<'\n';
    }
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D. Fun

题意

给定两个数 n , x n,x n,x , 求满足 a + b + c ≤ x , a b + a c + b c ≤ n a+b+c\le x , ab + ac + bc \le n a+b+cx,ab+ac+bcn 的三元组 ( a , b , c ) (a,b,c) (a,b,c) 的个数。 1 ≤ n , x ≤ 1 0 6 1\le n ,x \le 10^6 1n,x106

注意:三元组是有序的,即 ( 1 , 1 , 2 ) , ( 2 , 1 , 1 ) (1,1,2),(2,1,1) (1,1,2),(2,1,1) 视为不同的三元组

思路

如果暴力枚举,我们需要三重循环分别枚举 a , b , c a,b,c a,b,c ,他们的取值为 1 ≤ a , b , c ≤ x − 2 1\le a,b,c \le x-2 1a,b,cx2 ,此时的复杂度为 O ( x 3 ) O(x^3) O(x3) ,显然是不行的。考虑根据两个条件节时, 我们枚举最外层变量为a, 即在a确定之后:

  • 根据条件1: 一定有 b ≤ x − a − c ≤ x − a − 1 b \le x - a - c \le x - a - 1 bxacxa1 ,于是b只需要枚举到 x − a − 1 x-a-1 xa1即可。
  • 根据条件2:一定有 a ∗ b < n a * b < n ab<n , 即b最大为 ⌊ n a ⌋ \lfloor \frac{n}{a} \rfloor an

二者取min,得到b的最大值。可以得出,此时枚举a和b的复杂度大概为 n l n n nlnn nlnn , 那么我们需要 O ( 1 ) O(1) O(1) 求出c的取值范围,在确定完 a , b a,b a,b 的值后,可以得出$ 1\le c \le min(x - a -b,\frac{ n - ab}{a+b})$ , 而对于每个c,都会对答案贡献1,因此在确定完a和b后, 我们直接令答案加上$ min(x - a -b,\frac{ n - ab}{a+b})$ 即可。总体时间复杂度即为枚举a和b的复杂度 O ( n l n n ) O(nlnn) O(nlnn)

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,x;
    cin>>n>>x;
    int ans =0;
    rep(a,1,x){
        rep(b,1,x){
            if(a+b>=x) break;
            if(a*b>=n) break;
            int nn = n - a * b;
            int c1 = (n-a*b) / (a+b);
            int c2 = x - a - b;
            ans += min(c1,c2);
        }
    }
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

E. Decode

题意

给一个01串S,求对于每一对 ( l , r ) , ( 1 ≤ l ≤ r ≤ n ) (l,r), (1\le l\le r\le n) (l,r),(1lrn) ,计算 ( x , y ) , ( l ≤ x ≤ y ≤ r ) (x,y) ,(l\le x\le y \le r) (x,y),(lxyr) 这样的整数对的个数,要求 S [ x . . y ] S[x..y] S[x..y] 中0 和1的数量相同。

思路

我们考虑逆向思维,找出每一个满足 f 0 ( S [ x . . y ] ) = f 1 ( S [ x . . y ] ) f_0(S[x..y]) = f_1(S[x..y]) f0(S[x..y])=f1(S[x..y]) ( x , y ) (x,y) (x,y)对, 计算每个对的贡献(即为 在多少个子串 S [ l . . r ] S[l..r] S[l..r] 中),将其加和即可。 如果我们确定一个 ( x , y ) (x,y) (x,y) 那么很容易算出, 它的贡献为 x ∗ ( n − y + 1 ) x * (n-y+1) x(ny+1)

那么如何确定这些 ( x , y ) (x,y) (x,y) 对呢,我们考虑前缀和,将字符0的贡献为-1, 字符1的贡献为1 ,那么 f 0 ( S [ x . . y ] ) = f 1 ( S [ x . . y ] ) f_0(S[x..y]) = f_1(S[x..y]) f0(S[x..y])=f1(S[x..y]) 就等价于 s u m [ y ] = s u m [ x − 1 ] sum[y] = sum[x-1] sum[y]=sum[x1] , 我们边枚举y边对这么一个sum数组进行桶计数。于是 c n t [ s u m [ y ] ] cnt[sum[y]] cnt[sum[y]]即表示在y之前,有多少个 x x x满足 s u m [ x − 1 ] = s u m [ y ] sum[x-1] = sum[y] sum[x1]=sum[y] ,但是我们记录数量是不够的,我们还要考虑x的位置,即对于每个y,贡献为 x 1 ∗ ( n − y + 1 ) + x 2 ∗ ( n − y + 1 ) + . . . + x k ∗ ( n − y + 1 ) = ( x 1 + x 2 + . . . + x k ) ∗ ( n − y + 1 ) x_1*(n-y+1) + x_2*(n-y+1)+...+x_k*(n-y+1) = (x_1+x_2+...+x_k)*(n-y+1) x1(ny+1)+x2(ny+1)+...+xk(ny+1)=(x1+x2+...+xk)(ny+1) ,于是我们的桶数组每次应该令 c n t [ s u m [ x ] ] + = i + 1 cnt[sum[x]] += i+1 cnt[sum[x]]+=i+1 , 即记录为每个满足条件的 x x x的和。 (注意每次加到 c n t cnt cnt数组中的是 i + 1 i+1 i+1,不是 i i i ,因为 i = x − 1 i = x-1 i=x1

  • 注意 s u m [ x ] sum[x] sum[x] 可能是负数,我们进行桶计数是要进行偏移 n n n处理
  • 注意对答案加和的过程中取模

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
const int mod = 1e9+7;
void solve(){
    string str;
    cin>>str;
    int n = str.size();str = ' ' + str; // 将字符串变为下标从1开始
    vector<int> cnt(2 * n + 5); // 开2*n大小的桶,因为sum[i]的取值为[-n,n]
    vector<int> sum(n+5);
    cnt[0+n] = 1;
    int ans = 0;
    for(int i = 1;i <= n;i++){
        int y = i;
        sum[y] = sum[y-1];
        if(str[y] == '0') sum[y]--;
        else sum[y] ++;
        ans = (ans + cnt[sum[y]+n] * (n-y+1)%mod)%mod;
        cnt[sum[y] + n] += i+1; // 这里要加一,因为我们存的是sum[x-1],那么对于
    }
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F. Bomb

题意

给两个长度为 n n n的数组 a , b a,b a,b , 你至多进行 k ( 1 ≤ k ≤ 1 0 9 ) k(1\le k \le 10^9) k(1k109)次操作,每次操作如下:
选择一个数 i i i , 获得 a [ i ] a[i] a[i] 枚金币,并令 a [ i ] = m a x ( 0 , a [ i ] − b [ i ] ) a[i] = max(0,a[i]-b[i]) a[i]=max(0,a[i]b[i])

问最多能获得多少金币

思路

我们先考虑 O ( k ) O(k) O(k) 的朴素解法: 每次选择一个最大的 a [ i ] a[i] a[i] ,选择完后使用堆(优先队列)更新最大值,重复选择k次即可。

但是上述代码会导致超时(因为k太大了), 我们考虑二分搜索:

我们设 f ( x ) f(x) f(x)表示令所有的 a [ i ] a[i] a[i] 都减至 a [ i ] < x a[i] < x a[i]<x ,所需要的操作次数。 显而易见, f ( x ) f(x) f(x) 是单调递减的。因此满足二分性。

我们找到这样一个 l l l , 使得 f ( l ) > k , f ( l + 1 ) ≤ k f(l) > k , f(l+1) \le k f(l)>k,f(l+1)k , 这样我们先令所有的 a [ i ] a[i] a[i] 都减至小于 l l l ,此时相比k,会多进行 f ( l ) − k f(l)-k f(l)k 次操作, 因此会导致多获得一些金币,这里每次操作会使我们额外获得 l l l的贡献,令最终的金币数量减去 ( f ( l ) − k ) ∗ l (f(l)-k)*l (f(l)k)l 即为最终答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int n,k;
int a[200005];
int b[200005];
bool check(int x){
    int sum = 0;
    for(int i = 1;i<=n;i++){
        if(a[i]>=x){
            sum += (a[i]-x)/b[i] + 1;
        }
    }
    return sum <= k;
}
void solve(){
    cin>>n>>k;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) cin>>b[i];
    int l =0; int r =1e9+5;
    while(l<r){
        int mid = (l+r+1)>>1;
        if(check(mid)){
            r = mid-1;
        }else{
            l = mid;
        }
    }
    int ans = 0;
    int s = 0;
    for(int i = 1;i<=n;i++){
        if(a[i]>=l){
            int m = (a[i] - l)/b[i] + 1;
            ans += (a[i] + a[i]-(m-1)*b[i])*m/2;
            s += m;   
        }
    }
    ans -= 1LL * l * (s - k);
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}


原文地址:https://blog.csdn.net/qq_66608435/article/details/140856880

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!