CF1245

Posted on | Edited on | Views:

$Div.2$

感觉这场的 E,F 都偏简单了啊.

A Good ol’ Numbers Coloring

只需要判断 $a,b$ 是否互质.

证明可以参考小凯的疑惑.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int main()
{
	int T=read();
	while(T--)
	{
		int a=read(),b=read();
		if(__gcd(a,b)==1)
			puts("Finite");
		else
			puts("Infinite");
	}
	return 0;
}

B Restricted RPS

先判断能否赢,若能,就先把需要赢的位置确定好,剩下的随便放即可.

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
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=128;
char buf[MAXN],ans[MAXN];
int main()
{
	int T=read();
	while(T--)
	{
		int n=read(),r=read(),p=read(),s=read();
		int x=(n+1)>>1,R=0,P=0,S=0;
		scanf("%s",buf);
		for(int i=0;i<n;++i)
		{
			if(buf[i]=='R')
				++R; 
			else if(buf[i]=='P')
				++P;				
			else
				++S;				
		}
		x-=min(R,p)+min(P,s)+min(S,r);
		if(x>0)
			puts("NO");
		else
		{
			puts("YES");
			for(int i=0;i<n;++i)
				ans[i]='#';
			for(int i=0;i<n;++i)
			{
				if(buf[i]=='R' && p)
					ans[i]='P',--p;
				else if(buf[i]=='P' && s)
					ans[i]='S',--s;
				else if(buf[i]=='S' && r)
					ans[i]='R',--r;
			}
			for(int i=0;i<n;++i)
				if(ans[i]=='#')
				{
					if(p)
						ans[i]='P',--p;
					else if(s)
						ans[i]='S',--s;
					else
						ans[i]='R',--r;
				}
			for(int i=0;i<n;++i)
				putchar(ans[i]);
			puts("");
		}
	}
	return 0;
}

C Constanze’s Machine

先特判掉存在字符 $w$ 或 $m$ 的情况,答案为 $0$ .

剩余情况,对于各段连续的 $u$ 串, $n$ 串,方案数是互不影响的,可以用乘法原理乘起来.

设计一个 $dp$ 计算长度为 $i$ 的 $u​$ 串的方案数,可以发现它就是斐波那契数.

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
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=1e5+10;
char buf[MAXN];
int n,f[MAXN];
int main()
{
	scanf("%s",buf);
	n=strlen(buf);
	f[0]=f[1]=1;
	for(int i=2;i<=n;++i)
		f[i]=add(f[i-1],f[i-2]);
	int ans=1;
	for(int i=0,j;i<n;++i)
	{
		if(buf[i]=='m' || buf[i]=='w')
			ans=0;
		j=i;
		while(j+1<n && buf[j+1]==buf[i])
			++j;
		if(buf[i]=='n' || buf[i]=='u')
			ans=mul(ans,f[j-i+1]);
		i=j;
	}
	cout<<ans<<endl;
	return 0;
}

D Shichikuji and Power Grid

设置一个虚拟节点 $n+1$ ,每个点与这个虚拟节点之间连边,权值为向这个点直接供电的花费,即 $c_i$ .

任意两个点之间连边,权值为在它们之间修电线的花费,跑一颗最小生成树即可.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const ll inf=9e18;
const int MAXN=2019;
struct node
{
	int c,k,x,y,id;
	bool operator < (const node &rhs) const
	{
		return c>rhs.c;
	}
}p[MAXN];
ll calc(node i,node j)
{
	return 1LL*(i.k+j.k)*(abs(i.x-j.x)+abs(i.y-j.y));
}
struct Edge
{
	int u,v;
	ll c;
	Edge(int u=0,int v=0,ll c=0):u(u),v(v),c(c){}
	bool operator < (const Edge &rhs) const
	{
		return c<rhs.c;
	}
}E[MAXN*MAXN+MAXN];
int n,m=0,s=0,t[MAXN],e=0,ea[MAXN],eb[MAXN];
int fa[MAXN];
int Find(int x)
{
	return x==fa[x]?x:fa[x]=Find(fa[x]);
}
ll ans=0;
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		p[i].id=i;
		p[i].x=read();
		p[i].y=read();
	}
	for(int i=1;i<=n;++i)
		p[i].c=read();
	for(int i=1;i<=n;++i)
		p[i].k=read();
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;
		E[++m]=Edge(i,n+1,p[i].c);
		for(int j=i+1;j<=n;++j)
			E[++m]=Edge(i,j,calc(p[i],p[j]));
	}
	fa[n+1]=n+1;
	sort(E+1,E+1+m);
	int tot=0;
	for(int i=1;i<=m && tot<=n;++i)
	{
		int u=E[i].u,v=E[i].v;
		if(Find(u)!=Find(v))
		{
			fa[Find(u)]=Find(v);
			if(v==n+1)
				t[++s]=u;
			else
			{
				++e;
				ea[e]=u;
				eb[e]=v;	
			}
			++tot;
			ans+=E[i].c;
		}
	}
	cout<<ans<<endl;
	printf("%d\n",s);
	for(int i=1;i<=s;++i)
		printf("%d ",t[i]);
	printf("\n%d\n",e);
	for(int i=1;i<=e;++i)
		printf("%d %d\n",ea[i],eb[i]);
	return 0;
}

E Hyakugoku and Ladders

设 $f(x,y)$ 表示当前在位置 $(x,y)$ ,走到终点的最小期望步数.

终点处的 $f$ 值为 $0$ ,对于距离终点的步数 $<6$ 的位置, $f$ 值为 $6$ .

其余位置直接枚举转移到哪个位置即可,记忆化搜索时还要记录上一步是不是用了梯子,因为不能连续用两次.

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
57
58
59
60
61
62
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=11;
double f[MAXN][MAXN][2];
typedef pair<int,int> pii;
#define mp make_pair
pii nxt(int x,int y)
{
	if(y==10 && x%2==0)
		return mp(x-1,y);
	if(y==1 && x%2)
		return mp(x-1,y);
	if(x%2==0)
		return mp(x,y+1);
	return mp(x,y-1);
}
int h[MAXN][MAXN];
double dfs(int x,int y,bool ladder)
{
	if(x==1 && y==1)
		return 0.0;
	if(x==1 && y<=6)
		return 6.0;
	if(f[x][y][ladder]>0)
		return f[x][y][ladder];
	double &res=f[x][y][ladder];
	res=0;
	int a=x,b=y;
	for(int i=1;i<=6;++i)
	{
		pii tmp=nxt(a,b);
		a=tmp.first,b=tmp.second;
		res+=dfs(a,b,true);		
	}
	res/=6.0;
	res+=1.0;
	if(ladder && h[x][y])
		res=min(res,dfs(x-h[x][y],y,false));
	return res;
}
int main()
{
	for(int i=1;i<=10;++i)
		for(int j=1;j<=10;++j)
			h[i][j]=read();
	printf("%.10f\n",dfs(10,1,true));
	return 0;
}

F Daniel and Spring Cleaning

设 $f(x,y)$ 表示 $0\le a\le x,0\le b\le y$ 时的合法方案数.

在二维平面上简单容斥,可以发现答案为 $f(r,r)-2\cdot f(l-1,r)+f(l-1,l-1)$ .

而 $a\oplus b=a+b$ 的充要条件为 $a\&b=0$ ,所以直接数位 $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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int K=32;
ll f[K][2][2];
int x,y;
int kp(int s,int i)
{
	return (s>>i)&1;
}
ll dfs(int k,bool lx,bool ly)
{
	if(k<0)
		return 1LL;
	if(f[k][lx][ly]!=-1)
		return f[k][lx][ly];
	ll &res=f[k][lx][ly];
	res=0;
	int maxx=lx?kp(x,k):1;
	int maxy=ly?kp(y,k):1;
	for(int i=0;i<=maxx;++i)
		for(int j=0;j<=maxy;++j)
			if(i+j<2)
				res+=dfs(k-1,lx&&i==maxx,ly&&j==maxy);
	return res;
}
ll calc(int l,int r)
{
	memset(f,-1,sizeof f);
	x=l,y=r;
	if(x<0 || y<0)
		return 0;
	return dfs(31,true,true);
}
void solve()
{
	int l=read(),r=read();
	ll ans=calc(r,r)-2LL*calc(r,l-1)+calc(l-1,l-1);
	cout<<ans<<endl;
}
int main()
{
	int T=read();
	while(T--)
		solve();
	return 0;
}