Preface

究极坐牢场，比赛降智导致签到签挂，本来秒出的D写错一个极其傻逼的地方浪费半小时

然后后面两个小时坐牢想E和F1，但可惜并没有看出E的性质，被狠狠地薄纱

虽然说实话后面有点困了，但应该不至于写不出这个E的，只能说最近的状态真是堪忧啊

A. Subtraction Game

首先若\(a\ne 1\)则直接输出\(1\)即可，否则若\(b>2\)则直接输出\(2\)，否则就是\(a=1,b=2\)的情况，输出\(3\)即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int t,a,b;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&a,&b);
		if (a!=1) puts("1"); else
		if (b!=2) puts("2"); else puts("3");
	}
	return 0;
}

B. Permutations & Primes

首先不难发现所有不含\(1\)的区间的\(\operatorname{mex}\)都是\(1\)，不是质数，因此要想办法让不含\(1\)的区间个数最少，显然就是把\(1\)放在区间中间

然后考虑由于\(2,3\)都是质数，很容易想到如果把\(2,3\)分别放在两段，此时除了整个区间外所有跨过\(1\)的区间的\(\operatorname{mex}\)都是\(2/3\)，显然是最优的

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d",&n); int pos=n/2+1,num=1; a[pos]=1;
		for (i=1,j=n;i<pos||j>pos;)
		{
			if (i<pos) a[i]=++num,++i;
			if (j>pos) a[j]=++num,--j;
		}
		for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
	}
	return 0;
}

C. Particles

首先不难发现我们按照位置的奇偶性给球分类，则最后留下的那个球要么是只有奇数位置的要么是只有偶数位置的

然后手玩一下比如在所有的奇数位置中，我们可以任意选择其中的位置留下来，那么就直接贪心地让所有\(>0\)的数留下即可

但是要注意特判都是负数的情况，这种时候就选一个最大的即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,x; vector <int> s[2];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),s[0].clear(),s[1].clear(),i=1;i<=n;++i)
		scanf("%d",&x),s[i&1].push_back(x);
		for (i=0;i<2;++i) sort(s[i].begin(),s[i].end());
		long long ans=-1e18; for (i=0;i<2;++i) if (s[i].size())
		{
			if (s[i].back()<=0) ans=max(ans,1LL*s[i].back()); else
			{
				long long ret=0;
				for (int x:s[i]) if (x>0) ret+=x; ans=max(ans,ret);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

D. Row Major

其实是个丁真题，但刚开始脑抽了写挂了还没看出来

首先很容易想到从质数入手，如果一个数是质数那么只要用ab两种字符循环着放即可

否则考虑诸如\(n=4\)的情况，此时就是abc循环放，而\(n=6\)时就是````abcd```循环放

因此很容易猜测到，答案就是求一个最小的\(k\)，使得\(k\nmid n\)，然后用这\(k\)种字符的循环来构造即可

证明的话也很简单，考虑枚举\(n\)的所有约数\(d\)，则\(s_1\)和\(s_{1+d}\)之间相当于有边，而规定一条边上两个点的字符不同

不难发现设\(n\)的一段极长的约数段\(1,2,\cdots,k\)，则\(1\sim k+1\)这些点构成了一个完全图，因此上面说的那个一定是答案的下界

而这个答案为什么一定是对的也很显然，因为这个\(k\)一定不整除所有的\(n\)的约数，因此总是合法的

注意特判\(n=1\)的情况

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000005;
int t,n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; if (scanf("%d",&n),n==1) { puts("a"); continue; }
		if (n==2) { puts("ab"); continue; }
		for (i=2;;++i)
		if (n%i)
		{
			for (j=1;j<=n;++j) putchar((j-1)%i+'a');
			putchar('\n'); break;
		}
	}
	return 0;
}

E. Great Grids

战俘题，尤其是刚开始少看了一个限制，没看到相邻两个格子的数不同导致一直看不懂样例，还剩最后一个小时的时候才发现

考虑每个\(2\times 2\)的格子其实只有两种类型，分别对应两种对角线相同的情况，但由于具体填的数不同导致我们没办法把不同的情况统一起来

但其实我们并不关心每个位置具体填的是哪个数，这就提醒我们通过差值来判断

不妨设每个矩阵的左上角的格子那里有两个箭头，分别指向它右侧的格子和下侧的格子，箭头的值即为两个格子上的数的差（对\(3\)取模）

此时我观察一下合法的图形，此时会发现每一行每一列的箭头的值一定是相等的（因为一旦出线不相等的情况就会引出一个冲突，这个画下图很好理解）

因此每一行、每一列的取法是一起的，然后我们再回过头来看题目给出的限制，其实就是规定了某一行和某一列的取值是相同或者不同

因此题目变成一个判定是否有合法染色的问题，直接DFS搜一遍即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=4005;
int t,n,m,k,a,b,c,d,col[N]; vector <pi> v[N]; bool flag;
inline void addedge(CI x,CI y,CI z)
{
	v[x].push_back(pi(y,z)); v[y].push_back(pi(x,z));
}
inline void DFS(CI now,CI c=0)
{
	col[now]=c; for (auto [to,w]:v[now])
	{
		if (~col[to]&&col[to]!=(c^w)) flag=0;
		else if (!~col[to]) DFS(to,c^w);
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=n+m;++i) v[i].clear(),col[i]=-1;
		for (i=1;i<=k;++i) scanf("%d%d%d%d",&a,&b,&c,&d),addedge(a,n+min(b,d),a+b!=c+d);
		for (flag=1,i=1;i<=n+m;++i) if (!~col[i]) DFS(i); puts(flag?"YES":"NO");
	}
}

F1. Min Cost Permutation (Easy Version)

首先不难发现当\(c\ge 0\)是把原序列升序排序，若\(c<0\)时则降序排序，不难发现这样一定可以得到最小的值

但是由于还有个字典序最小的要求，当\(c\ge 0\)时是显然最优的，直接输出即可，而\(c<0\)时就要考虑可能可以通过把较小的数放在前面而使得答案不变

这类字典序最小的问题一般考虑贪心地从前往后放，每次从字典序较小的开始枚举放字符，如果可以使得答案不变就直接确定

具体到这道题上其实也是类似的，而至于如何让答案最小只要让后面没选的数依然降序排序即可

复杂度\(O(n^2)\)，F2的做法感觉是拿什么东西优化一下，但一时半会也想不到的说

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=5005;
int t,n,c,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&c),i=1;i<=n;++i) scanf("%d",&a[i]);
		if (c>=0)
		{
			for (sort(a+1,a+n+1),i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
			continue;
		}
		vector <int> left; for (i=1;i<=n;++i) left.push_back(a[i]);
		sort(left.begin(),left.end(),greater<int>());
		for (i=1;i<=n;++i)
		{
			int pos=0; for (j=left.size()-1;j>=1;--j)
			{
				long long dlt=abs(left[0]-left[j]-c)-abs(left[j]-left[j-1]-c);
				if (i!=1) dlt+=abs(left[j]-a[i-1]-c)-abs(left[0]-a[i-1]-c);
				if (j!=left.size()-1) dlt+=abs(left[j+1]-left[j-1]-c)-abs(left[j+1]-left[j]-c);
				if (!dlt) { pos=j; break; }
			}
			a[i]=left[pos]; left.erase(left.begin()+pos);
		}
		for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
	}
	return 0;
}