300iq Contest 2【杂题】

2023-12-26 16:22:15

传送门：link

D Determinant

给定 \(n\) 个点 \(m\) 条边的简单连通无向图，求邻接矩阵行列式\(\bmod 998244353\)。

\(n\le 2.5\cdot 10^4\)，\(m\le 5\cdot 10^5\)，\(\exist k\in\{1,2,\cdots,25\}\)，\(\forall A\subseteq V\land |A|=k+1\)，\(\exist a,b\in A\)，\(e\in E\)，删去 \(e\) 之后 \(a,b\) 不连通。

我们可以从题目条件推出这个图的双连通分量大小 \(\le k\)。

于是想到可以把双连通分量缩点，对这棵树搞树形 dp。

但好像转移很难弄，因为要选择每个点事与连通分量内的点在同一个环还是与树边匹配。

实际上都可以加起来，用一个行列式可以表示，每次暴力算就可以了，时间复杂度 \(O(nk^2)\)。

#include<bits/stdc++.h>
#define PB emplace_back
using namespace std;
typedef long long LL;
const int N = 25003, M = 1e6 + 3, K = 26, mod = 998244353;
int read(){
	int ch = getchar(), x = 0;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
	return x;
} template<typename T>
bool chmin(T &a, const T &b){if(a > b) return a = b, 1; return 0;}
int ksm(int a, int b){
	int res = 1;
	for(;b;b >>= 1, a = (LL)a * a % mod)
		if(b & 1) res = (LL)res * a % mod;
	return res; 
} 
int n, m, dfn[N], low[N], stk[N], tim, tp, col[N], id[N], ccnt;
bool ins[N]; vector<int> G[N], E[N], bl[N];
void dfs0(int x, int fa){
	low[x] = dfn[x] = ++tim; stk[++tp] = x; ins[x] = true;
	for(int v : G[x]) if(v != fa){
		if(!dfn[v]){dfs0(v, x); chmin(low[x], low[v]);}
		else if(ins[v]) chmin(low[x], dfn[v]);
	} if(dfn[x] == low[x]){ ++ccnt;
		while(true){
			int u = stk[tp--];
			col[u] = ccnt; ins[u] = false;
			id[u] = bl[ccnt].size();
			bl[ccnt].PB(u); if(u == x) break;
		}
	}
}
int coe[K], val[K][K], dp[N][2];
int Gauss(int n){
	static int a[K][K]; int ans = 1;
	for(int i = 0;i < n;++ i)
		for(int j = 0;j < n;++ j)
			if(i != j) a[i][j] = (LL)val[i][j] * coe[i] % mod;
			else a[i][j] = val[i][j];
	for(int i = 0;i < n;++ i){
		if(!a[i][i]){
			int p = 0;
			for(int j = i+1;j < n;++ j)
				if(a[j][i]){p = j; break;}
			if(!p) return 0;
			swap(a[i], a[p]); ans = mod - ans;
		} ans = (LL)ans * a[i][i] % mod;
		int inv = ksm(a[i][i], mod-2);
		for(int j = i+1;j < n;++ j) if(a[j][i]){
			int tmp = mod - (LL)a[j][i] * inv % mod;
			for(int k = i;k < n;++ k)
				a[j][k] = (a[j][k] + (LL)tmp * a[i][k]) % mod;
		}
	} return ans;
}
void dfs(int x, int fa){
	for(int v : E[x]) if(v != fa) dfs(v, x);
	int _ = bl[x].size(); coe[_] = 1;
	for(int i = 0;i <= _;++ i) memset(val[i], 0, _+1<<2);
	int spe = 0;
	for(int u : bl[x]){
		int res0 = 1, res1 = 0;
		for(int v : G[u]){
			if(col[v] == x) ++val[id[u]][id[v]];
			else if(col[v] == fa) spe = id[u];
			else {
				res1 = ((LL)res1 * dp[col[v]][0] + (LL)res0 * dp[col[v]][1]) % mod;
				res0 = (LL)res0 * dp[col[v]][0] % mod;
			}
		} coe[id[u]] = res0; val[id[u]][id[u]] = res1;
	} dp[x][0] = Gauss(_);
	val[spe][_] = val[_][spe] = 1;
	dp[x][1] = Gauss(_ + 1);
}
int main(){
	n = read(); m = read(); read();
	for(int i = 0, u, v;i < m;++ i){
		u = read(); v = read();
		G[u].PB(v); G[v].PB(u);
	} dfs0(1, 0);
	for(int i = 1;i <= n;++ i)
		for(int j : G[i]){
			int x = col[i], y = col[j];
			if(x < y){E[x].PB(y); E[y].PB(x);}
		}
	dfs(1, 0); printf("%d", dp[1][0]);
}

E Easy Win

给定 \(n\) 个点 \(q\) 条边的无向图，边带两个整数权值 \(a,w\)。

\(\forall i\in[1,q]\)，在前 \(i\) 条边中，求满足每个点度数为偶数的生成子图的 \(a\) 的异或和均不为 \(0\) 的生成子图的 \(w\) 之和的最大值。

\(n\le 64\)，\(q\le 2\cdot 10^5\)，\(0\le a_i<2^{60}\)，\(1\le w_i\le 10^9\)。

每个点度数为偶数的限制可以跟 \(a\) 的限制合并。于是就是线性基模板了。

F Fast Spanning Tree

给定 \(n\) 个点的无向图和 \(m\) 个整数三元组 \((a_i,b_i,s_i)\)，第 \(i\) 个点的点权为 \(w_i\)。进行以下操作尽量多次，求每次选取的 \(i\)。

求出最小的 \(i\) 使得 \(a_i,b_i\) 在不同连通块，且这两个连通块的 \(w\) 之和 \(\ge s_i\)，将 \(a_i,b_i\) 之间连边。

\(n,m\le 3\cdot 10^5\)。

404 Not Found.

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
#define fi first
#define se second 
using namespace std;
typedef pair<int, int> pii;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} const int N = 3e5+3, INF = 1e6;
int n, m, w[N], a[N], b[N], fa[N], s[N]; vector<int> ans;
priority_queue<pii, vector<pii>, greater<pii> > pq[N];
priority_queue<int, vector<int>, greater<int> > can;
int getf(int x){return x == fa[x] ? x : fa[x] = getf(fa[x]);}
void push(int _){
	int u = getf(a[_]), v = getf(b[_]);
	if(u == v) return;
	if(w[u] + w[v] >= s[_]){can.emplace(_); return;}
	int d = s[_]-w[u]-w[v]+1>>1;
	pq[u].emplace(w[u]+d, _);
	pq[v].emplace(w[v]+d, _);
}
void merge(int u, int v){
	if(pq[u].size() < pq[v].size()) swap(u, v);
	fa[v] = u; w[u] = min(w[u] + w[v], INF);
	while(!pq[u].empty()){
		pii _ = pq[u].top();
		if(_.fi > w[u]) break;
		pq[u].pop(); push(_.se);
	} while(!pq[v].empty()){
		pii _ = pq[v].top();
		if(_.fi > w[u]) break;
		pq[v].pop(); push(_.se);
	} while(!pq[v].empty()){pq[u].emplace(pq[v].top()); pq[v].pop();}
}
int main(){
	read(n); read(m);
	for(int i = 1;i <= n;++ i){fa[i] = i; read(w[i]);}
	for(int i = 1;i <= m;++ i){read(a[i]); read(b[i]); read(s[i]); push(i);}
	while(!can.empty()){
		int _ = can.top(); can.pop();
		int u = getf(a[_]), v = getf(b[_]);
		if(u != v){ans.PB(_); merge(u, v);}
	} printf("%u\n", ans.size());
	for(int u : ans) printf("%d ", u);
}

H Honorable Mention

给定长为 \(n\) 的整数序列 \(a_i\)，\(q\) 次询问 \(l,r,k\) 表示求 \(a[l,r]\) 的 \(k\) 个不交子段和的最大值。

\(n,a_i,q\le 35000\)。

众所周知答案关于 \(k\) 是凸的。

把区间左右端点是否选上记到状态里，线段树维护对应区间的答案，询问的时候平行 wqs 二分，因为斜率单调的时候对应最优位置也单调，可以少一个 log。

时间复杂度是大常数的 \(O((n+q)\log n\log V)\)。

#include<bits/stdc++.h>
#define PB emplace_back
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<LL, int> pli;
const int N = 35003, M = 1<<17, INF = 1.3e9;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0; bool f = false;
	for(;ch < '0' || ch > '9';ch = getchar()) f |= ch == '-';
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
	if(f) x = -x;
} template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
int n, Q, a[N], ps[M][2][2], l[N], r[N], kk[N], ans[N]; VI hul[M][2][2];
void build(int x, int L, int R){
	if(L == R){ int _; read(_);
		hul[x][0][0].PB(0); hul[x][0][0].PB(_);
		hul[x][0][1].PB(_); hul[x][1][0].PB(_);
		hul[x][1][1].PB(_); return;
	} int mid = L+R>>1; build(x<<1, L, mid); build(x<<1|1, mid+1, R);
	for(int a = 0;a < 2;++ a)
		for(int b = 0;b < 2;++ b)
			for(int c = 0;c < 2;++ c)
				for(int d = 0;d < 2;++ d){
					VI res((a||b)+(c||d)-(a||d)-(b&&c), -INF);
					VI &A = hul[x<<1][a][b], &B = hul[x<<1|1][c][d], &C = hul[x][a][d];
					int px = 0, py = 0;
					while(true){
						res.PB(A[px] + B[py]);
						if(px+1 == A.size() && py+1 == B.size()) break;
						if(px+1 < A.size() && (py+1 == B.size() || A[px+1] - A[px] > B[py+1] - B[py])) ++ px;
						else ++ py;
					} while(C.size() < res.size()) C.PB(-INF);
					for(int i = 0;i < res.size();++ i) chmax(C[i], res[i]);
				}
} pli res[2];
void calc(int x, int L, int R, int l, int r, int slp){ // qws!
	if(l <= L && R <= r){
		pli num[2] = {MP(-INF, 0), MP(-INF, 0)};
		for(int a = 0;a < 2;++ a)
			for(int b = 0;b < 2;++ b){
				VI &C = hul[x][a][b]; int &p = ps[x][a][b];
				while(p && C[p-1] > C[p] - slp) -- p;
				for(int c = 0;c < 2;++ c){
					int cnt = p + (a||b) - (c&&a);
					chmax(num[b], MP(res[c].fi + C[p] - (LL)slp * cnt, res[c].se + cnt));
				}
			}
		res[0] = num[0]; res[1] = num[1]; return;
	} int mid = L+R>>1;
	if(l <= mid) calc(x<<1, L, mid, l, r, slp);
	if(mid < r) calc(x<<1|1, mid+1, R, l, r, slp);
}
struct Node {
	int l, r, id;
	Node(int _l = 0, int _r = 0, int _i = 0): l(_l), r(_r), id(_i){}
	bool operator < (const Node &o) const {return l < o.l || l == o.l && id < o.id;}
} q[N];
int main(){
	read(n); read(Q); build(1, 1, n);
	for(int i = 1;i <= Q;++ i){
		read(l[i]); read(r[i]); read(kk[i]);
		q[i] = Node(-INF, INF, i);
	} bool flg = true;
	while(flg){
		flg = false;
		for(int i = 1;i < M;++ i)
			for(int a = 0;a < 2;++ a)
				for(int b = 0;b < 2;++ b)
					ps[i][a][b] = (int)hul[i][a][b].size() - 1;
		sort(q + 1, q + Q + 1);
		for(int i = 1;i <= Q;++ i) if(q[i].l < q[i].r){
			int mid = (1ll + q[i].l + q[i].r) >> 1;
			int _ = q[i].id; res[0] = MP(0, 0); res[1] = MP(-INF, 0);
			calc(1, 1, n, l[_], r[_], mid);
			if(kk[_] <= max(res[0], res[1]).se) q[i].l = mid;
			else q[i].r = mid-1;
			flg = true;
		}
	}
	for(int i = 1;i <= Q;++ i){
		int _ = q[i].id; res[0] = MP(0, 0); res[1] = MP(-INF, 0);
		calc(1, 1, n, l[_], r[_], q[i].l);
		ans[_] = max(res[0], res[1]).fi + (LL)q[i].l * kk[_];
	} for(int i = 1;i <= Q;++ i) printf("%d\n", ans[i]);
}

I Interactive Vertex

这是一道交互题

给定 \(n\) 个点的树，交互库有一个点 \(u\)，你可以询问至多 \(4\lceil\log_2n\rceil\) 次来求出 \(u\)。

每次询问给出 \(x,v_1,\cdots,v_k\)，交互库告诉你 \([\forall i\in[1,k]\cap\N,\text{dis}(u,v_i)\ge\text{dis}(u,x)]\)。

\(n\le 2\cdot 10^5\)。

树上求点当然要点分治。

若 \(v_1,\cdots,v_k\) 都与 \(x\) 相邻，那么返回 \(1\) 当且仅当 \(u\) 不在 \(v_1,\cdots,v_k\) 的子树内。于是就可以对子树二分了。

询问次数是 \(O(\log n)\) 的，但是不会算常数。

#include<bits/stdc++.h>
#define PB emplace_back
#define fi first
#define se second
using namespace std;
const int N = 200003;
typedef pair<int, int> pii;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
template<typename T>
bool chmin(T &a, const T &b){if(a > b) return a = b, 1; return 0;}
int n, cnt, head[N], to[N<<1], nxt[N<<1];
void add(int u, int v){
	to[++cnt] = v; nxt[cnt] = head[u]; head[u] = cnt;
}
int siz[N], rt, mx; bool vis[N]; vector<pii> V;
void dfs(int x, int f, int S){
	int tmp = 0; siz[x] = 1;
	for(int i = head[x];i;i = nxt[i]) if(to[i] != f && !vis[to[i]]){
		dfs(to[i], x, S); siz[x] += siz[to[i]];
		chmax(tmp, siz[to[i]]);
	} chmax(tmp, S - siz[x]);
	if(chmin(mx, tmp)) rt = x;
}
int ask(int x, int L, int R){
	printf("? %d %d", R-L+1, x);
	for(int i = L;i <= R;++ i) printf(" %d", V[i].se);
	putchar('\n'); fflush(stdout); read(x); return x;
}
void solve(int x, int S){
	if(S == 1){printf("! %d\n", x); exit(0);}
	mx = N; dfs(x, 0, S); vis[x = rt] = true; V.resize(0);
	for(int i = head[x];i;i = nxt[i]) if(!vis[to[i]])
		V.PB(siz[to[i]] > siz[x] ? S - siz[x] : siz[to[i]], to[i]);
	sort(V.begin(), V.end()); int L = 0, R = (int)V.size()-1;
	if(ask(x, L, R)){printf("! %d\n", x); exit(0);}
	while(L < R){
		int sum = 0, mn = N, tmp = 0, mid = 0;
		for(int i = L;i <= R;++ i) sum += V[i].fi;
		for(int i = L;i <= R;++ i){
			if(chmin(mn, max(tmp, sum - tmp))) mid = i-1; tmp += V[i].fi;
		} ask(x, L, mid) ? L = mid+1 : R = mid;
	} solve(V[L].se, V[L].fi);
}
int main(){ read(n);
	for(int i = 1, u, v;i < n;++ i){
		read(u); read(v); add(u, v); add(v, u);
	} solve(1, n);
}

K K-pop Strings

给定自然数 \(n,k\)，求有多少个长为 \(n\) 的字符串不存在长度 \(\ge n-k\) 的平方串。

\(n\le 100\)，\(k\le 16\)，\(|\Sigma|=35\)。

神必题。暴力容斥，如果当前考虑的段加不加都一样那么直接 return，就可以过了。

码农公寓