Codeforces Global Round 18(A-E)

A - Closing The Gap

签到：加起来模n即可。

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
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define endl "\n"
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+7;
const long long MOD=998244353;
const double pi=acos(-1);
const double eps=1e-4;
vector<int>di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};

int a[MAXN];

int main()
{
    fastIO
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        ll sum = 0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum += 1ll*a[i];
        }
        if(sum%(1ll*n)==0) cout<<"0"<<endl;
        else cout<<"1"<<endl;
    }

    return 0;
}

B - And It’s Non-Zero

前缀和处理前1-x中第i位有多少0和1得到 $cnt1，cnt0$两个数组。对于每个询问$l,r$ ，只需要$cnt0[r][i] - cnt0[l-1][i]$即可得到$l$到$r$有的第$i$位有多少$0$。对每一位便利找出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
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define endl "\n"
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+7;
const long long MOD=998244353;
const double pi=acos(-1);
const double eps=1e-4;
vector<int>di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};

int a[MAXN];
int cnt1[200000+5][30];
int cnt0[200000+5][30];
int main()
{
    fastIO
    for(int num = 1;num<=200000;num++)
    {
        for(int i=1;i<=20;i++)
        {
            if((num>>(i-1))&1==1)
            {
                cnt1[num][i] = cnt1[num-1][i] + 1;
                cnt0[num][i] = cnt0[num-1][i];
            }
            else
            {
                cnt1[num][i] = cnt1[num-1][i];
                cnt0[num][i] = cnt0[num-1][i] + 1;
            }
        }
    }
    int T;
    cin>>T;
    while(T--)
    {
        int l,r;
        cin>>l>>r;

        int ans = INF;
        for(int i=1;i<=20;i++)
        {
            if(cnt1[r][i] - cnt1[l-1][i]!=0) ans = min(ans,cnt0[r][i] - cnt0[l-1][i]);
        }
        cout<<ans<<endl;
    }

    return 0;
}

C - Menorah

首先不难想到，对于一个串，交换值为0和1的两个位置需要2次操作。

当两个串的01个数分别相等时，最小次数就是直接进行两个位置01交换的次数，设对应位不相等的数量为dif，答案就是dif/2*2，其中dif一定为偶数；

当不相等时，考虑如何使得他们01个数先相等，例如对于： 00000111 ，对其中一个1进行操作，得到11111001，可以发现奇数次变换可以改变01的数量，且只能使得1的个数多一个。因此当$n -a串中1的个数 == b串中1的个数 -1$时 可以使得01个数恢复相等，即转化为了第一种情况。

其他情况都是不可能存在的。

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
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define endl "\n"
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+7;
const long long MOD=998244353;
const double pi=acos(-1);
const double eps=1e-4;
vector<int>di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};


int main()
{
    fastIO
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        string a,b;
        cin>>a>>b;
        int ans = 999999, dif = 0;
        int a1 = count(a.begin(), a.end(), '1');
        int b1 = count(b.begin(), b.end(), '1');

        for(int i=0;i<n;i++) dif += (a[i]!=b[i]);

        if(a1 == b1) ans = min(ans, dif);
        if(n -a1  == b1 -1) ans = min(ans, (n - dif - 1) + 1);

        if(ans == 999999) ans = -1;
        cout<<ans<<'\n';
    }


    return 0;
}

D - X(or)-mas Tree

对于一个数的parity的奇偶性可以只改变最后一位来进行奇偶的转换，所有我们赋值只需要考虑0和1两个数即可。

我们首先定义点u的权值$value(u)$为$u$到树根的路径上所有路径异或的奇偶性(0/1)。

那么对于两个点u到v的路径奇偶性：

  • 如果题目规定他们的奇偶性是1(也就是奇数)，我们可以得到他们两者的$value(u)$ 和$value(v)$ 奇偶性是不同的。

  • 如果题目规定他们的奇偶性是0(也就是偶数)，我们可以得到他们两者的$value(u)$ 和$value(v)$ 奇偶性是相同的。

不难想到，我们可以首先用种类并查集维护这个东西，他们之间的关系可以看作约束条件(constraints)。

因此最后根据上述的约束条件对每个未知的边赋值，对于一个点$u$，如果$u$和$u+n$(拓展域并查集写法)相连说明自己和自己奇偶性不同(这是不可能的)，则无解输出NO。否则有解输出YES。

最后，对于给出的未知权重一条边：

  • 若这条边两点的$value$不同，说明这条边是值为1，经过这条边奇偶变化。

  • 若这条边两点的$value$可以相同或已给出的约束未对这两点出约束，说明这条边是值为0，经过这条边不影响奇偶。

总结一下：这题难点在于定义权值value为$u$到树根的路径上所有路径异或的奇偶性

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define endl "\n"
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+7;
const long long MOD=998244353;
const double pi=acos(-1);
const double eps=1e-4;
vector<int>di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};

int p[MAXN];
int fd(int x)
{
    if(p[x]!=x) p[x] = fd(p[x]);
    return p[x];
}
void mrge(int x,int y)
{
    int fax = fd(x), fay = fd(y);
    if(fax!=fay) p[fax] = fay;
}

int main()
{
    fastIO
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        vector<array<int,3>>edge;
        for(int i=1;i<=2*n+2;i++) p[i] = i;//init
        for(int i=1;i<=n-1;i++)
        {
            int x,y,v;
            cin>>x>>y>>v;
            edge.push_back({x,y,v});
            if(v!=-1)
            {
                if(__builtin_parity(v))//num of 1 is odd,x and y are different
                {
                    mrge(x,y+n);
                    mrge(x+n,y);
                }
                else 
                {
                    mrge(x,y);
                    mrge(x+n,y+n);
                }
            }
        }

        for(int i=1;i<=m;i++)
        {
            int x,y,v;
            cin>>x>>y>>v;
            if(v==1)
            {
                mrge(x,y+n);
                mrge(x+n,y);
            }
            else if(v==0)
            {
                mrge(x,y);
                mrge(x+n,y+n);
            }
        }



        for(auto &e:edge)
        {
            if(e[2]!=-1) continue;
            if(fd(e[0])==fd(e[1]+n)) //constraints make e[0] e[1] value different
            {
                e[2] = 1;
            }
            else //constraints make e[0] e[1] value same
            {
                e[2] = 0;
                mrge(e[0],e[1]);
                mrge(e[0]+n,e[1]+n);
            }
        }

        int ok = true;
        for(int i=1;i<=n;i++)
        {
            if(fd(i)==fd(i+n))
            {
                ok = false;
                break;
            }
        }

        if(!ok) cout<<"NO"<<endl;
        else
        {
            cout<<"YES"<<endl;
            for(auto &e:edge)
            {
                cout<<e[0]<<" "<<e[1]<<" "<<e[2]<<endl;
            }
        }
    }


    return 0;
}

E - Purple Crayon

把$w$替换为$n-r-b$得到： $r⋅(n−r)−b⋅(n−b). $

首先要想到：当红色涂完后，蓝色可以最多涂x个，那么蓝色涂色时对于小于等于x个都是可以实现的。

那么如何让 $goal = r⋅(n−r)−b⋅(n−b) $最小呢？

首先我们如果可以选择的x个红色(x是一个确定值，即我就选择x这么多个)，此时最佳的选择方法肯定是选择后让b最多可选的值maxb 越小越好(实现方法是：x个树叶的所有祖先节点构成的子树的节点越多越好，因为这些点不能染蓝色，其他都可以,也就是让蓝色最少)，因为如果其$maxb>=n/2$ 那么maxb一定会选择$n/2$使得$b⋅(n−b)$最大。如果$maxb< n/2$那么我们也是选择maxb，所以RED肯定想让BLUE的maxb越小越好。

现在遍历$r = 1,2,3…k$， 我们只要可以算出每个$r$ 对应的maxb，那么对于BLUE, 我们知道最优的b = min(n/2,minb)，带入goal算出结果，对于每个r取最大值更新即是RED的最优的开局策略。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define endl "\n"
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+7;
const long long MOD=998244353;
const double pi=acos(-1);
const double eps=1e-4;
vector<int>di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};


pii dep[MAXN];
unordered_map<int,int>point2dep;
vector<int>g[MAXN];
int vis[MAXN];
int g_re[MAXN];
vector<pii>leaves;

void dfs(int u,int fa,int d)
{
    g_re[u] = fa;
    dep[u] = {d,u};
    point2dep[u] = d;
    for(auto v:g[u])
    {
        if(v==fa) continue;
        else
        {
            dfs(v,u,d+1);
        }
    }
}

int vis_d = -1;
void dfs2(int u,int fa)
{
    if(vis[u]) {vis_d = point2dep[u];return;}

    vis[u] = 1;
    if(u == 1)
    {
        vis_d = 0;
        return;
    }

    int v = g_re[u];
    dfs2(v,u);


}


int main()
{
    fastIO
    int T;
    //cin>>T;
    T = 1;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n-1;i++)
        {
            int x,y;
            cin>>x>>y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        dfs(1,-1,1);
        sort(dep+1,dep+1+n,greater<pii>());

        for(int i=1;i<=n;i++)
        {
            if(g[dep[i].second].size()==1)
            {
                vis_d = -1;
                dfs2(dep[i].second,-1);
                int cover_leaves = dep[i].first - vis_d;
                leaves.push_back({cover_leaves,i});
            }
        }

        sort(leaves.begin(),leaves.end(),greater<pii>());
        int leaves_cnt = leaves.size();
        ll ans = -1e12;

        int red_cover_leaves = 0;
        int half = n/2;
        for(int i=1;i<=k;i++)
        {
            if(i>leaves_cnt)
            {
                if(k<=half) ans = max(ans,1ll*k*(n-k));//k half
                else if(leaves_cnt<=half) ans = max(ans,1ll*half*(n-half)); //lea half k
                break;
            }
            red_cover_leaves += leaves[i-1].first;
            int blue_cover_leaves = n - red_cover_leaves;
            if(blue_cover_leaves>=n/2) blue_cover_leaves = n/2;
            ans = max(ans,1ll*i*(n-i) - 1ll*blue_cover_leaves*(n-blue_cover_leaves));
        }



        cout<<ans<<endl;

    }


    return 0;
}
ACM-Codeforces

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！