Happy Birthday Elysia !
T1
很有味道的题目
\(dp_i\) 表示到 \(a\) 的第 \(i\) 个数，最多能到 \(b\) 的哪一个数。向后转移能够给到的是一个值域的后缀，离散化后 BIT 维护即可。
代码
#include <iostream>
#include <algorithm>
#define lowbit(x) ((x) & (-(x)))
#define int long long
using namespace std;
int n;
int a[1000005], b[1000005];
int dp[1000005];
struct BIT {
int bit[1000005];
void add(int x, int y) { for (; x <= 1000000; x += lowbit(x)) bit[x] = max(bit[x], y); }
int query(int x) {
int ret = 0;
for (; x; x -= lowbit(x)) ret = max(ret, bit[x]);
return ret;
}
} bit;
int d[1000005], dcnt;
signed main() {
freopen("were.in", "r", stdin);
freopen("were.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], d[i] = a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
sort(d + 1, d + n + 1);
dcnt = unique(d + 1, d + n + 1) - d - 1;
int ans = 0;
for (int i = 0; i <= n; i++) {
dp[i] = bit.query(lower_bound(d + 1, d + dcnt + 1, a[i]) - d);
int x = upper_bound(d + 1, d + dcnt + 1, a[i] * b[dp[i]]) - d;
bit.add(x, dp[i] + 1);
ans = max(ans, dp[i]);
}
cout << ans << "\n";
return 0;
}
T2
东百演说家
这个题比上个题有味道多了。
首先有 \(\begin{cases} xd + y \equiv a + d \\ yd + x \equiv b + d \end{cases} \pmod w\)。当 \(w > 2\) 时，加减可得其等价于 \(\begin{cases} (x + y)(d + 1) \equiv a + b + 2d \\ (x - y)(d - 1) \equiv a - b \end{cases} \pmod w\)。\(w = 2\) 时则平凡。然后考虑 \(d \pm 1\) 的逆元在模 \(w\) 意义下的存在性。若两逆元均存在，则等价于限定了 \(x\) 和 \(y\) 各自模 \(w\) 的余数。把两边的情况数乘起来即可。若两逆元都不存在，则没有任何限制，情况数为值域平方。然后是只有一个逆元不存在的情况，相当于限定了模意义下的和或差，要求方案数。枚举其中一个数，则另一个数可以确定，方案数为值域内模 \(w\) 同余于它的数的个数。容易发现这里的个数只有两种取值，于是可以求出界点然后分讨，然后就做完了。复杂度为 \(\mathcal{O}(T\log w)\)，瓶颈在于求逆元。
代码
#include <iostream>
#define int long long
using namespace std;
inline int qpow(int x, int y, int P) {
int ret = 1;
while (y) {
if (y & 1)
ret = ret * x % P;
y >>= 1;
x = x * x % P;
}
return ret;
}
inline int inv(int x, int P) { return qpow(x, P - 2, P); }
int f(int l, int r, int x, int P) {
l -= x, r -= x;
if (r < 0)
return 0;
if (l <= 0)
return r / P + 1;
else
return r / P - (l - 1) / P;
}
int calc(int l1, int r1, int l2, int r2) {
if (l1 <= l2 && r2 <= r1)
return r2 - l2 + 1;
if (l2 <= l1 && r1 <= r2)
return r1 - l1 + 1;
if (l1 > l2)
swap(l1, l2), swap(r1, r2);
return max(0ll, r1 - l2 + 1);
}
inline int M(int x, int y) { return x % y == 0 ? y : x % y; }
int Solve(int m, int d, int w, int a, int b) {
int lim = min(m, d), ans = 0, ls, ld;
// for (int i = 1; i <= lim; i++) {
// for (int j = 1; j <= lim; j++)
// ans += ((i * d + j) % w == (a + d) % w) && ((j * d + i) % w == (b + d) % w);
// }
// return ans;
if (w == 2) {
// x = 0, y = 0
if (0 == (a + d) % w && 0 == (b + d) % 2)
ans += (lim / 2) * (lim / 2);
// x = 0, y = 1
if (1 == (a + d) % w && d % 2 == (b + d) % 2)
ans += (lim / 2) * ((lim + 1) / 2);
// x = 1, y = 0
if (d % 2 == (a + d) % w && 1 == (b + d) % 2)
ans += ((lim + 1) / 2) * (lim / 2);
// x = 1, y = 1
if ((d + 1) % 2 == (a + d) % w && (d + 1) % 2 == (b + d) % 2)
ans += ((lim + 1) / 2) * ((lim + 1) / 2);
return ans;
}
if ((d + 1) % w == 0) {
if ((a + b + 2 * d) % w != 0)
return 0;
ls = -1;
} else
ls = (a + b + 2 * d) * inv(d + 1, w) % w;
if ((d - 1) % w == 0) {
if ((a - b) % w != 0)
return 0;
ld = -1;
} else {
ld = (a - b) * inv(d - 1, w) % w;
ld = (ld + w) % w;
}
if (ls == -1 && ld == -1)
return lim * lim;
// cout << "sdf\n";
if (ls == -1) {
// for (int x = 0; x < w; x++)
// ans += f(1, lim, x, w) * f(1, lim, (x + ld) % w, w);
int p = M(lim, w), a = (lim - 1) / w + 1, b = a - 1, c = 0, r = w;
int ll = M(1 + ld, w), rr = M(p + ld, w);
(ll <= rr) ? (c = calc(1, p, ll, rr)) : (c = calc(1, p, ll, w) + calc(1, p, 1, rr));
r -= c;
ans += c * a * a;
if (p != w) {
++p;
ll = M(p + ld, w), rr = M(w + ld, w);
(ll <= rr) ? (c = calc(p, w, ll, rr)) : (c = calc(p, w, ll, w) + calc(p, w, 1, rr));
r -= c;
ans += c * b * b;
}
ans += r * a * b;
return ans;
} else if (ld == -1) {
// for (int x = 0; x < w; x++)
// ans += f(1, lim, x, w) * f(1, lim, (ls - x + w) % w, w);
int p = M(lim, w), a = (lim - 1) / w + 1, b = a - 1, ll = M(w + ls - p, w), rr = M(w + ls - 1, w), r = w, c;
(ll <= rr) ? (c = calc(1, p, ll, rr)) : (c = calc(1, p, ll, w) + calc(1, p, 1, rr));
r -= c;
ans += c * a * a;
if (p != w) {
++p;
ll = M(w + ls - w, w), rr = M(w + ls - p, w);
(ll <= rr) ? (c = calc(p, w, ll, rr)) : (c = calc(p, w, ll, w) + calc(p, w, 1, rr));
r -= c;
ans += c * b * b;
}
ans += r * a * b;
return ans;
} else {
// cout << "asdf\n";
// cout << ls << " " << ld << "\n";
int x = (ls + ld) * inv(2, w) % w;
int y = (ls - ld + w) * inv(2, w) % w;
// cout << x << " " << y << "\n";
return f(1, lim, x, w) * f(1, lim, y, w);
}
return 0;
}
signed main() {
freopen("speech.in", "r", stdin);
freopen("speech.out", "w", stdout);
int tc;
cin >> tc;
while (tc--) {
int m, d, w, a, b;
cin >> m >> d >> w >> a >> b;
cout << Solve(m, d, w, a, b) << "\n";
}
return 0;
}
T3
不朽之蜍
应该想到求的其实是所有（数）字牌被第一次摸到的时间的最大值。可以考虑 min-max 容斥。那么现在我们钦定 \(n - k\) 张字牌变成鬼牌，要求此时一轮游戏终结时的期望轮数。可以列出式子 \(f(k) = \sum\limits_{i = 1}^{k} \frac{k^{\underline{i}}}{(n + m)^{\underline{i}}}\)。推一下式子会发现这个就等于 \(\frac{k}{n + m - k + 1}\)。然后在一轮结束时抽到的可能不是字牌变的鬼牌，因此要乘上 \(\frac{m + k}{k}\) 表示期望这么多轮结束后能抽到字牌变的鬼牌而结束。再套上 min-max 容斥的式子即可。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 19260817;
int f[1000005];
int fac[2000005], ifac[2000005], inv[2000005];
void Cpre(int n) {
fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * i % P;
inv[i] = (P - P / i) * inv[P % i] % P;
ifac[i] = ifac[i - 1] * inv[i] % P;
}
}
inline int C(int n, int m) { return fac[n] * ifac[m] % P * ifac[n - m] % P; }
int n, m, ans;
signed main() {
freopen("toad.in", "r", stdin);
freopen("toad.out", "w", stdout);
Cpre(2000000);
cin >> n >> m;
for (int i = 0; i < n; i++) f[i] = i * inv[n + m - i + 1] % P;
for (int i = 1; i <= n; i++) {
int x = (f[n - i] + 1) * (m + i) % P * inv[i] % P * C(n, i) % P;
i & 1 ? (ans += x) : (ans -= x);
}
cout << (ans % P + P) % P << "\n";
return 0;
}
T4
大战杀马特
容易想到超级钢琴套路。在这个题中，我们考虑把一维变成二维，每次求出一个矩形中的最优决策，然后分出更多决策。这里我们能算的是两维的区间完全相同和互不相交的情况，于是只需要保证每次分出的矩形都符合这两个条件即可。
代码
#include <iostream>
#include <cassert>
#include <queue>
#include <array>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
struct node {
array<int, 2> mx, mn;
array<int, 3> ans;
int tg;
void tag(int v) { mx[0] += v, mn[0] += v, tg += v; }
} T[400005];
int n, m;
int a[100005];
node operator+(node a, node b) {
node c;
c.mx = max(a.mx, b.mx), c.mn = min(a.mn, b.mn);
c.ans = max((array<int, 3>) { a.mx[0] - b.mn[0], a.mx[1], b.mn[1] }, max(a.ans, b.ans));
c.tg = 0;
return c;
}
struct Segment_Tree {
void pushdown(int o) {
if (!T[o].tg)
return;
T[o << 1].tag(T[o].tg);
T[o << 1 | 1].tag(T[o].tg);
T[o].tg = 0;
}
void Build(int o, int l, int r) {
if (l == r) {
T[o].mx[0] = T[o].mn[0] = a[l];
T[o].mx[1] = T[o].mn[1] = T[o].ans[1] = T[o].ans[2] = l;
return;
}
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
T[o] = T[o << 1] + T[o << 1 | 1];
}
void Add(int o, int l, int r, int L, int R, int v) {
if (L <= l && r <= R)
return T[o].tag(v);
pushdown(o);
int mid = (l + r) >> 1;
if (L <= mid)
Add(o << 1, l, mid, L, R, v);
if (R > mid)
Add(o << 1 | 1, mid + 1, r, L, R, v);
T[o] = T[o << 1] + T[o << 1 | 1];
}
node Query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return T[o];
pushdown(o);
int mid = (l + r) >> 1;
if (R <= mid)
return Query(o << 1, l, mid, L, R);
if (L > mid)
return Query(o << 1 | 1, mid + 1, r, L, R);
return Query(o << 1, l, mid, L, R) + Query(o << 1 | 1, mid + 1, r, L, R);
}
} seg;
inline array<int, 3> K1(int l, int r) { return seg.Query(1, 1, n, l, r).ans; }
struct X {
int l1, r1, l2, r2;
array<int, 3> v;
};
inline bool operator<(X a, X b) { return a.v[0] < b.v[0]; }
priority_queue<X> q;
void push(int l1, int r1, int l2, int r2) {
if (l1 == l2)
q.push((X) { l1, r1, l2, r2, K1(l1, r2) });
else {
array<int, 2> a = seg.Query(1, 1, n, l1, r1).mx;
array<int, 2> b = seg.Query(1, 1, n, l2, r2).mn;
q.push((X) { l1, r1, l2, r2, (array<int, 3>) { a[0] - b[0], a[1], b[1] } });
}
}
int Query(int L, int R, int k) {
while (!q.empty()) q.pop();
push(L, R, L, R);
int ret = 0;
while (k--) {
assert(q.size());
X tmp = q.top();
q.pop();
ret += tmp.v[0];
int x = tmp.v[1], y = tmp.v[2];
if (tmp.l1 == tmp.l2) {
int l = tmp.l1, r = tmp.r2;
if (l != x) {
push(l, x - 1, l, x - 1);
push(l, x - 1, x, r);
}
if (x != y)
push(x, x, x, x);
if (x + 1 < y)
push(x, x, x + 1, y - 1);
if (y != r)
push(x, x, y + 1, r);
if (x != r)
push(x + 1, r, x + 1, r);
} else {
if (x != tmp.l1)
push(tmp.l1, x - 1, tmp.l2, tmp.r2);
if (y != tmp.l2)
push(x, x, tmp.l2, y - 1);
if (y != tmp.r2)
push(x, x, y + 1, tmp.r2);
if (x != tmp.r1)
push(x + 1, tmp.r1, tmp.l2, tmp.r2);
}
}
return ret;
}
signed main() {
freopen("smart.in", "r", stdin);
freopen("smart.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
seg.Build(1, 1, n);
while (m--) {
int op, k, x, y;
cin >> op >> x >> y >> k;
if (op == 2)
cout << Query(x, y, k) << "\n";
else
seg.Add(1, 1, n, x, y, k);
}
return 0;
}
在第二题上花的时间太长了。还是分讨能力不行。
标签：20241111,tmp,r2,int,l2,l1,push From： https://www.cnblogs.com/forgotmyhandle/p/18540529