CCPC 2020 长春站 部分简略题解
- 2020 年 11 月 12 日
- 笔记
gym链接：CCPC 2020 changchun site
A：
题目大意：商店里有若干个充值档位和首充奖励，你有\(n\)块钱问最多能拿到多少水。
解：由于档位不多可以直接枚举，整个二进制枚举一下所有方案就可以了。不要陷入贪心的方向，因为可能买便宜的会更多。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
int v[10],e[10];
int main()
{
int n;scanf("%d",&n);
v[0] = 1,v[1] = 6,v[2] = 28,v[3] = 88,v[4] = 198,v[5] = 328,v[6] = 648;
e[0] = 8,e[1] = 18,e[2] = 28,e[3] = 58,e[4] = 128,e[5] = 198,e[6] = 388;
int res = 0;
for(int i = 0;i < (1 << 7);++i)
{
int t = 0,s = 0;
for(int j = 0;j < 7;++j)
if(i >> j & 1)
s += v[j];
if(s > n) continue;
for(int j = 0;j < 7;++j)
if(i >> j & 1)
t += e[j];
res = max(res,t + n * 10);
}
printf("%d",res);
return 0;
}
D：
题目大意：构造一个序列\(\{a\}\)，满足\(a_0=1,a[n] = c * \max_{i \in [0,n – 1]}a[i]\)。求\(\sum\limits_{i=0}^na_i \% (10^9+7)\)。
解：枚举之后可以发现\(a_i = c^{popcount(i)}\)。剩下的问题就是求和。由于长度\(\leq 3000\)，显然应该枚举每一位的可能，那么当本位是\(0\)的时候显然只能填\(0\)，如果是\(1\)则既可以填\(0\)也可以填\(1\)，往后继续讨论，如果本位填了\(0\)则之后的所有位都可以填任意的数字，并且贡献只和\(1\)的数量有关，不难想到之后的贡献与长度\(L\)有关，也就是\(\sum C_L^i * c^i\)，其中\(i\)表示填入\(1\)的个数，同时还与前面填过有多少个\(1\)相关。想到这里整个解差不多可以明确出来了：枚举前缀，当本位是\(1\)的时候计算后面任意填的贡献，并累加之前前缀的\(1\)的个数。整个算法复杂度是长度的平方，可以过掉。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 3007,MOD = 1e9+7;
char s[N];
ll C[N][N];
void init()
{
forn(i,0,N - 1)
forn(j,0,i)
{
if(j == 0) C[i][j] = 1;
else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
int main()
{
init();
scanf("%s",s + 1);int n = strlen(s + 1),c;scanf("%d",&c);
ll res = 0,fact = 1,cnt1 = 0;
forn(i,1,n)
{
if(s[i] == '0') continue;
else
{
int L = n - i;
ll p = 0,pc = 1;
forn(j,0,L)
{
p = (p + C[L][j] * pc % MOD) % MOD;
pc = pc * c % MOD;
}
res = (res + fact * p % MOD) % MOD;
fact = fact * c % MOD;
++cnt1;
}
}
res = (res + fact) % MOD;
printf("%lld",res);
return 0;
}
F:
题目大意：给定一颗树，求\(\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[a_i \oplus a_j = a_{lca(i,j)}](i\oplus j)\)。
解：一个显然的想法是，枚举所有点作为\(lca(i,j)\)的情形，然后再去寻找\(i,j\)。显然这样的两个点应该处于这个点的不同的子树中，否则\(lca\)就变了。由于问题是静态的，并且需要整个子树的信息，可以联想到树上启发式合并，考虑使用\(set\)记录子树中权值对应的点的编号。树上启发式合并的过程：
（1)向下递归所有\(u\)的轻儿子，并且做完他们的过程之后把对应的\(set\)清空。
（2)向下递归\(u\)的重儿子，把重儿子的答案算完后保留对应的\(set\)。
（3)再次递归所有\(u\)的轻儿子，计算所有轻儿子关于当前所有其他已经加入\(set\)中点的贡献，计算完后再把整个轻儿子的子树的信息加入\(set\)。
更具体的来说，树上启发式合并的过程是先递归把儿子的答案都计算好，（2)时保留重儿子的信息，之后再慢慢把轻儿子的信息也都加入，但是加入轻儿子的过程中，必须要先计算后加入，因为可能会出现同一颗子树中产生贡献的情况。显然这个做法的时间复杂度是\(O(nlog^2n)\)的，这个做法的时间复杂度还不够优，会被T掉。考虑优化掉\(set\)的一层\(log\)。
这里有一个不正确但是AC的做法：由于每次\(set\)的插入和删除的是一段连续的序列，所以直接把\(set\)换成\(vector\)，利用连续性直接\(pushback\)和\(popback\)就可以正确维护信息了。但是这个做法在树上权值大量相同的时候会退化到平方复杂度。
考虑用静态的数组踢掉\(vector\)的插入删除，本来做不了的原因是权值的编号不同，思路比较显然就是把编号的贡献也拆到位上，只有当两个位上都不同的时候才会有贡献，于是可以按这个思路把每个权值下，对应位数上记录累加了几次，删除的时候直接对本位删一次就可以了。
在具体实现上，需要记录往下有哪些重儿子已经被记录过了，在计算\删除的时候也要看是不是之前还没退出来的重儿子，需要打一个标记记录并跳过某些重儿子。
// Problem: F. Strange Memory
// Contest: Codeforces - 2020 China Collegiate Programming Contest - Changchun Site
// URL: //codeforces.com/gym/102832/problem/F
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Powered by CP Editor (//github.com/cpeditor/cpeditor)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 1e5+7,M = 2 * N,NC = 1e6+7;
vector<int> tb[NC];
int ver[N],succ[M],edge[M],idx;
int a[N],n,sz[N],son[N];
int cnt[(1 << 20) + 7][23][2];
bool st[N];
ll res = 0;
void add(int u,int v)
{
edge[idx] = v;
succ[idx] = ver[u];
ver[u] = idx++;
}
void update(int id,int val)
{
for(int i = 0;i < 20;++i)
cnt[a[id]][i][id >> i & 1] += val;
}
ll find(int id,int num)
{
ll res = 0;
for(int i = 0;i < 20;++i)
res += cnt[num][i][!(id >> i & 1)] * (1 << i);
return res;
}
void dfs1(int u,int fa)
{
sz[u] = 1;
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(v == fa) continue;
dfs1(v,u);
sz[u] += sz[v];
if(sz[son[u]] < sz[v]) son[u] = v;
}
}
void calc(int u,int fa,int lca)
{
if((a[u] ^ lca) < NC) res += find(u,a[u] ^ lca);
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(v == fa || st[v]) continue;
calc(v,u,lca);
}
}
void insert(int u,int fa)
{
update(u,1);
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(v == fa || st[v]) continue;
insert(v,u);
}
}
void remove(int u,int fa)
{
update(u,-1);
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(v == fa || st[v]) continue;
remove(v,u);
}
}
void dfs2(int u,int fa,int keep)
{
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(v == fa || v == son[u]) continue;
dfs2(v,u,0);
}
if(son[u]) dfs2(son[u],u,1),st[son[u]] = 1;
update(u,1);
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(v == fa || st[v]) continue;
calc(v,u,a[u]);
insert(v,u);
}
if(son[u]) st[son[u]] = 0;
if(!keep) remove(u,fa);
}
int main()
{
memset(ver,-1,sizeof ver);
scanf("%d",&n);
forn(i,1,n) scanf("%d",&a[i]);
forn(i,1,n-1)
{
int u,v;scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs1(1,-1);
dfs2(1,-1,1);
printf("%lld",res);
return 0;
}
H：
题目大意：有一个最多五位的密码锁，上面的数字都是\(0-9\)，每次可以拨动上面的一位（正反旋转都是允许的）。两个人轮流拨锁，当某个人转到一个之前有过的密码，或者是某个两方开始之前制定的某个密码时判输。问是否是先手必胜的。
解：假如把所有状态的和的奇偶性组织起来，那么每次状态之间的移动和会从奇数变成偶数，从偶数变成奇数，那么就可以构造成一个二分图。由于不能往已经走过的状态走，那么当起点在二分图的最大匹配的必须点上时(不妨说必须点在左侧，左部右部交换不影响正确性），而对手一定可以沿着最大匹配把状态移动回左部，并且移动过的边数一定是偶数，于是先手必败。
建图比较显然，先记录有哪些点是禁止的，没有影响的就按位枚举转移，每条边的流量都是\(1\)。不妨先不加入起始状态的边，做一次最大流，再把起始状态的边加入再求一次最大流，假如产生了增广，那么就说明起点是一个必须点，那么先手必败，反之先手必胜。
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 1e6+7,M = 2 * N,INF = 1 << 29;
int forb[N],fact[] = {1,10,100,1000,10000,100000};
int m,n,s,t,CASE,STR;
int edge[M],succ[M],cap[M],ver[N],idx;
int d[N],pre[N],now[N];
int q[M],hh,tt;
void add(int u,int v,int w)
{
edge[idx] = v;
cap[idx] = w;
succ[idx] = ver[u];
ver[u] = idx++;
edge[idx] = u;
cap[idx] = 0;
succ[idx] = ver[v];
ver[v] = idx++;
}
bool bfs()
{
memset(d,0,sizeof d);
hh = 0,tt = -1;
q[++tt] = s;d[s] = 1;now[s] = ver[s];
while(hh <= tt)
{
int u = q[hh++];
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(cap[i] && !d[v])
{
q[++tt] = v;
now[v] = ver[v];
d[v] = d[u] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
int dinic(int u,int limit)
{
if(u == t) return limit;
int flow = 0,k;
for(int i = now[u];~i && flow < limit;i = succ[i])
{
now[u] = i;
int v = edge[i];
if(cap[i] && d[v] == d[u] + 1)
{
k = dinic(v,min(limit - flow,cap[i]));
if(!k) d[v] = -1;
cap[i] -= k;
cap[i ^ 1] += k;
flow += k;
}
}
return flow;
}
int dinic()
{
int res = 0,flow = 0;
while(bfs())
while(flow = dinic(s,INF))
res += flow;
return res;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;cin >> T;
for(int CASE = 1;CASE <= T;++CASE)
{
memset(ver,-1,sizeof ver);idx = 0;
cin >> m >> n >> STR;
forn(i,1,n)
{
int x;cin >> x;
forb[x] = CASE;
}
s = fact[5] + 1,t = s + 1;
// for(int i = ver[4];~i;i = succ[i]) cout << edge[i] << endl;
for(int i = 0;i < fact[m];++i)
{
if(forb[i] == CASE) continue;
int sum = 0,x = i;
while(x)
{
sum += x % 10;
x /= 10;
}
// cout << i << " " <<s << endl;
if(sum % 2 == 1) {if(i != STR) add(i,t,1);}
else
{
// cout << i << endl;
if(i != STR) add(s,i,1);
// cout << i << endl;
for(int j=0;j<m;j++)
{
int num=i;
for(int k=0;k<j;k++)num/=10;
num=num%10;
int k=(num+1)%10*fact[j];
k=i-num*fact[j]+k;
if(k < fact[m])add(i,k,1);
k=(num-1+10)%10*fact[j];
k=i-num*fact[j]+k;
if(k < fact[m])add(i,k,1);
}
}
}
ll res = dinic();
int sum = 0;
int __ = STR;
while(__)
{
sum += __ % 10;
__ /= 10;
}
if(sum % 2 == 1) add(STR,t,1);
else add(s,STR,1);
ll res_r = dinic();
// cout << res << " " << res_r << endl;
if(!res_r) cout << "Bob\n";
else cout << "Alice\n";
}
return 0;
}
J：
题目大意：有一个长度为\(n\)的横线，一开始有若干个圆已经在图上，你可以增加若干个半径不超过\(5\)的圆，并且任意两个圆之间不能有超过\(1\)个交点，问有多少种不同的方案。数据保证最开始的圆都是合法的。
解：看到题面之后可以想到应该是一个\(dp\)问题，决策很多方案也很多。同时可以看到这个决策是与一段区间相关的，不妨先考虑简化的问题：假设一开始没有画上若干个圆，直接对应求方案数。状态：\(f[l][r][0]\)表示在\([l,r]\)这个位置上不存在恰好一个圆的左端点处在\(l\)且右端点处在\(r\)的方案数，\(f[l][r][1]\)表示恰好有一个圆处在\([l,r]\)这个位置上的方案数。
入口：显然对于\(f[i][i+1][0]=1\)，\(f[i][i+1][1]=0\)。
转移：先考虑存在一个恰好的圆处在\([l,r]\)的时候，当长度在\(10\)以内且是偶数的时候，有\(f[l][r][1] = f[l][r][0]\)。另外一种情况下，考虑状态的分界点，对于最左侧的端点\(l\)要么旁边没有圆，要么直接相切某个半径是\(k\)的圆，采用这种转移的原因是\(k\)的取值只有\(5\)种。如果\(l\)身边没有任何一个圆，那么就是\(f[l][r][0] += f[l + 1][r][0] + f[l + 1][r][1]\)。假设身边相切一个半径是\(k\)的圆，那么就是\(f[l][r][0] += f[l][l + 2k][1] * (f[l +2k][r][0] + f[l + 2k][r][1])\)。
出口：\(f[0][n][0] + f[0][n][1]\)
非法状态：再加回原来存在的圆之后，对于某一个\([l,r]\)范围的圆，那么对于内部的坐标\(j\in[l+1,r-1]\)不能有任何一个圆的覆盖位置是\([k,j]\)或\([j,k]\)其中\(k\in[0,l-1]\)或\(k\in[r+1,n]\)。标记这样的位置，这样的区间不能有任何方案数，其次\(f[l][r][0] = 0\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 2e3+7,MOD = 1e9+7;
int f[N][N][2],forb[N][N],cir[N][N];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
forn(i,1,k)
{
int r,c;scanf("%d%d",&c,&r);
cir[c - r][c + r] = 1;
forn(j,c - r + 1,c + r - 1)
{
forn(k,0,c - r - 1) forb[k][j] = 1;
forn(k,c + r + 1,n) forb[j][k] = 1;
}
}
forn(i,0,n - 1) f[i][i + 1][0] = 1,f[i][i + 1][1] = 0;
forn(len,2,n)
{
for(int l = 0;l + len <= n;++l)
{
int r = l + len;
if(forb[l][r])
{
f[l][r][1] = 0;
f[l][r][0] = 0;
continue;
}
int& v = f[l][r][0];
v = (1ll*v + f[l + 1][r][0] + f[l + 1][r][1]) % MOD;
for(int k = l + 2;k <= l + 10 && k <= r;k += 2)
v = (v + f[l][k][1] * (1ll* f[k][r][0] + f[k][r][1])) % MOD;
if(len <= 10 && len % 2 == 0) f[l][r][1] = f[l][r][0];
if(cir[l][r]) f[l][r][0] = 0;
}
}
printf("%lld",(1ll* f[0][n][0] + f[0][n][1]) % MOD);
return 0;
}
K:
题目大意：一开始有若干颗只有一个点的树，之后有若干个操作，每次操作是下面3种：
（1)增加一个只有一个点的树
（2)链接\(x,y\)两个点所在的树，如果两个点一开始就在一个树里，则不进行操作
（3)直接对编号为\(x\)的点修改他的权值
每个操作之后输出所有树里满足\(a_i \oplus a_j=gcd(a_i,a_j)\)的数对的总个数。
解：由于要合并两棵树，并且要知道树里的结点的具体个数，不难想到使用\(set<pii>\){权，个数}的方式表示一棵树。之后对于链接两棵树的过程通过并查集维护根以及\(set\)的启发式合并就可以使复杂度掉到\(O(nlog^2n)\)。看起来比较可做，继续考虑题目统计的条件。
对于\(a \oplus b = gcd(a,b)\)的条件，不妨假设\(a < b\)，左边的异或有\(a \oplus b \geq b – a\)，证明可以通过把数拆成位和，并且规约到每一位的情况解决。对于右边的\(gcd(a,b)=gcd(a,b-a) \leq b – a\)组合起来可以发现如果两边相等则必然有\(b-a | a\)，当然有这个条件不能说明一定有亦或的值也相等，但是这至少说明了\(b-a\)与\(a\)的关系，并启发可以通过枚举约数及其倍数的方式得到所有可能，但是还是要判断一下是不是异或值相等的。通过打表之后可以发现对于任意一个\(a\)他合法的\(b\)的个数很少，于是进而可以想到暴力解决这个问题。
对于每个\(2\)操作，我们枚举较小的树中所有权值，并在较大的树中查询是否有需要的权值及其个数，计算完对答案的增量之后再把较小的所有元素插入到较大的中去。对于每个\(3\)操作，不妨先删掉原有的值，再插入一个新的直接应用修改。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
typedef pair<int,int> pii;
#define x first
#define y second
const int N = 1e5+7,M = 2e5+7;
set<pii> tr[N + M];
vector<int> v[M + N];
int a[N + M],fa[N + M],idx;
int n,m;
ll res;
int find(int x)
{
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
ll calc(int x,int u,int cnt)
{
ll r = 0;
for(auto& tar : v[u])
{
auto it = tr[x].lower_bound({tar,0});
if(it == tr[x].end()) continue;
if((*it).x == tar) r += 1ll * (*it).y * cnt;
}
return r;
}
void merge(int x,int y)
{
int fx = find(x),fy = find(y);
if(fx == fy) return ;
if(tr[fx].size() > tr[fy].size()) swap(fx,fy);
fa[fx] = fy;
for(auto& u : tr[fx]) res += calc(fy,u.x,u.y);
for(auto& u : tr[fx])
{
auto it = tr[fy].lower_bound({u.x,0});
if(it == tr[fy].end()) tr[fy].insert(u);
else
{
if((*it).x == u.x) tr[fy].erase(it),tr[fy].insert({u.x,u.y + (*it).y});
else tr[fy].insert(u);
}
}
}
void update(int x,int v)
{
int fx = find(x);
auto it = tr[fx].lower_bound({a[x],0});
int num = (*it).y;
tr[fx].erase(it);
if((*it).y > 1) tr[fx].insert({a[x],num - 1});
res -= calc(fx,a[x],1);
a[x] = v;
res += calc(fx,a[x],1);
it = tr[fx].lower_bound({a[x],0});
if(it == tr[fx].end()) tr[fx].insert({a[x],1});
else
{
num = (*it).y;
if((*it).x == a[x]) tr[fx].erase(it),tr[fx].insert({a[x],num + 1});
else tr[fx].insert({a[x],1});
}
}
int main()
{
scanf("%d%d",&n,&m);
forn(i,1,n) scanf("%d",&a[i]),tr[i].insert({a[i],1});
//init
for(int d = 1;d <= 200000;++d)
for(int a = 2 * d;a <= 200000;a += d)
{
int b = d + a;
if(b > 200000 || (a ^ b) != b - a) continue;
v[a].push_back(b);
v[b].push_back(a);
}
forn(i,1,n + m) fa[i] = i;
while(m--)
{
int t;scanf("%d",&t);
if(t == 1)
{
int x,v;scanf("%d%d",&x,&v);
a[x] = v;
tr[x].insert({v,1});
}
else if(t == 2)
{
int x,y;scanf("%d%d",&x,&y);
merge(x,y);
}
else
{
int x,v;scanf("%d%d",&x,&v);
update(x,v);
}
printf("%lld\n",res);
}
return 0;
}
