Preface

上周末因为上课而且这天下午还有CF要打，所以就没现场打这场ARC了

这两天事情也特别多导致写题的时间很少，摸了好久总算是补了四个题

A - Replace C or Swap AB

感觉是我做法复杂了，怎么A题码量好大

首先我们找到所有\(Y\)中为\(C\)的位置，显然对应的\(X\)中的位置也必须为\(C\)，然后我们把\(C\)看作分隔符把序列划分成若干段，其中每段的\(Y\)串不含\(C\)

仅考虑第三个操作，其实就是一个把\(X\)串中的\(B\)前移的过程，因此假设\(X\)串中没有\(C\)，我们只要比较一下每个\(B\)出现位置的先后即可

考虑\(X\)串有\(C\)的话我们肯定是贪心地把后面的先变成\(B\)，直到两个部分\(B\)的个数相同即可

#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=200005;
int t,n; char A[N],B[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%s%s",&n,A+1,B+1); vector <int> posC;
		for (posC.push_back(0),i=1;i<=n;++i) if (B[i]=='C') posC.push_back(i);
		posC.push_back(n+1); bool flag=1;
		for (i=1;i<=n;++i) if (B[i]=='C'&&A[i]!='C') flag=0;
		auto solve=[&](CI l,CI r)
		{
			if (l>r) return true; int A_A=0,A_B=0,B_A=0,B_B=0;
			RI i; for (i=l;i<=r;++i)
			{
				if (A[i]=='A') ++A_A; else if (A[i]=='B') ++A_B;
				if (B[i]=='A') ++B_A; else if (B[i]=='B') ++B_B;
			}
			if (A_A>B_A||A_B>B_B) return false;
			for (i=l;i<=r;++i) if (A[i]=='C'&&A_A<B_A) A[i]='A',++A_A;
			for (i=r;i>=l;--i) if (A[i]=='C'&&A_B<B_B) A[i]='B',++A_B;
			static int posA[N],posB[N]; int cntA=0,cntB=0;
			for (i=l;i<=r;++i) if (A[i]=='B') posA[++cntA]=i;
			for (i=l;i<=r;++i) if (B[i]=='B') posB[++cntB]=i;
			for (i=1;i<=cntA;++i) if (posA[i]<posB[i]) return false;
			return true;
		};
		for (i=0;i<posC.size()-1&&flag;++i) flag&=solve(posC[i]+1,posC[i+1]-1);
		puts(flag?"Yes":"No");
	}
	return 0;
}

B - Make Multiples

感觉比A题简单，只要考虑清楚所有情况即可

由于可能会出现某些数变成其中\(2/3\)个数的倍数的情况，因此我们定义函数solve(...)，参数个数\(m\)表示最后要选出来的位置数

则只要遍历solve(a,b,c),solve(LCM(a,b),c),solve(LCM(a,c),b),solve(LCM(b,c),a),solve(LCM(a,b,c))这些情形即可

我们枚举要变成哪个数的倍数，显然有意义的只有操作次数最小的\(m\)个数，把这些数找出来然后爆搜一下即可

#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 int unsigned long long
#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=200005;
int n,A,B,C,a[N],vis[N],ans=2e18; vector <pi> w[5];
inline int LCM(CI x,CI y)
{
	return x/__gcd(x,y)*y;
}
inline void DFS(CI m,CI now=0,CI sum=0)
{
	if (now>=m) return (void)(ans=min(ans,sum));
	for (RI i=0;i<min(n,m);++i) if (!vis[w[now][i].se])
	vis[w[now][i].se]=1,DFS(m,now+1,sum+w[now][i].fi),vis[w[now][i].se]=0;
}
inline void solve(VI d)
{
	RI i,j; int m=d.size();
	for (i=0;i<m;++i)
	{
		for (w[i].clear(),j=1;j<=n;++j) w[i].push_back(pi((a[j]+d[i]-1)/d[i]*d[i]-a[j],j));
		nth_element(w[i].begin(),w[i].begin()+min(n,m)-1,w[i].end());
		w[i].erase(w[i].begin()+min(n,m)-1,w[i].end());
	}
	DFS(m);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%llu%llu%llu%llu",&n,&A,&B,&C),i=1;i<=n;++i) scanf("%llu",&a[i]);
	solve(VI{LCM(LCM(A,B),C)}); solve(VI{A,B,C});
	solve(VI{LCM(A,B),C}); solve(VI{LCM(A,C),B}); solve(VI{LCM(B,C),A}); 
	return printf("%llu",ans),0;
}

C - LU / RD Marking

好久没有遇到有思路的计数题了，这题恰好比较合胃口，上数电的时候随便画画就画出来了

考虑把图中的每个方格斜着切开变成两个三角形，涂黑左上方的三角形就等价于操作一，涂黑右下方的三角形就等价于操作二

不难发现不合法的情形就是存在两个相邻的直角三角形，它们有公共的直角边，而拥有公共斜边的三角形依然是合法的

我们发现沿着图示蓝色方向把矩形分开，则不合法的图形只会在每一部分内部产生

那么很容易发现合法的方案数只和每一部分的三角形个数有关了，不妨设\(f_i\)表示\(i\)个三角形对应的方案数

转移的话就是讨论新加的位置放或不放，写出来就是\(f_i=f_{i-1}+f_{i-2}\)，其实就是个斐波那契数列，不过要注意下边界

最后答案的构成稍微手玩下其实就是（令\(n\le m\)）：

\[(f_1f_3f_5\cdots f_{2n-1})^2\times (f_{2n})^{m-n} \]

预处理\(f_i\)以及其所有奇数项的前缀积即可快速求解

#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=2e6+5,mod=998244353;
int t,n,m,fib[N],prod[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 (fib[1]=2,fib[2]=3,i=3;i<=n;++i) fib[i]=(fib[i-1]+fib[i-2])%mod;
	for (prod[1]=fib[1],i=3;i<=n;i+=2) prod[i]=1LL*prod[i-2]*fib[i]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(2e6);t;--t)
	{
		scanf("%d%d",&n,&m); if (n>m) swap(n,m);
		printf("%d\n",1LL*prod[2*n-1]*prod[2*n-1]%mod*quick_pow(fib[2*n],m-n)%mod);
	}
	return 0;
}

D - Interval Counts

很有意思的一个题，但被二分的固化思维卡的太死了，导致没做出来，后面看了题解恍然大悟我是个傻逼

首先很容易观察到的一点是，如果我们要覆盖区间\(x_l\sim x_r\)，那么最优的放法就是\([x_{l-1}+1,x_{r+1}-1]\)

考虑直接贪心构造答案，不妨使用增量法，假设我们已经构造了一些区间满足了\(x_1,x_2,\cdots,x_{i-1}\)的限制

而使用的区间有些是两个端点都固定的，有些则是右端点未固定的，现在考虑加入\(x_i\)后带来的新情况：

\(y_{i-1}=y_i\)，此时直接把之前右端点未定的区间都向右延长即可，对答案没有影响
\(y_{i-1}<y_i\)，需要新加入\(y_i-y_{i-1}\)个区间，它们的左端点为\(x_{i-1}+1\)，右端点不定
\(y_{i-1}>y_i\)，需要将\(y_{i-1}-y_i\)个之前的右端点未固定的区间的右端点固定为\(x_i-1\)，为了使最小值最大我们优先选择左端点较小的区间

维护的话我们可以用二元组\((a,b)\)来存储区间的左端点以及其个数，不难发现在操作的过程中\(a\)是单调的，因此可以直接用一个队列来维护所有右端点不定的区间

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

#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=200005,INF=1e9;
int n,x[N],y[N],ans=INF;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&x[i]);
	for (i=1;i<=n;++i) scanf("%d",&y[i]); x[0]=-INF;
	queue <pi> q; for (i=1;i<=n;++i)
	{
		if (y[i]==y[i-1]) continue;
		if (y[i]>y[i-1]) q.push(pi(x[i-1]+1,y[i]-y[i-1])); else
		{
			int left=y[i-1]-y[i];
			while (!q.empty()&&left)
			{
				int dlt=min(q.front().se,left);
				q.front().se-=dlt; left-=dlt;
				ans=min(ans,x[i]-1-q.front().fi);
				if (!q.front().se) q.pop();
			}
		}
	}
	return printf("%d",ans!=INF?ans:-1),0;
}