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

离散对数问题,回头再写