TCO2017

TCO2017(选做)

​ By Acheing

Round1

A hard

将图转化一下，发现这是两个凸包

最后的体积为一堆圆台的圆台的和

微积分算一下就好了

并不会微积分。。所以没有代码

反正联赛不考

B hard

将每个点权值变为xw[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?(1ll*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,1ll*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=(1ll*w1*seed1%mod1+67+t)%mod1;
            w2=(1ll*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=(1ll*w1*seed1%mod1+67-t)%mod1;
            w2=(1ll*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 0ll;return 1ll;}
		X=m/2,Y=m-X;
		dfs1(1);dfs2(1);
		return ans;
	}
};

Round2

A mid

非常有趣的一道题，对于一个限制(x,y)(x,y)我们把它连向(∣x′−x∣≤1,∣y′−y∣≤1)(|x'-x| \leq 1,|y'-y| \leq 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]那么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]

考虑每次修改会发生什么

推一下会发现

newd[x]=d[x]⊕1newd[x]=d[x] \oplus 1

newd[x+1]=d[x+1]⊕1newd[x+1]=d[x+1] \oplus 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])(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]...

移动后的位置是q[1],q[2],q[3],q[4],q[5]...q[1],q[2],q[3],q[4],q[5]...

那么移动次数为∑i=1n∣q[i]−p[i]∣\sum_{i=1}^n |q[i]-p[i]|，显然是≤n2\leq n^2的

那么DP很显然

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 2ll*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;
//		printf("%d %d\n",tot,n);
		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;
//			for (j=1;j<=D;j++)printf("%d ",f[i][j]);printf("\n");
		}
//		for (i=1;i<=D;i++)printf("%d ",f[i]);
		return f[tot][D];
	}
};

B hard

好题啊

%%%xza一眼秒掉！

f[i][j]f[i][j]表示第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=(1ll*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≤DN-1 \leq 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]表示前i个数划分成j段的minvalue

然后我们会发现一个性质

f[i][j]∈(j,j+26]→f[i][j]−j∈[1,26]f[i][j] \in (j,j+26] \to f[i][j]-j \in [1,26]

还有一个性质

f[i][j]−j≤f[i][k]−k(j>k)f[i][j]-j \leq f[i][k]-k (j>k)

这是为什么呢

考虑f[i][j]−jf[i][j]-j的意义

意义就是前i个数分成j段，每段里减去一个字母的代价

显然j越大减去的代价就越多。

然后，我们可以知道

若f[n][j]−j=x(j<K)f[n][j]-j=x(j<K)那么f[n][K]<=x+Kf[n][K]<=x+K

我们可以设F[i][j]F[i][j]表示f[i][k]−k=jf[i][k]-k=j的最小的k

考虑更新ans，若F[n][i]<=KF[n][i]<=K则ans=min(ans,i+K)ans=min(ans,i+K)

F[i][j]F[i][j]该怎么转移呢？

每次枚举i前面每个字符第一次出现的位置，转移就好了。

F[i][j+k−1]=min(F[pre[k]][j]+1)F[i][j+k-1]=min(F[pre[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=1ll*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为这串数列的第一个数

那么假如有限制Si,j=YS_{i,j}=Y，则gcd(x+i,x+j)=1→gcd(x+i,j−i)=1gcd(x+i,x+j)=1 \to gcd(x+i,j-i)=1

所以我们只要考虑≤n\leq n的质数对这串数列的影响就好了

假设当前枚举的质数为PP,那么我们考虑x≡?(modP)x \equiv ?(\bmod P)

我们不断枚举i,若Si,j=NS_{i,j}=N，说明了什么？

说明gcd(x+i,x+j)=pgcd(x+i,x+j)=p

那么x≡−i(modp)x \equiv -i(\bmod p)

若一个p对于x有两个取值，那么必定无解

若一个p∗2≤np*2 \leq n，且对于x没有取值，那么也必定无解

我们确定了xmodpx \bmod 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

本文标题:TCO2017

文章作者:Acheing

发布时间:2018年10月01日 - 13时40分

最后更新:2018年10月14日 - 18时28分

原始链接:http://yoursite.com/2018/10/01/tco2017/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. TCO2017(选做)
    1. 1.1. Round1
      1. 1.1.1. A hard
      2. 1.1.2. B hard
      3. 1.1.3. C hard
    2. 1.2. Round2
      1. 1.2.1. A mid
      2. 1.2.2. A hard
      3. 1.2.3. B mid
      4. 1.2.4. B hard
      5. 1.2.5. C mid
      6. 1.2.6. C hard
    3. 1.3. Round 3
      1. 1.3.1. A easy
      2. 1.3.2. A mid
,