20260916 每日 2.0 3.5 4.0

No.3658 Darumake Number 2

Note

给定整数 $N$，求比 $N$ 小的，只由 4 和 5，组成的最大的数字

$4 \le N \le 10^{100000}$

一个构造，其实考虑 $N$ 如果出现了大于 5 的数位，那么可以前面一样，后面全是 5；如果出现了小于 $4$ 的数位，那么可以这个位置及之后是 5，这个位置前一个是 4 即可；如果前面没有 5，那么只能删一位。如果本身就只由 4 和 5 准备，原样输出即可。

namespace XK {
	bool cmp(string S, string T) {
		if(sz(S) > sz(T)) return 1;
		if(sz(S) < sz(T)) return 0;
		rep(i, sz(S)) if(S[i] != T[i]) return S[i] > T[i];
		return 1;
	}
  void solve() {
  	string S; cin >> S;
  	rep(i, sz(S)) {
  		if(S[i] > '5') {
  			rep(j, i) cout << S[j];
  			Rep(j, i, sz(S)) cout << '5';
  			return;
  		}
  		if(S[i] < '4') {
  			bool flg = 0;
  			rrep(j, 0, i) if(S[j] == '5') {
  				S[j] = '4';
  				Rep(k, j + 1, i + 1) S[k] = '5';
  				flg = 1; break;
  			}
  			Rep(j, i + 1, sz(S)) S[j] = '5';
  			if(!flg) {
  				Rep(j, 1, i + 1) S[j] = '5';
  				S.erase(S.begin());
  			}
  			rep(j, sz(S)) cout << S[j];
  			return;
  		}
  	}
  	rep(i, sz(S)) cout << S[i];
  }
};

No.1833 地铁规划（Subway Planning）

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

Note

给定一棵 $N$ 个点的树，每条边有一个拥堵度 $C_i$。

你可以选择两个点 $p,q$ 建一条地下铁。设树上 $p\to q$ 路径中的最小边权为 $m$，那么这条路径上的所有边权都会减去 $m$，其他边不变。

要求最小化操作后整棵树中的最大边权。

可以考虑二分答案，因为如果最大边权可以到 $X$ ，那么必然可以到 $X + 1$。

二分答案之后，所有 $C_i > X$ 的边就必须被操作，于是统计能不能找到一条路径包含所有上述边，然后对其进行操作，$mx \le x + mn$ 就可以操作，这里再考虑什么情况下没有路径：

存在度数 $\ge 3$ 的点显然不行，且度数 $=2$ 的点必须刚好两个。

于是可以写出代码了。时间复杂度 $O(N\log N)$ 的。

当然题解也有一个不用二分而是直接统计的方法，各位可以看一下。

namespace XK {

  void solve() {
  	int N; cin >> N;
  	V<V<pair<int, int>>> e(N);
  	V<AR<int, 3>> ed;
  	rep(i, N - 1) {
  		int A, B, C; cin >> A >> B >> C; -- A, -- B;
  		e[A].pb({B, C}); e[B].pb({A, C});
  		ed.pb({A, B, C});
  	}

  	auto ck = [&](int x) -> bool {
  		V<int> need(N);
  		int po = -1;
  		for(auto [u, v, w] : ed) if(w > x) {
  			need[u] = 1, need[v] = 1;
  			po = u;
  		}
  		if(po == -1) return true;

  		V<int> deg(N, 0);
  		int mx = -1, mn = LINF;

  		auto dfs = [&](auto&&dfs, int u, int fa) -> bool {
  			bool ok = need[u];
  			for(auto [v, w] : e[u]) if(v != fa) {
  				bool child = dfs(dfs, v, u);
  				if(child) {
  					deg[u] ++, deg[v] ++;
  					chmax(mx, w), chmin(mn, w);
  				}
  				ok |= child;
  			}
  			return ok;
  		};
  		dfs(dfs, po, -1);

  		int cnt = 0;
  		rep(i, N) {
  			if(deg[i] > 2) return 0;
  			if(deg[i] == 1) cnt ++;
  		}

  		if(cnt != 2) return 0;

  		return mx <= x + mn;
  	};

  	int ng = -1, ok = 1e9 + 1;
  	while(ok - ng > 1) {
  		int mid = ng + ok >> 1;
  		if(ck(mid)) ok = mid;
  		else ng = mid;
  	}
  	cout << ok;
  }
};

No.1431 東大文系数学2020第2問改

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

Note

在一个 $N × N$ 的网格中选择 $M$ 个不同的点。每一行和每一列都对应一条直线，一共有 $2N$ 条直线。要求恰好有 $K$ 条直线上没有任何被选中的点，求方案数，对 $998244353$ 取模。

设最终被选中的点覆盖了 $r$ 行、$c$ 列。

那么没有被覆盖的直线数为

$(N-r)+(N-c)=2N-r-c$

因此有： $r+c=2N-K$

先选择这 $r$ 行和 $c$ 列，方案数为 $\binom Nr\binom Nc$

接下来要求在这 $r\times c$ 个格子中选择 $M$ 个点，并且每一行、每一列都至少有一个点。

容斥一下：假设指定 $i$ 行、$j$ 列为空，那么剩余可选格子数为 $(r-i)(c-j)$

对应方案数为 $\binom ri\binom cj\binom{(r-i)(c-j)}M$

所以固定 $r,c$ 时的贡献为 $\binom Nr\binom Nc \sum_{i=0}^{r}\sum_{j=0}^{c} (-1)^{i+j} \binom ri \binom cj \binom{(r-i)(c-j)}M$

直接计算复杂度为 $O(N^3)$，需要继续化简。

$x=r-i,\qquad y=c-j$

$\binom Nr\binom ri = \binom Nx\binom{N-x}{i}$

$\binom Nc\binom cj = \binom Ny\binom{N-y}{j}$

因为 $r+c=2N-K$

所以 $i+j=2N-K-x-y$

这里我们假设 $S=2N-K-x-y$

则关于 $i,j$ 的部分可以使用范德蒙德恒等式： $\sum_{i+j=S} \binom{N-x}{i} \binom{N-y}{j} = \binom{2N-x-y}{S}$

由于 $S=2N-K-x-y$

组合数对称性： $\binom{2N-x-y}{S} = \binom{2N-x-y}{K}$

$(-1)^{i+j} = (-1)^{2N-K-x-y} = (-1)^{K+x+y}$

所以最终答案：
$$
\boxed{ \sum_{x=0}^{N}\sum_{y=0}^{N} (-1)^{K+x+y} \binom Nx \binom Ny \binom{2N-x-y}{K} \binom{xy}{M} }
$$

namespace XK {
const ll mod = 998244353;
struct mm {
};
struct Comb {
};

  void solve() {
  	int N, M, K; cin >> N >> M >> K;
  	Comb comb(N * N + 1);
  	mm ans = 0;
  	rep(x, N + 1) rep(y, N + 1) {
  		if(x * y < M) continue;
  		if(2 * N - x - y < K) continue;
  		mm cur = comb.C(N, x) * comb.C(N, y) * comb.C(2 * N - x - y, K) * comb.C(x * y, M);
  		if(K + x + y & 1) ans -= cur;
  		else ans += cur;
  	}
  	cout << ans.x;
  }
};