VP 记 #1 - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
VP 信息
时间：2022 年 11 月 20 日 14:40~17:10。
场次：Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)。
VP 题解
A. Divide and Multiply (00:02:43 +)
显然把所有 \(2\) 全乘给一个数是最优的，又显然要乘给把 \(2\) 除光以后最大的那个。
代码
// Problem: A. Divide and Multiply
// Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1609/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 20;
ll T, n, a[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int main() {
for(scanf("%lld", &T); T; T--) {
scanf("%lld", &n);
ll cnt = 0;
rep(i, 1, n) {
scanf("%lld", &a[i]);
for(; !(a[i] & 1); a[i] >>= 1) ++cnt;
}
sort(a+1, a+1+n, greater<ll>());
printf("%lld\n", accumulate(a+2, a+1+n, 0LL) + a[1] * (1LL << cnt));
}
return 0;
}
B. William the Vigilant (00:09:54 +)
对于每个 abc，需要改一个字母。因此每次询问的答案为当前包含 abc 子串的个数，容易维护之。
代码
// Problem: B. William the Vigilant
// Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1609/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, m;
char s[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int main() {
scanf("%d%d%s", &n, &m, s+1);
int cnt = 0;
rep(i, 1, n-2) {
if(s[i] == 'a' && s[i+1] == 'b' && s[i+2] == 'c') ++cnt;
}
while(m--) {
int i; char c[2];
scanf("%d%s", &i, c);
if(i >= 1 && s[i] == 'a' && s[i+1] == 'b' && s[i+2] == 'c') --cnt;
if(i >= 2 && s[i-1] == 'a' && s[i] == 'b' && s[i+1] == 'c') --cnt;
if(i >= 3 && s[i-2] == 'a' && s[i-1] == 'b' && s[i] == 'c') --cnt;
s[i] = c[0];
if(i >= 1 && s[i] == 'a' && s[i+1] == 'b' && s[i+2] == 'c') ++cnt;
if(i >= 2 && s[i-1] == 'a' && s[i] == 'b' && s[i+1] == 'c') ++cnt;
if(i >= 3 && s[i-2] == 'a' && s[i-1] == 'b' && s[i] == 'c') ++cnt;
printf("%d\n", cnt);
}
return 0;
}
C. Complex Market Analysis (00:22:00 +)
要使一堆数的乘积是质数，则必然有一个质数和一堆 \(1\)。对每个数看看前后每次跳 \(e\) 步有多少个 \(1\)，容易递推得到。线性筛一遍质数，枚举质数是哪个数，由预处理的前后 \(1\) 个数容易计算。
代码
// Problem: C. Complex Market Analysis
// Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1609/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 1e6+5;
ll T, n, e, a[N], pre[N], suf[N], tab[N], p[N], pcnt;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void sieve(ll lim) {
tab[1] = 1;
rep(i, 2, lim) {
if(!tab[i]) p[++pcnt] = i;
for(ll j = 1; j <= pcnt && i * p[j] <= lim; j++) {
tab[i*p[j]] = 1;
if(!(i % p[j])) break;
}
}
}
int main() {
sieve(N-5);
for(scanf("%lld", &T); T; T--) {
scanf("%lld%lld", &n, &e);
rep(i, 1, n) scanf("%lld", &a[i]);
rep(i, 1, e) pre[i] = a[i] == 1;
rep(i, e+1, n) pre[i] = a[i] == 1 ? pre[i-e] + 1 : 0;
per(i, n, n-e+1) suf[i] = a[i] == 1;
per(i, n-e, 1) suf[i] = a[i] == 1 ? suf[i+e] + 1 : 0;
ll ans = 0;
rep(i, 1, n) {
if(!tab[a[i]]) {
ll L = i - e >= 1 ? pre[i-e] : 0;
ll R = i + e <= n ? suf[i+e] : 0;
ans += (L + 1) * (R + 1) - 1;
}
}
printf("%lld\n", ans);
}
return 0;
}
D. Social Network (00:38:05 +)
样例解释明示答案是菊花（虽然不明示也显然）。用并查集维护连通块，同时维护可以选择前几大的连通块连成菊花：若加入一条要求，此时要求的两个点已经连通，则可以多选一个连通块。
代码
// Problem: D. Social Network
// Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1609/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e3+5;
int n, d, x, y;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Dsu {
int fa[N], sz[N];
void init(int x) {rep(i, 1, x) fa[i] = i, sz[i] = 1;}
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool merge(int x, int y) {
int u = find(x), v = find(y);
if(u == v) return 0;
if(sz[u] < sz[v]) swap(u, v);
fa[v] = u;
sz[u] += sz[v];
sz[v] = 0;
return 1;
}
}dsu;
int main() {
scanf("%d%d", &n, &d);
dsu.init(n);
int cnt = 1;
rep(i, 1, d) {
scanf("%d%d", &x, &y);
cnt += !dsu.merge(x, y);
vector<int> cb;
rep(j, 1, n) if(dsu.find(j) == j) cb.push_back(dsu.sz[j]);
sort(cb.begin(), cb.end(), greater<int>());
int sz = cb.size(), ans = 0;
rep(j, 0, min(sz, cnt) - 1) ans += cb[j];
printf("%d\n", ans-1);
}
return 0;
}
E. William The Oblivious (00:46:37 +)
把 B 题的子串改成了子序列，要麻烦了许多。
感觉中国玩家的科技树比较奇怪，数据结构这边点了好多技能点。
线段树维护区间 a/b/c 的个数，以及要使区间不包含子序列 ab/bc/abc 至少要改几个数。
前三个信息容易合并。第四个的话要么左侧的 a 全改掉并使右侧没有 ab，要么右侧的 b 全改掉并使左侧没有 ab。第五、六个同理。
代码
// Problem: E. William The Oblivious
// Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1609/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, m;
char s[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Node {
int a, b, c, noab, nobc, noabc;
};
struct SegTree {
Node t[N<<2];
#define lc(u) (u<<1)
#define rc(u) (u<<1|1)
void pushup(int u) {
t[u].a = t[lc(u)].a + t[rc(u)].a;
t[u].b = t[lc(u)].b + t[rc(u)].b;
t[u].c = t[lc(u)].c + t[rc(u)].c;
t[u].noab = min(t[lc(u)].a + t[rc(u)].noab, t[lc(u)].noab + t[rc(u)].b);
t[u].nobc = min(t[lc(u)].b + t[rc(u)].nobc, t[lc(u)].nobc + t[rc(u)].c);
t[u].noabc = min({t[lc(u)].a + t[rc(u)].noabc, t[lc(u)].noab + t[rc(u)].nobc, t[lc(u)].noabc + t[rc(u)].c});
}
void build(char* s, int u, int l, int r) {
if(l == r) {
t[u].a = s[l] == 'a';
t[u].b = s[l] == 'b';
t[u].c = s[l] == 'c';
t[u].noab = 0;
t[u].nobc = 0;
t[u].noabc = 0;
return;
}
int mid = (l + r) >> 1;
build(s, lc(u), l, mid);
build(s, rc(u), mid+1, r);
pushup(u);
}
void modify(int u, int l, int r, int pos, char c) {
if(l == r) {
s[l] = c;
t[u].a = s[l] == 'a';
t[u].b = s[l] == 'b';
t[u].c = s[l] == 'c';
t[u].noab = 0;
t[u].nobc = 0;
t[u].noabc = 0;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) modify(lc(u), l, mid, pos, c);
else modify(rc(u), mid+1, r, pos, c);
pushup(u);
}
#undef lc
#undef rc
}sgt;
int main() {
scanf("%d%d%s", &n, &m, s+1);
sgt.build(s, 1, 1, n);
while(m--) {
int i; char c[2];
scanf("%d%s", &i, c);
sgt.modify(1, 1, n, i, c[0]);
printf("%d\n", sgt.t[1].noabc);
}
return 0;
}
F. Interesting Sections (01:32:31 +)
这是分治做法，好像也可以线段树扫描线+单调栈来做，不清楚。
popcount 没有任何用得上的性质，就当是颜色属性了。
以前做过一些奇怪的分治，还整理过一类分治，感觉分治十分优美，于是就开始想分治。
设当前分治到区间 \([l,r]\)，分治中心为 \(m=\lfloor\frac{l+r}{2}\rfloor\)，则左右端点都在左侧或右侧的情况可以递归统计，只需统计左端点在左侧和右端点在右侧的情况。
显然，对于一个左端点来讲，右端点从左到右移动确定出的所有区间，可以先后分为三类：
- \(\min,\max\) 都在左侧。
- \(\min,\max\) 一个在左侧，一个在右侧。
- \(\min,\max\) 都在右侧。
而且当左端点向左移动时，三类情况的右端点范围一定只会向右移，也就是单调不减。使用双指针维护之。
接着考虑三类的统计方法：
- 第一类看看 \(\min,\max\) 的 popcount 是否相同。
- 第二类根据在左侧的是 \(\min\) 还是 \(\max\)，将右侧的 popcount 记在桶里，拿出需要的数据计算。
- 第三类依次枚举前缀统计。
代码
// Problem: F. Interesting Sections
// Contest: Codeforces - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1609/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 1e6+5, K = 64, inf = 0x3f3f3f3f3f3f3f3fll;
ll n, a[N], cntmnp[K], cntmxp[K], cntmnq[K], cntmxq[K], cnt[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
ll popcnt(ll x) {return __builtin_popcountll(x);}
ll solve(ll L, ll R) {
if(L == R) return 1;
ll M = (L + R) >> 1;
ll ans = solve(L, M) + solve(M+1, R);
ll mnpre = inf, mxpre = -inf;
cnt[M] = 0;
rep(i, M+1, R) {
chkmin(mnpre, a[i]);
chkmax(mxpre, a[i]);
cnt[i] = cnt[i-1] + (popcnt(mnpre) == popcnt(mxpre));
}
ll mn = inf, mx = -inf;
ll p = M, q = M, mnp = inf, mxp = -inf, mnq = inf, mxq = -inf;
per(i, M, L) {
chkmin(mn, a[i]);
chkmax(mx, a[i]);
while(p < R && mn <= min(mnp, a[p+1]) && mx >= max(mxp, a[p+1])) {
++p;
chkmin(mnp, a[p]);
chkmax(mxp, a[p]);
++cntmnp[popcnt(mnp)];
++cntmxp[popcnt(mxp)];
}
while(q < R && !(mn > min(mnq, a[q+1]) && mx < max(mxq, a[q+1]))) {
++q;
chkmin(mnq, a[q]);
chkmax(mxq, a[q]);
++cntmnq[popcnt(mnq)];
++cntmxq[popcnt(mxq)];
}
if(popcnt(mn) == popcnt(mx)) ans += p - M;
ans += cnt[R] - cnt[q];
if(mn <= mnq) ans += cntmxq[popcnt(mn)] - cntmxp[popcnt(mn)];
else ans += cntmnq[popcnt(mx)] - cntmnp[popcnt(mx)];
// printf("[%lld, %lld][%lld, %lld] i = %lld, p = %lld, q = %lld, ans = %lld\n", L, M, M+1, R, i, p, q, ans);
}
memset(cntmnp, 0, sizeof(cntmnp));
memset(cntmxp, 0, sizeof(cntmxp));
memset(cntmnq, 0, sizeof(cntmnq));
memset(cntmxq, 0, sizeof(cntmxq));
// printf("DIVIDE AND CONQUER [%lld, %lld] : %lld\n", L, R, ans);
return ans;
}
int main() {
scanf("%lld", &n);
rep(i, 1, n) scanf("%lld", &a[i]);
printf("%lld\n", solve(1, n));
return 0;
}
G. A Stroll Around the Matrix (-)
不会。
H. Pushing Robots (-)
不会。
标签：cnt,everyone,int,ll,Deltix,&&,Div,define From： https://www.cnblogs.com/ruierqwq/p/vp-1-cf-1609.html