arc143

标签：int dfs arc143 ++ vector mathcal adj

\(\textbf{B.}\)

发现一个符合条件的矩阵 \(a\) 当且仅当 \(\forall (i,j)\), "\(a_{i,j}\) 是 \(a_{i,k}\) 中的最大值"和"\(a_{i,j}\) 是 \(a_{k,j}\) 中的最小值"不同时成立.

考虑容斥. 注意到若同时存在 \((i,j),(x,y)\) 均不满足如上条件, 显然 \(i\neq x,j\neq y\).

则 \(\begin{cases}a_{i,j}>a_{i,y},a_{x,y}<a_{i,y}\;\;\to\;\;a_{i,j}>a_{x,y}\\a_{i,j}<a_{x,j},a_{x,y}>a_{x,j}\;\;\to\;\;a_{i,j}<a_{x,y}\end{cases}\), 矛盾!

于是容斥时枚举格子 \((i,j)\) 及 \(a_{i,j}=k\), 为 \(\dbinom{k-1}{n-1}(n-1)!\cdot\dbinom{n^2-k}{n-1}(n-1)!\cdot((n-1)^2)!\).

于是最终答案为: \((n^2)!-n^2\sum_{k}\cdot\dbinom{k-1}{n-1}(n-1)!\cdot\dbinom{n^2-k}{n-1}(n-1)!\cdot((n-1)^2)!\).

直接计算即可 \(\mathcal{O}(n^2)\).

void solve(){
	int n; cin >> n;
	Binom binom(n * n);
	modint ans = binom.fact(n * n);
	for(int k = 1; k <= n * n; k ++)
		ans -= modint(n * n) * binom.binom(k - 1, n - 1) * binom.binom(n * n - k, n - 1) * binom.fact(n * n - 2 * n + 1) * binom.fact(n - 1).qpow(2);
	cout << ans.val() << '\n';
}

---

\(\textbf{C.}\)

考虑设 \(b_i=a_i\bmod{x+y}\). 则:

• 若存在 \(1 \leq i \leq n\), 使得 \(y\leq b_i<x\), 则后手必胜.
• 若以上不成立且存在 \(1 \leq i \leq n\), 使得 \(x\leq b_i\), 则先手必胜.
• 若以上均不成立, 则后手必胜.

void solve(){
	int n, x, y; cin >> n >> x >> y;
	vector<int> val(n); for(int i = 0; i < n; i ++) cin >> val[i], val[i] %= (x + y);
 
	for(int i = 0; i < n; i ++) if(y <= val[i] && val[i] < x){cout << "Second" << '\n'; return;}
	for(int i = 0; i < n; i ++) if(x <= val[i]){cout << "First" << '\n'; return;}
	cout << "Second" << '\n';
}

---

\(\textbf{D.}\)

建无向图 \(\mathcal{G}\), 其中 \(V_\mathcal{G}=\{1,\cdots,n\}\), \(E_\mathcal{G}=\{(a_i,b_i):i=1,\cdots,m\}\). 设原题中的无向图为 \(\mathcal{G}'\).

则对于 \(\mathcal{G}\) 中的桥 \((u,v)\), 无论其如何定 0 或 1 均会在 \(\mathcal{G}'\) 中作为桥.

下面分别考虑 \(\mathcal{G}\) 中的所有边双连通分量. 对于每个 \(\mathcal{G}\) 中的边双连通分量, 可将其定向成为一个强连通分量. 于是按照这个定向定出 0 边和 1 边. 则 \(\mathcal{G}'\) 对于这些点是一个强连通分量.

所以在 tarjan 的时候对树边定正向, 返祖边定反向即可. 时间复杂度: \(\mathcal{O}(n+m)\).

void solve(){
	int n, m; cin >> n >> m;
	vector<int> p(m); for(int i = 0; i < m; i ++) cin >> p[i], p[i] --;
	vector<int> q(m); for(int i = 0; i < m; i ++) cin >> q[i], q[i] --;
 
	vector<vector<pair<int, int>>> adj(n);
	for(int i = 0; i < m; i ++) adj[p[i]].push_back({q[i], 2 * i}), adj[q[i]].push_back({p[i], 2 * i + 1});
 
	vector<int> ans(m);
 
	vector<int> dfn(n, -1), low(n, -1); int pdfn = 0;
	stack<int> stk;
	vector<int> ebcc(n, -1); int pebcc = 0;
	auto dfs_ebcc = [&](auto dfs_ebcc, int u, int frm = -1) -> void {
		dfn[u] = low[u] = pdfn ++;
		stk.push(u);
		for(auto [v, idx] : adj[u]){
			if(dfn[v] == -1) ans[idx >> 1] = idx % 2, dfs_ebcc(dfs_ebcc, v, idx), low[u] = min(low[u], low[v]);
			else if(frm != (idx ^ 1)) ans[idx >> 1] = 1 - idx % 2, low[u] = min(low[u], dfn[v]);
		}
		if(dfn[u] == low[u]){while(ebcc[u] == -1) ebcc[stk.top()] = pebcc, stk.pop(); pebcc ++;}
	} ;
 
	for(int i = 0; i < n; i ++) if(dfn[i] == -1) dfs_ebcc(dfs_ebcc, i);
 
	for(int i = 0; i < m; i ++) cout << ans[i]; cout << '\n';
}

---

\(\textbf{E.}\)

记 \(c_u\) 表示 \(u\) 的颜色(\(0\) 为白色, \(1\) 为黑色). 则 \(\forall v\in\mathrm{son}(u)\),

• 若 \(c_v=0\), 则只需要让 \(v\) 比 \(u\) 后染色, 此时 \(c_u\) 取反.
• 若 \(c_v=1\), 则只需要让 \(u\) 比 \(v\) 后染色, 此时 \(c_u\) 不变.

所以从 \(1\) 作为根按照上面更新方式dfs, 若 \(c_1=1\) 显然无解, 否则上述的 \(n-1\) 条限制是充要条件, 之后只需要 toposort 找到最小的符合条件的排列即可.

于是就做完了. 时间复杂度: \(\mathcal{O}(n\log n)\).

struct Topo{
private:
	vector<vector<int>> adj; vector<int> deg; int n;
public:
	void clear(int _n){n = _n, deg = vector<int>(n), adj = vector<vector<int>>(n);}
	void add(int u, int v){adj[u].push_back(v), deg[v] ++;}
	vector<int> topo(){
		vector<int> ans;
		set<int> s; for(int i = 0; i < n; i ++) if(!deg[i]) s.insert(i);
		while(!s.empty()){
			int u = *s.begin(); s.erase(u); ans.push_back(u);
			for(int v : adj[u]){deg[v] --; if(!deg[v]) s.insert(v);}
		}
		assert((int)ans.size() == n);
		return ans;
	}
} ;
 
void solve(){
	int n; cin >> n;
	vector<vector<int>> adj(n);
	for(int i = 0; i < n - 1; i ++){
		int u, v; cin >> u >> v; u --, v --;
		adj[u].push_back(v), adj[v].push_back(u);
	}
	string str; cin >> str;
 
	Topo topo; topo.clear(n); vector<int> col(n);
	auto dfs = [&](auto dfs, int u, int pa) -> void {
		col[u] = (str[u] == 'B');
		for(int v : adj[u]) if(v != pa){
			dfs(dfs, v, u);
			if(!col[v]) col[u] ^= 1, topo.add(v, u);
			else topo.add(u, v);
		}
	} ;
	dfs(dfs, 0, -1);
 
	for(int i = 0; i < n; i ++) 
 
	if(col[0]){cout << -1 << '\n'; return;}
	vector<int> ans = topo.topo(); for(int i = 0; i < n; i ++) cout << ans[i] + 1 << ' '; cout << '\n';
}

---

\(\textbf{F.}\)

咕咕咕.

标签：int,dfs,arc143,++,vector,mathcal,adj
From： https://www.cnblogs.com/zhangmj2008/p/arc143.html