传送门
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 105;
5 double a[maxn];
6 int main() {
7 int q; scanf("%d",&q);
8 while (q--) {
9 int n; scanf("%d",&n);
10 for (int i = 1; i <= n; ++i) {
11 scanf("%lf",&a[i]);
12 }
13 double sum = 0;
14 for (int i = 1; i <= n; ++i) sum += a[i];
15 int ans = ceil(sum / n);
16 printf("%d\n",ans);
17 }
18 return 0;
19 }
A. Equalize Prices Again
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+5;
5 bool vis[maxn];
6 int a[maxn], b[maxn];
7 deque<int> que;
8 int main() {
9 int n, k; scanf("%d%d",&n,&k);
10 for (int i = 1; i <= n; ++i) {
11 scanf("%d",&a[i]);
12 b[i] = a[i];
13 }
14 sort(b+1,b+1+n);
15 int m = unique(b+1,b+1+n) - b - 1;
16 for (int i = 1; i <= n; ++i) {
17 int id = lower_bound(b+1,b+1+m,a[i]) - b;
18 if (vis[id] == false) {
19 vis[id] = true;
20 if (que.size() < k) que.push_front(id);
21 else {
22 vis[que.back()] = false;
23 que.pop_back();
24 que.push_front(id);
25 }
26 }
27 else continue;
28 }
29 printf("%d\n",que.size());
30 while (!que.empty()) {
31 int id = que.front(); que.pop_front();
32 printf("%d ",b[id]);
33 }
34 printf("\n");
35 return 0;
36 }
B1. Social Network (easy version)
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+5;
5 bool vis[maxn];
6 int a[maxn], b[maxn];
7 deque<int> que;
8 int main() {
9 int n, k; scanf("%d%d",&n,&k);
10 for (int i = 1; i <= n; ++i) {
11 scanf("%d",&a[i]);
12 b[i] = a[i];
13 }
14 sort(b+1,b+1+n);
15 int m = unique(b+1,b+1+n) - b - 1;
16 for (int i = 1; i <= n; ++i) {
17 int id = lower_bound(b+1,b+1+m,a[i]) - b;
18 if (vis[id] == false) {
19 vis[id] = true;
20 if (que.size() < k) que.push_front(id);
21 else {
22 vis[que.back()] = false;
23 que.pop_back();
24 que.push_front(id);
25 }
26 }
27 else continue;
28 }
29 printf("%d\n",que.size());
30 while (!que.empty()) {
31 int id = que.front(); que.pop_front();
32 printf("%d ",b[id]);
33 }
34 printf("\n");
35 return 0;
36 }
B2. Social Network (hard version)
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+5;
5 string s1, s2;
6 int main() {
7 int q; scanf("%d",&q);
8 while (q--) {
9 int n; scanf("%d",&n);
10 cin >> s1 >> s2;
11 int now_x = 0, now_y = 0;
12 bool flag = true;
13 while (true) {
14 if (now_y == n) {
15 if (now_x == 0) flag = false;
16 break;
17 }
18 if (now_x == 0) {
19 if (s1[now_y] <= '2') {
20 now_y++;
21 }
22 else {
23 if (s2[now_y] <= '2') {
24 flag = false;
25 break;
26 }
27 now_x = 1, now_y++;
28 }
29 }
30 else {
31 if (s2[now_y] <= '2') {
32 now_y++;
33 }
34 else {
35 if (s1[now_y] <= '2') {
36 flag = false;
37 break;
38 }
39 now_x = 0, now_y++;
40 }
41 }
42 }
43 if (flag) puts("YES");
44 else puts("NO");
45 }
46 return 0;
47 }
C. Pipes
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 int C[30][100005];
5 char s[100005];
6 int lowbit(int x) {
7 return x&(-x);
8 }
9 void add(int ch, int x, int d) {
10 while (x <= 100000) {
11 C[ch][x] += d;
12 x += lowbit(x);
13 }
14 }
15 int sum(int ch, int x) {
16 int res = 0;
17 while (x > 0) {
18 res += C[ch][x];
19 x -= lowbit(x);
20 }
21 return res;
22 }
23 int main() {
24 scanf("%s",s+1);
25 int len = strlen(s+1);
26 for (int i = 1; i <= len; ++i) {
27 add(s[i]-'a',i,1);
28 }
29 int q; scanf("%d",&q);
30 while (q--) {
31 int op; scanf("%d",&op);
32 if (op == 1) {
33 int pos; char ch;
34 scanf("%d",&pos); getchar();
35 ch = getchar();
36 add(s[pos]-'a',pos,-1);
37 s[pos] = ch;
38 add(s[pos]-'a',pos,1);
39 }
40 else {
41 int l, r; scanf("%d%d",&l,&r);
42 int ans = 0;
43 for (char ch = 'a'; ch <= 'z'; ++ch) {
44 if (sum(ch-'a',r)-sum(ch-'a',l-1) > 0) ans++;
45 }
46 printf("%d\n",ans);
47 }
48 }
49 return 0;
50 }
D. Distinct Characters Queries
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+5;
5 int a[maxn], p[maxn];
6 vector<int> ve[maxn];
7 int main() {
8 int n, m; scanf("%d%d",&n,&m);
9 for (int i = 1; i <= n; ++i) {
10 p[i] = i;
11 }
12 for (int i = 1; i <= m; ++i) {
13 scanf("%d",&a[i]);
14 ve[a[i]].push_back(i);
15 }
16 ll ans = 0;
17 for (int i = 1; i < m; ++i) {
18 ans += abs(a[i]-a[i+1]);
19 }
20 printf("%lld",ans);
21
22 for (int i = 2; i <= n; ++i) {
23 for (int j = 0; j < ve[i].size(); ++j) {
24 int pos = ve[i][j];
25 if (pos > 1) ans -= abs(i - p[a[pos-1]]);
26 if (pos < m) ans -= abs(i - p[a[pos+1]]);
27 }
28 for (int j = 0; j < ve[i-1].size(); ++j) {
29 int pos = ve[i-1][j];
30 if (pos > 1 && a[pos-1] != i) ans -= abs(1 - p[a[pos-1]]);
31 if (pos < m && a[pos+1] != i) ans -= abs(1 - p[a[pos+1]]);
32 }
33 p[i] = 1; p[i-1] = i;
34 for (int j = 0; j < ve[i].size(); ++j) {
35 int pos = ve[i][j];
36 if (pos > 1) ans += abs(1 - p[a[pos-1]]);
37 if (pos < m) ans += abs(1 - p[a[pos+1]]);
38 }
39 for (int j = 0; j < ve[i-1].size(); ++j) {
40 int pos = ve[i-1][j];
41 if (pos > 1 && a[pos-1] != i) ans += abs(i - p[a[pos-1]]);
42 if (pos < m && a[pos+1] != i) ans += abs(i - p[a[pos+1]]);
43 }
44 printf(" %lld",ans);
45 }
46 printf("\n");
47 return 0;
48 }
E. Special Permutations
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e6+5;
5 const int _up = (1<<20);
6 char s[maxn];
7 int dp[maxn];
8 int main() {
9 scanf("%s",s+1);
10 int len = strlen(s+1);
11 for (int i = 1; i <= len; ++i) {
12 int now = 0;
13 for (int j = i; j <= len; ++j) {
14 if (now & (1 << (s[j]-'a'))) break;
15 now |= (1 << (s[j]-'a'));
16 dp[now] = j - i + 1;
17 }
18 }
19 for (int i = 1; i < _up; ++i) {
20 for (int j = 0; j < 20; ++j) {
21 int tmp = (1 << j);
22 if (i & tmp) {
23 dp[i] = max(dp[i], dp[i^tmp]);
24 }
25 }
26 }
27 int ans = 0;
28 for (int i = 1; i < _up; ++i) {
29 ans = max(ans, dp[i]+dp[_up - 1 - i]);
30 }
31 printf("%d\n",ans);
32 return 0;
33 }
F. Yet Another Substring Reverse