数学（十）完结 (3-2)

vector＜int＞ans;

for(int i=1;i＜=40;i++){

int mx=*max_element(a.begin(),a.end());

int mn=*min_element(a.begin(),a.end());

int mid=mn+mx＞＞1;ans.push_back(mid);

for(auto &j:a){

j=abs(j-mid);

}

}

cout＜＜40＜＜endl;

for(auto i:ans){

cout＜＜i＜＜" ";

}

cout＜＜endl;

}

D - Prime XOR Coloring

当且仅当两个数异或得到的值是质数时，这两个点之间才有边，所以我们把异或值是质数的两个点染为不同的颜色，也就是说不是质数的点都染成相同颜色

x ⨁ x＋4不可能为质数，所以我们按照对4取模得到的数字来染色

为什么x ⨁ x＋4 不是质数，设x的二进制下最后三位是abc，4的二进制是100，所以x+4二进制是（a+1）%2，b, c 所以x+4与x两数异或后最后两位数都是0，也就是说异或得到的一定是偶数并且该偶数一定大于2，所以可证。以此类推x与x+1，x+2，x+3异或均不能保证得到的一定是质数，所以最小染色数是4

void solve() {

int n;cin＞＞n;

if (n ＜= 5) {

const int ans[] = {0, 1, 2, 2, 3, 3};

cout＜＜ans[n]＜＜'\n';

for(int i=1;i＜=n;i++)cout＜＜ans[i]＜＜" ";

}else {

cout＜＜4 <

for(int i=1;i<=n;i++){

cout＜＜i % 4 + 1＜＜" ";

}

cout＜＜endl;

}

}

E - Coloring Game

不会二分图的可以先看这篇文章大致了解一下

判定二分图，如果这个图是二分图的话，即不存在奇数环，此时选择Bob，否则选择Alice

当选择Alice的时候，情况很简单，只需要两种颜色交替排列即可，由于奇数环的存在，必然存在一对颜色相同的边相邻的点

选择Bob的时候，按照是否与顶点1在一个连通块分为两部分a和b，a部分全选为颜色1，b部分全选为颜色2，也就是说遇到给颜色1时染色a部分中的点，给颜色2时染色b部分中的点，这样一定合法。

特殊情况是如果遇到给定颜色是2和3，但是此时b部分已经全部染色，此时给a部分染色颜色3，这样也是合法的，因为此时b部分都是颜色2，没有颜色1与颜色3

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。