Prutekoi's blog

这道提交答案题只给出了一个spj，题面说要求构造输入数据使得输出尽量小。

于是考察了选手读代码和构造的能力。
第1、2、3、5、8个点都没有什么有趣的地方，就不说了。（惊现斐波那契）

4.

这个点要求构造一个长度为 $n=2222$ 的排列，初始 $ans=0$，执行 for i in range(n):ans=abs(ans-p[i])的操作，最小化 $-ans$。
我当时的做法是考虑最后一个数一定是 $n$，那么让前面的数结果为 $1$。倒数第二个数不可能是 $n-1$，因为前 $n-2$ 个数不可能得到 $n-2$。照这么分析下去发现最后五个数可以填 $n-2,n-4,n-1,n-3,n$，且要求前面的结果为 $1$。这样发现可以 $4$ 个一循环。然后最后剩一个 $1$。
而题解更加直白：发现 $x,x-1,x-2,x-3$ 可以得到 $0$，于是直接从 $2221$ 到 $1$，最后一个 $2222$ 即可。发现这样的构造不管 $n$ 是多少都可以取到最大值。

6.

这个点我认为非常难。题目要求构造一张二分图，有一个阈值 $p=17$，要满足左部点的度不超过 $p+1$，右部点的度不超过 $p$，从左部点任意选出两个点连向的集合都有交。最大化左部点的个数。

我们来满打满算地算一下上界。
左部点每个点的边数当然要尽可能多。而我们设右部点每个点的度为 $d$，则每个点最多满足 $\frac{d(d-1)}{2}$ 对左部点的约束。设左部点有 $n$ 个点，则最多有 $n(p+1)$ 条边，于是有 $\frac{n(p+1)}{d}$ 个右部点，总共最多可以满足 $\frac{n(p+1)}{d}\cdot \frac{d(d-1)}{2}$ 对左部点。于是发现右部点的度数也是越大越好，取 $p$。于是得到 $\frac{n(p+1)(p-1)}{2}\geq \frac{n(n-1)}{2}$。$n\leq p^2$。

现在我们知道，答案上界为 $p^2$。考虑构造这样的解。于是得到右部点有 $p(p+1)$ 个，图中每个点的度数都达到了上界。接下来我们考虑每个右部点要连那些左部点。现在这个问题也可以转化成用 $p(p+1)$ 个大小为 $p$ 的团来覆盖一个 大小为 $p^2$ 的完全图，使得每条边都被覆盖到。不过这个转化没鸟用，仍然很困难。

发挥人类智慧，根据直觉我们让前 $p$ 个右部点先把 $p^2$ 个左部点都覆盖到。这时左部点分为 $p$ 组。接下来每次是每组选一个。然后就又很困难了。我是手玩了一会 $p=4$，发现比较自闭。想到了等差数列的构造，但是仍然会有冲突。这时灵光一现：题目中的 $p$ 是质数啊！！！根据数论的一个很基础的结论，等差数列的构造是合法的！

具体的构造为：枚举 $1\leq i \leq p,1\leq j \leq p$，取第 $k$ 组的第 $i+kj\ mod\ p+1$ 个。

而 $p$ 不是质数的做法暂时没有想到。

7.

把从 $1$ 到 $n=2222$ 分为 $3$ 组，使得每组的平方和相等。
$n$ 这么大，肯定是要归纳了。于是设一个 $x$，试图把 $x+1$ 到 $x+c$ 分为 $3$ 组，平方和相等。这个可以爆搜，发现 $c=18$ 时有解。

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

然后剩下的部分开始科学地爆搜。发现 $n=8$ 无解，但是 $n=26$ 有解。于是解决了。（我这科学爆搜连 $31$ 都能跑出来哦）

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int n,a[N],b[N],c[N],na,nb,nc,m,sa,sb,sc,S[N];bool fl;
void solve(){
	for(int i=1;i<=na;i++)printf("%d ",a[i]);puts("");
	for(int i=1;i<=nb;i++)printf("%d ",b[i]);puts("");
	for(int i=1;i<=nc;i++)printf("%d ",c[i]);puts("");
	fl=1;
}
void dfs(int x){
	int mx=max(sa,max(sb,sc));
	if(3*mx-sa-sb-sc>S[x]||fl)return;
	if(!x)solve();int y=x*x;
	a[++na]=x;sa+=y;dfs(x-1);na--;sa-=y;
	b[++nb]=x;sb+=y;dfs(x-1);nb--;sb-=y;
	c[++nc]=x;sc+=y;dfs(x-1);nc--;sc-=y;
}
int main(){
	sa=sb=sc=0;
	for(int i=1;i<100;i++)S[i]=S[i-1]+i*i;
	for(n=1;;n++)fl=0,dfs(n);
	return 0;
}

9.

这个点要求构造一张 $n$ 个点的无向图，要求每两个点 $x,y$ 都存在恰好两个点，使得 $x,y$ 与它都有连边，最大化 $n$。
这个点还没有完全弄懂。题解给出的最优解是 $16$，构造方法为把点排为 $4\times 4$ 的矩阵，每个点与同行或同列的点连边。这样显然满足条件（不过这构造也太难想）。可是上界是否就是 $16$ 并没有说。

10.

这个点要求给一张 $n=233$ 个点的完全图的无向边黑白染色，最小化同色三元环的个数。
关于三元环，有一个非常套路的分析方式。考虑不同色的三元环，一定存在恰好两个点出边颜色不同。于是如果一个点有 $d$ 条黑边，那么贡献为 $\frac{d(n-1-d)}{2}$。贡献最大时 $d=\frac{n-1}{2}$。那么考虑构造每个点都连出恰好 $\frac{n-1}{2}$ 条黑边的方案。题目给出的 $n$ 为奇数，感觉不好构造。于是考虑 $n$ 为偶数，那么很容易得到一种构造：分为两组，每组内部都连黑边，两组之间都连白边。$n$ 为奇数没有这么容易，但也可以借鉴这种思路。考虑一下可以得到这种构造：设 $n=2k+1$，分为两组，A 有 $k$ 个点 $1$ 到 $k$，B 有 $k+1$ 个点 $k+1$ 到 $2k+1$，A内部都连黑边，对于A中的点 $i$，$i$ 与 $i+k$ 连黑边。这时A已经满足条件，而B中如果连完全图，那么 $k+1$ 到 $2k$ 的度数会多 $1$。于是把 $(k+1,k+2),(k+3,k+4)...(2k-1,2k)$ 都变成白色即可。