20260921 每日 1.5 3.0 4.0
No.2196 Pair Bonus
https://yukicoder.me/problems/no/2196
分类讨论,线性贪心贪过去即可
No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
https://yukicoder.me/problems/no/1780
倍增思考转移,考虑 $f_{d, j, k} :=$ 从 $j$ 到 $k$ 颜色经过 $2^d$ 步转移之后的最大分数,然后分别对 每颗树考虑。步数 $K \le 10^7$,所以 $d$ 也就是 30 左右。矩阵取 max 即可。
void solve() {
V<int> C(26), K(26);
rep(i, 26) cin >> C[i], C[i] --; rep(i, 26) cin >> K[i];
int N; cin >> N;
V<string> S(N);
V<int> A(N), B(N), E(N);
rep(i, N) cin >> S[i] >> A[i] >> B[i] >> E[i], A[i] --, B[i] --;
ll f[30][16][16]{0}, ans[16]{0};
rep(i, 26) {
rep(d, 30) rep(j, 16) rep(k, 16) f[d][j][k] = -LINF;
rep(d, 30) rep(j, 16) f[d][j][j] = 0;
rep(n, N) {
if(S[n].find(ALPHA[i]) != string::npos) {
int u = A[n], v = B[n];
chmax(f[0][u][v], E[n]);
chmax(f[0][v][u], E[n]);
}
}
rep(d, 29) rep(j, 16) rep(k, 16) rep(l, 16) {
chmax(f[d + 1][j][l], f[d][j][k] + f[d][k][l]);
}
ll res[16]{-LINF};
rep(i, 16) res[i] = -LINF;
res[C[i]] = 0;
rrep(d, 0, 30) if((K[i] >> d) & 1) {
ll now[16];
rep(j, 16) now[j] = res[j];
rep(j, 16) rep(k, 16) chmax(now[k], res[j] + f[d][j][k]);
rep(j, 16) res[j] = now[j];
}
rep(j, 16) {
ans[j] += res[j];
chmax(ans[j], -LINF);
}
}
ll aa = -LINF;
rep(i, 16) chmax(aa, ans[i]);
if(aa > -LINF / 10)
cout << aa;
else
cout << "Impossible";
}
};No.551 暑假的回忆(2)
https://yukicoder.me/problems/no/551
离散对数问题,回头再写