希望联盟第二场

第一题的调整挺有意思的

不感兴趣

开通SVIP免广告

比前一次简单

几何牛顿线+建系貌似可以秒，那个直角给的真好

好想简单了一点

所以第四题答案是什么

第三题把每个正整数对应一个2018维01向量，必有一种出现2918次，取这2018个向量对应的正整数就行了

第四题，答案是9。直接转化成图论语音。一方面构造如下：把c1到c1000分成100组：c1~c10，c11~c20，...，c991~c1000，让每组内连边均为红色，让1~10组，10~20组，...，91~100组组间连边为蓝色，其余边为黄色，这就完成了9的构造。另一方面，先证明存在一个同色边构成的子图色数≥10。如果红色边构成的子图色数小于10，那在相应的点染色中有多于100个点同色，这些点之间不连红边。如果蓝色边构成子图色数也小于10，那这100多个点在相应染色中有多于10个同色，这些点之间只能全连黄边。从而存在黄色K10，故黄色边构成子图色数至少是10。
现在取出色数≥10的同色边构成子图，对每个点v，记以其为起点的有向链长度最大值是f(v)，则两个相邻点的f值不同。现将点v染成第f(v)种颜色，那么同色点不相邻，于是由色数≥10知最大的f(v)≥9，证毕。