比赛链接:https://codeforces.com/contest/1330
A. Dreamoon and Ranking Collection
知识点:枚举
只需要枚举一遍,遇到没出现的数字如果还有可用场次则场次数量减一,否则输出答案退出循环。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 2e5 + 117;
int t;
int n, x;
int a[117];
bool vis[117];
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &x);
memset(vis, false, sizeof(vis));
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
vis[a[i]] = true;
}
for(int i = 1; i <= 100; i++) {
if(!vis[i]) {
if(x) x--;
else {
printf("%d\n", i - 1);
break;
}
}
if(i == 100) {
printf("%d\n", i + x);
break;
}
}
}
return 0;
}
B. Dreamoon Likes Permutations
知识点:排列
思路:设序列中的最大值为x,则合法的情况只有前x项+后n-x项凑成排列和前n-x项+后x项凑成排列两种。那么问题就转化为给定一个序列判断是不是一个排列。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;
int t;
bool vis[MAXN];
int n, num, cnt;
int a[MAXN], ans[7][2];
bool check(int id, int len) {
for(int i = 1; i <= len; i++) vis[i] = false;
for(int i = 0; i < len; i++) vis[a[id + i]] = true;
for(int i = 1; i <= len; i++)
if(!vis[i]) return false;
return true;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
num = 0;
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
if(num < a[i]) num = a[i];
}
cnt = 0;
if(check(0, num) && check(num, n - num)) {
ans[cnt][0] = num;
ans[cnt++][1] = n - num;
}
if(num * 2 != n && check(0, n - num) && check(n - num, num)) {
ans[cnt][0] = n - num;
ans[cnt++][1] = num;
}
printf("%d\n", cnt);
for(int i = 0; i < cnt; i++) {
printf("%d %d\n", ans[i][0], ans[i][1]);
}
}
return 0;
}
C. Dreamoon Likes Coloring
知识点:构造
题意:题目中的$l_i$实际上是给了一个固定长度的块,起点可以是任意合法的点,在赛中花了点时间琢磨。
思路:在不影响前一个的情况下尽可能的往左放,但如果后面的无法填满则要适当的往右移。不合法的情况有两种:当前块必定会影响前面的块;后面的块无法填满后面的区间。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;
int n, m;
LL sum;
int a[MAXN], ans[MAXN];
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
bool pr = true;
if(sum < n) pr = false;//无法填满
for(int i = 1; i <= m; i++) {
if(!pr) break;
if(i + a[i] - 1 > n) pr = false;//一定会影响到前一个
else {
ans[i] = max((LL)i, n - sum + 1);
sum -= a[i];
}
}
if(pr) {
for(int i = 1; i <= m; i++) printf("%d ", ans[i]);
} else puts("-1");
return 0;
}
D. Dreamoon Likes Sequences
知识点:二进制+dp
划重点:a序列和b序列都严格递增
思路:若$b_i=1***$,则$a_{i+1}$应该满足什么条件?首先$a_i < a_{i+1}$,且满足$a_{i+1}>10000$。反证法:若$a_{i+1}$在区间$[1000,1111]$之间,则$b_{i+1}$在区间$[0000,0111]$之间,不满足b序列严格递增的条件;若$a_{i+1}$在区间$[0000,0111]$之间,则前i项里必定存在某个数大于$a_{i+1}$,也不满足a序列严格递增的条件。
结论:应使$a_i$的位数严格递增。问题转化为统计区间$[1,d]$中不同最高位的个数。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;
int t;
LL d, m;
LL ans, cnt[37];
void build() {//最高位为i的有多少个数
LL num = 2, t = 1;
for(int i = 0; i < 32; i++) {
if(d < t) cnt[i] = 0;
else if(d >= num - 1) cnt[i] = t;
else cnt[i] = d - t + 1;
num <<= 1;
t <<= 1;
}
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%lld%lld", &d, &m);
build();
ans = 1;
for(int i = 0; i < 32; i++) {
ans = ans * (cnt[i] + 1) % m;
}
ans = ((ans - 1) % m + m) % m;
printf("%lld\n", ans);
}
return 0;
}
E. Drazil Likes Heap
知识点:堆+贪心
题意:给了一个h阶完全大顶堆,需要删除一部分使得剩下一个g阶完全大顶堆的和最小。
划重点:大顶堆删除一个节点后是该节点的左右孩子中较大的一个上浮,g阶完全大顶堆应该存储在区间$[1,2^g-1]$中。
思路:要使剩下的和最小,贪心能删大的则删大的,关键在于怎么判断一个点能不能删。
- 能不能直接删除尽量大的数?不能。如下图所示,如果直接删除7、6、5、4会得到一个2阶大顶堆,而且和最小,但是存储的位置不对。
- 可以注意到删除根节点后上浮的总是较大的点,也就是说在整颗树中有一条链整体上移了,而这条链可以由dfs找到。如果我们发现链的底端已经在区间$[1,2^g-1]$中了,则该点不能删除,因为删除该点后会使该链再次上移而没有子节点能够补充。如下图所示,如果删除根节点5,则4会上移,左子树为空不符合存储的要求。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 3e6 + 117;
const int MAXM = 2e5 + 117;
int t;
LL sum;
int a[MAXN];
int ans[MAXN], tot;
int h, g, maxnum, tonum;
void init() {
sum = tot = 0;
tonum = 1 << g;
maxnum = 1 << h;
for(int i = 0; i < maxnum * 2; i++) a[i] = 0;
}
int getid(int i) {
if(a[i * 2] == 0 && a[i * 2 + 1] == 0) return i;
if(a[i * 2] >= a[i * 2 + 1]) return getid(i * 2);
return getid(i * 2 + 1);
}
void update(int i) {
if(a[i * 2] == 0 && a[i * 2 + 1] == 0) a[i] = 0;
else if(a[i * 2] >= a[i * 2 + 1]) {
a[i] = a[i * 2];
update(i * 2);
} else {
a[i] = a[i * 2 + 1];
update(i * 2 + 1);
}
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &h, &g);
init();
for(int i = 1; i < maxnum; i++) scanf("%d", &a[i]);
for(int i = 1; i < tonum; i++) {
while(getid(i) >= tonum) {
ans[tot++] = i;
update(i);
}
}
for(int i = 1; i < tonum; i++) sum += a[i];
printf("%lld\n", sum);
for(int i = 0; i < tot; i++) printf("%d ", ans[i]);
putchar(10);
}
return 0;
}
总结
或许是很久没打cf了,又或者是打cf的次数太少了,感觉这一场div2的难度低于自己的预期。然而在赛中码代码的效率和读题的能力仍然不够,例如B题赛中写了完全没必要的前缀和、C题花了40多分钟、D题题意没把握到。幸好正确率还可以,cf的hack机制真是可怕,希望继续保持正确率。
版权属于:小影
本文链接:http://kindkidll.com/index.php/archives/133/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改,但请务必注明文章来源并且不可用于商业目的。