A. Equalize Prices Again
题目链接：https://codeforces.com/contest/1234/problem/A
题意：给你 n 个数 , 你需要改变这些数使得这 n 个数的值相等 , 并且要求改变后所有数的和需大于等于原来的所有数字的和 , 然后输出满足题意且改变后最小的数值
分析：
签到题。记原来 n 个数的和为 sum , 先取这些数的平均值 ave , 然后每次判断 ave * n >= sum 是否成立成立则直接输出 , 不成立将 ave ++
1 #include<bits/stdc++.h> 2 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) 3 #define sd(n) scanf("%d",&n) 4 #define sdd(n,m) scanf("%d%d",&n,&m) 5 #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) 6 #define pd(n) printf("%d\n", (n)) 7 #define pdd(n,m) printf("%d %d\n", n, m) 8 #define pld(n) printf("%lld\n", n) 9 #define pldd(n,m) printf("%lld %lld\n", n, m) 10 #define sld(n) scanf("%lld",&n) 11 #define sldd(n,m) scanf("%lld%lld",&n,&m) 12 #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) 13 #define sf(n) scanf("%lf",&n) 14 #define sff(n,m) scanf("%lf%lf",&n,&m) 15 #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) 16 #define rep(i,a,n) for (int i=a;i<=n;i++) 17 #define per(i,n,a) for (int i=n;i>=a;i--) 18 #define mm(a,n) memset(a, n, sizeof(a)) 19 #define pb push_back 20 #define all(x) (x).begin(),(x).end() 21 #define fi first 22 #define se second 23 #define ll long long 24 #define numm ch - 48 25 #define INF 0x3f3f3f3f 26 #define pi 3.14159265358979323 27 #define debug(x) cout << #x << ": " << x << endl 28 #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; 29 #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; 30 #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; 31 using namespace std; 32 template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); 33 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} 34 template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} 35 ll pow_mod(ll x, ll n , ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} 36 const int N = 1e3+10; 37 38 int main() 39 { 40 int q , n; 41 sd(q); 42 while(q --) 43 { 44 sd(n); 45 int t = 0,ans = 0; 46 rep(i , 1, n) 47 { 48 int x; 49 sd(x); 50 t += x; 51 } 52 ans = t / n; 53 while(ans * n < t) 54 { 55 ans = ans + 1; 56 } 57 pd(ans); 58 } 59 return 0; 60 }
B1. Social Network (easy version)
题目链接：https://codeforces.com/contest/1234/problem/B1
题意：给你个长度为 n 的数组和一个队列 , 队列最多可以同时存在 k 个数。遍历这个数组 , 如果当前数组对应的数在队列中则不做改动 , 如果不在则将它插入队首 , 并且将队尾弹出。遍历完后按照队列顺序输出
分析：
签到题。 直接用 set 判断当前数是否已经在队列中 、 deque 进行头插尾删和储存
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) 4 using namespace std; 5 const int N = 2e5+10; 6 int n , k; 7 ll a[N]; 8 set<ll>qq; 9 deque<ll>txc; 10 deque<ll>::iterator it; 11 int main() 12 { 13 ios; 14 cin >> n >> k; 15 cin >> a[1]; 16 qq.insert(a[1]); 17 txc.push_front(a[1]); 18 for(int i = 2 ; i <= n ; i++) 19 { 20 cin >> a[i]; 21 if(qq.count(a[i])) continue; 22 if(qq.count(a[i]) == 0 && qq.size() < k) 23 { 24 qq.insert(a[i]); 25 txc.push_front(a[i]); 26 } 27 else if(qq.count(a[i]) == 0 && qq.size() == k) 28 { 29 it = txc.end(); it--; 30 qq.erase(*it); 31 txc.pop_back(); 32 txc.push_front(a[i]); 33 qq.insert(a[i]); 34 } 35 } 36 cout << txc.size() << endl; 37 for(it = txc.begin() ; it != txc.end(); it ++) 38 { 39 cout << *it << " "; 40 } 41 return 0; 42 } 43
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跑一遍就可以了
1 #include<bits/stdc++.h> 2 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) 3 #define sd(n) scanf("%d",&n) 4 #define sdd(n,m) scanf("%d%d",&n,&m) 5 #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) 6 #define pd(n) printf("%d\n", (n)) 7 #define pdd(n,m) printf("%d %d\n", n, m) 8 #define pld(n) printf("%lld\n", n) 9 #define pldd(n,m) printf("%lld %lld\n", n, m) 10 #define sld(n) scanf("%lld",&n) 11 #define sldd(n,m) scanf("%lld%lld",&n,&m) 12 #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) 13 #define sf(n) scanf("%lf",&n) 14 #define sff(n,m) scanf("%lf%lf",&n,&m) 15 #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) 16 #define rep(i,a,n) for (int i=a;i<=n;i++) 17 #define per(i,n,a) for (int i=n;i>=a;i--) 18 #define mm(a,n) memset(a, n, sizeof(a)) 19 #define pb push_back 20 #define all(x) (x).begin(),(x).end() 21 #define fi first 22 #define se second 23 #define ll long long 24 #define numm ch - 48 25 #define INF 0x3f3f3f3f 26 #define pi 3.14159265358979323 27 #define debug(x) cout << #x << ": " << x << endl 28 #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; 29 #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; 30 #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; 31 using namespace std; 32 template<typename T>void read(T &res) 33 { 34 bool flag=false; 35 char ch; 36 while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); 37 for(res=numm; isdigit(ch=getchar()); res=(res<<1)+(res<<3)+numm); 38 flag&&(res=-res); 39 } 40 template<typename T>void Out(T x) 41 { 42 if(x<0)putchar('-'),x=-x; 43 if(x>9)Out(x/10); 44 putchar(x%10+'0'); 45 } 46 ll pow_mod(ll x, ll n , ll mod) 47 { 48 ll res=1; 49 while(n) 50 { 51 if(n&1)res=res*x%mod; 52 x=x*x%mod; 53 n>>=1; 54 } 55 return res; 56 } 57 const int N = 1e3+10; 58 int n; 59 string s1 , s2 ,s[2]; 60 bool dfs(int i, int j) 61 { 62 if(i == n && j == 1) 63 return 1; 64 if(i == n) return 0; 65 if(s[0][i] == '1' && s[1][i] == '2') 66 { 67 if(j == 0) return dfs(i + 1 , 0); 68 else return 0; 69 } 70 if(s[0][i] == '2' && s[1][i] == '1') 71 { 72 if(j == 1) return dfs(i + 1 , 1); 73 else return 0; 74 } 75 if(s[0][i] == '1' && s[1][i] == '1') 76 { 77 return dfs(i + 1 , j); 78 } 79 if(s[0][i] == '2' && s[1][i] == '2') 80 { 81 return dfs(i + 1 , j ^ 1); 82 } 83 } 84 int main() 85 { 86 ios; 87 int t; 88 cin >> t; 89 while(t--) 90 { 91 92 cin >> n; 93 cin >> s1 >> s2; 94 s[0] = s1 , s[1] = s2; 95 rep(i ,0 ,n - 1) 96 { 97 if(s[0][i] == '2' || s[0][i] == '1') s[0][i] = '1'; 98 else s[0][i] = '2'; 99 if(s[1][i] == '1' || s[1][i] == '2') s[1][i] = '1'; 100 else s[1][i] = '2'; 101 } 102 if(dfs(0 , 0)) cout << "YES" << endl; 103 else cout << "NO" << endl; 104 } 105 return 0; 106 } 107
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即可
1 #include<bits/stdc++.h> 2 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) 3 #define sd(n) scanf("%d",&n) 4 #define sdd(n,m) scanf("%d%d",&n,&m) 5 #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) 6 #define pd(n) printf("%d\n", (n)) 7 #define pdd(n,m) printf("%d %d\n", n, m) 8 #define pld(n) printf("%lld\n", n) 9 #define pldd(n,m) printf("%lld %lld\n", n, m) 10 #define sld(n) scanf("%lld",&n) 11 #define sldd(n,m) scanf("%lld%lld",&n,&m) 12 #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) 13 #define sf(n) scanf("%lf",&n) 14 #define sff(n,m) scanf("%lf%lf",&n,&m) 15 #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) 16 #define rep(i,a,n) for (int i=a;i<=n;i++) 17 #define per(i,n,a) for (int i=n;i>=a;i--) 18 #define mm(a,n) memset(a, n, sizeof(a)) 19 #define pb push_back 20 #define all(x) (x).begin(),(x).end() 21 #define fi first 22 #define se second 23 #define ll long long 24 #define numm ch - 48 25 #define INF 0x3f3f3f3f 26 #define sz(x) ((int)x.size()) 27 #define pi 3.14159265358979323 28 #define debug(x) cout << #x << ": " << x << endl 29 #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; 30 #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; 31 #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; 32 using namespace std; 33 template<typename T>void read(T &res) 34 { 35 bool flag=false; 36 char ch; 37 while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); 38 for(res=numm; isdigit(ch=getchar()); res=(res<<1)+(res<<3)+numm); 39 flag&&(res=-res); 40 } 41 template<typename T>void Out(T x) 42 { 43 if(x<0)putchar('-'),x=-x; 44 if(x>9)Out(x/10); 45 putchar(x%10+'0'); 46 } 47 ll pow_mod(ll x, ll n , ll mod) 48 { 49 ll res=1; 50 while(n) 51 { 52 if(n&1)res=res*x%mod; 53 x=x*x%mod; 54 n>>=1; 55 } 56 return res; 57 } 58 #define lson l,mid,rt << 1 59 #define rson mid + 1,r,rt << 1 | 1 60 #define ll long long 61 using namespace std; 62 63 const int N = 4e5 + 5000; 64 const ll mod = 1e9 + 7; 65 66 ll n,k; 67 ll a[N]; 68 int t[N][26]; 69 70 void update(int l,int r,int rt,int id,int k,int val) 71 { 72 if(k < l || k > r) return ; 73 if(l == r) 74 { 75 t[rt][id] += val; 76 return ; 77 } 78 int mid = l + r >> 1; 79 if(k <= mid) update(lson,id,k,val); 80 else update(rson,id,k,val); 81 t[rt][id] = t[rt << 1][id] + t[rt << 1 | 1][id]; 82 83 } 84 int qu(int l,int r,int rt,int ql,int qr,int id) 85 { 86 if(r < ql || l > qr) return 0; 87 int res = 0; 88 if(ql <= l && qr >= r) return t[rt][id]; 89 int mid = l + r >> 1; 90 if(ql <= mid) res += qu(lson,ql,qr,id); 91 if(qr > mid) res += qu(rson,ql,qr,id); 92 return res; 93 } 94 int main() 95 { 96 string str = " "; 97 string strr; 98 cin >> strr; 99 str += strr; 100 n = sz(strr); 101 rep(i ,1 ,n) 102 { 103 update(1,n,1,str[i] - 'a',i,1); 104 } 105 int q,op,l,r; 106 sd(q); 107 while(q--) 108 { 109 sd(op); 110 if(op == 1) 111 { 112 int pos; 113 char c; 114 sd(pos); 115 cin >> c; 116 update(1,n,1,str[pos] - 'a',pos ,-1); 117 str[pos] = c; 118 update(1,n,1,c - 'a',pos,1); 119 } 120 else 121 { 122 sdd(l , r); 123 ll ans = 0; 124 rep(i,0,25) 125 { 126 if(0 < (qu(1,n,1,l,r,i))) ans++; 127 } 128 pd(ans); 129 } 130 } 131 return 0; 132 }
赛后听说有人是用26个set做的 ,因为set占用的空间比较小，所以我也用set写了一遍
思路：每个字符对应set存每个字符在母串中的位置 , 查询的时候只要对 L 进行二分查找判断找到的位置是否 <= R
因为可能是找不到的 , 所以我们可以用两种方法避免:
①、 再加个条件——判断lower_bound(L) 是否 >= L
②、 向每个set插入一个大于母串长度的数
两种方法我用注释区分
1 #include<bits/stdc++.h> 2 #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) 3 #define sd(n) scanf("%d",&n) 4 #define sdd(n,m) scanf("%d%d",&n,&m) 5 #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) 6 #define pd(n) printf("%d\n", (n)) 7 #define pdd(n,m) printf("%d %d\n", n, m) 8 #define pld(n) printf("%lld\n", n) 9 #define pldd(n,m) printf("%lld %lld\n", n, m) 10 #define sld(n) scanf("%lld",&n) 11 #define sldd(n,m) scanf("%lld%lld",&n,&m) 12 #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) 13 #define sf(n) scanf("%lf",&n) 14 #define sff(n,m) scanf("%lf%lf",&n,&m) 15 #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) 16 #define rep(i,a,n) for (int i=a;i<=n;i++) 17 #define per(i,n,a) for (int i=n;i>=a;i--) 18 #define mm(a,n) memset(a, n, sizeof(a)) 19 #define pb push_back 20 #define all(x) (x).begin(),(x).end() 21 #define fi first 22 #define se second 23 #define ll long long 24 #define numm ch - 48 25 #define INF 0x3f3f3f3f 26 #define pi 3.14159265358979323 27 #define debug(x) cout << #x << ": " << x << endl 28 #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; 29 #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; 30 #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; 31 using namespace std; 32 template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); 33 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} 34 template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} 35 ll pow_mod(ll x, ll n , ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} 36 const int N = 1e3+10; 37 string str = " "; 38 set<int>haha[27]; 39 int main() 40 { 41 ios; 42 string a; 43 cin >> a; 44 str += a; 45 rep(i , 1 , 26) 46 haha[i].insert(999999999); 47 rep(i , 1 , str.size() - 1) 48 { 49 haha[str[i] - 'a' + 1].insert(i); 50 } 51 int q; 52 cin >> q; 53 while(q--) 54 { 55 int x; 56 cin >> x; 57 if(x == 1) 58 { 59 int pos ;char ch; 60 cin >> pos >> ch; 61 haha[ str[pos] - 'a' + 1 ].erase( pos ); 62 haha[ch - 'a' + 1].insert(pos); 63 str[pos] = ch; 64 } 65 else if(x == 2) 66 { 67 int l , r , ans = 0;; 68 cin >> l >> r; 69 rep(i ,1 ,26) 70 { 71 if(*haha[i].lower_bound(l) <= r/* && *haha[i].lower_bound(l) >= l*/) 72 { 73 ans ++; 74 } 75 } 76 cout << ans << endl; 77 } 78 } 79 return 0; 80 } 81