目录
写在前面
战犯在此。
我宣布二周年这首是神。
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=2030210197&auto=0&height=66" width="330"></iframe>以下按个人向难度排序。
G
尺取法,右端点单调右移过程中右移调整左端点,使区间内每种数都至少出现 1 次,4 出现至少 \(k\) 次即可。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 1e5 + 10;
//=============================================================
int n, k, a[kN];
int num, cnt[5];
//=============================================================
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(), k = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
int l = 1, r = 0, ans = n;
while (r < n && num != 4 || cnt[4] < k) {
++ r;
if (cnt[a[r]] == 0) ++ num;
++ cnt[a[r]];
}
for (; r <= n; ) {
while (1) {
if (a[l] != 4) {
if (cnt[a[l]] == 1) break;
} else {
if (cnt[a[l]] == k) break;
}
-- cnt[a[l]];
++ l;
}
if (num == 4 && cnt[4] >= k) ans = std::min(ans, r - l + 1);
++ r;
cnt[a[r]] ++;
}
printf("%d\n", ans);
return 0;
}
D
\(b\) 整除 \(c\),则枚举 \(c\) 的因数即可得到所有可能的 \((a, b)\),检查是否满足条件即可。
H
每次行动结束后的结果是原数列的一段前缀被清空,而清空某一段等价于对这一段做一个 01 背包,那么有个显然的 DP:
首先预处理 \(f_{i, j, k}\) 表示对区间 \([i, j]\) 做容量为 \(k\) 的 01 背包可以获得的最大价值,再设 \(g_{i, j}\) 表示前 \(i\) 次 行动清空了前缀 \(1\sim j\) 可以获得的最大价值,转移时考虑考虑上一次行动结束时空前缀的位置,和这一次行动准备清空哪一段,则有:
\[g_{i, j} = \max\left(\max_{1\le k<i}{\left( g_{i - 1, k} + f_{k + 1, j, sz_i} \right)}, g_{i - 1, j}\right) \]预处理 01 背包时间复杂度 \(O(n^3)\),但是上述转移时间复杂度是 \(O(n^2m)\)的,瓶颈在于 \(m\) 过大。
发现 \(sz\) 递增的结论没用上,又发现至多仅有 \(n\) 个 \(sz\) 是有用的,那么仅需取至多 \(n\) 个最大的 \(sz\) 出来参与上述转移即可。总时间复杂度变为 \(O(n^3)\) 级别。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define pr std::pair
#define mp std::make_pair
#define LL long long
const int kN = 200 + 10;
const int kM = 1e5 + 10;
const LL kInf = 1e15 + 2077;
//=============================================================
int n, m, a[kN], b[kN];
int sznum, sz[kM], useful[kN];
LL f[kN][kN][kN], g[kN][kN];
//=============================================================
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;
}
void Init() {
n = read(), m = read();
for (int i = 1 ;i <= n; ++ i) a[i] = read(), b[i] = read();
for (int i = 1; i <= m; ++ i) sz[i] = read();
sznum = std::min(n, m);
for (int i = 1, j = m - sznum + 1; i <= sznum; ++ i, ++ j) {
useful[i] = sz[j];
}
}
void DPf() {
for (int l = 1; l <= n; ++ l) {
for (int r = l; r <= n; ++ r) {
int c = a[r], v = b[r];
for (int i = 1; i <= 200; ++ i) f[l][r][i] = f[l][r - 1][i];
for (int i = 200; i >= c; -- i) {
f[l][r][i] = std::max(f[l][r][i], f[l][r - 1][i - c] + 1ll * v);
}
for (int i = 1; i <= 200; ++ i) {
f[l][r][i] = std::max(f[l][r][i], f[l][r][i - 1]);
}
}
}
}
void DPg() {
for (int i = 1; i <= sznum; ++ i) {
int s = useful[i];
for (int j = 0; j <= n; ++ j) {
g[i][j] = g[i - 1][j];
for (int k = 0; k < j; ++ k) {
g[i][j] = std::max(g[i][j], g[i - 1][k] + f[k + 1][j][s]);
}
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
// freopen("std.txt", "w", stdout);
Init();
DPf(), DPg();
LL ans = 0;
for (int i = 0; i <= n; ++ i) ans = std::max(ans, g[sznum][i]);
printf("%lld\n", ans);
return 0;
}
C
赛时猜结论过了呃呃,估计八十车人也是这么过的。
数据水了,要不然就被卡死了。
咕一下先。
E
大力手玩题,但是我没脑子,玩不出来呜呜
题目中特别指出了区间要么是相互包含的要么是互不相交的,即所有区间按照包含关系构成了树状结构。在这种限制下逆序对的限制是比较宽松的,发现只要没有限制区间长度为 1 并且钦定逆序对为奇数,都能构造出来。于是我们再另外加入 \(n\) 个长度为 1 的区间,使得这棵树可以覆盖整个排列。
考虑递归地解决问题,钦定区间 \([l, r]\) 为 \(l\sim r\) 的一个排列,然后考虑如何若干个合法的小区间合并为一个大的合法区间。如果大的区间此时也合法那么皆大欢喜,否则考虑做一点小调整。我们考虑这些小区间中相邻的两个 \([l_1, r_1], [r_1 + 1, r_2]\),\([l_1, r_1]\) 是 \(l_1\sim r_1\) 的一个排列,\([r_1 + 1, r_2]\) 是 \(r_1 + 1\sim r_2\) 的一个排列,那么只需交换 \(r_1\) 与 \(r_1 + 1\) 的位置即可在不影响小区间的情况下翻转大区间的奇偶性。
按照上述过程先对限制区间进行排序,再递归解决即可。递归过程中每个限制区间只会访问一次,则总时间复杂度上界是 \(O(n + m)\) 级别的。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 1e3 + 10;
//=============================================================
int n, m, ans[kN], pos[kN];
int num;
struct TMOperaO {
int l, r, w, solved;
} a[kN << 1];
//=============================================================
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;
}
bool cmp(TMOperaO fir_, TMOperaO sec_) {
if (fir_.l != sec_.l) return fir_.l < sec_.l;
return fir_.r > sec_.r;
}
void Dfs(int L_, int R_) {
if (L_ == R_) return ;
int sumw = 0;
for (int i = L_ + 1, j; i <= R_; ++ i) {
if (a[i].solved) continue;
for (j = i; a[j].l <= a[i].r && j <= R_; ++ j);
Dfs(i, j - 1);
sumw += a[i].w;
}
a[L_].solved = 1;
if (sumw % 2 == a[L_].w) return ;
int p1 = L_ + 1;
std::swap(pos[a[p1].r], pos[a[p1].r + 1]);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read(), m = read();
for (int i = 1; i <= m; ++ i) {
int l = read(), r = read(), w = read();
if (l == r && w == 1) {
printf("-1\n");
return 0;
}
if (l == r) continue;
a[++ num] = (TMOperaO) {l, r, w, 0};
}
for (int i = 1; i <= n; ++ i) {
a[++ num] = (TMOperaO) {i, i, 0, 1};
pos[i] = i;
}
std::sort(a + 1, a + num + 1, cmp);
for (int i = 1, j; i <= num; ++ i) {
if (a[i].solved) continue;
for (j = i; a[j].l <= a[i].r && j <= num; ++ j);
Dfs(i, j - 1);
}
for (int i = 1; i <= n; ++ i) ans[pos[i]] = i;
for (int i = 1; i <= n; ++ i) printf("%d ", ans[i]);
return 0;
}
I
哈,这题的核心 idea 我还拿出来出过超级弱化版,我真牛逼:https://www.luogu.com.cn/problem/U150104。
考虑把题目中的式子拆成三段分别考虑。
先做个前缀/后缀异或,区间异或变成了两点异或。然后考虑拆位,枚举 \(r_1\) 的同时统计前缀中某一位为 0/1 的数量,即可求得某个前缀的第一段的贡献,第三段同理。
再考虑中间一段,仍然考虑拆位,枚举 \(r_2\) 的同时统计前缀中某一位为 0/1 的位置的第一段的贡献,统计贡献时将三段相乘即可。不太好描述,详见代码。
总时间复杂度 \(O(n\log v)\) 级别。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const LL p = 998244353;
const int kN = 2e5 + 10;
//=============================================================
int n;
LL a[kN], prea[kN], sufa[kN], presum[kN], sufsum[kN];
LL ans, cntpre[2], cntsuf[2], sum[2];
//=============================================================
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;
}
void Init() {
for (int i = 1; i <= n; ++ i) prea[i] = prea[i - 1] ^ a[i];
for (int i = n; i; -- i) sufa[i] = sufa[i + 1] ^ a[i];
for (int i = 0, j = 1; i <= 30; ++ i, j <<= 1) {
cntpre[0] = cntpre[1] = 0;
for (int k = 0; k <= n; ++ k) {
int l = prea[k] & j ? 1 : 0;
presum[k] = (presum[k] + 1ll * j * cntpre[l ^ 1] % p) % p;
++ cntpre[l];
}
}
for (int i = 1; i <= n; ++ i) presum[i] = (presum[i - 1] + presum[i]) % p;
for (int i = 0, j = 1; i <= 30; ++ i, j <<= 1) {
cntsuf[0] = cntsuf[1] = 0;
for (int k = n + 1; k >= 0; -- k) {
int l = sufa[k] & j ? 1 : 0;
sufsum[k] = (sufsum[k] + 1ll * j * cntsuf[l ^ 1] % p) % p;
++ cntsuf[l];
}
}
for (int i = n; i >= 1; -- i) sufsum[i] = (sufsum[i + 1] + sufsum[i]) % p;
}
void Solve() {
for (int i = 0, j = 1; i <= 30; ++ i, j <<= 1) {
sum[0] = sum[1] = 0;
for (int r2 = 1; r2 < n; ++ r2) {
int l = prea[r2] & j ? 1 : 0;
if (r2 >= 2) {
ans = (ans + sum[l ^ 1] * j % p * sufsum[r2 + 1] % p) % p;
}
sum[l] = (sum[l] + presum[r2]) % p;
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
Init();
Solve();
printf("%lld\n", ans);
return 0;
}
写在最后
学到了什么:
- 多余的物品,有用的物品。
- 有条件没用?再看两眼。
- 预处理大法好。
- 构造某种数量要求的逆序对。