邮寄
核爆赛，拿完暴力走人了......
A（由于题目名称为“我是 A 题”所以省略，下同）
我们处理掉整个整个的 \(A \times B\) 的面，然后从上往下倒序枚举 C。
当枚举到一个 C 时，我们把这个 C 独有的贡献加上去（这就是为什么要倒序枚举 C）。
由于本题数据太水，暴力可过。理论上可以线段树优化，但是我不会。
#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
using i128 = __int128_t;
int n, a[30000030], b[30000030], c[30000030], A, B, C, hst, mh[30000030];
u64 x, y;
i128 ans;
u64 twist(u64 &x, u64 &y) {
u64 u = x, v = y;
x = v;
u ^= u << 23;
y = u ^ v ^ (u >> 17) ^ (v >> 26);
return v + y;
}
void write(i128 x) {
if(!x) {
return ;
}
write(x / 10);
cout.put(x % 10 + '0');
}
int main() {
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
cin >> n >> A >> B >> C >> x >> y;
for(int i = 1; i <= n; i++) {
a[i] = twist(x, y) % A + 1;
b[i] = twist(x, y) % B + 1;
c[i] = twist(x, y) % C + 1;
if(twist(x, y) % 3 == 0) {
a[i] = A;
}
if(twist(x, y) % 3 == 0) {
b[i] = B;
}
if(a[i] != A && b[i] != B) {
c[i] = C;
}
if(a[i] == A && b[i] == B) {
hst = max(hst, c[i]);
}
}
ans = (i128)(A) * B * hst;
for(int r = C; r > hst; r--) {
for(int i = 1; i <= n; i++) {
if(c[i] == r) {
mh[a[i]] = max(mh[a[i]], b[i]);
}
}
for(int i = A; i >= 1; i--) {
mh[i] = max(mh[i], mh[i + 1]);
ans += mh[i];
}
}
write(ans);
return 0;
}
B
一道智障概率 dp。
但是我没有想出来......
我们设 \(dp_{i, j}\) 为当前过了 \(i\) 道工序，目前的物品排名为 \(j\) 的概率
\(dp_{i + 1, j} \leftarrow dp_{i, j} * (1 - p_{i + 1})^j\)
\(dp_{i + 1, j - 1} \leftarrow dp_{i, j} * [1 - (1 - p_{i + 1})^{j - 1}]\)
然后就可以直接做了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int kMod = (int)(1e9) + 7;
int n, dp[330][330], p[330], ans;
int qpow(int x, int y) {
int rs = 1;
for(; y; y >>= 1) {
if(y & 1) {
rs = 1ll * rs * x % kMod;
}
x = 1ll * x * x % kMod;
}
return rs;
}
signed main() {
freopen("B.in", "r", stdin);
freopen("B.out", "w", stdout);
cin >> n;
for(int i = 1; i < n; i++) {
cin >> p[i];
}
for(int x = 1; x <= n; x++) {
dp[0][x] = 1;
for(int i = 0; i < n - 1; i++) {
for(int j = 1; j <= n; j++) {
dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * qpow((kMod + 1 - p[i + 1]) % kMod, j)) % kMod;
dp[i + 1][j - 1] = (dp[i + 1][j - 1] + 1ll * dp[i][j] * (kMod + 1 - qpow((kMod + 1 - p[i + 1]) % kMod, j - 1))) % kMod;
//cout << dp[i][j] << ' ';
}
}
ans = (ans + 1ll * dp[n - 1][1] * x) % kMod;
for(int i = 0; i < n; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = 0;
}
}
}
cout << ans << '\n';
return 0;
}
C
如果 $[l, r]$ 因为一个数导致 $[l, r]$ 不合法，那么任何包含这个数的 $[l, r]$ 的子区间都不合法
假设这个数为 \(x\)，位置为 \(p\)。
\([l, r]\) 的一个子区间，长度一定 \(\le r - l + 1\)，所以 \(b_{len} \le b_{len'}\)。
既然这个子区间包含 \(p\)，那么 \(cnt_p \ge cnt'_p\)。
\(\therefore b_{len'} \ge b_{len} \ge cnt_p \ge cnt'_p\)，这个子区间不合法。
然后就可以随便找到一个断点分治了。
#include <bits/stdc++.h>
using namespace std;
int n, arr[1000010], brr[1000010], cnt[1000010], ans;
void solve(int l, int r) {
if(l > r) {
return ;
}
int len = r - l + 1;
for(int i = l, j = r; i <= j; i++, j--) {
if(cnt[arr[i]] < brr[len]) {
for(int k = l; k <= i; k++) {
cnt[arr[k]]--;
}
solve(i + 1, r);
for(int k = l; k < i; k++) {
cnt[arr[k]]++;
}
solve(l, i - 1);
return ;
}
if(cnt[arr[j]] < brr[len]) {
for(int k = j; k <= r; k++) {
cnt[arr[k]]--;
}
solve(l, j - 1);
for(int k = j + 1; k <= r; k++) {
cnt[arr[k]]++;
}
solve(j + 1, r);
return ;
}
}
ans = max(ans, len);
for(int i = l; i <= r; i++) {
cnt[arr[i]]--;
}
}
int main() {
freopen("C.in", "r", stdin);
freopen("C.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
cnt[arr[i]]++;
}
for(int i = 1; i <= n; i++) {
cin >> brr[i];
}
solve(1, n);
cout << ans << '\n';
return 0;
}