TCO2017(选做)
By Acheing
Round1
A hard
将图转化一下,发现这是两个凸包
最后的体积为一堆圆台的圆台的和
微积分算一下就好了
并不会微积分。。所以没有代码
反正联赛不考
B hard
将每个点权值变为x w [ i ] x^{w[i]} x w [ i ] 问题就转化为求树上所有联通块的权值积的和,DP一下就好了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std ;typedef long long ll;static const int N=60 ;static const int mod=1000000007 ;int i,j,k,n,m,x,y,t,w[N];ll f[N][N],ans[N],ANS; int fi[N*2 ],ne[N*2 ],la[N*2 ],a[N*2 ];struct SubtreeSumHash { void add (ll &x,ll y) {x+=y;if (x>=mod)x-=mod;} ll mi (ll x,ll y) {if (y==0 )return 1 ;ll t=mi(x,y>>1 );t=t*t%mod;return y&1 ?(1l l*x*t%mod):t;} void add (int x,int y) {k++;a[k]=y;if (fi[x]==0 )fi[x]=k;else ne[la[x]]=k;la[x]=k;} void dp (int x,int fa) { f[x][1 ]=w[x];f[x][0 ]=1 ; for (int i=fi[x];i;i=ne[i]) if (a[i]!=fa){ dp(a[i],x); for (int j=n;j>=2 ;j--) for (int k=1 ;k<=j-1 ;k++) add(f[x][j],f[x][j-k]*f[a[i]][k]%mod); } } int count (vector <int >weight,vector <int >p,int x) { n=weight.size(); for (i=1 ;i<=n;i++)w[i]=mi(x,weight[i-1 ]); for (i=0 ;i<=n-2 ;i++)add(p[i]+1 ,i+2 ),add(i+2 ,p[i]+1 ); for (i=1 ;i<=n;i++){ memset (f,0 ,sizeof f); dp(i,-1 ); for (j=1 ;j<=n;j++)add(ans[j],f[i][j]); } for (i=1 ;i<=n;i++)add(ANS,1l l*ans[i]*mi(i,mod-2 )%mod); return (int )ANS; } };
C hard
n很小,meet in the middle暴力就好了,注意要双哈希。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <bits/stdc++.h> using namespace std ;typedef long long ll;#define seed1 23 #define mod1 1000000007 #define seed2 29 #define mod2 1000000009 map <pair<int ,int >,int >mp;int i,j,k,n,m,X,Y,t,a[1010 ][1001 ];int win[4 ][4 ],cho[1010 ];ll ans; struct EllysRPS { void mark1 () { int w1=0 ,w2=0 ; for (k=1 ;k<=n;k++){ int t=0 ;for (i=1 ;i<=X;i++)t+=win[cho[i]][a[k][i]]; w1=(1l l*w1*seed1%mod1+67 +t)%mod1; w2=(1l l*w2*seed2%mod2+69 +t)%mod2; } mp[make_pair(w1,w2)]++; } void work () { int w1=0 ,w2=0 ; for (k=1 ;k<=n;k++){ int t=0 ;for (i=1 ;i<=Y;i++)t+=win[cho[i]][a[k][i+X]]; w1=(1l l*w1*seed1%mod1+67 -t)%mod1; w2=(1l l*w2*seed2%mod2+69 -t)%mod2; } ans+=mp[make_pair(w1,w2)]; } void dfs1 (int x) { if (x==X+1 ){mark1();return ;} cho[x]=1 ;dfs1(x+1 );cho[x]=2 ;dfs1(x+1 );cho[x]=3 ;dfs1(x+1 ); } void dfs2 (int x) { if (x==Y+1 ){work();return ;} cho[x]=1 ;dfs2(x+1 );cho[x]=2 ;dfs2(x+1 );cho[x]=3 ;dfs2(x+1 ); } ll getCount (vector <string >s) { win[1 ][1 ]=0 ;win[2 ][2 ]=0 ;win[3 ][3 ]=0 ; win[1 ][2 ]=-1 ;win[2 ][1 ]=1 ;win[1 ][3 ]=1 ; win[3 ][1 ]=-1 ;win[2 ][3 ]=-1 ;win[3 ][2 ]=1 ; m=s[0 ].size();n=s.size(); for (i=0 ;i<n;i++)for (j=0 ;j<m;j++) a[i+1 ][j+1 ]=(s[i][j]=='R' ?1 :(s[i][j]=='P' ?2 :3 )); for (i=1 ;i<=n;i++){for (j=1 ;j<=m;j++)printf ("%d " ,a[i][j]);printf ("\n" );} if (m==1 ){for (j=1 ;j<=n;j++)if (a[j][1 ]!=a[1 ][1 ])return 0l l;return 1l l;} X=m/2 ,Y=m-X; dfs1(1 );dfs2(1 ); return ans; } };
Round2
A mid
非常有趣的一道题,对于一个限制( x , y ) (x,y) ( x , y ) 我们把它连向( ∣ x ′ − x ∣ ≤ 1 , ∣ y ′ − y ∣ ≤ 1 ) (|x'-x| \leq 1,|y'-y| \leq 1) ( ∣ x ′ − x ∣ ≤ 1 , ∣ y ′ − y ∣ ≤ 1 ) 再跑一边最短路判一下就行了
为什么这样是对的呢?
因为仔细观察会发现每个限制的每一维在图中只会被那一维他小1的更新 无解情况其实就是找不到连出的边的情况。我写烦了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <bits/stdc++.h> using namespace std ;struct DistanceZeroAndOne { int w[51 ][51 ],d[51 ][51 ]; queue <int >q; vector <string >construct(vector <int >X,vector <int >Y){ vector <string >ans; int n=X.size(); for (int i=0 ;i<n;i++) for (int j=0 ;j<n;j++) if (i!=j&&(abs (X[i]-X[j])<=1 &&abs (Y[i]-Y[j])<=1 ))w[i][j]=1 ,d[i][j]=1 ; else w[i][j]=0 ,d[i][j]=1013687232 ; for (int i=0 ;i<n;i++)d[i][i]=0 ; for (int k=0 ;k<n;k++) for (int i=0 ;i<n;i++) if (i!=k) for (int j=0 ;j<n;j++) if (i!=j&&j!=k) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); for (int i=0 ;i<n;i++)if (d[0 ][i]!=X[i])return ans; for (int i=0 ;i<n;i++)if (d[1 ][i]!=Y[i])return ans; for (int i=0 ;i<n;i++){ string s="" ; for (int j=0 ;j<n;j++) if (w[i][j]==1 )s+='Y' ;else s+='N' ; ans.push_back(s); } return ans; } };
A hard
神题啊。。终于A了。。mls的题解好难看懂啊。。
先设d [ x ] = a [ x ] ⊕ a [ x + 2 ] d[x]=a[x] \oplus a[x+2] d [ x ] = a [ x ] ⊕ a [ x + 2 ] 那么a [ x ] ⊕ a [ x + 1 ] ⊕ a [ x + 2 ] ⊕ a [ x + 3 ] = d [ x ] ⊕ d [ x + 1 ] a[x] \oplus a[x+1] \oplus a[x+2] \oplus a[x+3]=d[x] \oplus d[x+1] a [ x ] ⊕ a [ x + 1 ] ⊕ a [ x + 2 ] ⊕ a [ x + 3 ] = d [ x ] ⊕ d [ x + 1 ]
考虑每次修改会发生什么
推一下会发现
n e w d [ x ] = d [ x ] ⊕ 1 newd[x]=d[x] \oplus 1 n e w d [ x ] = d [ x ] ⊕ 1
n e w d [ x + 1 ] = d [ x + 1 ] ⊕ 1 newd[x+1]=d[x+1] \oplus 1 n e w d [ x + 1 ] = d [ x + 1 ] ⊕ 1
也就是,d[x]与d[x+1]换了一个数字!
那么一个a序列我们可以表示成:
a [ 0 ] , a [ 1 ] , d [ 0 ] , d [ 1 ] , d [ 2 ] . . . . . a[0],a[1],d[0],d[1],d[2]..... a [ 0 ] , a [ 1 ] , d [ 0 ] , d [ 1 ] , d [ 2 ] . . . . .
且( a [ 0 ] , a [ 1 ] ) (a[0],a[1]) ( a [ 0 ] , a [ 1 ] ) 只有两种取值
先考虑没有a的限制该怎么做?
题目就转化为你有n个位置,m个小球,每个小球只能移到旁边的一个空位。
问你有几种移小球的方案。
为了不重不漏的计数,每个方案我们只记移动次数最少的一次。
移动次数怎么算呢?
设移动前的位置是p [ 1 ] , p [ 2 ] , p [ 3 ] , p [ 4 ] , p [ 5 ] . . . p[1],p[2],p[3],p[4],p[5]... p [ 1 ] , p [ 2 ] , p [ 3 ] , p [ 4 ] , p [ 5 ] . . .
移动后的位置是q [ 1 ] , q [ 2 ] , q [ 3 ] , q [ 4 ] , q [ 5 ] . . . q[1],q[2],q[3],q[4],q[5]... q [ 1 ] , q [ 2 ] , q [ 3 ] , q [ 4 ] , q [ 5 ] . . .
那么移动次数为∑ i = 1 n ∣ q [ i ] − p [ i ] ∣ \sum_{i=1}^n |q[i]-p[i]| ∑ i = 1 n ∣ q [ i ] − p [ i ] ∣ ,显然是≤ n 2 \leq n^2 ≤ n 2 的
那么DP很显然
f [ i ] [ j ] [ k ] f[i][j][k] f [ i ] [ j ] [ k ] 表示当前在位置i,枚举到第j个1,还有k次移动方案
记忆化一下就好了细节少
但还有a[0]和a[1]的限制。
我们发现每种限制都代表着一种不同的方案,所以ans*2,但当K=1时,两个限制算一种。所以要减1
代码很短。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <bits/stdc++.h> using namespace std ;typedef long long ll;struct FourLamps { ll f[52 ][52 ][52 *52 ]; bool g[52 ][52 ][52 *52 ]; int a[52 ],i,j,k,n,m,b[52 ]; ll dp (int x,int y,int res) { if (y==m+1 )return 1 ; if (x==n+1 )return 0 ; if (g[x][y][res])return f[x][y][res]; g[x][y][res]=1 ; f[x][y][res]=dp(x+1 ,y,res); if (res>=abs (b[y]-x))f[x][y][res]+=dp(x+1 ,y+1 ,res-abs (b[y]-x)); return f[x][y][res]; } ll count (string init,int K) { n=init.length()-1 ; for (i=0 ;i<=n-2 ;i++)if (init[i+2 ]!=init[i])a[++a[0 ]]=1 ;else a[++a[0 ]]=0 ;n=a[0 ]; printf ("%d\n" ,n); for (i=1 ;i<=n;i++)printf ("%d " ,a[i]);printf ("\n" ); for (i=1 ;i<=n;i++)if (a[i])b[++m]=i; if (m==0 ||m==n)return 1 ; return 2l l*dp(1 ,1 ,min(K,n*n))-(K==1 ); } };
B mid
把连着的且字母一样的边缩在一起。
这样每个都代表一段深度区间。
题目转化为给你若干个区间,求覆盖完所有区间的方案数
按左端点排序后DP一遍就行了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <bits/stdc++.h> using namespace std ;static const int N=2010 ;static const int mod=1000000007 ;struct data {int l,r;}s[N*26 ];bool cmp (const data&a,const data&b) {return a.l<b.l;}struct DengklekGaneshAndTree { int i,j,k,n,m,x,y,t,tot,D; int fi[N*2 ],ne[N*2 ],la[N*2 ],a[N*2 ],d[N],c[N],f[N][N]; void add (int x,int y) { k++;a[k]=y; if (fi[x]==0 )fi[x]=k;else ne[la[x]]=k; la[x]=k; } void dfs (int x,int fa,int de) { d[x]=de;if (de>D)D=de; for (int i=fi[x];i;i=ne[i]){ dfs(a[i],x,de+1 ); if (c[a[i]]==c[x])d[x]=max(d[x],d[a[i]]); } if (fa==-1 ||c[fa]!=c[x])s[++tot]={de,d[x]}; } int getCount (string S,vector <int >P) { n=S.length(); for (i=2 ;i<=n;i++)add(P[i-2 ]+1 ,i); for (i=1 ;i<=n;i++)c[i]=S[i-1 ]-'a' +1 ; dfs(1 ,-1 ,1 ); sort(s+1 ,s+1 +tot,cmp); memset (f,0 ,sizeof f);f[0 ][0 ]=1 ; for (i=1 ;i<=tot;i++){ for (j=s[i].l-1 ;j<=D;j++) f[i][max(j,s[i].r)]=(f[i][max(j,s[i].r)]+f[i-1 ][j])%mod; for (j=1 ;j<=D;j++)f[i][j]=(f[i][j]+f[i-1 ][j])%mod; } return f[tot][D]; } };
B hard
好题啊
%%%xza一眼秒掉!
f [ i ] [ j ] f[i][j] f [ i ] [ j ] 表示第i个数被翻了j次的概率
g [ i ] [ j ] g[i][j] g [ i ] [ j ] 表示第i个数被翻了j次,0的数量的期望值
考虑每个i对答案的贡献
一种是i往右使多少0变为1
另一种是有多少1使i从0变为1
转移一下就可以了!
想了一整天
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std ;const int N=1000010 ;struct DengklekGaneshAndDetention { double g[N][2 ],f[N][2 ],p[N],ans; int i,j,k,n,m,x,y,t,a[N],cnt; double getExpected (int N,int vi,int vm,int va,int vmo) { n=N;x=vi; for (i=1 ;i<=n;i++)a[i]=x%2 ,p[i]=(double )(x%101 )/100 ,x=(1l l*x*vm%vmo+va)%vmo; for (i=1 ;i<=n;i++)cnt+=a[i]; memset (f,0 ,sizeof f); f[1 ][0 ]=1 ;ans=0.0 ; for (i=1 ;i<=n;i++){ cnt-=a[i]; for (j=0 ;j<2 ;j++) if (f[i][j]){ g[i][j]/=f[i][j]; if (a[i]^j){ f[i+1 ][j]+=f[i][j]*p[i]; f[i+1 ][j^1 ]+=f[i][j]*(1 -p[i]); g[i+1 ][j]+=(i-1 -g[i][j])*f[i][j]*p[i]; g[i+1 ][j^1 ]+=g[i][j]*f[i][j]*(1 -p[i]); ans+=f[i][j]*g[i][j]*p[i]; if (j)ans+=f[i][j]*cnt*(1 -p[i]); else ans+=f[i][j]*(n-i-cnt)*(1 -p[i]); } else { f[i+1 ][j]+=f[i][j]; g[i+1 ][j]+=(g[i][j]+1 )*f[i][j]; } } } return ans; } };
C mid
官方题解写的好烦啊。。并没有看懂题解在写什么
先考虑什么时候Demon一定赢?那就是N − 1 ≤ D N-1 \leq D N − 1 ≤ D 的时候,这样D可以切掉与0相连的边
否则Demon一定不赢
再考虑什么时候Angel一定赢?
考虑费用流
令S->0连一条(D+1,0)的边(第一个数表示流量,第二个数表示费用)
对于所有的i和j,若i->j在原图中有边,则为 (1,0)否则为(1,1)
跑一遍费用流。
若最大流==D+1且最小费用小于等于A,则Angel赢
否则为平局
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include <bits/stdc++.h> using namespace std ;const int N=5100 ;struct AngelDemonGame { int i,j,k,n,m,x,y,t; int d[N],Ans,mn,pre1[N],pre2[N],inq[N]; int fi[N*2 ],ne[N*2 ],la[N*2 ],a[N*2 ],c[N*2 ],f[N*2 ]; queue <int >q; void add (int x,int y,int flow,int cost) { k++;a[k]=y;c[k]=cost;f[k]=flow; if (fi[x]==0 )fi[x]=k;else ne[la[x]]=k; la[x]=k; } void insert (int x,int y,int f,int c) {add(x,y,f,c);add(y,x,0 ,-c);} bool spfa () { memset (d,-1 ,sizeof d); d[0 ]=0 ;q.push(0 );inq[0 ]=1 ; while (!q.empty()){ x=q.front();q.pop();inq[x]=0 ; for (int i=fi[x];i;i=ne[i]) if ((d[a[i]]==-1 ||d[a[i]]>d[x]+c[i])&&f[i]){ d[a[i]]=d[x]+c[i];pre1[a[i]]=i;pre2[a[i]]=x; if (!inq[a[i]]){inq[a[i]]=1 ;q.push(a[i]);} } } return d[n]!=-1 ; } void work () { mn+=d[n]; int no=n,flow=1013687232 ; while (no){ int la=pre1[no]; flow=min(flow,f[la]); no=pre2[no]; } no=n;Ans+=flow; while (no){ int la=pre1[no]; f[la]-=flow;f[la^1 ]+=flow; no=pre2[no]; } } string winner (vector <string >G,int A,int D) { n=G.size(); if (D>=n-1 )return "Demon" ; k=1 ; for (i=0 ;i<n;i++) for (j=0 ;j<n;j++) if (G[i][j]=='Y' )insert(i+1 ,j+1 ,1 ,0 ); else insert(i+1 ,j+1 ,1 ,1 ); insert(0 ,1 ,D+1 ,0 ); while (spfa())work(); if (Ans==D+1 &&mn<=A)return "Angel" ; return "Unknown" ; } };
C hard
首先会发现一个很简单的DP
f [ i ] [ j ] f[i][j] f [ i ] [ j ] 表示前i个数划分成j段的minvalue
然后我们会发现一个性质
f [ i ] [ j ] ∈ ( j , j + 2 6 ] → f [ i ] [ j ] − j ∈ [ 1 , 2 6 ] f[i][j] \in (j,j+26] \to f[i][j]-j \in [1,26] f [ i ] [ j ] ∈ ( j , j + 2 6 ] → f [ i ] [ j ] − j ∈ [ 1 , 2 6 ]
还有一个性质
f [ i ] [ j ] − j ≤ f [ i ] [ k ] − k ( j > k ) f[i][j]-j \leq f[i][k]-k (j>k) f [ i ] [ j ] − j ≤ f [ i ] [ k ] − k ( j > k )
这是为什么呢
考虑f [ i ] [ j ] − j f[i][j]-j f [ i ] [ j ] − j 的意义
意义就是前i个数分成j段,每段里减去一个字母的代价
显然j越大减去的代价就越多。
然后,我们可以知道
若f [ n ] [ j ] − j = x ( j < K ) f[n][j]-j=x(j<K) f [ n ] [ j ] − j = x ( j < K ) 那么f [ n ] [ K ] < = x + K f[n][K]<=x+K f [ n ] [ K ] < = x + K
我们可以设F [ i ] [ j ] F[i][j] F [ i ] [ j ] 表示f [ i ] [ k ] − k = j f[i][k]-k=j f [ i ] [ k ] − k = j 的最小的k
考虑更新ans,若F [ n ] [ i ] < = K F[n][i]<=K F [ n ] [ i ] < = K 则a n s = m i n ( a n s , i + K ) ans=min(ans,i+K) a n s = m i n ( a n s , i + K )
F [ i ] [ j ] F[i][j] F [ i ] [ j ] 该怎么转移呢?
每次枚举i前面每个字符第一次出现的位置,转移就好了。
F [ i ] [ j + k − 1 ] = m i n ( F [ p r e [ k ] ] [ j ] + 1 ) F[i][j+k-1]=min(F[pre[k]][j]+1) F [ i ] [ j + k − 1 ] = m i n ( F [ p r e [ k ] ] [ j ] + 1 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <bits/stdc++.h> using namespace std ;struct TreasureOfWinedag { string s; int i,j,k,n,m,x,y,t; vector <int >pre[100010 ]; int f[100010 ][26 ],be[100010 ][26 ]; int solvePuzzle (int N, int K, int m, int c0, vector <int > c1, vector <int > c2, vector <int > c3, vector <int > c4, string str) { s=str;n=N; for (i=s.length();i<=N-1 ;i++){ t=1l l*i*c0%m;char newchar='z' ; for (j=0 ;j<=24 ;j++) if (t>=c3[j]&&t<=c4[j]&&(t%c1[j])==c2[j]){ newchar='a' +j; break ; } s+=newchar; } s=' ' +s; for (i=1 ;i<=n;i++){ pre[i].clear(); for (j=0 ;j<26 ;j++)be[i][j]=be[i-1 ][j]; be[i][s[i]-'a' ]=i; for (j=0 ;j<26 ;j++)if (be[i][j])pre[i].push_back(be[i][j]); sort(pre[i].begin(),pre[i].end()); reverse(pre[i].begin(),pre[i].end()); } for (int i=1 ;i<=n;i++) for (int j=0 ;j<26 ;++j) f[i][j]=1013687232 ; for (int i=1 ;i<=n;i++) { for (int j=1 ;j<=pre[i].size();j++) { int p=(j==pre[i].size())?0 :pre[i][j]; for (int z=0 ;z+j<=26 ;++z) f[i][z+j-1 ]=min(f[i][z+j-1 ],f[p][z]+1 ); } } for (int j=0 ;j<26 ;++j) if (f[n][j]<=K) return j+K; } };
终于把Round2干完了。。
好吃力啊。。
Round 3
A easy
真是一道有趣的题
怎么一个easy我都不会啊。。
设x为这串数列的第一个数
那么假如有限制S i , j = Y S_{i,j}=Y S i , j = Y ,则g c d ( x + i , x + j ) = 1 → g c d ( x + i , j − i ) = 1 gcd(x+i,x+j)=1 \to gcd(x+i,j-i)=1 g c d ( x + i , x + j ) = 1 → g c d ( x + i , j − i ) = 1
所以我们只要考虑≤ n \leq n ≤ n 的质数对这串数列的影响就好了
假设当前枚举的质数为P P P ,那么我们考虑x ≡ ? ( mod P ) x \equiv ?(\bmod P) x ≡ ? ( mod P )
我们不断枚举i,若S i , j = N S_{i,j}=N S i , j = N ,说明了什么?
说明g c d ( x + i , x + j ) = p gcd(x+i,x+j)=p g c d ( x + i , x + j ) = p
那么x ≡ − i ( mod p ) x \equiv -i(\bmod p) x ≡ − i ( mod p )
若一个p对于x有两个取值,那么必定无解
若一个p ∗ 2 ≤ n p*2 \leq n p ∗ 2 ≤ n ,且对于x没有取值,那么也必定无解
我们确定了x mod p x \bmod p x mod p 后,就用这个取值更新一下矩阵中其他的值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <bits/stdc++.h> using namespace std ;struct CoprimeMatrix { int i,j,k,n,m,x,y,t; string yes="Possible" ,no="Impossible" ; char ans[51 ][51 ]; int gcd (int x,int y) {return y==0 ?x:gcd(y,x%y);} string isPossible (vector <string >S) { n=S.size(); if (S[0 ][0 ]=='Y' ){ for (i=0 ;i<n;i++) for (j=0 ;j<n;j++) if (gcd(i+1 ,j+1 )==1 &&S[i][j]=='N' )return no; else if (gcd(i+1 ,j+1 )!=1 &&S[i][j]=='Y' )return no; return yes; } printf ("!!!\n" ); for (i=0 ;i<n;i++)for (j=0 ;j<n;j++)if (S[i][j]!=S[j][i])return no; for (i=0 ;i<n;i++)if (S[i][i]=='Y' )return no; for (i=0 ;i<n;i++)for (j=0 ;j<n;j++)ans[i][j]='Y' ; for (i=0 ;i<n;i++)ans[i][i]='N' ; for (int p=2 ;p<=n;p++){ bool flag=0 ; for (j=2 ;j<=sqrt (p);j++)if (p%j==0 ){flag=1 ;break ;} if (flag)continue ; int cnt=0 ,res=0 ; for (i=0 ;i<p;i++){ if (i+p>=n)break ; if (S[i][i+p]=='N' ){cnt++;if (cnt>1 )return no;res=i;} } if (cnt==0 &&p*2 <=n)return no; printf ("%d %d %d\n" ,p,res,cnt); if (cnt){ for (i=res;i<n;i+=p) for (x=res;x<n;x+=p)ans[i][x]=ans[x][i]='N' ; } } for (i=0 ;i<n;i++){ for (j=0 ;j<n;j++)printf ("%c" ,ans[i][j]);printf ("\n" ); } for (i=0 ;i<n;i++) for (j=0 ;j<n;j++) if (ans[i][j]!=S[i][j])return no; return yes; } };
A mid
标算都T了是什么鬼。。
updating