中国式家长 2
链接：https://www.nowcoder.com/acm/contest/179/A
来源：牛客网
输出一行两个整数代表最终剩下的行动力点数、获得的悟性的点数
如果挖取过程不合法则输出一行-1 -1
挖取不合法有以下几种可能：
1、试图挖取一个没有开启的格子
2、试图重复挖取一个格子
3、行动力小于10的时候尝试挖取一个悟性格
只要挖取过程中的任何一步不合法，挖取过程就不合法
最后一次挖取时，行动力已经不够了，因此最后一次挖取失败了
/*
一道没什么细节的模拟...
*/
#include<bits/stdc++.h>
#define N 207
using namespace std;
int n,m,k,x,y,T,tmp,ans;
int a[N][N],can[N][N],vis[N][N];
int e[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>‘9‘||c<‘0‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
return x*f;
}
int main()
{
n=read();m=read();k=read();tmp=k;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
a[i][j]=read();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
can[i][j]=read();
T=read();int flag=0;
while(T--)
{
x=read();y=read();
if(!can[x][y]){flag=1;break;}
if(vis[x][y]){flag=1;break;}
if(a[x][y]<=0 && k<10){flag=1;break;}
vis[x][y]=1;
if(a[x][y]<=0) k-=10,ans+=10;
if(a[x][y]>0) k+=a[x][y],k=min(k,tmp);
int xx,yy;
for(int i=0;i<8;i++)
{
xx=x+e[i][0];yy=y+e[i][1];
if(xx>0 && xx<=n && yy>0 && yy<=m) can[xx][yy]=1;
}
}
if(flag) {printf("-1 -1\n");return 0;}
else printf("%d %d\n",k,ans);
return 0;
}
随机生成树
链接：https://www.nowcoder.com/acm/contest/179/B
来源：牛客网
第一行一个整数N代表点数
输出一个整数最多有多少联通块
2号点和3号点的父亲一定是1，4号点父亲可能是1或者2，两种情况下联通块数都是2
/*
要求连通块尽量多。
考虑贪心，则当前点如果能连到和它颜色不同的点就对答案有贡献。
对一个点扫他的倍数哦按段是否连边计算答案即可。
*/
#include<bits/stdc++.h>
#define N 500001
using namespace std;
int n,m,ans,cnt,flag;
int col[N],vis[N];
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>‘9‘||c<‘0‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
return x*f;
}
int main()
{
n=read();
for(int i=1;i<=n;i++) col[i]=read();
for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i)
{
if(col[j]!=col[i] && !vis[j]) {vis[j]=1;cnt++;}
}
cout<<cnt+1<<endl;
return 0;
}
洞穴
链接：https://www.nowcoder.com/acm/contest/179/C
来源：牛客网
代表牛牛的一个询问
输出Q行依次回答牛牛的Q个询问
每行输出YES或NO，YES代表存在符合条件的路径，NO代表不存在
这个图是一个三元环，从1号点开始走100步之后必定停在2号点上
/*
首先思考暴力怎么写。
f[a][i][b]表示从a到b经i步是否可达。
转移类似floyed ，枚举中间点c，用(f[a][i-1][c] && f[c][1][b])更新。
然后就发现i可以二进制拆分。
f[a][i][b]表示从a到b经2^i步可达，然后数据水就可以过掉这道题了2333
正解：因为f只有0,1两种状态，想到能用bitset优化。
首先预处理 若f[a][j][b]==1 则 f[a][j+1]|=f[b][j]
然后扫一遍各个系答案即可。
复杂度大约是n^3
*/
#include<bits/stdc++.h>
#define N 107
#define S 31
using namespace std;
int n,m,u,v,l,a,b,Q;
bitset<N>f[N][33],ans,tmp;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
scanf("%d%d",&u,&v),f[u][0][v]=1;
for(int j=0; j<=S; j++) for(int i=1; i<=n; i++)
{
for(int k=1; k<=n; k++)
if(f[i][j][k])f[i][j+1]|=f[k][j];
}
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d%d",&l,&a,&b);
ans.reset();ans[a]=1;
for(int i=0;i<=S;i++)
{
if(!(l>>i))break;
if((l>>i)&1)
{
tmp=ans;
ans.reset();
for(int j=1; j<=n; j++)if(tmp[j])ans|=f[j][i];
}
}
puts(ans[b]? "YES":"NO");
}
return 0;
}
原文：https://www.cnblogs.com/L-Memory/p/9866675.html