Preface

先补一下这场ARC的博客，因为在来回合肥的路上一直在想这场的CD，所以有空后就先把这场补了

A - <Inversion>

不难发现对于一段连续的<，设其长度为\(x\)，则它最少要贡献\(\frac{x(x+1)}{2}\)的答案

而我们很容易构造一种方案刚好满足这个下界，只要让每段的结束比下一段的开头大很多即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=250005;
int n; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; scanf("%d%s",&n,s+1); LL ans=0; int lst=-1;
	for (i=1;i<n;++i) if (s[i]=='<')
	{
		if (!~lst) continue; ans+=1LL*(i-lst)*(i-lst+1)/2LL; lst=-1;
	} else if (!~lst) lst=i;
	if (~lst) ans+=1LL*(n-lst)*(n-lst+1)/2LL;
	return printf("%lld",ans),0;
}

B - Arbitrary Nim

首先若\(\oplus_{i=1}^n a_i\ne 0\)则答案显然为\(-1\)，否则考虑用SG函数来推一推

手玩很容易发现\(SG(x)=x\bmod (k+1)\)，考虑要让最后的SG函数发生变化，则显然就是要找一个最大的且出现次数为奇数的数\(y\)，那么答案就是\(y-1\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=250005;
int n,x,sum; map <int,int> c;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; int ret=0; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&x),++c[x],sum^=x;
	if (sum) return puts("-1"),0;
	for (auto it=c.rbegin();it!=c.rend();++it)
	if (it->se%2==1) { ret=it->fi-1; break; }
	return printf("%d",ret),0;
}

C - Swap Characters

我是大傻逼，这题祁神提示了我114514次才会做，菜的离谱

直接考虑能变化到的字符串有点难以下手，不妨先考虑以下问题：

给定\(S\)与\(T\)，求从\(S\)最少要进行多少次操作才能得到\(T\)

手玩一下会发现对于一对AB和BA的位置，我们肯定是直接交换最优，对于其它两种情况也是同理

否则如果有解最后剩下的一定是相同个数的AB,BC,CA这种循环变化的，我们可以用两次操作把每一对数减少\(1\)

知道了这个后我们就可以考虑直接枚举最后每种变化的个数，然后直接可重全排列算方案数即可

注意到自由量只有四个，即循环变化的次数、AB与BA的个数、BC与CB的个数、AC与CA的个数

复杂度\(O(n+k^4)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=250005,mod=998244353;
int n,m,fact[N],ifac[N],c[3],ans; char s[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int calc(CI x,CI y,CI z)
{
	if (x<y+z) return 0;
	return 1LL*fact[x]*ifac[y]%mod*ifac[z]%mod*ifac[x-y-z]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k,l; for (scanf("%d%d%s",&n,&m,s+1),init(n),i=1;i<=n;++i) ++c[s[i]-'A'];
	for (l=0;l*2<=m;++l) for (i=0;i+l*2<=m;++i) for (j=0;j+i+l*2<=m;++j) for (k=0;k+j+i+l*2<=m;++k)
	(ans+=(l?2LL:1LL)*calc(c[0],l+i,j)*calc(c[1],l+k,i)%mod*calc(c[2],l+j,k)%mod)%=mod;
	return printf("%d",ans),0;
}

D - Maximize Update

这个题也很劲啊，想了半天只会一个\(O(n^4)\)的暴力区间DP，后面看了题解才发现连第一步的关键转化都没想到

首先我们考虑对于某种涂色方案，构造如下的一个序列\(\{a_1,a_2\cdots,a_k\}\)来代表它

其中\(k\)即为涂色的次数，而\(a_i\)则表示在第\(i\)次涂色中变黑的方格的编号（有多个就任取一个）

那么现在问题转化为求一个合法的且长度最长的格子序列，考虑对于某个序列我们要怎样验证其是否合法

正着做不好考虑，我们可以倒过来想，假设初始时所有操作都被进行了，\(i\)从\(k\)到\(1\)：

检验\(a_i\)是否是黑色的，若为白色则不合法
将所有包含\(a_i\)的区间\([L_j,R_j]\)的影响撤销

考虑这么做的好处，当我们选择了某个点\(a_i\)后，由于所有经过它的区间都不能再考虑了，因此问题会被划分成\([1,a_i-1],[a_i+1,n]\)两个子问题

因此可以考虑区间DP，设\(f_{l,r}\)表示仅考虑在区间\([l,r]\)的修改时序列的最长长度，转移方程很简单但需要快速确定某个位置\(m\)是否可以被选出

这个问题等价于询问仅考虑包含在\([l,r]\)中的所有修改区间，是否存在至少一个区间覆盖了\(m\)

我们可以统计出\(c_{l,r}\)表示包含在\([l,r]\)中的区间个数，这样只用看\(c_{l,m-1}+c_{m+1,r}\)是否等于\(c_{l,r}\)即可

总复杂度\(O(n^3)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=505;
int n,m,x,y,f[N][N],g[N][N];
inline int DP(CI l,CI r)
{
	if (l>r) return 0; if (~f[l][r]) return f[l][r];
	int ret=0; for (RI i=l;i<=r;++i)
	if (g[l][i-1]+g[i+1][r]!=g[l][r])
	ret=max(ret,DP(l,i-1)+DP(i+1,r)+1);
	return f[l][r]=ret;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d",&x,&y),g[x][y]=1;
	for (i=1;i<=n;++i) for (j=i;j<=n;++j) g[i][j]+=g[i][j-1];
	for (j=1;j<=n;++j) for (i=j;i>=1;--i) g[i][j]+=g[i+1][j];
	//for (i=1;i<=n;++i) for (j=i;j<=n;++j) printf("g[%d][%d] = %d\n",i,j,g[i][j]);
	return memset(f,-1,sizeof(f)),printf("%d",DP(1,n)),0;
}