Codeforces Round #590 (Div. 3)

A. Equalize Prices Again

代码：

#include<bits/stdc++.h> using namespace std; typedef long long ll; int T, N; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> T; while (T--) { cin >> N; ll sum = 0; for (int i = 1; i <= N; i++) { int x; cin >> x; sum += x; } ll p = sum / N; if (p * N < sum) p++; cout << p << endl; } return 0; }

B.Social Network

题解： 模拟题，因为可以离线处理，所以预先将$i{d}_i$给读入然后离散化处理即可 代码：

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define sz sizeof using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int MAX = 2e5 + 10; int N, K; int id[MAX], q[MAX], now[MAX]; int b[MAX], cnt; int pos(int x) { return lower_bound(b + 1, b + 1 + cnt, x) - b; } int main() { #ifdef ACM_LOCAL freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); auto start_clock = clock(); #endif ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> K; for (int i = 1; i <= N; i++) cin >> id[i], b[++cnt] = id[i]; sort(b + 1, b + 1 + cnt); cnt = unique(b + 1, b + 1 + cnt) - b - 1; int head = 1, tail = 0; for (int i = 1; i <= N; i++) {//模拟 int p = pos(id[i]); if (now[p]) continue;//如果已经在里面就跳过 while (tail - head + 1 >= K) now[q[head]] = 0, head++;//弹出最上面的 q[++tail] = p, now[p] = 1; } cout << tail - head + 1 << endl; for (int i = tail; i >= head; i--) { if (i != tail) cout << " "; cout << b[q[i]]; } #ifdef ACM_LOCAL cerr << (double)(clock() - start_clock) / CLOCKS_PER_SEC << "s" << endl; #endif return 0; }

C.Pipes

题解： 因为管子可以旋转，所以实质上只有两种管子，一种是1、2，一种是3、4、5、6，不妨分别记为①和② 因为第一种管子只能连通左右，而第二种管子可以连通上下左右 所以考虑2种情况 如果当前列不是最后一列的话，并且前一行通过来的管子接到的是②，那么必须还要一个② 如果前一行管子接到的是①，那么直接往下一列走就是了 最后判断下是否能在最后一列接到出口 代码：

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define sz sizeof using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int MAX = 2e5 + 10; int T, N; char s[2][MAX]; int main() { #ifdef ACM_LOCAL freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); auto start_clock = clock(); #endif ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); scanf("%d", &T); while (T--) { scanf("%d", &N); scanf("%s%s", s[0] + 1, s[1] + 1); int pre = 0, flag = 0;//pre表示上一列是从第一行来还是第二行来 for (int i = 1; i <= N; i++) { char now = s[pre][i], other = s[pre ^ 1][i];//now当前管子，other为当前列另外一个管子 if (now == '1' || now == '2') {//如果是第一种管子，直接通往下一列 if (i == N && pre == 1) flag = 1;//如果是最后一列判一下 continue; } //第二种管子 if (other == '1' || other == '2') break;//如果另外一个管子是第一种管子，则不可能连通 pre ^= 1;//连到另外一行去了 if (i == N && pre == 1) flag = 1; } printf("%s\n", flag ? "YES" : "NO"); } #ifdef ACM_LOCAL cerr << (double)(clock() - start_clock) / CLOCKS_PER_SEC << "s" << endl; #endif return 0; }

D.Distinct Characters Queries

题解： 因为只有26个字母，所以直接状态压缩掉，用一个数$num$来表示状态，即二进制对应位01状态分别表示没有和有，然后就可以用线段树来做，复杂度为$O(nlogn)$ 代码：

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define sz sizeof #define lc u<<1 #define rc u<<1|1 #define m (l+r)/2 #define mid (t[u].l+t[u].r)/2 using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int MAX = 1e5 + 10; int Q, N; char s[MAX]; int get_sum(int x) {//得到区间状压num后计算有几个1，即几种 int ans = 0; while (x) ans += x % 2, x /= 2; return ans; } struct SegTree{ int l, r, num; } t[MAX << 2]; void push_up(int u) { t[u].num = t[lc].num | t[rc].num; } void build(int u, int l, int r) { t[u].l = l, t[u].r = r; if (l == r) { int val = s[l] - 'a'; t[u].num = pow(2, val); return; } build(lc, l, m); build(rc, m + 1, r); push_up(u); } void update(int u, int p) { if (t[u].l == t[u].r) { int val = s[t[u].l] - 'a'; t[u].num = pow(2, val); return; } if (p <= mid) update(lc, p); if (p > mid) update(rc, p); push_up(u); } int query(int u, int ql, int qr) { if (ql <= t[u].l && t[u].r <= qr) return t[u].num; int ans = 0; if (ql <= mid) ans |= query(lc, ql, qr); if (qr > mid) ans |= query(rc, ql, qr); return ans; } int main() { #ifdef ACM_LOCAL freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); auto start_clock = clock(); #endif scanf("%s%d", s + 1, &Q); N = strlen(s + 1); build(1, 1, N); while (Q--) { int op, l, r, p; char x[10]; scanf("%d", &op); if (op == 1) { scanf("%d%s", &p, x); s[p] = x[0]; update(1, p); } else { scanf("%d%d", &l, &r); cout << get_sum(query(1, l, r)) << endl; } } #ifdef ACM_LOCAL cerr << (double)(clock() - start_clock) / CLOCKS_PER_SEC << "s" << endl; #endif return 0; }

E.Special Permutations

题解： 这里直接计算一下每次转移会对答案有什么影响，统计完后直接输出答案即可 对于$a=min(x[i],x[i+1]),b=max(x[i],x[i+1])$，只需要考虑$a!=b$的情况($a=b$的话怎么放都答案都是0) 如果是初始状态，即$1,2,3,4,\cdot \cdot \cdot ,n$，那么当前答案显然就是$b-a$ 因为$i$不同序列也不同，这里我们对$p_i$进行分类讨论 如果$i<a$，则 $a$-> $a+1$， $b$->$b+1$，答案仍然为$b-a$ 如果$i=a$，则答案为$b-1$，变化量为$(b-1)-(b-a)=a+1$ 如果$a<i<b$，则答案为$b-a-1$，变化量为$-1$ 如果$i=b$，则答案为$a$，变化量为$2a-b$ 如果$i>b$，答案仍然为$b-a$ 所以我们这里多用一个差分数列来统计即可（差分数列来计算$a<i<b$的情况）

代码：

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define sz sizeof using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int MAX = 2e5 + 10; int N, M; ll x[MAX], d[MAX], cnt[MAX]; int main() { #ifdef ACM_LOCAL freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); auto start_clock = clock(); #endif ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; ll ans = 0; for (int i = 1; i <= M; i++) { cin >> x[i]; if (i != 1) { ll a = min(x[i - 1], x[i]), b = max(x[i - 1], x[i]); ans += b - a;//初始答案 if (a + 1 <= b - 1) d[a + 1]--, d[b]++;//差分数列 if (a < b) cnt[a] += a - 1, cnt[b] += 2 * a - b;//直接加到统计量上 } } for (int i = 1; i <= N; i++) { d[i] += d[i - 1], cnt[i] += d[i]; cout << ans + cnt[i] << endl; } #ifdef ACM_LOCAL cerr << (double)(clock() - start_clock) / CLOCKS_PER_SEC << "s" << endl; #endif return 0; }

F.Yet Another Substring Reverse