CF1950 A~G

前言

报了名没打的一场 Div. 4，我是怎么想到回去做的呢？上课的时候无聊于是随机了一道 1700 的题，找到了本场比赛的 F 题，我那时还没发现。过了差不多 \(2\sim3\) 天去随机了一道 1900，又找到了 G 题，一看 G 题竟然只有 1900，意识到这是 Div. 4，就想着 AK 一场 Div. 4，结果发现 F 做过了，这场我还报名了？于是倒序开题并 AK 了。根据我的习惯，每次完成一套题，就要发一个 Overall Tutorial，于是有了本文。

\(\textsf{Overall}\)

CF1950A

难度：800

直接比较三数即可。

CF1950B

难度：800

把每 \(4\) 格看做一格，当 \(i+j\) 是 \(2\) 的倍数的时候这个格子就是 #。

CF1950C

难度：800

除了 \(0\) 点钟特判，其他输出减一取模加一即可。

CF1950D

难度：1100

先简化题意：一个数 \(x\) 能否拆成若干只由 0 和 1 组成的数的乘积。注意到这种数不多，枚举出来，计算哪些 \(x\) 可以表示，\(O(1)\) 判断答案。

CF1950E

难度：1500

显然 \(x\) 是 \(n\) 的因数，所以可以枚举 \(n\) 的因数，再每 \(x\) 个字符检查一次。把串 \(S\) 分成 \(x\) 个串，也就是 \(S_1S_2\cdots S_x,S_{x+1}S_{x+2}\cdots S_{2x},\cdots\)，把这些子串放进 set 里去重。如果 set 内只有一个串或两个满足条件的串且它们其中一种不超过一个，那么 \(x\) 就是符合条件的答案。

#include <bits/stdc++.h>
using namespace std;
set<string> st;
map<string,int> mp;
int check(string s,string t)
{int cnt=0;for(int i=0;i<s.size();i++) cnt+=(s[i]!=t[i]);if(cnt>1) return 0;return 1;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;while(t--){int n;cin>>n;string s;cin>>s;s=' '+s;for(int i=1;i<=n;i++){if(n%i) continue;st.clear();mp.clear();for(int j=1;j<=n;j+=i){string t=s.substr(j,i);st.insert(t);mp[t]++;}if(st.size()>2){continue;}if(st.size()==1){cout<<i<<'\n';break;}if((mp[*st.begin()]>1&&mp[*(++st.begin())]>1)||!check(*st.begin(),*(++st.begin()))){continue;}cout<<i<<'\n';break;}}
}

CF1950F

难度：1700

点数不变，那么平均每层节点越多，深度越小。不难联想到对于某一层来说，它的节点最大值与它上一层节点个数和剩余节点数量有关。因此应尽可能地把子节点最多的那 \(a\) 个放到深度小的位置，把次多的 \(b\) 个放到仅比那 \(a\) 个稍深一点的位置，\(c\) 个叶子有多深放多深。

#include <bits/stdc++.h>
using namespace std;
vector<int> G[300010];
int dep[300010];
int main()
{ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;while(t--){int a,b,c,now=1;cin>>a>>b>>c;for(int i=1;i<=a+b+c;i++) G[i].clear(),dep[i]=0;queue<int> q;q.push(1);while(q.size()){int u=q.front();q.pop(); if(a){a--;G[u].push_back(++now);q.push(now);dep[now]=dep[u]+1;G[u].push_back(++now);q.push(now);dep[now]=dep[u]+1;}else if(b){b--;G[u].push_back(++now);q.push(now);dep[now]=dep[u]+1;}else c--;}if(a||b||c){cout<<-1<<'\n';continue;}int ans=0;for(int i=1;i<=now;i++) ans=max(ans,dep[i]);cout<<ans<<'\n';}
}

CF1950G

观察到 \(n\) 的范围极小，本题应该是要 \(O(2^n\times n)\) 左右的复杂度，不难想到状压 dp。定义 \(dp_{i,j}=0/1\) 表示达到 \(i\) 这个状态（一个二进制数，第 \(i\) 首歌选那么状态的第 \(i\) 位为 \(1\)，否则为 \(0\)，\(0\le i<n\)）并以第 \(j\) 首歌结尾是否可能。有了状态，自然推出转移即某一个状态 \(i\) 中选择一个未被选择的歌并且能与第 \(j\) 首歌接上，那么假设该歌曲编号为 \(k\)，那么 \(dp_{i+2^k,k}\leftarrow 1\)。初始值的设置也易得：对于每个 \(0\le x<n\)，\(dp_{2^x,x}\leftarrow 1\)。答案自然就是满足 \(dp_{i,j}=1\) 的 \(n-\operatorname{popcount}(i)\) 的最小值。

这题有点卡常，需要注意一些事情，否则就会如图。

要注意的几点：

• popcount 提前处理好，最好是在多测开始前就把 \(0\sim 2^{16}\) 的每个数的 popcount 处理好。

• 关闭同步流或使用 scanf 读入或开快读。

• 歌曲流派与作者先离散化，否则常数很大。

• 记录一个 \(vis_{i,j}\) 表示是否计算过 \(dp_{i,j}\)，如果搜索到状态 \(i,j\) 时 \(vis_{i,j}=1\) 就直接退出本次搜索。

• 多测清空。

#include <bits/stdc++.h>
using namespace std;
string g[20],w[20];
int g2[20],w2[20],cl[1<<17];
int dp[1<<17][20],n,cnt=0,vis[1<<17][20];
map<string,int> mp;
void dfs(int sta,int lst)
{if(vis[sta][lst]) return;vis[sta][lst]=1;dp[sta][lst]=1;for(int i=0;i<n;i++){if((sta>>i&1)||(g2[i]!=g2[lst]&&w2[i]!=w2[lst])){vis[sta+(1<<i)][i]=1;continue;}dfs(sta+(1<<i),i);}
}
int calc(int k)
{int ret=0;for(int i=0;i<16;i++) ret+=k>>i&1;return ret;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;for(int i=0;i<(1<<16);i++) cl[i]=calc(i);while(t--){mp.clear();int ans=0;cin>>n;for(int i=0;i<n;i++){cin>>g[i]>>w[i];if(!mp[g[i]]) mp[g[i]]=++cnt;if(!mp[w[i]]) mp[w[i]]=++cnt;g2[i]=mp[g[i]];w2[i]=mp[w[i]];}for(int i=0;i<(1<<n);i++)for(int j=0;j<n;j++)dp[i][j]=vis[i][j]=0;for(int i=0;i<n;i++) dfs(1<<i,i);for(int i=0;i<(1<<n);i++)for(int j=0;j<n;j++)ans=max(ans,dp[i][j]*cl[i]);cout<<n-ans<<'\n';}
}