Codeforces Round 646 (Div. 2)（A—E）题解

好久没写题解了，忙里偷闲来摸一摸。

A Odd Selection

日常A乱WA系列，没奇数必定不行，先扔了，然后贪心搞一下，先把$x$全填成偶数，然后看能否扔进去奇数个奇数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
il ll read(){char c=getchar();ll f=1,x=0;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}return x*f;}
const int N =1e5+5;
const int MAX=1e9;
const int mod = 1e9+7;
#define db double
#define eps 1e-8
int a[N];
signed main() {
    int t=read();
    while(t--){
        int l=0,r=0;
        int n=read(),x=read();
        for (int i = 1; i <=n ; ++i) {
            a[i]=read();
            if(a[i]%2!=0)l++;
            else r++;
        }
        if(l==0){
            cout<<"No"<<endl;
        }else{
            if(r>=x){
                cout<<"Yes"<<endl;
            }else{
                x-=r;
                if(x%2!=0)cout<<"Yes"<<endl;
                else if(x%2==0&&r!=0&&x+1<=l){
                    cout<<"Yes"<<endl;
                }else{
                    cout<<"No"<<endl;
                }
            }
        }
    }
    return 0;
}

B Subsequence Hate

维护一个前缀和后缀，分别计算0/1个数，之后遍历看看那种刷法省钱即可(10，01，00，11)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
il ll read(){char c=getchar();ll f=1,x=0;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}return x*f;}
const int N =1e3+5;
const int MAX=1e9;
const int mod = 1e9+7;
#define db double
#define eps 1e-8
int pre[2][N],suf[2][N];
signed main() {
    int t=read();
    while(t--){
        char s[2020];
        cin>>(s+1);
        memset(pre,0, sizeof(pre));
        memset(suf,0, sizeof(suf));
        int len=strlen(s+1);
        for (int i = 1; i <=len ; ++i) {
            pre[0][i]=pre[0][i-1]+(s[i]=='0');
            pre[1][i]=pre[1][i-1]+(s[i]=='1');
        }
        for (int i = len; i >=1 ; --i) {
            suf[0][i]=suf[0][i+1]+(s[i]=='0');
            suf[1][i]=suf[1][i+1]+(s[i]=='1');
        }
        int ans=len;
        for (int j = 1; j <=len ; ++j) {
            ans=min(ans,pre[1][j]+suf[0][j+1]);
            ans=min(ans,pre[0][j]+suf[1][j+1]);
            ans=min(ans,pre[0][j]+suf[0][j+1]);
            ans=min(ans,pre[1][j]+suf[1][j+1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

C Game On Leaves

如果目标节点不是叶子节点，必输的情况就是仅剩三个节点并且目标节点在中间。那么只需要判断$n-3$的奇偶性即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
il ll read(){char c=getchar();ll f=1,x=0;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}return x*f;}
const int N =1e3+5;
int d[N];
signed main() {
    int t=read();
    while(t--){
        int n=read(),x=read();
        for (int j = 0; j <=n ; ++j)d[j]=0;
        for (int i = 0; i <n-1 ; ++i) {
            int u=read(),v=read();
            d[u]++; d[v]++;
        }
        if(d[x]<=1){
            cout<<"Ayush"<<endl;
        }else{
            n-=3;
            if(n%2!=0){
                cout<<"Ayush"<<endl;
            }else{
                cout<<"Ashish"<<endl;
            }
        }
    }
    return 0;
}

D Guess The Maximums

看到12次很明显就是二分了。
直接二分询问即可。如果数列的最大值是$\max$，那么密码至少有$n-1$位是$\max$，我们只需要二分询问那个子集中最大值是$\max$即可。然后再询问除该子集之外的最大值就是这一位的密码。有点找假金币的感觉==

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
il ll read(){char c=getchar();ll f=1,x=0;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}return x*f;}
const int N =1e3+5;
const int MAX=1e9;
const int mod = 1e9+7;
#define db double
#define eps 1e-8
vector<int> g[N];
bitset<N> bit[N];
int n,k;
int ma;
int query(int l,int r){
    int sz=0;
    for (int i = l; i <=r ; ++i) {
        sz+=g[i].size();
    }
    cout<<"? "<<sz<<" ";
    for (int j = l; j <=r ; ++j) {
        for(int i:g[j])cout<<i<<" ";
    }
    cout.flush();
    int ans;
    cin>>ans;
    return ans;
}int vis[1010];
void solve(){
    cout<<"? "<<n<<" ";
    for (int i = 1; i <=n ; ++i) {
        cout<<i<<" ";
    }
    cout.flush();
    cin>>ma;
    int tmp=ma+1;
    int l=1,r=k;
    while(l<r){
        int mid=(l+r)>>1;
        tmp=query(l,mid);
        if(tmp==ma){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    memset(vis,0, sizeof(vis));
    for (int m : g[l]) {
        vis[m]=1;
    }
    vector<int> tm;
    for (int i1 = 1; i1 <=n ; ++i1) {
        if(!vis[i1]){
            tm.push_back(i1);
        }
    }
    cout<<"? "<<tm.size()<<" ";
    for (int i:tm) {
        cout<<i<<" ";
    }
    cout.flush();
    cin>>tmp;
    cout<<"! ";
    for (int j = 1; j <=k ; ++j) {
        if(l!=j)cout<<ma<<" ";
        else cout<<tmp<<" ";
    }
}
signed main() {
    int t=read();
    while(t--){
        n=read(),k=read();
        for (int i = 1; i <=k ; ++i) {
            g[i].clear();
            int tmp=read();
            while(tmp--){
                int a=read();
                g[i].push_back(a);
            }
        }
        solve();
        string s;
        cin>>s;
        if(s=="Correct")continue;
        else return 0;
    }
    return 0;
}

E Tree Shuffling

如果某个节点的费用大于其父亲结点，显然选父亲比选它更优。考虑先$dfs$一波保证每个节点的费用$tr[x]$满足$tr[x]=\min(tr[x],tr[fa]),fa$是$x$的父亲结点。然后对于每个节点，假设其当前需要刷$k$个节点，显然有$k=2*\min(dif1[x],dif2[x])$，其中$dif1,dif2$分别代表$01$和$10$类型。如果$x$比其父亲结点费用要小，那就没必要向上传递了，记录当前节点费用，然后在其父亲结点的两个$dif$值里减去$k$，否则就把当前节点的$k$向上传递，然后令$k=0$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
il ll read(){char c=getchar();ll f=1,x=0;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}return x*f;}
const int N =2e5+5;
const int MAX=1e9;
const int mod = 1e9+7;
#define db double
#define eps 1e-8
#define int long long
int d[N],sz[N];
struct edge{
    int u,v,w,nxt;
}e[N*2];
int head[N],cnt,dif1[N],dif2[N];
void add(int u,int v,int w){
    e[cnt]={u,v,w,head[u]};
    head[u]=cnt++;
}
struct node{
    int a,b,c;
}tr[N];
int work[N];
void dfs(int x,int fa){
    if(tr[x].b>tr[x].c){
        dif1[x]++;
    }else if(tr[x].b<tr[x].c){
        dif2[x]++;
    }
    tr[x].a=min(tr[fa].a,tr[x].a);
    for (int i = head[x]; i !=-1 ; i=e[i].nxt) {
        int v=e[i].v;
        if(v!=fa){
            dfs(v,x);
            dif1[x]+=dif1[v];
            dif2[x]+=dif2[v];
        }
    }

    work[x]=2*min(dif1[x],dif2[x]);
    if(tr[x].a<tr[fa].a){
        dif1[fa]-=work[x]/2;
        dif2[fa]-=work[x]/2;
    }else{
        work[x]=0;
    }
}
signed main() {
    memset(head,-1, sizeof(head));
    int n=read(),l=0,r=0;
    for (int i = 1; i <=n ; ++i) {
        tr[i].a=read();tr[i].b=read();tr[i].c=read();
        if(tr[i].b>tr[i].c)l++;
        else if(tr[i].c>tr[i].b)r++;
    }

    if(l!=r){cout<<"-1";return 0;}
    for (int j = 0; j <n-1 ; ++j) {
        int u=read();int v=read();
        add(u,v,1);
        add(v,u,1);
    }
    tr[0].a=100000000000;
    dfs(1,0);//cout<<dif1[1]<<" "<<dif2[1]<<endl;
    int ans=0;
    for (int k = 1; k <=n ; ++k) {
        ans+=work[k]*tr[k].a;
    }
    cout<<ans;
    return 0;
}