CF1191

Posted on | Views:

$Div.2$

怎么出了两个博弈的题啊…

A Tokitsukaze and Enhancement

  • 模拟即可.
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
#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 x=read();
	x%=4;
	if(x==0)
		puts("1 A");
	else if(x==1)
		puts("0 A");
	else if(x==2)
		puts("1 B");
	else
		puts("2 A");
	return 0;
}

B Tokitsukaze and Mahjong

  • 模拟即可.
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
#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;
}
char buf[3][3];
int k1(int i)
{
	return buf[i][0];
}
int k2(int i)
{
	return buf[i][1];
}
bool equal(int i,int j)
{
	return k1(i)==k1(j) && k2(i)==k2(j);
}
bool nx(int i,int j)
{
	return abs(k1(i)-k1(j))<=2 && k2(i)==k2(j);
}
int main()
{
	for(int i=1;i<=3;++i)
		scanf("%s",buf[i]);
	if(k1(1)==k1(2) && k1(1)==k1(3) && k2(1)==k2(2) && k2(2)==k2(3))
	{
		puts("0");
		return 0;
	}
	if(k2(1)==k2(2) && k2(1)==k2(3))
	{
		int a[3];
		a[0]=k1(1),a[1]=k1(2),a[2]=k1(3);
		sort(a,a+3);
		if(a[1]-a[0]==1 && a[2]-a[1]==1)
		{
			puts("0");
			return 0;
		}
	}
	if(equal(1,2) || equal(1,3) || equal(2,3))
		puts("1");
	else if(nx(1,2) || nx(1,3) || nx(2,3))
		puts("1");
	else
		puts("2");
	return 0;
}

C Tokitsukaze and Discard Items

  • 模拟删数的过程,二分找出此次删掉的最后一个数.
  • 每次至少删掉一个数,时间复杂度 $O(m\cdot \log m)$ .
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll 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=1e5+10;
ll p[MAXN];
int x=1,m;
int bs(ll lim,int tot)
{
	int L=x,R=m;
	int ans=x;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(p[mid]-tot<=lim)
			ans=mid,L=mid+1;
		else
			R=mid-1;
	}
	return ans;
}
int main()
{
	ll n=read();
	m=read();
	ll k=read();
	for(int i=1;i<=m;++i)
		p[i]=read()-1;
	int tot=0,ans=0;
	while(tot!=m)
	{
		ll pos=(p[x]-tot)/k;
		ll y=bs(pos*k+k-1,tot);
		ans++;
		tot+=y-x+1;
		x=y+1;
	}
	cout<<ans<<endl;
	return 0;
}

D Tokitsukaze, CSL and Stone Game

  • 感觉思路已经非常接近正解了,但有个情况没判到.
  • 除了先手第一次拿后就必败,最后一定是石子数形成 $0,1,2,\dots n-1$ 的排列.
  • 记初始时石子数为 $x$ 的有 $cnt_x$ 堆,特判一下先手第一次拿后就必败的情况:

  • 若第一次取后未败,则只需判断使局面形成 $0,1,2,\dots n-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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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=1e5+10;
int n,a[MAXN],p[MAXN];
unordered_map<int,int> cnt;
bool check()
{
	if(cnt[0]==n)
		return true;
	if(cnt[0]>=2)
		return true;
	int k=0;
	sort(p+1,p+1+n);
	int m=unique(p+1,p+1+n)-p-1;
	for(int i=1;i<=m;++i)
	{
		int x=p[i];
		if(cnt[x]>=3)
			return true;
		if(cnt[x]==2 && cnt[x-1]>=1)
			return true;
		if(cnt[x]==2)
			++k;
	}
	if(k>=2)
		return true;
	return false;
}
int main()
{
	n=read();
	int s=0;
	for(int i=1;i<=n;++i)
	{
		p[i]=a[i]=read();
		++cnt[p[i]];
	}	
	if(check())
		return puts("cslnb")&0;	
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
		s^=(a[i]-i+1)&1;
	if(s)
		puts("sjfnb");
	else
		puts("cslnb");
	return 0;
}

E Tokitsukaze and Duel

  • 给一段 $0/1$ 序列,双方轮流操作,每次操作将一段长度为 $k$ 的区间全部变成一个值,操作后使得整个序列全是 $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
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
#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=1e5+10;
int n,k,a[MAXN],sum[MAXN];
int pre[MAXN][2],nxt[MAXN][2];
char s[MAXN];
bool first_win(int p)
{
	int l=p,r=p+k-1;
	if(sum[l-1]+sum[n]-sum[r]+k==n)
		return true;
	if(sum[l-1]+sum[n]-sum[r]==0)
		return true;
	return false;
}
int find_first(int L,int R,int x)
{
	int s=nxt[L][x];
	if(s==0 || s>R)
		return 0;
	return s;
}
int find_last(int L,int R,int x)
{
	int s=pre[R][x];
	if(s==0 || s<L)
		return 0;
	return s;	
}
bool second_win(int p,int x)
{
	int l=p,r=p+k-1;
	int L,R;
	L=find_first(1,l-1,x);
	if(!L)
		L=find_first(r+1,n,x);
	R=find_last(r+1,n,x);
	if(!R)
		R=find_last(1,l-1,x);
	assert(L && R);
	return R-L+1<=k;
}
bool Second_win(int p)
{
	return second_win(p,0) && second_win(p,1);
}
int main()
{
	n=read(),k=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;++i)
	{
		a[i]=s[i]-'0';
		sum[i]=sum[i-1]+a[i];
	}	
	for(int i=1;i<=n;++i)
	{
		pre[i][0]=(a[i]==0)?i:pre[i-1][0];
		pre[i][1]=(a[i]==1)?i:pre[i-1][1];
	}
	for(int i=n;i>=1;--i)
	{
		nxt[i][0]=(a[i]==0)?i:nxt[i+1][0];
		nxt[i][1]=(a[i]==1)?i:nxt[i+1][1];
	}
	bool f=true;
	for(int i=1;i+k-1<=n;++i)
	{
		if(first_win(i))
		{
			puts("tokitsukaze");
			return 0;
		}
		if(f && !Second_win(i))
			f=false;
	}
	if(f)
		puts("quailty");
	else
		puts("once again");
	return 0;
}