平衡树(线段树 / 树状数组二分),AC 自动机 + zkw 线段树,状压 dp
# A. 工作
考场上怒调 3h 平衡树 + 启发式合并,然后脑子短路了,硬是没想到正解。
事实上你只需要维护一棵平衡树,支持查询前 大数的和,区间 -1,快速维护区间 -1 之后树的形态。
前两个操作就不多说了,下面来看一下第三个操作。
我们是对最大的 个数进行的区间 -1,由于只减去了 1,所以可以分两种情况讨论:
第 大的数大于第 大的数,那么 -1 之后依然满足平衡树的性质,无需进行额外操作。
第 大数等于第 大的数。这种情况下有可能有好多数都相同。假设第 大数权值为 ,且第 大的数以及第 大的数均为 。
此时我们有两棵树(前 和 ),当把 大的数减 1 之后,它们会小于原本排在 的数,所以我们把这两棵树拆成四棵树,即数的排名为 的四棵树,设四棵树的根分别为 。
这时 已经小于 了,所以把 和 合并,再把 和 合并,最后再合并到一起即可。
然后这题就变成板子了。
但是这题比较卡常,朴素写法得跑 2s 多,考虑优化建树过程。
不难发现,插数顺序并不影响我们的树,所以直接对输入的 排个序,然后直接 即可,也就是对于每个数省掉了一次 ,然后就可以卡过了。
#include <bits/stdc++.h> | |
#define ls(x) ch[x][0] | |
#define rs(x) ch[x][1] | |
#define ll long long | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0, f = 1; | |
char ch = getchar(); | |
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x * f; | |
} | |
template <typename T> inline void write(T x){ | |
if(x < 0) putchar('-'), x = -x; | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 5e5 + 10; | |
int n, m, root, tot; | |
int v[N]; | |
ll sum[N]; | |
int siz[N], val[N], ch[N][2], wei[N], tag[N]; | |
inline void pushup(int x){ | |
sum[x] = sum[ls(x)] + sum[rs(x)] + val[x]; | |
siz[x] = siz[ls(x)] + siz[rs(x)] + 1; | |
} | |
inline void pushtag(int x, int k){ | |
tag[x] += k, val[x] -= k, sum[x] -= 1ll * siz[x] * k; | |
} | |
inline void pushdown(int x){ | |
if(tag[x]){ | |
if(ls(x)) pushtag(ls(x), tag[x]); | |
if(rs(x)) pushtag(rs(x), tag[x]); | |
tag[x] = 0; | |
} | |
} | |
inline void split_siz(int x, int k, int &a, int &b){ | |
if(!x) return a = b = 0, void(); | |
pushdown(x); | |
if(siz[ls(x)] + 1 <= k) a = x, split_siz(rs(x), k - siz[ls(x)] - 1, rs(x), b); | |
else b = x, split_siz(ls(x), k, a, ls(x)); | |
pushup(x); | |
} | |
inline void split_val(int x, int k, int &a, int &b){ | |
if(!x) return a = b = 0, void(); | |
pushdown(x); | |
if(val[x] <= k) a = x, split_val(rs(x), k, rs(x), b); | |
else b = x, split_val(ls(x), k, a, ls(x)); | |
pushup(x); | |
} | |
inline int merge(int x, int y){ | |
if(!x || !y) return x | y; | |
if(wei[x] <= wei[y]){ | |
rs(x) = merge(rs(x), y); | |
return pushup(x), x; | |
}else{ | |
ls(y) = merge(x, ls(y)); | |
return pushup(y), y; | |
} | |
} | |
inline int newnode(int k){ | |
siz[++tot] = 1, val[tot] = k, wei[tot] = rand(), sum[tot] = k; | |
return tot; | |
} | |
inline void Union(int x, int y){ | |
int a, b, c, d; | |
split_siz(y, 1, a, b); | |
int tmp = val[a]; | |
y = merge(a, b); | |
split_val(y, tmp, a, b); | |
split_val(x, tmp - 1, c, d); | |
root = merge(merge(c, a), merge(d, b)); | |
} | |
ll ans = 0; | |
inline void solve(int k){ | |
int a = 0, b = 0; | |
split_siz(root, n - k, a, b); | |
ans += sum[b], tag[b]++, val[b]--, sum[b] -= siz[b]; | |
Union(a, b); | |
} | |
signed main(){ | |
// freopen("A.in", "r", stdin); | |
// freopen("A.out", "w", stdout); | |
n = read(); | |
for(int i = 1; i <= n; ++i) v[i] = read(); | |
sort(v + 1, v + 1 + n); | |
for(int i = 1; i <= n; ++i) root = merge(root, newnode(v[i])); | |
// cout << "insert" << endl; | |
m = read(); | |
for(int i = 1; i <= m; ++i) solve(read()); | |
write(ans), puts(""); | |
return 0; | |
} | |
// X.K. |
然后再简单说说 神仙的思路,还是查询前 大的数的和,然后区间减 1,同样是上面的讨论。假设 的数都相同, 的数减 1 之后不再是前 大。
这时候我们考虑不去减这些数,而是去减排名为 的数。
容易证明,这样效果是一样的,而且不会破坏现有的递增的关系,可以继续进行接下来的操作。
# B. 大水题
思路过于神仙,代码也不会写,咕咕咕。
# C. 榜滚 (ranklist)
是 21 年联合省选「滚榜」的不知道加强版还是弱化版,暴力全排列的话还是可以取得 45pts 的好成绩。
思路其实是差不多的,但是状态跟那道题略有不同。
设 表示状态为 的人,当前这个人比上一个人多过了 道题,总共消耗了 道题。
这道题由于给出了一个 值,所以不 的那些人题数必须严格多余之前的。
然后赋初值,转移即可,刷表法可能要好写一些。
#include <bits/stdc++.h> | |
#define uint unsigned int | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0, f = 1; | |
char ch = getchar(); | |
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x * f; | |
} | |
template <typename T> inline void write(T x){ | |
if(x < 0) putchar('-'), x = -x; | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 14; | |
int n, m, K, mx; | |
int a[N], luck[N]; | |
int dp[1 << N][N][511]; | |
signed main(){ | |
n = read(), m = read(), K = read(); | |
for(int i = 0; i < n; ++i) mx = max(mx, a[i] = read()); | |
for(int i = 1; i <= K; ++i) luck[read() - 1] = 1; | |
for(int i = 0; i < n; ++i){ | |
int t = ((mx == a[i]) || (!luck[i])); | |
int b = mx - a[i] + t; | |
if(b <= m) dp[1 << i][t][b] = 1; | |
} | |
for(int s = 0; s < (1 << n); ++s) | |
for(int i = 0; i <= n; ++i) | |
for(int j = 1; j <= m; ++j) | |
if(dp[s][i][j]) | |
for(int k = 0; k < n; ++k) | |
if(!((s >> k) & 1)){ | |
int t = i + ((mx + i == a[k]) || (!luck[k])); | |
int b = mx - a[k] + t; | |
if(j + b <= m) dp[s | (1 << k)][t][j + b] += dp[s][i][j]; | |
} | |
uint ans = 0; | |
for(int i = 1; i <= n; ++i) | |
for(int j = 1; j <= m; ++j) ans += dp[(1 << n) - 1][i][j]; | |
write(ans), puts(""); | |
return 0; | |
} | |
// X.K. |