本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-10 22:47:30

记录

ABCD 切了，E 想了想切了，F 没想出来，G 看出是矩阵了没写出来，Ex 没看，但是也很板。总之全很板。

题解

A - 2^N

基本题，略过不表。

B - Batters

模拟基本题，略过不表。

C - Filling 3x3 array

发现确定四个格后就能唯一确定或填法，所以枚举 $a_{1,1},a_{1,2},a_{2,1},a_{2,2}$，之后判断是否能填出合法方案即可，复杂度 $O(30^4)$

D - Union of Interval

用差分前缀和维护每个点是否在最终的并集中，然后对于每个连续段输出即可。

E - Takahashi's Anguish

发现每个人只有一个 $x_i$ 需要在其之后，如果这样连单向边，就是一个基环树森林。如果要尽量满足更多的条件，就只需要在每个环中选一个权值最小的不满足，拓扑排序处理环即可。

F - Cumulative Cumulative Cumulative Sum

推式子，$c_x=\sum_{i=1}^x b_i=\sum_{i=1}^x(x-i+1)a_i$，$d_i=\sum_{i=1}^x c_i=\sum_{i=1}^x\sum_{k=1}^{x-i+1}ka_i$

接着往下拆，$d_i=\sum_{i=1}^x\sum_{k=1}^{x-i+1}ka_i=\sum_{i=1}^x\frac{(x-i+2)(x-i+1)}{2}a_i$

拆开分子得 $(x^2+3x+2)a_i-2xia_i+(i^2-3i)a_i$，用树状数组动态维护前缀 $a_i,ia_i,(i^2-3i)a_i$ 的和，系数直接计算即可。

G - Black and White Stones

考虑朴素 dp，首先要枚举每条边上的白石子数量 $x$，断环为链，设 $f_{i,0/1,0/1}$ 表示考虑前 $i$ 条边，第一条边开头是/否是白色，第 $i$ 条边结尾是/否是白色的方案数，设 $c_i=\binom{d-1}{i}$，转移如下：

• $f_{i,0/1,0}=f_{i-1,0/1,0}\times c_x+f_{i-1,0/1,1}\times c_{x-1}$
• $f_{i,0/1,1}=f_{i-1,0/1,0}\times c_{x-1}+f_{i-1,0/1,1}\times c_{x-2}$

发现是线性转移，用矩阵加速即可，然后发现 $f_1$ 的初始矩阵和转移矩阵相同，直接 $n$ 次方即为答案，答案中有效的为 $f_{n,0,0}+f_{n,1,1}$，对于 $x\in[1,d+1]$ 分别计算，最后加上 $x=0$ 的一种情况即为结果，时间复杂度 $O(2^3d\log n)$

Ex - I like Query Problem

考虑把整除也转化为区间修改，发现若区间最大值和区间最小值整除 $k$ 相等，就可以直接区间修改为相同的值。因此势能线段树，维护区间和以及最值，每次都暴力下到一个可以区间修改的区间进行修改，由于每个区间被除 $\log V$ 次或被修改一次即可以保证整除相等，总复杂度为 $O(n\log n\log V)$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-03 21:41:25

• Day -4 2.26

来wfyz开学了，一天三节文化课，感觉很好。

• Day 0 3.1

上午文化课请了假，在机房半学半颓。

中午火车过去了，下午在酒店半学半颓。

晚上去崔神和杰哥房间打三国杀，颓了一晚上。

• Day 1 3.2

开场看T1就感觉不简单，直接奔着特殊性质去了。

差不多两个多小时写出特殊性质AC，测了测发现 $n=1$ 全过了？

然后T2写dfs，T3写阶乘的特殊性质。

期望得分 $60+12+8=80$

（对了两块巧克力吃了仨小时）

然后中午在塔斯汀吃饭等了一个小时，下午又去颓了一下午三国杀，跟zibenlun一块上了上分。

晚上五点多被lxn抓住在颓，回屋去看了会大纲和板子。

六点左右一帮人去我屋叫我出去吃饭，我说点外卖就行，他们非要出去，结果出去转了近一个小时一无所获，最后在酒店楼下吃了个肉夹馍，还去买了崔神最爱的蜜雪冰城。

然后回去，一块口胡了ABC后几个题，颓了一会三国杀和粥，跟同学在微信上聊了会就睡了。

• Day 2 3.3

（这回是三块巧克力吃了仨小时）

上来先读题，发现T3不可做，敲了T1复杂度超高的双重dfs暴力，估计过不了 $n=5$ 的极端情况，然后写了特殊性质A，码量一共近3k。

T2只会 $10$ 分特殊性质，写了写。

此时只有十二点......半睡半醒地过去了一个小时就结束了

期望得分 $15+10=25$

然后随便吃了个包子客就返程了，在火车站等了近一个小时。

回来以后发现在学校的大佬都在关注着民间数据评测，晚上发现云斗数据过了 $70+50=120$，感觉还行吧，可能是数据水。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-05 21:15:51

C.Inverse of Permutation

红题，略过不表。

D.Cutting Woods

赛时过了，但是用了离散化+树状数组写了近一个小时，然而set+二分非常简单，所以还得多练练set和multiset之类的stl，也尽量别把简单问题想复杂了。

E.Sorting Queries

赛时做了大约十分钟，使用一个队列和一个小根堆维护即可，不再赘述。

F.Make Pair

组合计数+区间dp，赛后我看题解用了另一种方法：

设 $f_{l,r,0}$ 为 $l$ 和 $r$ 匹配时区间 $l,r$ 的方案数；$f_{l,r,1}$ 为 $l$ 和 $r$ 不匹配，即该区间可分成多个区间时区间 $l,r$ 的方案数。

边界即为对于所有可匹配的 $i,i+1$ 有 $f_{i,i+1,0}=1$

显然若 $l,r$ 可匹配则 $f_{l,r,0}=f_{l+1,r-1,0}$，否则 $f_{l,r,0}=0$

而 $f_{l,r,1}$ 的计算需要枚举中断点 $k$，若按乘法原理，答案为 $(f_{l,k,0}+f_{l,k,1})\times (f_{k+1,r,0}+f_{k+1,r,1})$。

但由于这样枚举会出现重复，在这里强制其中一段区间不可拆分来去重，因此变为 $(f_{l,k,0}+f_{l,k,1})\times f_{k+1,r,0}$。

然后由于方案与顺序有关，则中断点两侧还可以改变顺序，因此上面的式子还要乘上 $\binom{\frac{k-l+1}{2}}{\frac{r-l+1}{2}}$，即在所有位置中选择若干个给左边部分的方案数。

最后还要注意由于成对选取，枚举区间和中断点时只需枚举偶数长度即可。

G.Groups

还是组合计数。

这题有三种做法，目前还不会二项式反演。

其中最简单的一种如下：

设 $f_{i,j}$ 为把前 $i$ 个数放到恰好 $j$ 个组中的方案数，则放第 $i$ 个数时可以新开一组，也可以放到已有的组内。显然已放的与 $i$ 模 $m$ 同余的数个数为 $\lfloor \frac{i-1}{m} \rfloor$，于是可放的组就会减少这么些，若没有可放组则这种可能为 $0$。

如上，$f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\times max(0,j-\lfloor \frac{i-1}{m} \rfloor)$

边界为 $f_{0,0}=1$

总之FG这种考察思维的组合计数题目还得多加练习才行。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-23 22:48:32

题意

给出一个只包含 $0$ 和 $1$ 的字符串，每个字符取反需要一定代价，要求最后使串中有且仅有一组相邻字符相同，求最小代价。

思路

考虑动态规划（或者说是递推）。

首先能想到的是设 $f_i$ 表示前 $i$ 个字符的答案。

然而我们发现难以从 $f_{i-1}$ 向 $f_{i}$ 转移，有以下两个问题需要解决：

• 转移时当前位是否要改变？这还与上一位的值有关。
• 相同的那组字符在哪？是这一位与上一位还是在这一位之前？

为了解决这两个问题，我们就要增加状态的维度，于是有了新的状态：设 $f_{i,j,k}$ 为前 $i$ 位中有 $j$ 组相同的相邻字符，且第 $i$ 位为 $k$ 的最小代价。显然这里的 $j,k$ 都只有 $0$ 和 $1$ 两种取值。

接下来考虑转移：$f_{i,0}$ 只能从 $f_{i-1,0}$ 转移来，分为修改和不修改两种。而 $f_{i,1}$ 可从 $f_{i-1,0}$ 且令第 $i$ 位与上一位相同，或 $f_{i-1,1}$ 且令第 $i$ 位与上一位不同转移来。

最后是边界：显然有 $f_{1,0,a_i}=0,f_{1,0,!a_i}=c_i,f_{1,1,0}=f_{1,1,1}=+\infty$

答案即为 $f_{n,1,0}$ 与 $f_{n,1,1}$ 的较小值。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=2e5+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
char s[N];
int n,a[N],c[N],f[N][2][2];\/\/状态如上述 
signed main()
{
	n=read();
	cin>>s;
	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0',c[i]=read(); 
	f[1][0][a[1]]=0,f[1][0][!a[1]]=c[1];
	f[1][1][a[1]]=f[1][1][!a[1]]=1e18;\/\/初值 
	for(int i=2;i<=n;i++)
	{
		f[i][0][a[i]]=f[i-1][0][!a[i]];
		f[i][1][a[i]]=min(f[i-1][1][!a[i]],f[i-1][0][a[i]]);\/\/不修改 
		f[i][0][!a[i]]=f[i-1][0][a[i]]+c[i];
		f[i][1][!a[i]]=min(f[i-1][1][a[i]],f[i-1][0][!a[i]])+c[i];\/\/修改 
	}
	cout<<min(f[n][1][0],f[n][1][1]);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-23 23:33:04

题意

有一个 $H$ 行 $W$ 列网格，初始均为颜色 $0$。$M$ 次操作，每次把一整行或一整列涂成一种颜色，求最后的颜色种数和每种颜色的格子数。

思路

暴力修改查找复杂度过高，无法通过本题。

我们发现每次操作都会覆盖之前的操作，所以考虑倒序处理，这样每次就能直接确定下若干格的颜色，之后不再考虑这些格。

那么若涂某一行，则以后再涂这行就不再产生影响，再涂列时都不会再涂这行的那一格。涂某一列造成的影响也一样。

如此处理，由于初始为颜色 $0$，最后把没涂过的格子涂成颜色 $0$ 即可。

具体看代码实现吧。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=2e5+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
struct nod
{
	int t,x,id;
}a[N];
bool hang[N],lie[N];\/\/标记某一行\/列是否整体被涂过 
int h,w,m,sum[N],aa[N],ab[N],cnt; 
signed main()
{
	h=read(),w=read(),m=read();
	int th=h,tw=w;\/\/剩余可涂的行\/列数 
	for(int i=1;i<=m;i++) a[i].t=read(),a[i].id=read(),a[i].x=read();
	for(int i=m;i>=1;i--)\/\/记录操作并倒序处理 
	{
		if(a[i].t==1)\/\/涂行 
		{
			if(hang[a[i].id]) continue;\/\/涂过就跳过
			hang[a[i].id]=1,sum[a[i].x]+=tw;\/\/标记并更新答案 
			th--;\/\/之后涂列时少涂一格 
		}
		else\/\/涂列同上 
		{
			if(lie[a[i].id]) continue;
			lie[a[i].id]=1,sum[a[i].x]+=th;
			tw--;
		}
	}
	sum[0]=h*w;
	for(int i=1;i<=2e5;i++) sum[0]-=sum[i];\/\/从总数中减掉非零的格子数 
	for(int i=0;i<=2e5;i++) if(sum[i]) 
		aa[++cnt]=i,ab[cnt]=sum[i];\/\/记录答案 
	cout<<cnt<<"\n";
	for(int i=1;i<=cnt;i++) cout<<aa[i]<<' '<<ab[i]<<"\n";
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-24 11:19:06

题意

给出整数 $N$ 和两个字符串 $S$ 和 $T$，将字符串 $S$ 整体复制 $N$ 次拼接起来得到母串，要求把 $T$ 中每个字符分别复制 $k$ 次再拼接起来得到的串为母串的子序列，求 $k$ 的最大值。

思路

显然，若 $k$ 合法，则 $k-1$ 只需在 $k$ 的取法上把原串中每个字符少取一个即可，因此具有单调性，可以二分答案。

现在需要写出check函数，考虑反过来做，对于一个 $k$ 值求出需要复制 $S$ 串的次数，再与 $N$ 比较来check。

这样问题就成了求把 $T$ 中每个字母按顺序分别取 $k$ 个所需的 $S$ 数量。为了求出这个数量，需要维护 $S$ 串中各字母出现的后缀次数以及各字母出现的位置，具体看下边的代码实现吧。

这里要注意二分的上界，设 $S$ 长度为 $ls$，$T$ 长度为 $lt$，若 $N$ 个 $S$ 串被尽可能利用，最多能使 $k$ 达到 $\lfloor \frac{n\times ls}{lt}\rfloor$，以此为二分上界能在不爆longlong的前提下通过。

代码

#include<iostream>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+10;
const int K=26+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,ls,lt;
char s[N],t[N];
int a[N][K];\/\/a_i 记录s串中第i位到末尾 各个字母出现次数
vector <int> pos[K];\/\/pos_i 记录s串中第i个字母出现的位置 
bool check(int x)
{
	if(x==0) return true;
	int cnt=0,lpos=ls;\/\/cnt表示构成g(T,x)需要的s串个数，lpos表示上一个s串用到了第(lpos-1)位 
	for(int i=0;i<lt;i++)\/\/构成每个字母 
	{
		int tc=t[i]-'a',ts=x;\/\/需要的字符及数量 
		if(ts<=a[lpos][tc]) \/\/如果上一个s串中剩余的tc足够
			lpos=pos[tc][a[0][tc]-a[lpos][tc]+ts-1]+1;\/\/只需修改使用到的位置 
		else
		{
			ts-=a[lpos][tc];\/\/先把上个串用完 
			cnt+=ts\/a[0][tc];\/\/再用完整的若干个串 
			ts%=a[0][tc];\/\/还需要多少个该字母 
			if(ts) 
			{
				cnt++;
				lpos=pos[tc][ts-1]+1;
			}\/\/如果还需要，就多用一个串并记录位置 
			else lpos=pos[tc][a[0][tc]-1]+1;\/\/否则记录s串中该字母最后一次出现的位置即可 
		} 
	}
	return cnt<=n;\/\/判断是否合法 
}
signed main()
{
	n=read();
	cin>>s>>t;
	ls=strlen(s),lt=strlen(t);
	for(int i=ls-1;i>=0;i--)
	{
		for(int j=0;j<26;j++) a[i][j]=a[i+1][j];
		a[i][s[i]-'a']++;
	}\/\/倒序处理后缀a数组 
	for(int i=0;i<lt;i++) if(!a[0][t[i]-'a'])
	{
		cout<<0;
		return 0;
	}\/\/这里特判：若t串中有s串没有的字符，则直接输出0
	\/\/如果不判的话，在check函数里会除以0寄掉 
	for(int i=0;i<ls;i++) pos[s[i]-'a'].push_back(i);\/\/正序记录各字母出现位置 
	int l=0,r=n*ls\/lt,ans;\/\/这里二分上界要注意 
	while(l<=r)
	{
		int mid=(l+r)\/2;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}\/\/二分答案 
	cout<<ans;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-25 08:20:35

题意

在一个环上有 $N$ 个人，每两人之间有一把勺子，所有人按照 $P$ 排列顺序操作。一人操作时若左右都有勺子，则拿自己惯用手那边的；若只有一边有勺子，则直接拿；若无勺子则不操作。

给定 $P$ 和某些人的惯用手，求能使所有人都拿到勺子的惯用手方案数。

思路

如果把这个环画出来，环上就是一个人一个勺子交叉，如此重复 $N$ 组。

模拟一下就会发现，若某两人选择勺子的方向不同，则他们之间剩下的勺子数与人数之和为奇数，这样一定不合法。

所以我们得到，合法的取法只有两种，即所有人都取自己左手边的勺子，或所有人都取自己右手边的勺子。

那么只需要模拟取两次，每次都直接钦定每个人所拿的勺子，再按 $P$ 的顺序依次处理。

处理时，若不拿的另一把勺子还在，就必须确定惯用手以拿到指定的那把，此时若与 $S$ 中给出的信息冲突则无解；若另一把已经不在了，那么惯用手任意，此时若给出信息为问号则方案数乘 $2$。

此处不需要考虑自己要拿的勺子是否已被取走，因为每个人都只会取自己对应的那把勺子，不会出现拿别人勺子的情况。

最后把两种取法对应的方案数相加即可。

代码

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=2e5+10;
const int mod=998244353;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,sa=1,sb=1,p[N]; 
char s[N];
bool v[N];\/\/勺子是否被取走 
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) p[i]=read();
	cin>>s;
	for(int i=1;i<=n;i++)\/\/所有人都取左手边的 
	{
		if(v[(p[i]%n)+1]) \/\/若另一把已被取走，则惯用手任意 
		{
			if(s[p[i]-1]=='?') sa=(sa*2)%mod;\/\/若是问号则乘2 
		}
		else if(s[p[i]-1]=='R') \/\/另一把未被取走，则需确定惯用手 
		{
			sa=0;
			break;
		}\/\/此时若与给定信息冲突则无解 
		v[p[i]]=1;\/\/标记已取走 
	}
	memset(v,0,sizeof(v));
	for(int i=1;i<=n;i++)\/\/都取右手边的，同上 
	{
		if(v[p[i]]) 
		{
			if(s[p[i]-1]=='?') sb=(sb*2)%mod;
		} 
		else if(s[p[i]-1]=='L')
		{
			sb=0;
			break;
		}
		v[(p[i]%n)+1]=1;
	}
	cout<<(sa+sb)%mod;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-25 08:42:00

题意

给出一个括号序列，有两种操作方式，交换两个字符需要 $A$ 的代价，直接修改一个字符需要 $B$ 的代价，求使这个序列合法需要的最小代价。

思路

这题看上去好像是dp，但是复杂度显然不太对。

我们发现，交换相当于两次修改；而若把一个左括号改成右括号，再把一个右括号改成左括号，就相当于把这两个字符交换。

这样就可以先无脑修改，记录下修改为左括号和右括号的次数，最后再处理一下可以转换成交换操作的数量即可。

因此从左到右操作，若碰到左括号则压入栈中；碰到右括号时，若栈中有左括号则弹出一个与之匹配，若没有则只能修改成左括号并压入栈中，同时记录一下修改为左括号的次数。

最后若栈中还剩 $k$ 个左括号，显然此时 $k$ 一定为偶数。那么需要把其中 $\frac{k}{2}$ 个改成右括号以令其匹配，那么 $\frac{k}{2}$ 就是修改为右括号的次数。

此处由于只有左括号会被压入栈中，所以不需要开栈存储，只需要记录一下栈中的左括号数量即可。

最后可以把两种修改各一次转换为交换，贪心求出答案即可。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=1e6+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,a,b,sl,sr,sn;\/\/sl sr为修改为左\/右括号的次数，sn为栈中的左括号数量 
char s[N];
signed main()
{
	n=read(),a=read(),b=read();
	cin>>s;
	for(int i=0;i<2*n;i++)
	{
		if(s[i]==')')
		{
			if(sn) sn--;
			else sl++,sn++;
		}
		else sn++;
	}\/\/如上述，记录修改为左括号次数 
	if(sn) sr=sn\/2;\/\/计算修改为右括号次数 
	if(sl<sr) swap(sl,sr);\/\/使sl为较大值 
	if(b*2<=a) cout<<(sl+sr)*b;\/\/若两次修改代价小于交换，则全用修改 
	else cout<<sr*a+(sl-sr)*b;\/\/否则把能转换的修改全部转换 
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 11:16:22

题意

初始有一个长度为 $N$，元素均为 $0$ 的数组 $A$ 和一个空集合 $S$。进行 $Q$ 次操作，每次给出一个数 $x$，若其不在 $S$ 中则加入 $S$，否则将其从 $S$ 中删除。之后给 $A$ 中下标在 $S$ 中的元素各加上 $\left|S\right|$，$\left|S\right|$ 为 $S$ 中的元素个数。求最终的 $A$ 数组。

思路

如果暴力修改，复杂度为 $O(N^2)$，无法通过本题。

因此考虑分别处理 $A$ 的每一位。对于每一个下标，都会在其第 $(2k-1)$ 次和第 $2k$ 次被操作之间被加上数，那么就可以把最终答案变为若干个区间的和。

那么记录下所有操作时的 $\left|S\right|$ 并求前缀和，对于 $A$ 中每一位分别操作即可。

这样时间复杂度优化至 $O(N)$，可以通过本题。

代码

#include<iostream>
#include<vector>
#define int long long
const int N=2e5+10;
using namespace std;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int n,Q,cnt,s[N];\/\/cnt为目前S中元素个数，s为前缀和数组 
bool f[N];\/\/每个下标是否在S中 
vector <int> pos[N];\/\/每个下标出现的位置 
signed main()
{
	n=read(),Q=read();
	for(int i=1;i<=Q;i++)
	{
		int t=read();
		if(!f[t]) cnt++,f[t]=1;
		else cnt--,f[t]=0;
		s[i]=s[i-1]+cnt;
		pos[t].push_back(i); 
	} 
	for(int i=1;i<=n;i++)
	{
		int t=0;\/\/分别处理每一位 
		if(pos[i].size()%2) pos[i].push_back(Q+1);\/\/如果出现奇数次，则操作结束时其还在序列中，需要特判 
		for(int j=0;j<pos[i].size();j+=2)
		{
			int l=pos[i][j],r=pos[i][j+1]-1;
			t+=s[r]-s[l-1];
		}\/\/每两次之间都能取得贡献 
		cout<<t<<' ';
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-14 10:26:02

题意

有一个三行三列的网格，每格上有一个数，两人在上面玩井字棋，选到连续三个格子即获胜。若出现平局，则所选格子上的数字和较大者获胜，问谁有必胜策略。

思路

是一道博弈论题，但数据规模很小，一共只有 $9$ 个格子，可以dfs乱搞。

直接暴力dfs搜索两人的选择，分别标记为两人的序号，随时检查是否分出胜负即可。

要注意的是，只要在当前局面下有一种操作能使对方必败，则自己如此操作就必胜；若所有操作方式最终都让对方有必胜策略，则自己必败。

具体请看代码实现。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=3+10;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int a[N][N],v[N][N];\/\/输入的数和每个格子被选的情况 
bool dfs(int st,int x,int y)\/\/已选了st个格子，初始先手的和为x，初始后手的和为y，此时操作是否有必胜策略 
{
	int now=st%2+1,la=(st+1)%2+1;\/\/1为初始先手，2为初始后手；now为现在即将操作的人，la为上一个操作者 
	if(v[1][1]==la&&v[1][2]==la&&v[1][3]==la) return 0;
	if(v[2][1]==la&&v[2][2]==la&&v[2][3]==la) return 0;
	if(v[3][1]==la&&v[3][2]==la&&v[3][3]==la) return 0;
	if(v[1][1]==la&&v[2][2]==la&&v[3][3]==la) return 0;
	if(v[1][3]==la&&v[2][2]==la&&v[3][1]==la) return 0;
	if(v[1][1]==la&&v[2][1]==la&&v[3][1]==la) return 0;
	if(v[1][2]==la&&v[2][2]==la&&v[3][2]==la) return 0;
	if(v[1][3]==la&&v[2][3]==la&&v[3][3]==la) return 0;\/\/判断上一个操作者是否连成三个 
	if(st==9)\/\/若全部选完，则根据大小判断胜负 
	{
		if(x>y) return 0;
		else return 1;\/\/要注意此处st=9，即初始后手即将操作，所以y较大时是必胜 
	}
	for(int i=1;i<=3;i++) for(int j=1;j<=3;j++)
	{
		if(v[i][j]) continue;
		v[i][j]=now;
		bool tf;
		if(now==1) tf=dfs(st+1,x+a[i][j],y);
		else tf=dfs(st+1,x,y+a[i][j]);\/\/分初始先后手判断 
		v[i][j]=0;\/\/注意回溯 
		if(!tf) return true;\/\/对方必败则如此操作可必胜 
	}
	return false;
}
signed main()
{
	for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) a[i][j]=read();
	if(dfs(0,0,0)) cout<<"Takahashi"; 
	else cout<<"Aoki";
	return 0;
}