eforces

Even小分类讨论题意给定一个数每次操作可以选取其前缀然后翻转其前缀问你最少操作几次可以把该数变为偶数思路对次数分类讨论即可如果本来就是偶数就是0次如果s[1]是偶数翻转一整个就行如果没有偶数位就是-1其余都是两次Code#include

bits/stdc.h

main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int

__1;cin__;//p_init(1e6);while(__--)solve();return

}B.

Mathematicians贪心题意有a个数学家和b个计算机学家4个人一组组队每组至少包含两种学科问最多能组几队谢谢不会小学数学思路要使队伍数尽可能多就让少的那个学科每队派一人然后和另一个队组队那么答案就是min(min(a,b),(ab)/4)Code#include

bits/stdc.h

solve(){cinab;coutmin(min(a,b),(ab)/4)\n;

signed

main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int

__1;cin__;//p_init(1e6);while(__--)solve();return

}C.

Permutation构造排列题意思路一开始写了一小时的双指针模拟操作然后写了一坨错了这是构造题考虑将一些一般条件特殊化一般来说这种一般条件都是比较难处理的像之前过年那会有个子序列它就直接选了一整个序列对于这种难处理的一般条件我们考虑将其特殊化注意到答案的排列即原来的排列的两端一定是最大值否则就是无解这道题就是把

这个条件

固定一个指针动另一个固定的那个指针大小一定为n直接将其翻转即可Code#include

bits/stdc.h

Students尺取法题意找出最长的连续子串使得其前缀和s0思路尺取法模板题这道题居然有*1800逆Code#include

bits/stdc.h

solve(){memset(sum,0,sizeof(sum));cinns;for(int

i1;in;i)

l1,r1;ln;l){while(rnsum[r]-sum[l-1]-s)

r;r--;if(ansr-l1){ansr-l1;ansll;ansrr;}}if(ans-1||anslansr)

cout-1\n;else

main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int

__1;cin__;while(__--)solve();return

}D.

Edges构造题意给定一棵树又给了一个排列对于p[i]满足dis[p[i]]dis[p[i-1]]dis是该结点的树上前缀和w是边权要你给这棵树的边权w赋值使得能满足p排列的条件思路模拟一下样例发现我们可以遍历p[i]排列把边权变成公差为1

的等差数列特殊化边权如果父亲结点在p[i]中出现的id大于结点i那么父亲结点的dis必然小于结点i矛盾所以这种情况无解否则就去递推出p[i]的dis和wCode#include

bits/stdc.h

fa[mxn],w[mxn],dis[mxn],id[mxn],p[mxn];

void

solve(){memset(dis,0,sizeof(dis));memset(w,0,sizeof(w));cinn;for(int

rti;}for(int

i1;in;i){cinp[i];id[p[i]]i;}if(p[1]!rt)

cout-1\n;else{int

i2;in;i){if(id[p[i]]id[fa[p[i]]])

ok0;w[p[i]]dis[p[i-1]]1-dis[fa[p[i]]];dis[p[i]]dis[fa[p[i]]]w[p[i]];}if(!ok)

i1;in;i)

main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int

__1;cin__;while(__--)solve();return

}E1.

version)BFS题意有一棵树Vlad和n个朋友玩游戏Vlad位于节点1n个朋友位于其他节点第i个朋友位于xi。

每个时刻每个人都能沿着树边到达另一个点或者留在原地。

如果Vlad到达叶子节点则Vlad赢。

如果在其到达叶子前和其他人碰面叶子也不能有其他人则Vlad输。

问最少需要保留多少个人能够保证Vlad输即选取朋友的一个最小的子集使得Vlad不能赢。

思路直接去BFS模拟过程一格格染色如果能把叶子结点染成1就是赢Code#include

bits/stdc.h

x[mxn],d[mxn],head[mxn],mark[mxn],vis[mxn];

void

v){edge[tot].tov;edge[tot].nexthead[u];head[u]tot;

void

i0;in;i){x[i]0;head[i]-1;d[i]0;mark[i]0;vis[i]0;}

bool

q.push(x[i]),vis[x[i]]1;q.push(1);vis[1]1;mark[1]1;while(!q.empty()){int

uq.front();q.pop();if(d[u]1mark[u]1u!1)

ok1;for(int

ihead[u];~i;iedge[i].next){if(vis[edge[i].to])

continue;vis[edge[i].to]1;q.push(edge[i].to);mark[edge[i].to]mark[u];}}return

ok;

i1;in-1;i){cinuv;add(u,v);add(v,u);d[v];d[u];}//for(int

i1;in;i)

main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int

__1;cin__;while(__--)solve();return