写在前面
我是飞舞。
A
随便做。
B
发现每一个长度为 \(i\) 的区间中至少有 1 个 \(i\) 的倍数，于是仅需检查能整除 \(n\) 的最长的 \(1\sim n\) 的前缀即可。
C1/C2
一个显然的想法是先让所有数同正/同负，再做前缀和/后缀和。
如果某种数的数量不多于 7 个，考虑将这种数变另一种。有 \(2^5=32 > 20\)，则可以通过不多于 5 次操作构造出一个极大/极小值，再用这个极大/极小值对进行操作即可统一符号。此时所需次数上限为 7 + 5 + 19 = 31。
否则两种数的数量肯定都不多于 12，考虑将所有数变为绝对值最大的数，则所需次数上限为：12 + 19 = 31。
代码实现时没有显式地区分上面两种情况，而是对每种数都尝试构造绝对值最大的数并统一符号后取了最小值。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define pr std::pair
#define mp std::make_pair
const int kInf = 1e5 + 10;
//=============================================================
int n, a[50];
int maxa = -kInf, mina = kInf, maxx;
int posmaxa, posmina;
std::vector <pr <int, int> > ansp, ansn;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
int Solvep() {
ansp.clear();
int pos = posmaxa, temp = maxa;
while (temp < abs(mina)) {
temp *= 2;
ansp.push_back(mp(pos, pos));
}
for (int i = 1; i <= n; ++ i) {
if (a[i] < 0) ansp.push_back(mp(i, pos));
}
for (int i = 2; i <= n; ++ i) ansp.push_back(mp(i, i - 1));
return ansp.size();
}
int Solven() {
ansn.clear();
int pos = posmina, temp = mina;
while (abs(temp) < abs(maxa)) {
temp *= 2;
ansn.push_back(mp(pos, pos));
}
for (int i = 1; i <= n; ++ i) {
if (a[i] > 0) ansn.push_back(mp(i, pos));
}
for (int i = n - 1; i; -- i) ansn.push_back(mp(i, i + 1));
return ansn.size();
}
void Solve() {
bool allpos = 1, allneg = 1;
maxa = -kInf, mina = kInf, maxx;
for (int i = 1; i <= n; ++ i) {
if (a[i] > 0) allneg = 0;
if (a[i] < 0) allpos = 0;
if (a[i] < mina) mina = a[i], posmina = i;
if (a[i] > maxa) maxa = a[i], posmaxa = i;
}
if (allpos) {
printf("%d\n", n - 1);
for (int i = 2; i <= n; ++ i) printf("%d %d\n", i, i - 1);
return ;
}
if (allneg) {
printf("%d\n", n - 1);
for (int i = n - 1; i; -- i) printf("%d %d\n", i, i + 1);
return ;
}
maxx = std::max(abs(maxa), abs(mina));
int cntp = Solvep(), cntn = Solven();
if (cntp < cntn) {
printf("%d\n", cntp);
for (int i = 0, sz = ansp.size(); i < sz; ++ i) {
printf("%d %d\n", ansp[i].first, ansp[i].second);
}
} else {
printf("%d\n", cntn);
for (int i = 0, sz = ansn.size(); i < sz; ++ i) {
printf("%d %d\n", ansn[i].first, ansn[i].second);
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
Solve();
}
return 0;
}
D
发现操作次序无关。考虑先进行若干拓展解锁操作再进行取价值操作。
考虑在牌堆后面加 \(n\) 个 0 来处理拓展过头的问题，显然，如果可以恰好拓展解锁到 \(i\) 并在 \(i\) 处停止拓展并取所有的价值，那么所得价值一定为 \(\sum_{j = 1}^{i} a_i - i + 1\)。于是仅需考虑能否拓展到某个位置。
很容易想到 \(O(n^2)\) 的背包，设 \(f_{i, j}\) 表示使用前 \(i\) 张牌能否恰好解锁到位置 \(j\)（即 \(j\) 作为某次拓展解锁的终点），初始化 \(f_{0, 1} = \text{true}\)，转移时考虑对第 \(i\) 张牌使用后的影响，则有：
特别地需要置零 \(f_{i, i}\)，表示位置 \(i\) 上的牌已经消失了（用于拓展了），这之后位置 \(i\) 已经不会产生贡献了。
在每次转移之前检查 \(f_{i, i} = \text{true}\) 是否成立，如果成立则答案与 \(\sum_{j = 1}^{i} a_i - i + 1\) 取最大值。
发现这玩意可以用 bitset 优化，总时间复杂度变为 \(O\left(\frac{n^2}{w}\right)\) 级别。呃呃然后就能跑 \(10^5\) 了，太厉害啦！
//
/*
By:Luckyblock
*/
#include <cmath>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, a[kN << 1];
LL ans, sum[kN << 1];
std::bitset <kN << 1> f;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
sum[i] = sum[i - 1] + a[i];
}
ans = a[1];
f.set(1);
for (int i = 1; i <= n; ++ i) {
if (f.test(i)) ans = std::max(ans, sum[i] - i + 1);
f |= f << a[i];
f.reset(i);
}
for (int i = n + 1; i <= 2 * n; ++ i) {
if (f.test(i)) ans = std::max(ans, sum[n] - i + 1);
}
printf("%lld\n", ans);
return 0;
}
写在最后
学到了什么：
bitset太厉害啦
我是飞舞。