翻车笔记_ BZOJ3043 IncDec Sequence [差分, 清奇脑回路, 翻车]

脑洞非常重要

懵逼的 题目

传送至 BZOJ

扯淡的 题解

癌…最近刷不动难题了…然后想找点水题都被虐…Van♂了全™Van♂了…(顺便为王的驾崩默哀一下)

很早之前就听(REfun神犇)说一种统计[区间±1将一个序列变为一个数]的最小次数的方法…差分然后乱搞…然而今天还是翻车车了…

这个题…先差分一下…我们就发现…在差分后的数列上, 区间的加一减一操作其实就转化为了在一个数上加一, 然后在另一个数上减一, 那么题目就转化为了如何把一个序列除了第一个数变成全零(这样第一个数其实就是更改后整个序列的数值)

显然最小的次数就是把所有的正数加起来, 记为$X_1$, 负数的绝对值也加起来记为$X_2$, 答案就是$max(X_1, X_2)$, 因为在将一个数的绝对值变小的时候一定可以顺便将另一个数(符号与之相反)的绝对值变小(当然也可以不变是吧, 就是从头加或者加到最后)

然后就是方案…一开始当成是求加减顺序的方案WA了好几发…然后我们发现, 其实最后序列的方案数就是b[1]可能的值, 显然就是$X_1 + X_2 + 1$…分别代表 把全部正数的影响放在b[1]上 && 把全部负数的影响放在b[1]上 && 不变 时b[1]取值有多少种可能…

沙茶的 代码

癌我真是太菜了…

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
/**************************************************************
Problem: 3043
User: Cansult
Language: C++
Result: Accepted
Time:324 ms
Memory:2852 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define LL long long
#define abs(a) ((a) > 0 ? (a) : (-(a)))
#define pll pair<LL, LL>
using namespace std;
int n;
LL a[MAXN], f[MAXN];
pll ans;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), f[i] = a[i] - a[i - 1];
for (int i = 2; i <= n; i++)
if (f[i] > 0)
ans.first += f[i];
else
ans.second += f[i];
printf("%lld\n", max(ans.first, -ans.second));
printf("%lld", abs((LL)ans.first + ans.second) + 1);
return 0;
}

By 脑浆炸裂的 Cansult