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 }
View Code
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
View Code
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
View Code
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 }
View Code
赛后听说有人是用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
View Code