Codeforces Round #590 (Div. 3)【D题：26棵树状数组维护字符出现次数】

A题

题意：给你 n 个数 , 你需要改变这些数使得这 n 个数的值相等 , 并且要求改变后所有数的和需大于等于原来的所有数字的和 , 然后输出满足题意且改变后最小的数值。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define int long long

 signed main(){

     int _;

     cin>>_;

     while(_--){

         int n;

         cin>>n;

         int arr[n+];

         int s=;

         for(int i=;i<=n;i++){

             cin>>arr[i];

             s+=arr[i];

         }

         int x=s/n;

         if(s%n==){

             cout<<x;

         }else{

             cout<<x+;

         }

         cout<<endl;

     }

     return ;

 }

B1，B2题

题意：给你个长度为 n 的数组和一个队列 , 队列最多可以同时存在 k 个数。遍历这个数组 , 如果当前数组对应的数在队列中则不做改动 , 如果不在则将它插入队首 , 并且将队尾弹出。遍历完后按照队列顺序输出。

思路：模拟即可【deque+map】

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define int long long

 map<int,int> vis;

 deque<int> q;

 signed main(){

     int n,k;

     cin>>n>>k;

     int temp;

     for(int i=;i<=n;i++){

         scanf("%lld",&temp);

         if(vis[temp]){

             continue;

         }else{

             vis[temp]++;

             q.push_front(temp);

             if(q.size()>k){

                 int x=q.back();

                 q.pop_back();

                 vis[x]--;

             }

         }

     }

     deque<int>::iterator it = q.begin();

     cout<<q.size()<<endl;

     for(;it!=q.end();it++){

         printf("%lld ",*it);

     }

     return ;

 }

C题：

题意：有六种管子 , 其中1、2可以互相转换， 3、4、5、6可以互相转换，然后给你两行管道，每行有 n 列问水能不能从左上角（第1行第1列）流到右下角（第2行第n列）

思路：模拟即可。判断是否从row==2行流出。是，则判断流出的水是不是水平的。否则，直接NO。【注意：后面四种的形状只能上下两个都是才能往前走】

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int _;

     cin>>_;

     while(_--){

         int n;

         cin>>n;

         string s1,s2;

         cin>>s1>>s2;

         int mp[][n+];

         int row=;

         int flag=;

         for(int i=;i<n;i++){

             if(!flag){

                 break;

             }

             if(i==){

                 if(s1[i]==''||s1[i]==''){

                     mp[row][i]=;

                 }else{

                     mp[row][i]=;

                     row=;

                     if(s2[i]==''||s2[i]==''){

                         flag=;

                         break;

                     }else{

                         mp[row][i]=;

                     }

                 }

                 continue;

             }

             if(row==){

                 if(s1[i]==''||s1[i]==''){

                     mp[row][i]=;

                     continue;

                 }else{

                     mp[row][i]=;

                     row=;

                     if(s2[i]==''||s2[i]==''){

                         flag=;

                         break;

                     }else{

                         mp[row][i]=;

                     }

                 }

             }else{

                 if(s2[i]==''||s2[i]==''){

                     mp[row][i]=;

                     continue;

                 }else{

                     mp[row][i]=;

                     row=;

                     if(s1[i]==''||s1[i]==''){

                         flag=;

                         break;

                     }else{

                         mp[row][i]=;

                     }

                 }

             }

         }

         if(!flag||row==){

             printf("NO\n");

             continue;

         }

         if(mp[][n-]==||mp[][n-]==){

             printf("YES\n");

         }else{

             printf("NO\n");

         }

     }

     return ;

 } 

 /*

 6

 7

 2323216

 1615124

 1

 3

 4

 2

 13

 24

 2

 12

 34

 3

 536

 345

 2

 46

 54

 */

D题

题意：给你一个字符串，有q个操作：
①、将 pos 位置的字符改为 c

②、查询 L~ R 区间不同字符的个数

思路1：set模拟实现。

AC代码：

#include<bits/stdc++.h>

using namespace std;

set<int> s[];

char str[];

int main(){

    scanf("%s",str+);

    for(int i=;i<=strlen(str+);i++){

        s[str[i]-'a'].insert(i);

    }

    int _;

    scanf("%d",&_);

    while(_--){

        int T;

        scanf("%d",&T);

        if(T==){

            int x;

            char c;

            scanf("%d",&x);

            cin>>c;

            s[str[x]-'a'].erase(x);

            s[c-'a'].insert(x);

            str[x]=c;

        }else{

            int l,r;//cin>>l>>r;

            scanf("%d%d",&l,&r);

            int ans=;

            for(int i=;i<;i++){

                set<int>::iterator it;

                it=s[i].lower_bound(l);

                if(it==s[i].end()){

                    continue;

                }

                if(*it>=l&&*it<=r)

                    ans++;

            }

            printf("%d\n",ans);

        }

    }

    return ;

}

思路2：【了解了大佬们的写法】维护26个树状数组,代表每个字母从1到i出现了多少次,对于查询,遍历这26个树状数组看每个字母是否在区间内出现,对于修改,这个位置原来的字母减去1,新来的字母加上1即可.

AC代码：

 #include<bits/stdc++.h>// 维护26棵树状数组QAQ 

 using namespace std;

 #define int long long

 int n;

 struct str{

     int c[];

     int lowbit(int x){

         return x&(-x);

     }

     void update(int x,int v){

         for(int i=x;i<=n;i+=lowbit(i))

             c[i]+=v;

     }

     int getsum(int x){

         int res=;

         for(int i=x;i;i-=lowbit(i))

             res+=c[i];

         return res;

     }

     int query(int l,int r){

         return getsum(r)-getsum(l-);

     }

 }st[];

 signed main(){

     string s;

     cin>>s;

     n=s.size();

     for(int i=;i<s.size();i++){

         st[s[i]-'a'].update(i+,);

     }

     int Q;

     cin>>Q;

     int temp;

     while(Q--){

         cin>>temp;

         if(temp==){

             int x;

             char y;

             cin>>x>>y;

             st[s[x-]-'a'].update(x,-);

             s[x-]=y;

             st[y-'a'].update(x,);

         }else{

             int sum=;

             int L,R;

             cin>>L>>R;

             for(int i=;i<;i++){

                 if(st[i].query(L,R)>)

                     sum++;

             }

             printf("%lld\n",sum);

         }

     }

     return ;

 }

巴特西

Codeforces Round #590 (Div. 3)【D题：26棵树状数组维护字符出现次数】

最新文章

热门文章