A 青蛙
题目大意 : 给定d,如果第 i 只青蛙的某次跳跃的距离超过 d,那么需要付出 (c_i) 的代价,只有给定的石头可以跳,且只能跳一次,不能不跳,问全部青蛙过河的最小费用
-
首先想到先让花费大的跳给定的石头,让他们免费跳,最后没石头了花费小的再跳
-
发现如果有一只可以免费跳过去,那么可以保证所有的都跳过去
-
所以求出最多可以免费跳过 m 只青蛙,让费用最大的 m 只青蛙免费跳过并踩掉所有石头、剩下的青蛙直接从 1 跳到 n。
-
如果 m 为 0,那就先让费用最小的把所有石头都踩掉就好了
-
如果1 和 n 之间的距离小于 d,那全部青蛙都可以免费跳过了
-
至于如何求 m,这就是之前的一道青蛙过河的原题了
-
看每个从1不能到的石头有几个前面的石头可以到自己,取个min就是m
Code
Show Code
#include <cstdio>
#include <algorithm>
const int N = 1e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int m, n, k, d, p[N];
long long s[N], ans;
int main() {
for (int T = read(); T; --T) {
m = read(), n = read(); k = read() + 2; d = read(); ans = 0;
for (int i = 1; i <= n; ++i) s[i] = read();
for (int i = 2; i < k; ++i) p[i] = read();
p[1] = 1; p[k] = m;
std::sort(s + 1, s + n + 1);
std::sort(p + 1, p + k + 1);
for (int i = 1; i <= n; ++i) s[i] += s[i-1];
for (int i = 1; i <= k; ++i)
if (p[i] > d + 1) m = std::min(m, p + i - std::lower_bound(p + 1, p + i, p[i] - d));
if (m) ans = s[1];
else {
for (int i = 2; i <= k; ++i)
if (p[i] - p[i-1] > d) ans += s[1];
}
printf("%lld
", 1 + d >= p[k] ? 0ll : ans + s[n-m] - s[1]);
}
return 0;
}
B 蚯蚓排队
题目大意 : 动态连接字符串,回答一个字符串的出现次数
- 因为 k 只有 50,每次连接断开的时候枚举每个改变的字符串在哈希表里更新就好了
Code
Show Code
#include <cstdio>
#include <cstring>
typedef unsigned long long ull;
const int N = 2e5 + 5, M = 998244353, bs = 13331;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
struct Hash {
#define M 5000000
int h[M], n[M], t[M], hac; ull w[M];
int & operator [] (ull ha) {
int x = ha % M;
for (int i = h[x]; i; i = n[i])
if (w[i] == ha) return t[i];
w[++hac] = ha; n[hac] = h[x]; h[x] = hac;
return t[hac];
}
#undef M
}mp;
int n, m, a[N], l[N], r[N], len;
char c[N*50];
ull P[55];
void Update(int x, int w) {
ull s1 = 0, s2;
for (int p = x, i = 0; p && i <= 48; p = l[p], ++i) {
s1 += a[p] * P[i]; s2 = s1;
for (int q = r[x], j = i + 2; q && j <= 50; q = r[q], ++j)
s2 = s2 * bs + a[q], mp[s2] += w;
}
}
int main() {
n = read(); m = read(); P[0] = 1;
for (int i = 1; i <= n; ++i) a[i] = read(), mp[a[i]]++;
for (int i = 1; i <= 50; ++i) P[i] = P[i-1] * bs;
while (m--) {
int od = read();
if (od == 1) {
int x = read(), y = read();
r[x] = y; l[y] = x; Update(x, 1);
}
else if (od == 2) {
int x = read(), y = r[x];
Update(x, -1); r[x] = l[y] = 0;
}
else {
scanf("%s", c + 1); len = strlen(c + 1);
int k = read(), ans = 1; ull s = 0;
for (int i = 1; i <= len; ++i) {
s = s * bs + (c[i] -= '0');
if (i >= k) ans = 1ll * ans * mp[s-=P[k]*c[i-k]] % M;
}
printf("%d
", ans);
}
}
return 0;
}
C 最大价值
题目大意 : 从n个物品里选i个使价值最大
-
因为如果第i个物品放在第j位,他的贡献是(j-1)*a[i]+b[i],所以a越大放的位置越靠后,所以先按a排序
-
然后就可以n2的Dp了,f[i][j]=max(f[i-1][j],f[i-1][j-1]+(j-1)*a[i]+b[i])
-
会发现一个事情,如果第i件物品放在第j位比前面找出来的方案更优,那第i件放在第j+1到i位都可以更优
-
然后看差分数组,发现前面的不变,只是在第一次改变的地方j这里,差分数组插入了一个(j-1)*a[i]+b[i],然后后面的都加a[i]
-
于是可以有Splay维护差分数组进行DP
Code
Show Code
#include <cstdio>
#include <algorithm>
#define Get(x) (ch[fa[x]][1] == x)
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
ll read(ll x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, a[N], p[N], fa[N], sz[N], ch[N][2], rt, stk[N], tp;
ll b[N], w[N], tag[N], ans;
bool Cmp(int x, int y) {
return a[x] < a[y];
}
void Pushup(int x) {
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
void Rotate(int x) {
int y = fa[x], z = fa[y], k = Get(x), B = ch[x][k^1];
ch[z][Get(y)] = x; fa[x] = z;
ch[x][k^1] = y; fa[y] = x;
ch[y][k] = B; fa[B] = y;
Pushup(y); Pushup(x);
}
void Update(int x, ll v) {
w[x] += v, tag[x] += v;
}
void Pushdown(int x) {
if (!tag[x]) return;
Update(ch[x][0], tag[x]);
Update(ch[x][1], tag[x]);
tag[x] = 0;
}
void Splay(int x) {
for (int i = x; i; i = fa[i]) stk[++tp] = i;
while (tp) Pushdown(stk[tp--]);
while (fa[x] != 0) {
int y = fa[x];
if (fa[y] != 0) Get(x) != Get(y) ? Rotate(x) : Rotate(y);
Rotate(x);
}
rt = x;
}
void Print(int x) {
if (!x) return;
Pushdown(x);
Print(ch[x][0]);
printf("%lld
", ans += w[x]);
Print(ch[x][1]);
}
int main() {
n = read();
for (int i = 1; i <= n; ++i)
a[i] = read(), b[i] = read(), p[i] = i;
sort(p + 1, p + n + 1, Cmp);
w[1] = b[p[1]]; rt = 1;
for (int i = 2; i <= n; ++i) {
int x = rt, s = 0, lt, k;
while (x) {
Pushdown(lt = x);
if (w[x] < 1ll * (s + sz[ch[x][0]]) * a[p[i]] + b[p[i]]) k = 0;
else k = 1, s += sz[ch[x][0]] + 1;
x = ch[lt][k];
}
ch[lt][k] = i; fa[i] = lt; w[i] = 1ll * s * a[p[i]] + b[p[i]];
Splay(i); Update(ch[i][1], a[p[i]]);
}
Print(rt); return 0;
}