A. Four Digits
一遍 AC。
int n;
int main() {
scanf("%d", &n);
std::string str = std::to_string(n);
while (str.size() != 4) str = '0' + str;
printf("%s
", str.c_str());
return 0;
}
B. Failing Grade
一遍 AC。
int n, p;
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> p;
int ans = 0;
rep (i, 1, n) {
int x; cin >> x;
ans += (x < p);
}
cout << ans << endl;
return 0;
}
C. Swiss-System Tournament
机房里吵得读不下去题，拖到后面才做的。
WA 了 1 发，先是读错题，然后又打了好几个 typo。
#错误警示：拒绝打错微小字符，比如 i 和 j。
#错误警示：读好题目的数据范围信息，比如 (2n) 个人需要开两倍数组。
const int MAXN = 50 + 10;
const int MAXM = 100 + 10;
int judge(int id1, char s1, int id2, char s2) {
if (s1 == s2) return 2;
if (s1 == 'G') return s2 == 'C';
if (s1 == 'C') return s2 == 'P';
/* s1 == 'P' */ return s2 == 'G';
}
int n, m;
char give[MAXN * 2][MAXM];
int rank[MAXN * 2]; // do not forget
struct ND { int val, id; } wins[MAXN * 2];
bool cmp(ND x, ND y) { return x.val == y.val ? x.id < y.id : x.val > y.val; }
bool cmp2(ND x, ND y) { return x.id < y.id; }
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
rep (i, 1, 2 * n) { cin >> (give[i] + 1); rank[i] = i; wins[i].id = i; }
rep (i, 1, m) {
// typo: i -> j
std::sort(wins + 1, wins + 1 + 2 * n, cmp2);
rep (j, 1, n) {
int s1 = rank[j * 2 - 1], s2 = rank[j * 2];
if (judge(s1, give[s1][i], s2, give[s2][i]) == 2) continue;
if (judge(s1, give[s1][i], s2, give[s2][i])) ++wins[s1].val;
else ++wins[s2].val;
} std::sort(wins + 1, wins + 1 + 2 * n, cmp);
rep (j, 1, 2 * n) rank[j] = wins[j].id;
// rep (x, 1, 2 * n) cout << rank[x] << ' ';
// cout << endl;
}
rep (i, 1, 2 * n) cout << rank[i] << endl;
return 0;
}
D. Between Two Arrays
设 f[i][j] 表示考虑前 i 个限制，第 i 次选的数是 j 的方案数。搞一个前缀和优化转移即可。
一遍 AC。
const int MAXN = 3000 + 10;
const int MAXS = 3000;
const int HA = 998244353;
int n, aa[MAXN], bb[MAXN];
int dp[MAXN][MAXN];
lli sumdp[MAXN][MAXN]; // sum of dp[i][1~j]
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
rep (i, 1, n) cin >> aa[i];
rep (i, 1, n) cin >> bb[i];
rep (i, 1, 1) {
rep (x, aa[i], bb[i]) dp[i][x] = 1;
rep (x, aa[i], MAXS) (sumdp[i][x] = sumdp[i][x - 1] + dp[i][x]) %= HA;
}
rep (i, 2, n) {
rep (j, aa[i], bb[i]) {
dp[i][j] = sumdp[i - 1][j];
} rep (j, aa[i], MAXS) (sumdp[i][j] = sumdp[i][j - 1] + dp[i][j]) %= HA;
}
cout << sumdp[n][bb[n]] << endl;
return 0;
}
E. Red and Blue Tree
首先可以算出每条边被经过的次数 (c_i)，然后就可以 DP 了。
最开始想的是 f[i][j] 表示前 (i) 条边，(R - B = j) 的方案数，但是时空复杂度是 (O(N|K|)) 的，可不可以滚动数组没试过，总觉得应该过不去就没写。
题解又做了一步转化：设 (S = sum c_i)，于是题目转化成了选择一些 (c_i) 求和得到 (frac{S + K}{2}) 的方案数（(S + K < 0) 或是偶数的情况即是无解）。这就是一个背包板子了。
时间复杂度还是 (O(N|K|)) 居然能过 离谱。
const int MAXN = 1000 + 10;
const int MAXM = 100000 + 10;
const int HA = 998244353;
int n, m, k;
struct E { int v, id; };
std::vector<E> G[MAXN];
int cnt[MAXN];
int dp[MAXM];
bool dfs(int u, int fa, int end) {
if (u == end) return true;
bool ans = false;
forall (G[u], i) {
int v = G[u][i].v, id = G[u][i].id;
if (v == fa) continue;
if (dfs(v, u, end)) {++cnt[id]; ans = true;}
} return ans;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
std::vector<int> vc;
rep (i, 1, m) { int x; cin >> x; vc.push_back(x); }
rep (i, 1, n - 1) {
int u, v; cin >> u >> v;
G[u].push_back({v, i}); G[v].push_back({u, i});
}
rep (i, 1, m - 1) {
dfs(vc[i - 1], 0, vc[i]);
}
int S = 0;
rep (i, 1, n - 1) {
S += cnt[i];
}
if ((S + k) < 0 || ((S + k) & 1)) {
cout << 0 << endl; return 0;
}
dp[0] = 1;
for (int i = 1; i <= n - 1; ++i) {
for (int j = MAXM - 10; j >= cnt[i]; --j) {
(dp[j] += dp[j - cnt[i]]) %= HA;
}
} cout << dp[(S + k) >> 1] << endl;
return 0;
}
F. Expensive Expense
树的直径端点。
后悔考场上没开这题。
交了好几发没过，一查发现是 dis 和 dist 写 typo 了。
#错误警示：写代码专注一点，不要纯靠肌肉记忆，因为你肌肉记忆的和这题可能有些出入。
const int MAXN = 200000 + 10;
int n;
lli val[MAXN];
struct E { int v; lli val; }; std::vector<E> G[MAXN];
bool operator < (const E &x, const E &y) {
return x.val > y.val;
}
lli dist[MAXN];
void sp(int st, lli *dis) {
for (int i = 1; i <= n; ++i) dis[i] = (1ll << 62);
std::priority_queue<E> q;
static bool vis[MAXN]; memset(vis, 0, sizeof vis);
q.push({st, dis[st] = 0});
while (!q.empty()) {
int u = q.top().v; q.pop();
if (vis[u]) continue;
vis[u] = true;
forall (G[u], i) {
int v = G[u][i].v, w = G[u][i].val;
// typo: dist dis
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({v, dis[v]});
}
}
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
rep (i, 1, n - 1) {
int u, v, w; cin >> u >> v >> w;
G[u].push_back({v, w}); G[v].push_back({u, w});
}
rep (i, 1, n) cin >> val[i];
int s1 = 0;
sp(1, dist);
for (int i = 1; i <= n; ++i) {
if (dist[s1] + val[s1] < dist[i] + val[i]) {
s1 = i;
}
}
sp(s1, dist);
int s2 = 0;
for (int i = 1; i <= n; ++i) {
if (s1 == i) continue;
if (dist[s2] + val[s2] < dist[i] + val[i]) {
s2 = i;
}
}
// DEBUG(s1); DEBUG(s2);
static lli dist2[MAXN];
sp(s2, dist2);
for (int i = 1; i <= n; ++i) {
// DEBUG(dist[i]); DEBUG(dist2[i]);
if (i == s1) cout << dist[s2] + val[s2] << endl;
else if (i == s2) cout << dist2[s1] + val[s1] << endl;
else {
if (dist2[i] + val[s2] > dist[i] + val[s1]) cout << dist2[i] + val[s2] << endl;
else cout << dist[i] + val[s1] << endl;
}
}
return 0;
}