Codeforces Round #652 (Div. 2) A~E
链接：题目
赛后总结
Codeforces Round #652 (Div. 2)
A.FashionabLee
题意：能不能构造多边形和x轴，y轴同时平行
思路：边数得是偶数的同时，同时满足(n-2)/2为奇数
int main(){
int _;
for(scanf("%d" , &_); _ ; _ --){
int n ;
scanf("%d" , &n);
if(n % 2)no;
else {
if(((n - 2) / 2) % 2 == 1 )yes;
else no;
}
}
return 0;
}
B.AccurateLee
题意：对于每一个1,0都可以任意删除一个
思路：第一个1后面的所有0都可以删掉，但是最后一个0删掉就不行了，然后从后往前第一个0前面的1都可以删掉
int a[N];
int vis[N];
int main(){
int _;
for(scanf("%d" , &_); _ ; _ --){
int n ;
scanf("%d" , &n);
int num[2] = {0 , 0};
for(int i = 1;i <= n ; i ++){
scanf("%1d" , &a[i]);
vis[i] = 0;
}
int flag = 1;
for(int i = n ; i >= 1;i --){
if(a[i] == 1){
if(flag)continue;
else vis[i] = 1;
}
else flag = 0;
}
flag = 0;
for(int i = 1;i <= n ;i ++){
if(a[i] == 0){
if(flag) vis[i] = 1;
else continue;
}
else flag = 1;
}
for(int i = n ; i >= 1;i --){
if(a[i] == 0){vis[i] = 0;break;}
}
for(int i = 1;i <= n ; i++){
if(vis[i])continue;
printf("%d",a[i]);
}
puts("");
}
return 0;
}
C. RationalLee
题意：每一个朋友要wi个快乐值，其中只有最大最小值有贡献，让你最大化这个贡献
思路：对于只要求一个快乐值得，肯定给他最大的快乐值，其他两个以上得要求都是等价的，但是要求把每个最大快乐值都取到，剩下的所有快乐值都依次取最小，很简单的贪心。
LL a[N] , b[N];
int vis[N];
int main(){
int _;
for(scanf("%d" , &_); _ ; _ --){
int n ,k ;
scanf("%d %d" , &n , &k);
for(int i = 1;i <= n ; i ++){
scanf("%lld" ,&a[i]);
}
for(int i = 1; i <= k ; i ++){
scanf("%lld",&b[i]);
}
sort(b + 1, b + k + 1);
sort(a + 1, a + n + 1);
int l = 1, r = n ;
LL ans = 0 ;
for(int i = 1;i <= k ; i ++){
if(b[i] == 1){
ans += 2*a[r];
r --;
}
}
for(int i = k ;i >= 1; i --){
if(b[i] > 1){
ans += a[r];
ans += a[l];
l += b[i] - 1;
r --;
}
}
printf("%lld\n",ans);
}
return 0;
}
D. TediousLee
题意：对于一棵构造树
找到爪子形的样式就算一次贡献，问你x层的最大贡献是多少？
思路：这题算是比较优秀的题吧，我当时思考的过程我觉得对自己还是挺有参考价值的。因为对于一个独立节点每一次形成爪子都需要经历两步，也就是说两步以后每一个独立节点一定会形成一个爪子，于是我们可以先维护出每一层新生成的独立节点，这个还是很好求的：
a[i] = (a[i-2] * 2 % mod + a[i-1] % mod) % mod
接下来每一层的爪子就是上两层的独立节点：
b[i] = a[i-2]
然后就是贪心隔两层的前缀和
f[i] = (f[i-3]%mod + b[i]%mod)%mod;
于是整体就可以维护出来了，当然题解上说的那个1e18，用的那个公式我还不太会。暂时先这样。
LL f[N];
LL a[N];
LL b[N];
int main(){
int _;
a[1] = 1;
a[2] = 1;
for(int i = 3; i <= M ;i ++){
a[i] = (a[i-2] * 2 % mod + a[i-1] % mod) % mod ;
}
/** b[3] = 1; b[4] = 1; b[5] = 3; b[6] = 5; **/
b[1] = 0;
b[2] = 0;
for(int i = 3 ; i <= M; i ++){
b[i] = a[i-2];
}
f[1] = 0;
f[2] = 0;
f[3] = 1;
f[4] = 1;
f[5] = 3;
for(int i = 5;i <= M; i ++){
f[i] = (f[i-3]%mod + b[i]%mod)%mod;
}
for(scanf("%d" , &_); _ ; _ --){
int n;
scanf("%d",&n);
printf("%lld\n",(f[n]*4)%mod);
}
return 0;
}
E. DeadLee
题意：每人都会吃一盘最喜欢的食物，问你最后他能吃完生成的序列。
思路：类拓扑排序，反相思维
int a[N], vis[N],in[N] , n ,m;
vector<PII> G[N];
int main(){
while(~scanf("%d %d", &n ,&m)){
for(int i = 1;i <= n ; i ++){
scanf("%d" ,&a[i]);
in[i] = 0,vis[i] = 0;
G[i].clear();
}
for(int i = 1;i <= m ; i ++){
int x,y;
scanf("%d %d" ,&x,&y );
G[x].pb({y,i});
G[y].pb({x,i});
a[x] --; a[y] --;
}
queue<int> q;
for(int i = 1;i <= n ;i ++){
if(a[i] >= 0) q.push(i),in[i]=1;
}
VI ans;
while(q.size()){
int x = q.front();
q.pop();
for(auto y:G[x]){
if(!vis[y.se])vis[y.se] = 1, ans.pb(y.se);
if(!in[y.fi]){
a[y.fi] ++;
if(a[y.fi] >= 0){
in[y.fi] = 1;
q.push(y.fi);
}
}
}
}
reverse(ans.begin(),ans.end());
if(SZ(ans) == m){
puts("ALIVE");
for(auto x:ans)cout << x <<" ";
puts("");
}
else puts("DEAD");
}
}
小总结
这一次整体做的十分流畅，可能是才睡了一觉的缘故 ，重要的还是这一场带来的经验，冷静思考，沉着应对吧，这一次的E题大约是有点小自满，刚开始觉得是一个2-SAT或者二分图，（当然这是我接下来打算跟进的知识点）我觉得自己不太会这类型的题，后来赛后发现竟然是个拓扑排序，难度简直就是while(1) s–;这说实话同样提醒着我，在icpc区域赛中其实经常也会出现这样的情况，就是这一道题其实你能做，但是你不去开。当然现在还是得好好补习自己关于区域赛类型的题，不然到时候只有被虐和拖队友后腿的情况了。题解还是要坚持写的。题还是要快快补的。
