InvestigatingLegions

ZYB likes to read detective novels and detective cartoons. One day he is immersed in such story:

As a spy of country B, you have been lurking in country A for many years. There are $n$ troops and $m$ legions in country A, and each troop belongs to only one legion. Your task is to investigate which legion each troop belongs to.

One day, you intercept a top secret message--a paper which records all the pairwise relationship between troops. You can learn from the paper that whether troop ${i}$ and troop ${j}$ belongs to the same legion for each ${(i,j)}$ . However, each piece of data has a independent probability of $\frac{1}{S}$ being reversed.
Formally, the troop is numbered from ${0}$ to ${n-1}$ , and the region is numbered from ${0}$ to ${m-1}$ . You are given $\frac{n(n-1)}{2}$ boolean numbers, indicating whether ${i}$ and ${j}$ belong to the same region (1 for yes and 0 for no). However, every number will be reversed(i.e., 0 to 1 and 1 to 0) in a probablity of $\frac{1}{S}$ . You can assume that the data is generated like this:

be[i] means the region that troop ${i}$ belongs to. rand() can be considered as a uniform random function. i.e., select a integer from interval $[0, \mathrm{lcm}(m, S)-1]$ with equal probability.

Note that you have already known ${n}$ and ${S}$ , but you don't know the exact value of $m$. Please help country B construct the original data.

The input contains multiple cases. The first line of the input contains a single integer $T\ (1 \le T \le 100)$ , the number of cases.

For each case, the first line of the input contains two integers ${n,S}$ ( $30 \le n \le 300,20 \le S \le 100$ ), denoting the number of troops and the integer parameter to generate data. There is a binary string (i.e. the string only contains '0' and '1') with length $\frac{n(n-1)}{2}$ in the next line, decribing the pairwise relationship. It is arrayed like this: $(0,1),(0,2)...(0,n-1),(1,2) \dots (n-3,n-1),(n-2,n-1)$ .

${m}$ is not given but it is guaranteed that $1 \le m \le \lfloor \frac{n}{30} \rfloor$ . And the sum of ${n}$ over ${T}$ cases doesn't exceed ${1200}$ .

For each case, output integers seperated by space, the $i$-th integer describes be[i]. The value of be[i] is meaningless, so please output the solution with the smallest lexicographical order. For example, if there are 4 troops and 2 regions ${\{0,3\},\{1,2\}}$ , you should output $0 \ 1 \ 1 \ 0$ .

#include<bits/stdc++.h> #define pb push_back using namespace std; int ans[305];bool e[305][305];char str[90005]; int main(){ int T;scanf("%d",&T); while(T--){ int n,s,now=0,cc=-1;vector<int>v; scanf("%d%d",&n,&s);scanf("%s",str+1); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++)e[i][j]=e[j][i]=(str[++now]=='1'); e[i][i]=true;ans[i]=-1; } for(int i=1;i<=n;i++)if(ans[i]==-1){ v.clear();cc++; for(int j=1;j<=n;j++)if(ans[j]==-1&&e[i][j])v.pb(j); for(int j=1,cnt;j<=n;j++)if(ans[j]==-1){ cnt=0;for(auto x:v)if(e[j][x])cnt++; if(cnt>=(v.size()>>1))ans[j]=cc; } } for(int i=1;i<=n;i++)printf("%d ",ans[i]);puts(""); } return 0; }

详情