Codeforces Round #646 (Div. 2) 1363 ABCE题解

首先

Cue一下队友链接:

核心选手:https://me.csdn.net/qq_43559193

核心选手:https://me.csdn.net/weixin_43916298

比赛链接:https://codeforces.ml/contest/1363

小总结:

3题..,原因在于C题都错题了(具体下文种指出,不过延伸了一种新题),从开始看了3分钟就交..一直wa3。

最后重新读了一遍题,C题过了已经一个小时了(好久没这么晚过了)。

然后开始写E—— 树链剖分+贪心?

上来思路错了导致我调树剖调了45分钟。

最后样例没过。

最后换了一下思路,感觉树上贪心就可以。于是写了21分钟左右就写完了(已经超过比赛7分钟)

总体来说,还可以 C题研究了新题,E巩固了树链剖分归根还是不亏。


A. Odd Selection

时间:30min (slow)

题目大意:

给出n个数问能否选出x个数,使得这x个数的和是奇数

题目思路:

疯狂讨论即可(if else题):

1.没有奇数一定不可以

2.存在奇数,考虑m的奇偶性

(1)如果m是偶数,并且没有偶数存在,那么此时偶数个奇数一定是偶数,所以不可以。

(2)其他情况,此时Codeforces Round #646 (Div. 2) 1363 ABCE题解,所以发现当a是个奇数就行,所以要求 a取一个小于m的奇数,让b凑齐x即可。

根据上面判断b一定存在并且a+b==n ,首先,a是奇数一定成立 ,a是偶数只需要a-1即可变为奇数,但此时就需要a-1+b>=m

所以a-1+b>=n-1,所以当m<=n-1时恒成立,只需要特判m==n的情况即可:

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e18;
const int maxn=1e6+6;
const int mod=998244353;
const double eps=1e-15;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p,x,y;
ll num[maxn];
char str[maxn];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        read(n);read(m);
        int a = 0,b = 0;
        for(int i=1;i<=n;i++){
            ll x;read(num[i]);
            num[i]%=2;
            if(num[i]) a++;
            else b++;
        }
        if(!a) printf("No\n");
        else{
            if(m==n){
                if(a%2==0) printf("No\n");
                else printf("Yes\n");
            }
            else{
                if(m%2==0&&!b) printf("No\n");
                else printf("Yes\n");
            }
        }
    }
    return 0;
}
/**
1 3 4 5 ->2
2 4 -> 1
**/

B. Subsequence Hate

时间:4min (quick)

题目大意:

给你一串01字符串,问最少修改多少次(0变1,1变0),使得该序列没有101与010的子序列。

题目思路:

老掉牙的套路题了。

考虑最后不含有 101 与 010 子序列的字符串满足的要求:11110000 , 00001111,000000,111111

四种状态每种状态都可以以其中任意一个作为分隔符,所以直接On求出就可以啦

手速流登场

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e18;
const int maxn=1e6+6;
const int mod=1e9+7;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
char str[maxn];
int pre0[maxn],pre1[maxn];
int cur0[maxn],cur1[maxn];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%s",str+1);
        int len = strlen(str+1);
        for(int i=1;i<=len;i++){
            pre0[i] = pre0[i-1];
            pre1[i] = pre1[i-1];
            if(str[i]=='0') pre0[i]++;
            else pre1[i]++;
        }
        cur0[len+1]=cur1[len+1]=0;
        for(int i=len;i>=1;i--){
            cur0[i] = cur0[i+1];
            cur1[i] = cur1[i+1];
            if(str[i]=='0') cur0[i]++;
            else cur1[i]++;
        }
        int res = 1e9+7;
        for(int i=1;i<=len;i++){
            res = min(res,pre0[i]+cur0[i+1]);
            res = min(res,pre1[i]+cur1[i+1]);
            res = min(res,pre0[i]+cur1[i+1]);
            res = min(res,pre1[i]+cur0[i+1]);
        }
        printf("%d\n",res);
    }
    return 0;
}
/***
4
abacc
***/

C. Game On Leaves

时间:30min (slow)

题目大意:

两个人玩游戏,每次每个人都要删除一个叶子节点,给出节点x,输出最后删除x节点的玩家。

题目思路:

一个博弈水题,被我搞砸了。

刚开始读题还发现了这个叶子节点,后面写题的时候被自己的样例给坑到了:

Codeforces Round #646 (Div. 2) 1363 ABCE题解

一直觉得删除5之后,面临的就是必胜态了 (不可饶恕)....

所以判断时 一直判断的是 n-in[x] - 1 的奇偶性,in[x] 代表x的度数

所以此时延伸到一个新的题:如果不删除叶子节点该为 确定一个节点为根,每次只能删除外围节点,那就是判断n-in[x]-1的奇偶性了。

然而这个题并不是,考虑这个x成为叶子节点必然是所有点都被拿了。

所以考虑n的奇偶性即可。

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e18;
const int maxn=1e6+6;
const int mod=998244353;
const double eps=1e-15;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p,x,y;
ll num[maxn];
ll minl = INF;
int f = 0;
int in[maxn];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        a = b = 0;
        read(n);read(m);
        for(int i=1;i<=n;i++){
            v[i].clear();
            in[i] = 0;
        }
        for(int i=1;i<=n-1;i++){
            int x,y;scanf("%d%d",&x,&y);
            in[x]++;in[y]++;
        }
        if(n==1){
            printf("Ayush\n");
            continue;
        }
        if(in[m] == 1) printf("Ayush\n");
        else{
            ll temp = n ;
            if(temp%2==0) printf("Ayush\n");
            else printf("Ashish\n");
        }
    }
    return 0;
}
/**
1 3 4 5 ->2
2 4 -> 1
**/

E. Tree Shuffling

时间:57min (slow)

题目大意:

给出一个树,每棵树每个点都有一个点权a[i],含有进制位b[i],目标进制位c[i],每次可以对一个节点的子树,选择任意k个节点,使得其重新排序,花费k*a[i],问最少花费多少使得每个点都可以达到目标c[i]

题目思路:

这个题写了个树剖也是绝了。

但是思路是对的:

首先,要记录一下每个节点下的 1->0 和 0->1

其次这种转换的题目必定是,从下往上去操作:因为无论如何,你都要操作下面的。

所以说,考虑对节点u进行操作,那么节点u有多少个 想从1->0 和 0->1的,取一下这两个最小值就可以 让这些重新组合回到原位,此时u下的1->0,1->0下的数量都要减少最小值,花费是多少呢,那绝对是从当前节点u到根节点路径下的最小值,也就是这k个节点祖先中花费最小的:所以我就想到了树剖...绝了。

调树剖的bug调了很久很久...不打算调了,就接了个水(战术接水hhh)

突然想到 u -> root 的最小值可以回溯实现。

然后就写了一遍AC的思路,不过已经超出7分钟去了..

不过深度总结一下还是不亏,毕竟又复习了树剖。

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e18;
const int maxn=1e6+6;
const int mod=998244353;
const double eps=1e-15;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p,x,y;
ll a[maxn],b[maxn],c[maxn];
ll one[maxn],zero[maxn];
vector<int>v[maxn];
ll ans = 0;
void dfs(int u,int fa,ll minl){
    if(!b[u]&&c[u]) one[u]++;
    if(b[u]&&!c[u]) zero[u]++;
    for(int e:v[u]){
        if(e==fa) continue;
        dfs(e,u,min(minl,a[e]));
        zero[u] += zero[e];
        one[u] += one[e];
    }
    ll temp = min(one[u],zero[u]);
    ans+=minl*temp*2ll;
    one[u]-=temp;
    zero[u]-=temp;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        read(b[i]);
        read(c[i]);
    }
    for(int i=1;i<=n-1;i++){
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1,a[1]);
    if(one[1]||zero[1]) printf("-1\n");
    else printf("%lld\n",ans);
    return 0;
}
/**
1 3 4 5 ->2
2 4 -> 1
**/

至于这个D(交互体一般都不太想做),能不鸽就不鸽尽量更新。

上一篇:线路规划--最小生成树(克鲁斯卡尔)


下一篇:单源最短路