CF-Codeforces Round #210 (Div. 1)-A-Levko and Array Recovery

2019-11-06 07:52:10

字体：大中小

来源：转载

供稿：网友

ACM模版

描述

题解

像我这样的渣渣，怎么可能有 Div.1 的门票，完全是一个网友找我帮他参谋这道题，才有机会看 Div.1，这是一道有坑的问题，还好被我瞎猫逮着死耗子，碰对了。

英文题，最让我头疼，还好网友给我大致翻译了一下，我第一结论，这是个逆向思维的问题，需要反推，但是，随后我就陷入了死胡同，怎么推啊？想来想去，还好我不是意志坚定的人，我放弃了逆向思维，想到了一个正向收缩区间的思路，给 a[i] 初始化一个特别大的区间，然后正向推，不断收缩区间，最后在区间内输出一组解后即可，但是后来发现，首先我想着区间就有问题，因为这里有的需要满足最大值等于 d，那么区间内的数就不是随便取的就可以满足最后结果，那么我们求区间的意义何在呢？这里的操作除了加法外，只让求最大值，那么我想，这里我们完全可以忽略下界，只考虑上界，初始化 a[i] 一个无穷大的数作为上界，然后不断收缩上界，最后我们只需要把得到的 a 数组作为结果正向执行操作检验一次即可判断是否为 NO。可是这时我却 WA ON 3，挂在了第三组，陷入了一个数据范围的坑，我设置的 INF 为 0x3f3f3f3f，大于题目要求的 10^9，所以对于有些特殊的数据，比如说第三组，存在某一个（或多个）位置的数没有对 m 次操作产生大的影响，所以最后仍然为 INF，那么就不符合题意了，自然 WA，所以呢，最后统一进行一下判断是否为 INF 即可 AC 之。

我想，这个够详细了吧……虽然废话占了一大半。

代码

#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int MAXN = 5e4 + 10;const int INF = 0x3f3f3f3f;int n, m;int a[MAXN], cnt[MAXN];int op[MAXN], l[MAXN], r[MAXN], d[MAXN];int main(){ memset(a, 0x3f, sizeof(a)); memset(cnt, 0, sizeof(cnt)); cin >> n >> m; for (int i = 0; i < m; i++) { scanf("%d%d%d%d", op + i, l + i, r + i, d + i); if (op[i] == 1) { for (int j = l[i]; j <= r[i]; j++) { cnt[j] += d[i]; } } else { for (int j = l[i]; j <= r[i]; j++) { a[j] = min(a[j], d[i] - cnt[j]); } } } for (int i = 1; i <= n; i++) { if (a[i] == INF) { cnt[i] = a[i] = 0; } else { cnt[i] = a[i]; } } for (int i = 0; i < m; i++) { if (op[i] == 1) { for (int j = l[i]; j <= r[i]; j++) { cnt[j] += d[i]; } } else { int MAX_ = -INF; for (int j = l[i]; j <= r[i]; j++) { MAX_ = max(MAX_, cnt[j]); } if (MAX_ != d[i]) { PRintf("NO/n"); return 0; } } } printf("YES/n"); for (int i = 1; i < n; i++) { printf("%d ", a[i]); } printf("%d/n", a[n]); return 0;}

上一篇：关于servlet中getParameterValues()的报错问题

下一篇：第一周作业2

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注