数学（十）完结

A - Maximize the Last Element

void solve() {

int n;cin＞＞n;

vector＜int＞a(n+1);

int ans=0;

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

cin＞＞a[i];

if(((i-1)%2==0)&&((n-i)%2==0)){

ans=max(a[i],ans);

}

}

cout＜＜ans＜＜endl;

}

B - AND Reconstruction

由于a2即和a1按位与得到b1，也和a3按位与得到b2，所以a2实际上需要有b1和b2所有位数上的1，也就是等于这两个数的或，a1和an比较特殊，可以直接变成b1和bn-1，这样操作一下看是否等于b数组即可

void solve() {

int n;cin＞＞n;

vector＜int＞a(n+1),b(n+1);

for (int i = 1; i＜n; i++) cin＞＞b[i];

b[0] = b[n] = 0;

for (int i = 1; i ＜= n; i++)

a[i] = b[i - 1] | b[i];

int ok=1;

for (int i = 1; i＜n; i++)

if ((a[i] & a[i + 1]) != b[i]) {

ok = 0;

break;

}

if (ok) {

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

cout＜＜a[i]＜＜ ' ';

} else{

cout＜＜-1;

}

cout＜＜endl;

}

C - Absolute Zero

首先判断不成立的条件，奇偶性不同的两个数减去相同的x后，得到的数的绝对值奇偶性必然不同，（这个很好证明,只需要枚举一下所有可能的情况即可）所以我们是没法让既存在奇数和偶数的数组置为0

观察操作特性，每次选定一个数x，使得所有的a[i]都等于abs(a[i]-x),就相当于找到一个数x，并将所有的数的值改为与x的距离差的绝对值，可以想到用数组的最大最小的均值去不断缩小整个数组

void solve(){

int n;cin＞＞n;

vector＜int＞a(n);

for(int i=0;i＜n;i++) cin＞＞a[i];

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

if(a[i]%2!=a[0]%2){

cout＜＜-1＜＜endl;

return;

}

}

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

我使用的并查集维护

void solve(){

int n,m;cin＞＞n＞＞m;

DSU dsu(n*2+10);

for(int i=0;i＜m;i++){

int u,v;cin＞＞u＞＞v;

dsu.merge(u,v+n);

dsu.merge(v,u+n);

}

int ok=0,pos=0;

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

if(dsu.find(i)==dsu.find(i+n)){

ok=1;

}

}

if(ok){

cout＜＜"Alice"＜＜endl;

for(int i=0;i＜n;i++){

cout＜＜1＜＜" "＜＜2＜＜endl;

int l,r;cin＞＞l＞＞r;

}

}else {

cout＜＜"Bob"＜＜endl;

vector＜int＞ a, b;

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

if (dsu.find(i) == dsu.find(1)) {

a.push_back(i);

} else {

b.push_back(i);

}

}

for (int i = 0; i＜n; i++) {

int x, y;cin＞＞x＞＞y;

vector＜int＞cnt(4,0);

cnt[x]++;cnt[y]++;

if (a.empty()) {

cout＜＜b.back()＜＜" "＜＜(cnt[2] ? 2 : 3)＜＜endl;

b.pop_back();

continue;

}

if (b.empty()) {

cout＜＜a.back()＜＜" "＜＜(cnt[1]? 1 : 3)＜＜endl;

a.pop_back();

continue;

}

if (cnt[2]) {

cout＜＜b.back()＜＜" " ＜＜2＜＜endl;

b.pop_back();

} else {

cout＜＜a.back()＜＜" "＜<1＜＜endl;

a.pop_back();

}

}

}

}

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。