C o d e f o r c e s R o u n d 958 ( D i v . 2 ) \Huge{Codeforces Round 958 (Div. 2)} CodeforcesRound958(Div.2)
文章目录
- Problems A. Split the Multiset
- 题意
- 思路
- 标程
- Problems B. Make Majority
- 题意
- 思路
- 标程
- Problems C. Increasing Sequence with Fixed OR
- 题意
- 思路
- 标程
- Problems D. The Omnipotent Monster Killer
- 题意
- 思路
- 标程
比赛链接:https://codeforces.com/contest/1988
Problems A. Split the Multiset
题意
给出一个数组,每次可以选择数组中的一个数,并将其拆为不超过 k k k个数。
问最少需要几次可以构造出全 1 1 1数组(数组中只包含 1 1 1)。
思路
贪心的想,我们每次可以将选出的数字x拆为1+1+1+…+(x-k+1)。
那么结果即为:
⌈
n
−
1
k
−
1
⌉
\left \lceil \frac{n-1}{k-1} \right \rceil
⌈k−1n−1⌉
标程
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
void Solved() {
int n, k; cin >> n >> k;
n --;
cout << (n + k - 2) / (k - 1) << endl;
}
signed main(void) {
IOS
int ALL = 1;
cin >> ALL;
while(ALL -- ) Solved();
return 0;
}
Problems B. Make Majority
题意
给出一个 01 01 01串,每次可以选择一个区间,若区间 s u m 0 ≥ s u m 1 sum_0\ge sum_1 sum0≥sum1,则将该区间变为一个数字 0 0 0,否则变为一个数字 1 1 1。
求是否可以令 01 01 01串最后变为一个数字 1 1 1。
思路
贪心的想,我们每次可以令全 0 0 0子串变为一个 0 0 0。
然后容易发现,对比现在子串中的 0 , 1 0,1 0,1个数即可判断是否能构造出数字 1 1 1。
标程
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define endl '\n'
void Solved() {
int n; cin >> n;
string s; cin >> s;
int c0 = 0, c1 = 0;
string s1;
for(int i = 0; i < n; i ++ ) {
if(s[i] == '0') {
c0 ++;
if(i == 0 || (i && s[i - 1] == '1')) s1 = s1 + '0';
}
else {
c1 ++;
s1 = s1 + s[i];
}
}
int x= 0, y = 0;
for(int i = 0; i < s1.size(); i ++ ) {
if(s1[i] == '0') x ++;
else y ++;
}
if(c1 > c0) {
cout << "YES\n"; return;
}
if(x < y) cout << "YES\n";
else cout << "NO\n";
}
signed main(void) {
IOS
int ALL = 1;
cin >> ALL;
while(ALL -- ) Solved();
return 0;
}
Problems C. Increasing Sequence with Fixed OR
题意
给出一个正整数 n n n,要求构造出一个序列:
-
a i ≤ n ( 1 ≤ i ≤ k ) a_i\le n(1\le i\le k) ai≤n(1≤i≤k)。
-
a i > a i − 1 ( 2 ≤ i ≤ k ) a_i>a_{i-1}(2\le i\le k) ai>ai−1(2≤i≤k), a a a数组是严格递增的
-
a i ∣ a i − 1 = n ( 2 ≤ i ≤ k ) a_i\,|\,a_{i-1}=n(2\le i\le k) ai∣ai−1=n(2≤i≤k), ∣ | ∣ 表示按位异或操作。
要求构造出一个符合要求的最长的序列并输出。
思路
考察位运算。
很明显能发现,构造出的数列的最后一项一定是 n n n,因此我们考虑从后往前构造。
为了符合递增和相邻数字异或和为 n n n,我们考虑从低位到高位,依次让二进制下为 1 1 1的位变为零;对于该题,这即是最优情况。
但是需要特判一下当二进制下只有 1 1 1位 1 1 1时,能构造出来的序列只有其本身,特判即可。
标程
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long
#define endl '\n'
void Solved() {
int n; cin >> n;
bitset<63> b(n);
vector<int> a;
int sum = 0, x = -1;
for(int i = 0; i < 64; i ++ ) {
if(b[i] == 1) {
sum ++;
a.push_back(i);
}
if(b[i] == 1 && x == -1) x = i;
}
x = 64 - x;
if(sum == 1) {
cout << "1\n" << n << endl; return;
}
int t = n, k = 0;
vector<int> v;
for(int i = a.size() - 1; i >= 0; i -- ) {
k ++;
t = t - (1ll << (a[i]));
for(int j = i + 1; j < a.size(); j ++ ) {
t |= (1ll << (a[j]));
}
v.push_back(t);
}
v.push_back(n);
cout << k + 1 << endl;
for(auto i : v) cout << i << ' ';
cout << endl;
}
signed main(void) {
IOS
int ALL = 1;
cin >> ALL;
while(ALL -- ) Solved();
return 0;
}
Problems D. The Omnipotent Monster Killer
题意
有一颗树,树上有若干的怪物,每个怪物有对应的攻击值;每回合都会按顺序发生下面两种情况:
- 所有存活的怪物攻击你,你的生命值将会减少其攻击值的总和。
- 选择若干怪物杀掉,选择的限制条件是:不能同时选择一条边上的两只怪物。
当杀死全部怪物后结束游戏。求最少受到的攻击值。
思路
树形DP
假设游戏进行的回合数为
L
L
L,怪物
i
i
i在第
S
i
S_i
Si轮被杀死,并且满足同一条边上的两只怪物
i
,
j
(
S
i
!
=
s
j
)
i,j(S_i ~!=s_j)
i,j(Si !=sj),那么攻击值为:
∑
i
=
1
L
a
i
×
S
i
\sum_{i=1}^{L}{a_i\times S_i}
i=1∑Lai×Si
然后我们会发现本题的求解思路和这道题相同:P4395 [BOI2003] Gem 气垫车 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 。
关于树形DP练习,可以参考这一篇博客:树形dp(学习过程+刷题总结)
对于本题,我们可以用时间复杂度为
O
(
n
L
2
)
O(nL^2)
O(nL2)来进行树形DP,用二维数组
f
x
,
j
f_{x, j}
fx,j表示
S
x
=
j
S_x=j
Sx=j时,以
x
x
x为根的子树价值之和的最小值,则有:
f
x
,
j
=
S
x
×
a
x
+
∑
i
∈
s
o
n
(
x
)
min
S
J
!
=
S
x
(
f
i
,
j
)
f_{x,j}=S_x \times a_x+\sum_{i \in son(x)}\min_{S_J!=S_x}(f_{i,j})
fx,j=Sx×ax+i∈son(