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;
}
