求调试!代码不长 矩阵快速幂+bitset
  • 板块题目总版
  • 楼主dongdaye
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/5/25 22:21
  • 上次更新2023/11/7 01:43:08
查看原帖
求调试!代码不长 矩阵快速幂+bitset
62946
dongdaye楼主2020/5/25 22:21

题目是NOI Online#3 魔法值,原来写了个矩阵快速幂,不知为何RE了,只有80分。后来把所有scanf换成了cin就从RE变成了WA+TLE。后来又加了个bitset(本蒟蒻第一次用bitset也可能有锅吧...),还是WA+TLE,而且一用scanf就会RE。

我还特地和题解的跑了跑对拍,也没拍出啥错。为啥啊???

#include<bits/stdc++.h>
#include<bitset>
#define MAXN 105
using namespace std;
int N,M,Q;
long long a[MAXN];
bitset<MAXN> adj[MAXN];
bitset<MAXN> t[MAXN];
bitset<MAXN> ans[MAXN];
bitset<MAXN> A[40][MAXN];
void kuaisumi(int y)
{
	for(int i=1;i<=N;++i) ans[i]=0;
	for(int i=1;i<=N;++i) ans[i][i]=1;
	int tt=1;
	while(y)
	{
		if(y&1) 
		{
			for(int i=1;i<=N;++i)
			{
				t[i]=0;
				for(int k=1;k<=N;k++)
					if(ans[i][k]) t[i]=t[i]^A[tt][k];
			}
			for(int i=1;i<=N;i++) ans[i]=t[i];
		}
		y>>=1; tt++;
	}
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("wode.out","w",stdout);
	cin>>N>>M>>Q;
//	scanf("%d%d%d",&N,&M,&Q);
	for(int i=1;i<=N;++i) cin>>a[i];
//	for(int i=1;i<=N;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=M;++i)
	{
		int u,v;
		cin>>u>>v;
		adj[u][v]=adj[v][u]=1;
	}
	for(int i=1;i<=N;++i)
		for(int j=1;j<=N;++j) A[1][i][j]=adj[i][j];
	for(int k=2;k<=32;k++)
	{
		for(int i=1;i<=N;++i)
			for(int kk=1;kk<=N;kk++)
				if(A[k-1][i][kk]) A[k][i]=A[k][i]^A[k-1][kk];
	}
	while(Q--)
	{
		int q; long long res=0;
		cin>>q;
//		scanf("%d",&q);
		kuaisumi(q);
		res=0;
		for(int i=1;i<=N;++i) if(ans[1][i]) res^=a[i];
		cout<<res<<endl;
//		printf("%lld\n",res);
	}
	return 0;
}
2020/5/25 22:21
加载中...