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;
}

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