CSP-S模拟赛加赛
| T1 | T2 | T3 | T4 |
|---|---|---|---|
| 100 AC | 60 RE | 15 TLE | 37 WA |
总分：212；排名：4/5。
T1 A 了，T2 部分分，T3 挂了 20 分，T4 干了 1.5h，思路基本正确，码力太差细节太多，最后输出 0。
T1 Divisors
不难，不说了。
#include <bits/stdc++.h>
#define il inlineusing namespace std;const int bufsz = 1 << 20;
char ibuf[bufsz], *p1 = ibuf, *p2 = ibuf;
#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, bufsz, stdin), p1 == p2) ? EOF : *p1++)
il int read() {int x = 0; char ch = getchar(); bool t = 0;while (ch < '0' || ch > '9') {t ^= ch == '-'; ch = getchar();}while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}return t ? -x : x;
}
bool Beg;
const int N = 200 + 10;
int n, m, a[N];
int p[20000000], tot;
int ans[N];
bool End;
il void Usd() {cerr << "\nUse: " << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
signed main() {n = read(), m = read();for (int i = 1; i <= m; i++) {a[i] = read();}for (int i = 1; i <= m; i++) {for (int j = 1; j * j <= a[i] && j <= n; j++) {if (a[i] % j == 0) {p[++tot] = j;if (a[i] / j <= n) p[++tot] = a[i] / j;}}}sort(p + 1, p + 1 + tot);tot = unique(p + 1, p + 1 + tot) - p - 1;for (int i = 1; i <= tot; i++) {int cnt = 0;for (int j = 1; j <= m; j++) {cnt += (a[j] % p[i] == 0);}ans[cnt]++;}ans[0] = n;for (int k = 1; k <= m; k++) ans[0] -= ans[k];for (int k = 0; k <= m; k++) {printf("%d\n", ans[k]);}Usd();return 0;
}
T2 Market
按 \(t\) 排序依次处理得思路不难想到，跑朴素得 01 背包即可。
正解算一个有点类似与背包的 dp。\(f_i\) 表示价值为 \(i\) 的最小花费。这就很巧妙地解决了 \(M_i\) 和 \(c_i\) 过大得问题。令 \(g_i=\min_{j=i}^V f_j\)，即 \(f\) 的后缀最小值。查询就是在 \(g\) 上 lower_bound 即可。其实不难。
#include <bits/stdc++.h>
#define il inline
#define int long longusing namespace std;const int bufsz = 1 << 20;
char ibuf[bufsz], *p1 = ibuf, *p2 = ibuf;
#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, bufsz, stdin), p1 == p2) ? EOF : *p1++)
il int read() {int x = 0; char ch = getchar(); bool t = 0;while (ch < '0' || ch > '9') {t ^= ch == '-'; ch = getchar();}while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}return t ? -x : x;
}
bool Beg;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 300 + 10, M = 1e5 + 10, maxn = 90000 + 10;
int n, m;
struct node {int c, v, t;il bool operator < (const node & cmp) const {return t < cmp.t;}
} a[N];
struct nodeq {int t, m, id;il bool operator < (const nodeq & cmp) const {return t < cmp.t;}
} qq[M];
int f[maxn], mn[maxn];
int ans[M];
bool End;
il void Usd() {cerr << "\nUse: " << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
signed main() {n = read(), m = read();for (int i = 1; i <= n; i++) {int c = read(), v = read(), t = read();a[i] = {c, v, t};}for (int i = 1; i <= m; i++) {int t = read(), mm = read();qq[i] = {t, mm, i};}sort(a + 1, a + 1 + n);sort(qq + 1, qq + 1 + m);a[n + 1].t = INF;int sum = 0;for (int i = 1; i <= n; i++) sum += a[i].v;for (int i = 1; i <= sum; i++) f[i] = INF;for (int i = 0; i < maxn; i++) mn[i] = INF;for (int i = 1, j = 1; j <= m; i++) {for (; j <= m && qq[j].t < a[i].t; j++) {ans[qq[j].id] = upper_bound(mn, mn + 1 + sum, qq[j].m) - mn - 1;}if (j > m) break;for (int k = sum; k >= a[i].v; k--) {f[k] = min(f[k], f[k - a[i].v] + a[i].c);}for (int k = sum; k >= 0; k--) {mn[k] = min(f[k], mn[k + 1]);}}for (int i = 1; i <= m; i++) {printf("%lld\n", max(0ll, ans[i]));}Usd();return 0;
}