Codeforces Round #590 (Div. 3)
A. Equalize Prices Again
代码
1
2
3
4
5
6
7
8
9
10
int Solve() {
int n; scanf("%d", &n);
int sum = 0, x;
rep(i, 0, n) {
scanf("%d", &x);
sum += x;
}
int ans = sum / n + (sum % n != 0);
return printf("%d\n", ans);
}
B. Social Network
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int N = 2e5+7;
// ------- 变量 ------- //
int n, k, a[N];
set <int> S;
// ------- 函数 ------- //
void Init() {
scanf("%d%d", &n, &k);
S.clear();
rep(i, 0, n) scanf("%d", a+i);
}
int Solve() {
deque <int> Q;
rep(i, 0, n) {
if (S.count(a[i])) continue;
if (sz(Q) == k) {
S.erase(Q.back());
Q.pop_back();
}
Q.push_front(a[i]);
S.insert(a[i]);
}
printf("%d\n", sz(Q));
rep(i, 0, sz(Q)) printf("%d%c", Q[i], " \n"[i==sz(Q)-1]);
return 0;
}
C. Pipes
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int N = 2e5+7;
// ------- 变量 ------- //
int n;
char s[3][N];
int dp[3][N][3];
// ------- 函数 ------- //
void Init() {
scanf("%d", &n);
rep(i, 1, 3) scanf("%s", s[i] + 1);
}
int Solve() {
dp[1][1][1] = 1;
rep(j, 1, n+2) {
rep(i, 1, 3) {
if (i == 1) dp[i][j][2] = (dp[i+1][j][1] && s[i+1][j] - '0' > 2);
if (i == 2) dp[i][j][0] = (dp[i-1][j][1] && s[i-1][j] - '0' > 2);
}
rep(i, 1, 3) {
int x = s[i][j] - '0';
if (i == 1) dp[i][j+1][1] = (dp[i][j][1] && x < 3 || dp[i][j][2] && x > 2);
if (i == 2) dp[i][j+1][1] = (dp[i][j][1] && x < 3 || dp[i][j][0] && x > 2);
}
}
return puts(dp[2][n+1][1] ? "YES" : "NO");
}
D. Distinct Characters Queries
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
const int N = 1e5+7;
// ------- 变量 ------- //
char s[N];
// ------- 函数 ------- //
#define ls rt << 1
#define rs rt << 1 | 1
#define lson l, m, ls
#define rson m + 1, r, rs
int sz[N<<2], t[N<<2][26];
inline ll op(ll a, ll b) { return a + b; } // ?
inline void Add(int rt, char ch) {
rep(i, 0, 26) t[rt][i] = 0;
t[rt][ch-'a'] = 1;
}
inline void build(int l, int r, int rt) {
sz[rt] = r - l + 1;
if (l == r) { rep(i, 0, 26) t[rt][i] = 0; t[rt][s[l]-'a'] = 1; return; }
int m = (l + r) >> 1;
build(lson); build(rson);
rep(i, 0, 26) t[rt][i] = t[ls][i] | t[rs][i];
}
inline void upd(int pos, char ch, int l, int r, int rt) {
if (l == r) { Add(rt, ch); return ; }
int m = (l + r) >> 1;
if (pos <= m) upd(pos, ch, lson);
if (m < pos) upd(pos, ch, rson);
rep(i, 0, 26) t[rt][i] = t[ls][i] | t[rs][i];
}
inline int qry(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
int res = 0;
rep(i, 0, 26) res |= t[rt][i] << i;
return res;
}
int m = (l + r) >> 1;
int res = 0;
if (L <= m) res |= qry(L, R, lson);
if (m < R) res |= qry(L, R, rson);
return res;
}
void Init() {
scanf("%s", s + 1);
}
int Solve() {
int n = strlen(s + 1);
build(1, n, 1);
int q; scanf("%d", &q);
while (q--) {
int op; scanf("%d", &op);
if (op == 1) {
int pos; char c[5];
scanf("%d%s", &pos, c);
upd(pos, c[0], 1, n, 1);
} else {
int l, r; scanf("%d%d", &l, &r);
int ans = qry(l, r, 1, n, 1);
printf("%d\n", __builtin_popcount(ans));
}
}
return 0;
}
E. Special Permutations
线段树
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
const int N = 2e5+7;
// ------- 变量 ------- //
int n, m, a[N], ans[N];
// ------- 函数 ------- //
#define ls rt << 1
#define rs rt << 1 | 1
#define lson l, m, ls
#define rson m + 1, r, rs
int sz[N<<2]; ll lazy[N<<2], t[N<<2];
inline void Add(int rt, ll val) {
lazy[rt] += val;
t[rt] += val * sz[rt];
}
inline void PushDown(int rt) {
if (lazy[rt]) {
Add(ls, lazy[rt]);
Add(rs, lazy[rt]);
lazy[rt] = 0;
}
}
inline void build(int l, int r, int rt) {
lazy[rt] = 0; sz[rt] = r - l + 1;
if (l == r) { t[rt] = 0; return; }
int m = (l + r) >> 1;
build(lson); build(rson);
t[rt] = t[ls] + t[rs];
}
inline void upd(int L, int R, ll val, int l, int r, int rt) {
if (L > R) return ;
if (L <= l && r <= R) { Add(rt, val); return ; }
PushDown(rt);
int m = (l + r) >> 1;
if (L <= m) upd(L, R, val, lson);
if (m < R) upd(L, R, val, rson);
t[rt] = t[ls] + t[rs];
}
inline ll qry(int pos, int l, int r, int rt) {
if (l == r) return t[rt];
PushDown(rt);
int m = (l + r) >> 1;
ll res = 0;
if (pos <= m) res = res + qry(pos, lson);
if (m < pos) res = res + qry(pos, rson);
return res;
}
void Init() {
scanf("%d%d", &n, &m);
rep(i, 1, m+1) scanf("%d", a+i);
}
int Solve() {
build(1, n, 1);
rep(i, 1, m) {
int l = a[i], r = a[i+1];
if (l == r) continue;
if (l > r) swap(l, r);
upd(1, l-1, r - l, 1, n, 1);
upd(r+1, n, r - l, 1, n, 1);
upd(l+1, r-1, r - l - 1, 1, n, 1);
upd(l, l, r - 1, 1, n, 1);
upd(r, r, l, 1, n, 1);
}
rep(i, 1, n+1) printf("%lld%c", qry(i, 1, n, 1), " \n"[i==n]);
return 0;
}
F. Yet Another Substring Reverse
dp 高维前缀和
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N = 1e6+7;
// ------- 变量 ------- //
char s[N];
int dp[N<<1];
// ------- 函数 ------- //
void Init() {
scanf("%s", s + 1);
memset(dp, 0, sizeof(dp));
}
int Solve() {
int len = strlen(s + 1);
rep(i, 1, len+1) s[i] -= 'a';
rep(i, 1, len+1) {
int mask = 0;
rep(j, 0, 20) {
if (i + j > len) break;
if (mask >> s[i+j] & 1) break;
mask ^= 1 << s[i+j];
dp[mask] = j + 1;
}
}
rep(i, 0, 20) rep(mask, 1, 1 << 20) if (mask >> i & 1)
dp[mask] = max(dp[mask], dp[mask ^ 1 << i]);
int ans = 0;
rep(i, 1, 1 << 20) ans = max(ans, dp[i] + dp[((1 << 20) - 1) ^ i]);
return printf("%d\n", ans);
}
