20260911 每日 1.0 3.0 4.0

No.773 竞赛

https://yukicoder.me/problems/no/773

Note

给定无法参赛的时间 $[A,B]$，问 $23, 24,25$ 日能参加几天

随便写一下

namespace XK {
  void solve() {
  	int A, B; in(A, B);
  	V<int> x(32, 0);
  	Rep(i, A, B + 1) x[i] = 1;
  	ll ans = 0;
  	Rep(i, 23, 26) if(x[i]) ans ++;
  	out(3 - ans);
  }
};

No.3561 收集 KCPC

https://yukicoder.me/problems/no/3561

Note

一个有向图上，有边权，每个点有一个字母，问能不能找到一条从 $1$ 开始，每一次可选收不收集点上的字母，手中的字母按顺序构成 KCPC。有的话输出最小的代价，反之 -1。

这里给出部分点 3 的解法，也就是保证图是 DAG。

可以考虑按照拓扑序列 做 自动机 DP。

当 $S_i = T_i$ 的时候： $f_{v,i + 1} = \text{min}{e[u] = v}(f{u,i} + \text{cost}_{u, v})$

如果不相等的时候就不取：$f_{v,i} = \text{min}{e[u] = v}(f{u,i} + \text{cost}_{u, v})$

于是可以写出：

namespace XK {

  void solve() {
  	int N, M; in(N, M);
  	V<V<pair<int, int>>> e(N), re(N);
  	V<int> deg(N, 0);
  	// map<pair<int, int>, int> mp;
  	rep(_, M) {
  		int u, v, w; in(u, v, w); -- u, -- v;
  		// mp[{u, v}] = w;
  		e[u].pb({v, w});
  		re[v].pb({u, w});
  		deg[v] ++;
  	}
  	V<V<int>> f(N, V<int>(5, LINF));
  	const char T[] = "KCPC";
  	string S; in(S);
  	f[0][0] = 0;
  	queue<int> q;
  	rep(i, N) if(deg[i] == 0) q.push(i);
  	V<int> topo;
  	while(!empty(q)) {
  		int u = q.front(); q.pop();
  		topo.pb(u);
  		for(auto [v, w] : e[u]) {
  			deg[v] --;
  			if(!deg[v]) q.push(v);
  		}
  	}

  	for(auto v : topo) {
  		for(auto [u, w] : re[v]) {
  			rep(i, 5) if(f[u][i] < LINF) chmin(f[v][i], f[u][i] + w);
  		}
  		V<ll> nf = f[v];
  		rep(i, 4) if(S[v] == T[i] && nf[i] < LINF)
  			chmin(f[v][i + 1], nf[i]);
  	}

  	ll ans = LINF;
  	rep(i, N) chmin(ans, f[i][4]);
  	out((ans == LINF ? -1 : ans));
  	
  }
};

先这样，剩下的明天更新