A. Equalize Prices Again

题目链接：https://codeforces.com/contest/1234/problem/A

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

分析：

签到题。记原来 n 个数的和为 sum , 先取这些数的平均值 ave , 然后每次判断 ave * n >= sum 是否成立成立则直接输出 , 不成立将 ave ++

 #include<bits/stdc++.h>

 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)

 #define sd(n) scanf("%d",&n)

 #define sdd(n,m) scanf("%d%d",&n,&m)

 #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)

 #define pd(n) printf("%d\n", (n))

 #define pdd(n,m) printf("%d %d\n", n, m)

 #define pld(n) printf("%lld\n", n)

 #define pldd(n,m) printf("%lld %lld\n", n, m)

 #define sld(n) scanf("%lld",&n)

 #define sldd(n,m) scanf("%lld%lld",&n,&m)

 #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)

 #define sf(n) scanf("%lf",&n)

 #define sff(n,m) scanf("%lf%lf",&n,&m)

 #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)

 #define rep(i,a,n) for (int i=a;i<=n;i++)

 #define per(i,n,a) for (int i=n;i>=a;i--)

 #define mm(a,n) memset(a, n, sizeof(a))

 #define pb push_back

 #define all(x) (x).begin(),(x).end()

 #define fi first

 #define se second

 #define ll long long

 #define numm ch - 48

 #define INF 0x3f3f3f3f

 #define pi 3.14159265358979323

 #define debug(x) cout << #x << ": " << x << endl

 #define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;

 #define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;

 #define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;

 using namespace std;

 template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);

 for(res=numm;isdigit(ch=getchar());res=(res<<)+(res<<)+numm);flag&&(res=-res);}

 template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}

 ll pow_mod(ll x, ll n , ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}

 const int N = 1e3+;

 int main()

 {

     int q , n;

     sd(q);

     while(q --)

     {

         sd(n);

         int t = ,ans = ;

         rep(i , , n)

         {

             int x;

             sd(x);

             t += x;

         }

         ans = t / n;

         while(ans * n < t)

         {

             ans  = ans + ;

         }

     pd(ans);

     }

     return ;

 }

B1. Social Network (easy version)

题目链接：https://codeforces.com/contest/1234/problem/B1

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

分析：

签到题。直接用 set 判断当前数是否已经在队列中、 deque 进行头插尾删和储存

 #include<bits/stdc++.h>

 #define ll long long

 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)

 using namespace std;

 const int N = 2e5+;

 int n , k;

 ll a[N];

 set<ll>qq;

 deque<ll>txc;

 deque<ll>::iterator it;

 int main()

 {

     ios;

     cin >> n >> k;

     cin >> a[];

     qq.insert(a[]);

     txc.push_front(a[]);

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

     {

         cin >> a[i];

         if(qq.count(a[i])) continue;

         if(qq.count(a[i]) ==  && qq.size() < k)

         {

             qq.insert(a[i]);

             txc.push_front(a[i]);

         }

         else if(qq.count(a[i]) ==  && qq.size() == k)

         {

             it = txc.end(); it--;

             qq.erase(*it);

             txc.pop_back();

             txc.push_front(a[i]);

             qq.insert(a[i]);

         }

     }

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

     for(it = txc.begin() ; it != txc.end(); it ++)

     {

         cout << *it << " ";

     }

     return ;

 }

B2. Social Network (hard version)

题目链接：https://codeforces.com/contest/1234/problem/B2

改变了 n 和 k 的范围 , 因为 n 和 k 最大也还是只有 2e5 + 10 , 所以对于set + deque的解法是不会造成影响的同B1一样的代码

C. Pipes

题目链接：https://codeforces.com/contest/1234/problem/C

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

分析：

因为管子之间可以互相转换，所以我们可以先将1、2类型的管子记为1 ， 3、4、5、6类型的管子记为2 , 然后仔细思考我们会发现水的流向肯定是固定的：假设水是从第k列第j行流向第k + 1列, 那么第k+1列肯定是用第j行的管子接水 , 如果第k+1列第j行的管子类型为1 , 那么水将直接流向第k+2列 ; 如果第k+1列第j行的管子类型为2 , 那么水只能传给 j 的上一行或者下一行 , 然后再传向第k+2列 , 因为每行每列的管子类型已经确定了, 所以水的流向也就是固定的了。而水能从当前列流向下一列的条件只有几个：

①接收水的管子类型为 1 ，所在行为 j 直接流向下一列的第 j 行

②接收水的管子类型为 2 ，则如果 j ^ 1 行管子的类型也为 2 ，则流向下一列的第 j ^ 1行

剩下情况水皆不能流通（水不能倒流），所以直接dfs跑一遍就可以了

 #include<bits/stdc++.h>

 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)

 #define sd(n) scanf("%d",&n)

 #define sdd(n,m) scanf("%d%d",&n,&m)

 #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)

 #define pd(n) printf("%d\n", (n))

 #define pdd(n,m) printf("%d %d\n", n, m)

 #define pld(n) printf("%lld\n", n)

 #define pldd(n,m) printf("%lld %lld\n", n, m)

 #define sld(n) scanf("%lld",&n)

 #define sldd(n,m) scanf("%lld%lld",&n,&m)

 #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)

 #define sf(n) scanf("%lf",&n)

 #define sff(n,m) scanf("%lf%lf",&n,&m)

 #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)

 #define rep(i,a,n) for (int i=a;i<=n;i++)

 #define per(i,n,a) for (int i=n;i>=a;i--)

 #define mm(a,n) memset(a, n, sizeof(a))

 #define pb push_back

 #define all(x) (x).begin(),(x).end()

 #define fi first

 #define se second

 #define ll long long

 #define numm ch - 48

 #define INF 0x3f3f3f3f

 #define pi 3.14159265358979323

 #define debug(x) cout << #x << ": " << x << endl

 #define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;

 #define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;

 #define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;

 using namespace std;

 template<typename T>void read(T &res)

 {

     bool flag=false;

     char ch;

     while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);

     for(res=numm; isdigit(ch=getchar()); res=(res<<)+(res<<)+numm);

     flag&&(res=-res);

 }

 template<typename T>void Out(T x)

 {

     if(x<)putchar('-'),x=-x;

     if(x>)Out(x/);

     putchar(x%+'');

 }

 ll pow_mod(ll x, ll n , ll mod)

 {

     ll res=;

     while(n)

     {

         if(n&)res=res*x%mod;

         x=x*x%mod;

         n>>=;

     }

     return res;

 }

 const int N = 1e3+;

 int n;

 string s1 , s2 ,s[];

 bool dfs(int i, int j)

 {

     if(i == n && j == )

         return ;

     if(i == n) return ;

     if(s[][i] == '' && s[][i] == '')

     {

         if(j == )  return dfs(i +  , );

         else return ;

     }

     if(s[][i] == '' && s[][i] == '')

     {

         if(j == ) return dfs(i +  , );

         else return ;

     }

     if(s[][i] == '' && s[][i] == '')

     {

         return dfs(i +  , j);

     }

     if(s[][i] == '' && s[][i] == '')

     {

         return dfs(i +  , j ^ );

     }

 }

 int main()

 {

     ios;

     int t;

     cin >> t;

     while(t--)

     {

         cin >> n;

         cin >> s1 >> s2;

         s[] = s1 , s[] = s2;

         rep(i , ,n - )

         {

             if(s[][i] == '' || s[][i] == '') s[][i] = '';

             else s[][i] = '';

             if(s[][i] == '' || s[][i] == '') s[][i] = '';

             else s[][i] = '';

         }

         if(dfs( , )) cout << "YES" << endl;

         else cout << "NO" << endl;

     }

     return ;

 }

D. Distinct Characters Queries

题目链接：https://codeforces.com/contest/1234/problem/D

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

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

分析：

挺水的一题。因为全是小写字符 , 所以我们可以对每个单独字符开个线段树, 那么一共就开了26个线段树 ,然后预处理：将母串中第 i 个位置的字符对应的线段树的第 i 个区间的值 + 1。

那么当操作为 ① 的时候我们只要将母串pos位置的字符对应线段树的pos区间值 -1 , 然后c字符对应线段树的pos区间 +1

当操作为 ②的时候我们只要判断每个字符是否有出现在L ~ R区间 , 即遍历 26 颗线段树 L ~ R 的区间和是否为 0 .若不为 0 , ans++ , 遍历完后输出ans即可

 #include<bits/stdc++.h>

 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)

 #define sd(n) scanf("%d",&n)

 #define sdd(n,m) scanf("%d%d",&n,&m)

 #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)

 #define pd(n) printf("%d\n", (n))

 #define pdd(n,m) printf("%d %d\n", n, m)

 #define pld(n) printf("%lld\n", n)

 #define pldd(n,m) printf("%lld %lld\n", n, m)

 #define sld(n) scanf("%lld",&n)

 #define sldd(n,m) scanf("%lld%lld",&n,&m)

 #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)

 #define sf(n) scanf("%lf",&n)

 #define sff(n,m) scanf("%lf%lf",&n,&m)

 #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)

 #define rep(i,a,n) for (int i=a;i<=n;i++)

 #define per(i,n,a) for (int i=n;i>=a;i--)

 #define mm(a,n) memset(a, n, sizeof(a))

 #define pb push_back

 #define all(x) (x).begin(),(x).end()

 #define fi first

 #define se second

 #define ll long long

 #define numm ch - 48

 #define INF 0x3f3f3f3f

 #define sz(x) ((int)x.size())

 #define pi 3.14159265358979323

 #define debug(x) cout << #x << ": " << x << endl

 #define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;

 #define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;

 #define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;

 using namespace std;

 template<typename T>void read(T &res)

 {

     bool flag=false;

     char ch;

     while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);

     for(res=numm; isdigit(ch=getchar()); res=(res<<)+(res<<)+numm);

     flag&&(res=-res);

 }

 template<typename T>void Out(T x)

 {

     if(x<)putchar('-'),x=-x;

     if(x>)Out(x/);

     putchar(x%+'');

 }

 ll pow_mod(ll x, ll n , ll mod)

 {

     ll res=;

     while(n)

     {

         if(n&)res=res*x%mod;

         x=x*x%mod;

         n>>=;

     }

     return res;

 }

 #define lson l,mid,rt << 1

 #define rson mid + 1,r,rt << 1 | 1

 #define ll long long

 using namespace std;

 const int N = 4e5 + ;

 const ll mod = 1e9 + ;

 ll n,k;

 ll a[N];

 int t[N][];

 void update(int l,int r,int rt,int id,int k,int val)

 {

     if(k < l || k > r) return ;

     if(l == r)

     {

         t[rt][id] += val;

         return ;

     }

     int mid = l + r >> ;

     if(k <= mid) update(lson,id,k,val);

     else update(rson,id,k,val);

     t[rt][id] = t[rt << ][id] + t[rt <<  | ][id];

 }

 int qu(int l,int r,int rt,int ql,int qr,int id)

 {

     if(r < ql || l > qr) return ;

     int res = ;

     if(ql <= l && qr >= r) return t[rt][id];

     int mid = l + r >> ;

     if(ql <= mid)  res += qu(lson,ql,qr,id);

     if(qr > mid)  res += qu(rson,ql,qr,id);

     return res;

 }

 int main()

 {

     string str = " ";

     string strr;

     cin >> strr;

     str += strr;

     n = sz(strr);

     rep(i , ,n)

     {

         update(,n,,str[i] - 'a',i,);

     }

     int q,op,l,r;

     sd(q);

     while(q--)

     {

         sd(op);

         if(op == )

         {

             int pos;

             char c;

             sd(pos);

             cin  >> c;

             update(,n,,str[pos] - 'a',pos ,-);

             str[pos] = c;

             update(,n,,c - 'a',pos,);

         }

         else

         {

             sdd(l , r);

             ll ans = ;

             rep(i,,)

             {

                 if( < (qu(,n,,l,r,i))) ans++;

             }

             pd(ans);

         }

     }

     return ;

 }

赛后听说有人是用26个set做的 ,因为set占用的空间比较小，所以我也用set写了一遍

思路：每个字符对应set存每个字符在母串中的位置 , 查询的时候只要对 L 进行二分查找判断找到的位置是否 <= R

因为可能是找不到的 , 所以我们可以用两种方法避免:

①、再加个条件——判断lower_bound(L) 是否 >= L

②、向每个set插入一个大于母串长度的数

两种方法我用注释区分

 #include<bits/stdc++.h>

 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)

 #define sd(n) scanf("%d",&n)

 #define sdd(n,m) scanf("%d%d",&n,&m)

 #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)

 #define pd(n) printf("%d\n", (n))

 #define pdd(n,m) printf("%d %d\n", n, m)

 #define pld(n) printf("%lld\n", n)

 #define pldd(n,m) printf("%lld %lld\n", n, m)

 #define sld(n) scanf("%lld",&n)

 #define sldd(n,m) scanf("%lld%lld",&n,&m)

 #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)

 #define sf(n) scanf("%lf",&n)

 #define sff(n,m) scanf("%lf%lf",&n,&m)

 #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)

 #define rep(i,a,n) for (int i=a;i<=n;i++)

 #define per(i,n,a) for (int i=n;i>=a;i--)

 #define mm(a,n) memset(a, n, sizeof(a))

 #define pb push_back

 #define all(x) (x).begin(),(x).end()

 #define fi first

 #define se second

 #define ll long long

 #define numm ch - 48

 #define INF 0x3f3f3f3f

 #define pi 3.14159265358979323

 #define debug(x) cout << #x << ": " << x << endl

 #define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;

 #define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;

 #define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;

 using namespace std;

 template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);

 for(res=numm;isdigit(ch=getchar());res=(res<<)+(res<<)+numm);flag&&(res=-res);}

 template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}

 ll pow_mod(ll x, ll n , ll mod){ll res=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}

 const int N = 1e3+;

 string str = " ";

 set<int>haha[];

 int main()

 {

     ios;

     string a;

     cin >> a;

     str += a;

     rep(i ,  , )

     haha[i].insert();

     rep(i ,  , str.size() - )

     {

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

     }

     int q;

     cin >> q;

     while(q--)

     {

         int x;

         cin >> x;

         if(x == )

         {

             int pos ;char ch;

             cin >> pos >> ch;

             haha[ str[pos] - 'a' +  ].erase( pos );

             haha[ch - 'a' + ].insert(pos);

             str[pos] = ch;

         }

         else if(x == )

         {

             int l , r , ans = ;;

             cin >> l >> r;

             rep(i , ,)

             {

                 if(*haha[i].lower_bound(l) <= r/* && *haha[i].lower_bound(l) >= l*/)

                 {

                     ans ++;

                 }

             }

             cout << ans << endl;

         }

     }

     return ;

 }

巴特西

Codeforces Round #590 (Div. 3)