A.中国式家长2
模拟题，毫无坑点
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
inline int read(){char c,p=0;int w;
while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();
for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));return p?-w:w;
}
template<typename T,typename U>inline char smin(T&x,const U&y){return x>y?x=y,1:0;}
template<typename T,typename U>inline char smax(T&x,const U&y){return x<y?x=y,1:0;}
const int N=202,dx[]={-1,-1,-1,0,1,1,1,0},dy[]={-1,0,1,1,1,0,-1,-1};
int n,m,k,now,nowc,a[N][N];
bool vis[N][N],exi[N][N];
int main(){
n=read(),m=read(),k=read();
REP(i,1,n)REP(j,1,m)a[i][j]=read();
REP(i,1,n)REP(j,1,m)exi[i][j]=read();
int T=read();now=k;
while(T--){
int x=read(),y=read();
if(exi[x][y]&&!vis[x][y]&&x>0&&y>0&&x<=n&&y<=m){
if(a[x][y]>0)now=min(k,now+a[x][y]);
else if(now<10)return puts("-1 -1"),0;
else nowc+=10,now-=10;
vis[x][y]=1;
REP(i,0,7){
int tx=dx[i]+x,ty=dy[i]+y;
if(tx<1||tx>n||ty<1||ty>m)continue;
exi[tx][ty]=1;
}
}else return puts("-1 -1"),0;
}
printf("%d %d
",now,nowc);
return 0;
}
B.随机生成树
发现要给每个节点找一个父亲，如果父亲和他颜色相同，对答案无贡献，如果不同，对答案贡献加1
因此尽量找颜色不同的即可
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
using namespace std;
inline int read(){char c,p=0;int w;
while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();
for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));return p?-w:w;
}
const int N=5e5+7;
int n,c[N],vis[N],ans=1;
int main(){
n=read();
REP(i,1,n)c[i]=read();
REP(i,1,n)for(int j=i+i;j<=n;j+=i)if(!vis[j]&&c[i]!=c[j])++ans,vis[j]=1;
cout<<ans;
return 0;
}
C.洞穴
先看50分的，(l le 100)
设 (f[k][i]) 表示走了 (k) 步 (i) 能到达的集合(这个集合可以用bitset表示)，直接刷表转移即可
bitset<N> g[N],f[N][N];
int main(){
n=read(),m=read();
while(m--){int x=read(),y=read();f[1][x][y]=1,g[x][y]=1;}
REP(k,1,99)REP(i,1,n)REP(j,1,n)if(f[k][i][j])f[k+1][i]|=g[j];
int q=read();
while(q--){
int l=read(),x=read(),y=read();
if(l<=100)puts(f[l][x][y]?"YES":"NO");
}
return 0;
}
观察100分数据范围，发现 (qle 1000,nle 100,lle 10^9) ，那么 (n^2qle10^7) 考虑把 (l) 分成3段，比如(233333333)，分为 (233,333,333) 设 (f[d][k][i]) 表示 (i) 走 (k imes 1000^d) 步能到达的集合，还像刚刚那样预处理，处理询问时，枚举两个中转点 (u,v) 判断即可。复杂度 (O(frac{1000n^3}{64}+n^2q))
const int N=105;
int n,m;
bitset<N> g[N],f[3][1005][N];
int main(){
n=read(),m=read();
while(m--){int x=read(),y=read();f[0][1][x][y]=g[x][y]=1;}
REP(i,1,n)f[0][0][i][i]=f[1][0][i][i]=f[2][0][i][i]=1;
REP(k,1,999)REP(i,1,n)REP(j,1,n)if(f[0][k][i][j])f[0][k+1][i]|=g[j];
REP(i,1,n)f[1][1][i]=f[0][1000][i];
REP(k,1,999)REP(i,1,n)REP(j,1,n)if(f[1][k][i][j])f[1][k+1][i]|=f[0][1000][j];
REP(i,1,n)f[2][1][i]=f[1][1000][i];
REP(k,1,999)REP(i,1,n)REP(j,1,n)if(f[2][k][i][j])f[2][k+1][i]|=f[1][1000][j];
int q=read();
while(q--){
int l=read(),x=read(),y=read(),ans=0;
if(l<=1000)puts(f[0][l][x][y]?"YES":"NO");
else if(l<=1000000){
int t1=l/1000,t2=l%1000;
REP(i,1,n)if(f[1][t1][x][i]&&f[0][t2][i][y]){
ans=1;break;
}
puts(ans?"YES":"NO");
}else{
int t1=l/1000000,t2=(l/1000)%1000,t3=l%1000;
REP(i,1,n)if(f[2][t1][x][i]){
REP(j,1,n)if(f[1][t2][i][j]&&f[0][t3][j][y]){
ans=1;break;
}
if(ans)break;
}
puts(ans?"YES":"NO");
}
}
return 0;
}
那么是不是这题就完了呢？如果 (lle 10^{18}) 呢？这做法就GG了。
发现，这个东西本质上就是矩阵乘法，我们预处理出矩阵的log次方，询问时直接矩阵乘法即可
该问题还可以改为求经过k条边的方案数、概率期望、经过k条边的最短路等等
复杂度 (O(frac{n^3log10^9+nqlog10^9}{64}))
const int N=105,L=__lg(1000000000);
bitset<N>f[33][N],tmp,ans;
int main(){
int n=read(),m=read();
while(m--){int x=read(),y=read();f[0][x][y]=1;}
REP(t,0,L)REP(i,1,n)REP(j,1,n)if(f[t][i][j])f[t+1][i]|=f[t][j];
int q=read();
while(q--){
int l=read(),x=read(),y=read();
ans.reset();ans[x]=1;
REP(i,0,L){
if((l>>i)==0)break;
if(l>>i&1){
tmp=ans;ans.reset();
REP(j,1,n)if(tmp[j])ans|=f[i][j];
}
}
io.putstr(ans[y]?"YES
":"NO
");
}
return 0;
}