[CSP-S模拟测试]:传递（暴力+bitset）

题目描述

我们称一个有向图$G$是传递的，当且仅当对于图$G$的三个不同顶点$a,b,c$，若图$G$中有一条边从$a$到$b$且有一条边从$b$到$c$，那么图中也有一条边从$a$到$c$。
我们称一个图$G$是竞赛图，当且仅当它是一个有向图且它的基图是完全图。也就是，将无向完全图的每条边重新定向就能得到一个竞赛图。
现在，给定两张有向图$P=(V,E_P)$和$Q=(V,E_Q)$，满足：$E_p$和$E_q$没有公共边，且图$(V,E_P\cup E_Q)$是一个竞赛图。
你的任务是：判定有向图$P$和$Q$是不是都是传递的。

输入格式

输入文件为$trans.in$。
输入文件中包含多组测试数据，每组第一行有一个整数$T$表示数据组数。
对于每组数据，第一行一个整数$N$表示点数。接下来$N$行，每行为连续的$N$个字符。每个字符只可能是$'-','P','Q'$中的一种。
如果第$i$行第$j$列的字符为$'-'$，表示两个图中均没有边从$i$到$j$。
如果第$i$行第$j$列的字符为$'P'$，表示有向图$P$中有一条边从$i$到$j$。
如果第$i$行第$j$列的字符为$'Q'$，表示有向图$Q$中有一条边从$i$到$j$。

输出格式

输出文件为$trans.out$。
输出共$T$行。对于每组数据，如果图$P$和$Q$都是传递的，输出$'T'$，否则输出$'Q'$。

样例

样例输入：

2
4
-PPP
--QQ
----
--Q-
4
-P-P
--PQ
P--Q
----

样例输出：

T
N

数据范围与提示

对于$30\%$的数据，满足$N\leqslant 200$。
对于$60\%$的数据，满足$N\leqslant 800$。
对于$100\%$的数据，满足$1\leqslant T\leqslant 5,1\leqslant N\leqslant 2016$。

题解

再一次没有打正解

遇到这种题，直接想$bitset$，用一个$bitset$优化暴力就好了。

时间复杂度：$\Theta(\frac{n^3}{\omega})$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int nxt,to;}P[10000000],Q[10000000];

int headP[2100],headQ[2100],cntP,cntQ;

int n;

char ch[2100];

bitset<2100> bitP[2100],bitQ[2100];

void pre_work()

{

	memset(headP,0,sizeof(headP));

	memset(headQ,0,sizeof(headQ));

	for(int i=1;i<=2099;i++)

	{

		bitP[i].reset();

		bitQ[i].reset();

	}

	cntP=cntQ=0;

}

void addP(int x,int y)

{

	P[++cntP].nxt=headP[x];

	P[cntP].to=y;

	headP[x]=cntP;

	bitP[x][y]=1;

}

void addQ(int x,int y)

{

	Q[++cntQ].nxt=headQ[x];

	Q[cntQ].to=y;

	headQ[x]=cntQ;

	bitQ[x][y]=1;

}

int main()

{

	int T;scanf("%d",&T);

	while(T--)

	{

		pre_work();scanf("%d",&n);

		for(int i=1;i<=n;i++)

		{

			scanf("%s",ch+1);

			for(int j=1;j<=n;j++)

				switch(ch[j])

				{

					case 'P':addP(i,j);break;

					case 'Q':addQ(i,j);break;

				}

		}

		for(int x=1;x<=n;x++)

			for(int i=headP[x];i;i=P[i].nxt)

				if((bitP[x]&bitP[P[i].to])!=bitP[P[i].to]){puts("N");goto nxt;}

		for(int x=1;x<=n;x++)

			for(int i=headQ[x];i;i=Q[i].nxt)

				if((bitQ[x]&bitQ[Q[i].to])!=bitQ[Q[i].to]){puts("N");goto nxt;}

		puts("T");nxt:;

	}

	return 0;

}

rp++

巴特西