A
题意
给定一个由 0，1 和 ? 组成的长为 \(n\) 序列，其中 ? 需要被替换为 0 或 1，询问是否有且仅有一种 ? 的替换方案使得序列中有 \(k\) 个 1 并且这 \(k\) 个 1 是连续的
序列总长度小于 \(3\times10^5\)
题解
先分别统计整个序列中 0 和 1 的个数，若 1 的个数大于 \(k\) 显然无解
考虑序列上每一个长度为 \(k\) 的子区间，统计这个区间中 0 和 1 的个数，一个区间满足条件当且仅当
- 这个区间中没有
0 - 这个区间中
1的个数与整个序列中1的个数一样
若有且仅有一个这样的区间就说明满足题意，否则不满足
动态维护区间就行，每次移动端点复杂度 \(\Theta(1)\)，总复杂度 \(\Theta(n)\)
Code
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
char s[N];
void Main()
{
memset(s,0,sizeof(s));
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",s+1);
int zero=0,one=0;
for(int i=1;i<=n;++i)
if(s[i]=='0')++zero;
else if(s[i]=='1')++one;
if(one>k)return puts("No"),void(0);
int now0=0,now1=0;
for(int i=1;i<k;++i)
if(s[i]=='0')++now0;
else if(s[i]=='1')++now1;
int ans=0;
for(int ed=k;ed<=n;++ed)
{
if(s[ed]=='0')++now0;
else if(s[ed]=='1')++now1;
if(now0==0&&now1==one)++ans;
if(s[ed-k+1]=='0')--now0;
else if(s[ed-k+1]=='1')--now1;
}
return puts(ans==1?"Yes":"No"),void(0);
}
signed main()
{
int T;
scanf("%d",&T);
while(T--)Main();
return 0;
}
B
题意
共 \(T\) 组数据，每组数据给定正整数 \(A,B\)，请你找到一组非负整数 \(X,Y\) 使得在 \(B+Y\) 是 \(A+X\) 的整数倍的同时，最小化 \(X+Y\)
数据范围：\(1\le A,B\le10^9,\ 1\le T\le 100\)
题解
若 \(A\ge B\) 答案显然为 \(A-B\)
若 \(B>A\)
不难发现答案一定小于等于 \(\min\{B-A,A\}\)
方法一，那么直接从 \(0\) 到 \(A\) 枚举 \(X\)，对于每一个 \(A+X\) 直接 \(\Theta(1)\) 找到最小的满足题意的自然数 \(Y\) 即可，总复杂度 \(\Theta(A)\)
方法二，那么从 \(1\) 到 \(\lfloor\frac{B}{A}\rfloor+1\) 枚举 \(\frac{B+Y}{A+X}\) 的值 \(t\)（若 \(t>\lfloor\frac{B}{A}\rfloor+1\) 显然更劣），对于每一个 \(t\) 先找到最小的 \(Y\) 使得 \(B+Y\) 是 \(t\) 的倍数，接着就能算出 \(A+X\) 的值，若算出的 \(A+X<A\) 那么说明 \(Y\) 太小了，令 \(X=0\)，再根据 \(t\) 算出新的 \(Y\)，若 \(A+X\ge A\) 那么直接算出 \(X\) 即可，每次检验的复杂度还是 \(\Theta(1)\)，总复杂度 \(\Theta(\lfloor\frac{B}{A}\rfloor)\)
如果单纯使用一种方法肯定会超时，若 \(A\le\sqrt{B}\) 那么使用第一种方法复杂度为 \(O(\sqrt{B})\)，若 \(A>\sqrt{B}\) 那么使用第二种方法复杂度也为 \(O(\sqrt{B})\)，这样分类做，总复杂度就是 \(\Theta(\sqrt{B})\)
Code
#include<bits/stdc++.h>
using namespace std;
void Main()
{
long long a,b,x,y,t,ans=2e18;
cin>>a>>b;
if(a>=b)return cout<<a-b<<'\n',void(0);
if(a<=sqrt(b))
{
int ax;
for(x=0;x<=a;++x)
{
ax=a+x;
if(b%ax==0)y=0;
else y=ax-b%ax;
ans=min(ans,x+y);
}
}
else
{
int mn=b/a+1;
for(t=1;t<=mn;++t)
{
if(b%t==0)y=0;
else y=t-b%t;
x=(b+y)/t-a;
if(x<0)
{
x=0;
y=a*t-b;
}
ans=min(ans,x+y);
}
}
cout<<ans<<'\n';
}
signed main()
{
int T;
cin>>T;
while(T--)Main();
return 0;
}
C
题意
给定一个有 \(n\) 个点的无向连通图，每个点有一个点权 \(v_i\)，同时给定一个长度为 \(k\) 的序列 \(\{b\}\)，询问是否任意从节点 \(1\) 到节点 \(n\) 的简单路径都满足如下性质：
- 把经过的所有点的权值组成一个序列，\(\{b\}\) 是这个序列的子序列
数据范围：\(2\le n\le 10^5\)
题解
考虑 dp，设 \(f_i\) 表示从节点 \(1\) 到节点 \(i\) 的所有简单路径上至少已经匹配了序列 \(\{b\}\) 的前 \(f_i\) 位
考虑从节点 \(u\) 转移到节点 \(v\)
如果在节点 \(u\) 时已经至少匹配了 \(k\) 位那么就用 \(f_u=k\) 更新 \(f_v\)
如果在节点 \(v\) 时还没有匹配完 \(\{b\}\) 的 \(k\) 位并且可以匹配第 \(f_u+1\) 位那么就用 \(f_u+1\) 更新 \(f_v\)
总结成一个式子就是
\[f_v=\min\{f_v,f_u+[f_u<k]\cdot[v_v=b_{f_u+1}]\} \]类似 Dijkstra 做一遍就行
最后看终点，若 \(f_n=k\) 则满足，否则不满足
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=4e5+5,INF=1e9;
int n,m,k;
int head[N],nxt[M],to[M],cnt;
int a[N],b[N],d[N];
bool vis[N];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>>q;
inline void create(int ff,int tt){nxt[++cnt]=head[ff],head[ff]=cnt,to[cnt]=tt;}
signed main()
{
cin>>n>>m>>k;
for(int i=1,t1,t2;i<=m;++i)cin>>t1>>t2,create(t1,t2),create(t2,t1);
for(int i=1;i<=n;++i)cin>>a[i],d[i]=INF;
for(int i=1;i<=k;++i)cin>>b[i];
d[1]=bool(a[1]==b[1]);
q.push(make_pair(d[1],1));
while(q.size())
{
int pos=q.top().second;
q.pop();
if(vis[pos])continue;
vis[pos]=1;
for(int i=head[pos],tmp;i;i=nxt[i])
{
tmp=d[pos]+bool(d[pos]<k&&a[to[i]]==b[d[pos]+1]);
if(d[to[i]]>tmp)
{
d[to[i]]=tmp;
q.push(make_pair(d[to[i]],to[i]));
}
}
}
puts(d[n]==k?"Yes":"No");
return 0;
}
D
题意
给定一棵有 \(n\) 个节点的有根树，每个点可以有黑白两种颜色，一开始所有点都是白色
一个点被定义为“好点”当且仅当从树根到它的简单路径上所有点都是黑色
现在可以进行操作，每次操作可以在树上所有不是“好点”中随机地选择一个染成黑色，询问期望要操作多少次才能让整棵树都变为黑色
数据范围：\(2\le n\le 2\times10^5\)
题解
假设第 \(i\) 个点被染色的次数是 \(x_i\)，期望次数是 \(E[x_i]\)，根据期望的线性性，最终的答案就是 \(\sum E[x_i]\)
下面我们来单独看一个点 \(v\)，在考虑 \(v\) 被染色的期望次数时，我们可以忽略不在根节点到 \(v\) 路径上的操作，因为这些操作不会影响 \(v\) 的答案
考虑这条路径上一共有 \(k\) 个节点，其中有 \(i\) 个节点已经是“好点”了，新增一个“好点”的概率是 \(\frac1{k-i}\)，也就是说当 \(v\) 变成“好点”（不能再被选）时，整条路径的全部 \(k\) 个点都是“好点”，每次新增“好点”时 \(v\) 也有 \(\frac1{k-i}\) 的概率被选中，那么 \(v\) 被染色的期望次数 \(E[x_v]=\sum\limits_{i=1}^k\frac1i\)
预处理到 \(\sum\limits_{i=1}^n\frac1i\)，然后把每一个点的 \(E[x_i]\) 加起来就可以了
这样说很不严谨只能感性理解，可以看官方题解更加清楚
Code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,mod=998244353;
int n,dep[N],inv[N],f[N],ans;
inline int add(int x,int y){x+=y;if(x>=mod)x-=mod;return x;}
inline void Add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
signed main()
{
cin>>n;
inv[1]=1;
for(int i=2;i<=n;++i)inv[i]=mul(mod-mod/i,inv[mod%i]);
for(int i=1;i<=n;++i)f[i]=add(f[i-1],inv[i]);
dep[1]=1;
ans=1;
for(int i=2,tmp;i<=n;++i)cin>>tmp,dep[i]=dep[tmp]+1,Add(ans,f[dep[i]]);
cout<<ans;
return 0;
}