Preface

打的跟shi一样竟然还能上分的说，C一开始写的跟shi一样WA了好几发

然后D看一眼没思路就只能去肝E了，结果写了半天还是TLE第14个点，直接心态爆炸

A. Make it Beautiful

很容易想到把最大的数\(a_n\)放在最前面，然后找一个和它不同的数\(a_i(1\le i<n)\)放在第二个位置

由于\(a_i\ge 1\)，因此\([2,n]\)的前缀和显然是大于\(a_n\)的，满足题意

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
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; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		if (a[1]==a[n]) puts("NO"); else
		{
			puts("YES"); printf("%d ",a[n]); 
			int pos=-1; for (i=n-1;i>=1&&!~pos;--i) if (a[i]!=a[n]) printf("%d ",a[i]),pos=i;
			for (i=1;i<n;++i) if (i!=pos) printf("%d ",a[i]); putchar('\n');
		}
	}
	return 0;
}

B. Matrix of Differences

简单构造题，尝试一种构造方案使得所有\([1,n^2-1]\)的差值都出现过，这样显然是最大的

我们考虑旋转着来填，每次填的顺序按照\(1,n^2,2,n^2-1,\cdots\)这样来

举个例子，比如当\(n=4\)时，有：

1 11 6 12
16 7 9 5
2 10 8 13
15 3 14 4

就是填数的时候处理起来有点小繁琐，需要注意下

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=55,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int t,n,a[N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j,k=0,p=1,num=1; int tot=1; scanf("%d",&n);
		for (i=1;i<=n;++i) for (j=1;j<=n;++j) a[i][j]=0;
		for (a[1][1]=1,p^=1,i=j=1;tot<n*n;)
		{
			int nx=i+dx[k],ny=j+dy[k];
			if (nx<=0||nx>n||ny<=0||ny>n||a[nx][ny]) { k=(k+1)%4; continue; }
			++tot; i=nx; j=ny;
			if (p) a[i][j]=num; else a[i][j]=n*n-num+1,++num; p^=1;
		}
		for (i=1;i<=n;putchar('\n'),++i) for (j=1;j<=n;++j) printf("%d ",a[i][j]);
	}
	return 0;
}

C. Yet Another Tournament

经典套路题，答案具有二分性，那么就考虑验证如何是否存在某种方案使得前面有\(k\)个人存在

但是考虑到要排在这个位置有两种情况，即是否战胜第\(n-k\)个人：

• 若战胜了第\(n-k\)个人，需要先付出\(b_{n-k}\)的代价，然后再需要战胜其他的\(n-k-1\)个人即可
• 若不战胜第\(n-k\)个人，则需要战胜其他的\(n-k\)个人即可

直接先把所有的人战力排序后再做即可，复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
struct element
{
	int val,pos;
	friend inline bool operator < (const element& A,const element& B)
	{
		return A.val<B.val;
	}
}a[N]; int t,n,b[N]; long long m;
inline bool check(CI rk)
{
	RI i; long long tot=b[n-rk]; int ct=1,tar=n-rk-1;
	for (i=1;i<=n&&ct<tar;++i) if (a[i].pos!=n-rk) tot+=a[i].val,++ct;
	if (tot<=m) return 1;
	for (tot=ct=0,tar=n-rk,i=1;i<=n&&ct<tar;++i) tot+=a[i].val,++ct;
	return tot<=m;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%lld",&n,&m),i=1;i<=n;++i)
		scanf("%d",&b[i]),a[i].val=b[i],a[i].pos=i;
		sort(a+1,a+n+1); int l=0,r=n,mid,ret;
		while (l<=r) if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
		printf("%d\n",ret+1);
	}
	return 0;
}