夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

CSP-S2考前综合强化刷题（第四场）

2020-10-04 16 min read # TSP # 单调队列 # 比赛题 # 最短路 # 动态规划

D实在不会orzljhwyz

A

显然可以二分答案变成判定问题

然后考虑解决一下怎么两两可达,显然有向图是强联通分量,所有点在一个强联通分量就行

当然也可以从一出发能到达所有点,然后反图中从所有点出发能到达1就行


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 6e4 + 7;
const int MAXM = 3e5 + 7;
int n, m, ccnt, mid;
struct  rec {
	int x, y, z;
	bool operator<(const rec &w)const {
		return z < w.z;
	}
} e[MAXM];

int home[MAXN], nxt[MAXM], to[MAXM];
int dfn[MAXN], low[MAXN], fl[MAXN];
int bel[MAXN], st[MAXN], tp, depp;

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	return;
}
inline void init() {
	memset(dfn, 0, sizeof(dfn));
	memset(fl, 0, sizeof(fl));
	memset(low, 0, sizeof(low));
	memset(home, 0, sizeof(home));
	memset(bel, 0, sizeof(bel));
	ccnt = 0;
	tp = 0;
	depp = 0;
}
inline void tarjan(int u) {
	st[++tp] = u;
	dfn[u] = low[u] = ++depp;
	fl[u] = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
			tarjan(v);
		} else if(!fl[v])continue;
		low[u] = min(low[u], low[v]);
	}
	if(low[u] == dfn[u]) {
		while(st[tp] != u) {
			int v = st[tp];
			--tp;
			bel[v] = u;
			fl[v] = 0;
		}
		--tp;
		bel[u] = u;
		fl[u] = 0;
	}
	return ;
}

inline int chk(int x) {
	init();
	for(int i = 1; i <= x; ++i) {
		ct(e[i].x, e[i].y);
	}
	for(int i = 1; i <= n; ++i) {
		if(!dfn[i]) {
			tarjan(i);
		}
	}
	for(int i = 1; i <= n; ++i) {
		if(bel[i] != bel[1]) {
			return 0;
		}
	}
	return 1;
}

int main() {
	n = read();
	m = read();
	for(int i = 1; i <= m; ++i) {
		e[i].x = read();
		e[i].y = read();
		e[i].z = read();
	}
	sort(e + 1, e + m + 1);
	int l = 1, r = m, ans = -1;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(chk(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	printf("%d\n", e[ans].z);
	return 0;
}

B

NOIP树上计数都是...

首先有nqnq做法,就是从一个端点开始dfs,然后我们考虑dfs到另一个点的时候就可知道路径了

那么我们维护一个到根的a的和,然后用每个b去乘上a的和即可

ai==bia_i==b_i

∑i<jai∗aj\sum_{i<j}{a_i*a_j}

这个式子可以求出(x,y)路径所有a的和*所有a的和,然后减去每个数自己的平方和

然后你发现我们算了两边,可以除以二就是答案

std:

考场做法:

考虑我们跨过lca的很好算,就是右边的b的和*左边的a的和

但是会发现两个点在一边的不太好搞?

于是可以统计一个ai∗sumba_i*sumb即(每个点i*到根的bb的和)的前缀和

然后你会发现在x的那一边的就可以算了,相当于这个前缀和相减然后再减去lca以上多算的bib_i

然后y那一边会发现变得和y相关而不是lca相关??

灵机一动会发现这个如果我们维护bi∗sumab_i*suma就能变换成x那边a的那种形式了

所以这三部分求和就是答案了

树上倍增std做法?

可以避免前缀和?

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 7;
const int MAXM = 4e5 + 7;
int n, ccnt, home[MAXN], nxt[MAXM], to[MAXM], m;
int fa[MAXN], a[MAXN], b[MAXN];
ll suma[MAXN], sumb[MAXN], sumab[MAXN], sumba[MAXN];
int son[MAXN], siz[MAXN], top[MAXN], dep[MAXN];

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

inline void dfs1(int u) {
	suma[u] += a[u];
	sumb[u] += b[u];
	sumab[u] += 1ll * a[u] * sumb[fa[u]];
	sumba[u] += 1ll * b[u] * suma[fa[u]];
	siz[u] = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		suma[v] = suma[u];
		sumb[v] = sumb[u];
		sumab[v] = sumab[u];
		sumba[v] = sumba[u];
		dep[v] = dep[u] + 1;
		dfs1(v);
		siz[u] += siz[v];
		if(siz[son[u]] < siz[v])son[u] = v;
	}
	return ;
}

inline void dfs2(int u, int topf) {
	top[u] = topf;
	if(!son[u])return ;
	dfs2(son[u], topf);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == son[u])continue;
		dfs2(v, v);
	}
}

inline int LCA(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]])swap(x, y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])swap(x, y);
	return x;
}

inline ll getans(int x, int y) {
	int z = LCA(x, y);
	ll ans = 0;
	ans += sumab[x] - sumab[z] - sumb[fa[z]] * (suma[x] - suma[z]);
	ans += sumba[y] - sumba[z] - suma[fa[z]] * (sumb[y] - sumb[z]);
	ans += (suma[x] - suma[z]) * (sumb[y] - sumb[z]);
	return ans;
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 2; i <= n; ++i) {
		scanf("%d", &fa[i]);
		ct(fa[i], i);
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	dfs1(1);
	dfs2(1, 1);
	for(int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		printf("%lld\n", getans(x, y));
	}
	return 0;
}

C

显然可以动态规划?

fi,j,k,lf_{i,j,k,l}表示前i个格子,第i个染了j这种颜色然后有没有用那一次,用了的话长多少

转移O(n)O(n)或者前缀和优化都可以,都屑屑屑

仔细想这个l没有用,我们只需要考虑k是直接染完还是之前就染完就好了,没有必要拖到后面再染

所以fi,j,kf_{i,j,k}表示前i个格子,第i个染了j这种颜色然后有没有用那一次

第一个转移是dpi−1,col!=j,kdp_{i-1,col!=j,k}可以转移来,用个前缀最小值和后缀最小值优化一下就好了

然后我们又有一个转移是dpk,col==j,0+sumi,j−sumk,jdp_{k,col==j,0}+sum_{i,j}-sum_{k,j}

这个k是一段区间,可以单调队列优化

老师讲的我们可以枚举一段区间和颜色,然后再考虑左右两边都不能选相同就做完了

code:


//前缀和优化 + 单调队列优化
//可以做到O(nm)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;
const int MAXN = 2050;
const ll inf = 1e18;
int n, m, K, w[MAXN][MAXN];
ll dp[MAXN][MAXN][2], sum[MAXN][MAXN];
ll mip[MAXN][MAXN][2], mis[MAXN][MAXN][2];
int que[MAXN][MAXN * 2], fr[MAXN], ed[MAXN];
int main() {
	n = read();
	m = read();
	K = read();
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			w[i][j] = read();//i - > j
			sum[i][j] = sum[i - 1][j] + w[i][j];
		}
	}
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	memset(mis, 0x3f3f3f3f, sizeof(mis));
	memset(mip, 0x3f3f3f3f, sizeof(mip));
	for(int i = 1; i <= m; ++i) {
		dp[0][i][0] = 0;
		mip[0][i][0] = 0;
		mis[0][i][0] = 0;
		fr[i] = ed[i] = 1;//一开始有决策0
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			while(que[j][fr[j]] < i - K + 1 && fr[j] <= ed[j]) {
				++fr[j];
			}//过时决策
		}
		for(int j = 1; j <= m; ++j) {
			dp[i][j][0] = min(dp[i][j][0], min(mip[i - 1][j - 1][0], mis[i - 1][j + 1][0]) + w[i][j]);
			//0的转移- > 直接继承,前缀和优化
			dp[i][j][1] = min(dp[i][j][1], min(mip[i - 1][j - 1][1], mis[i - 1][j + 1][1]) + w[i][j]);
			//在此之前我们就已经有了
			if(fr[j] <= ed[j]) {
				int k = que[j][fr[j]];
				dp[i][j][1] = min(dp[k][j][0] + sum[i][j] - sum[k][j], dp[i][j][1]);
			}
			//从这里另起一段
		}
		for(int j = 1; j <= m; ++j) {
			mip[i][j][0] = min(mip[i][j - 1][0], dp[i][j][0]);
			mip[i][j][1] = min(mip[i][j - 1][1], dp[i][j][1]);
		}
		for(int j = m; j >= 1; --j) {
			mis[i][j][0] = min(mis[i][j + 1][0], dp[i][j][0]);
			mis[i][j][1] = min(mis[i][j + 1][1], dp[i][j][1]);
		}
		for(int j = 1; j <= m; ++j) {
			while(dp[que[j][ed[j]]][j][0] - sum[que[j][ed[j]]][j] >= dp[i][j][0] - sum[i][j] && fr[j] <= ed[j]) {
				--ed[j];
			}//不优决策,下一秒i至少比她好看
			++ed[j];
			que[j][ed[j]] = i;//加入决策i
		}
	}
	ll ans = inf;
	for(int i = 1; i <= m; ++i)ans = min(dp[n][i][0], min(dp[n][i][1], ans));
	printf("%lld\n", ans);
	return 0;
}

D

考场上使用IDA*写了20/kk

然后出考场人均70/ll

首先这个题不需要AC自动机上计数什么毒瘤东西,因为所有串长都相同

我们会发现如果把所有的串写出来的话,我们可以计算出从一个串到另一个串的代价

然后如果把这个东西建成一张图

那么好像答案就是把所有的好串都经过一遍的最短路径....

TSP哎QAQ

显然我们坏串就是不被经过的点,能预处理出来

然后状压一下有哪些点是已经被经过的,最后停留在那个点,然后我们下一个点走到那个关键点预处理一下即可

时间复杂度O(n2∗2n)O(n^2*2^n)

TSP状压注意下标平移的问题,以及初始化

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
int n, m, k;
int bd[MAXN], g[MAXN];
int vis[MAXN];
int ccnt, home[MAXN], nxt[MAXN], to[MAXN], w[MAXN];

inline void ct(int x, int y, int z) {
	if(bd[x] || bd[y])return ;//bad
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	w[ccnt] = z;
}
int T = 1;
struct machine {
	int ch[MAXN][5], fa[MAXN], rt = 1;
	inline void ins(char *c, int l, int id) {
		int nw = 1;
		for(int i = 0; i < l; ++i) {
			int t = c[i] - '1';
			if(!ch[nw][t])ch[nw][t] = ++T;
			nw = ch[nw][t];
		}
		if(id)g[id] = nw;
		else bd[nw] = 1;
	}
	inline void init() {
		static queue<int> q;
		for(int i = 0; i < 4; ++i) {
			if(ch[rt][i]) {
				fa[ch[rt][i]] = rt;
				q.push(ch[rt][i]);
			} else
				ch[rt][i] = rt;
		}
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int i = 0; i < 4; ++i) {
				if(ch[u][i]) {
					fa[ch[u][i]] = ch[fa[u]][i];
					q.push(ch[u][i]);
				} else ch[u][i] = ch[fa[u]][i];
			}
		}
		for(int i = 1; i <= T; ++i) {
			for(int j = 0; j < 4; ++j) {
				ct(i, ch[i][j], j + 1);
			}
		}
		return;
	}
} ac;
#define pii pair<int,int>
#define mkp(x,y) (make_pair(x,y))
#define fi first
#define se second
char s[123];
int dis[21][MAXN];

inline void dij(int *dis, int s) {
	static priority_queue<pii, vector<pii>, greater<pii> > q;
	for (int i = 1; i <= T; ++i)dis[i] = 1e9, vis[i] = 0;
	q.push(mkp(dis[s] = 0, s));
	while(!q.empty()) {
		int u = q.top().se;
		q.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = home[u]; i; i = nxt[i]) {
			int v = to[i];
			if(bd[v])continue;
			if(dis[v] > dis[u] + w[i]) {
				dis[v] = dis[u] + w[i];
				q.push(mkp(dis[v], v));
			}
		}
	}
	return ;
}

int f[20][(1 << 20) + 5];

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s);
		ac.ins(s, k, i);
	}
	for(int i = 1; i <= m; ++i) {
		scanf("%s", s);
		ac.ins(s, k, 0);
	}
	ac.init();
	dij(dis[0], 1);
	for(int i = 1; i <= n; ++i) {
		dij(dis[i], g[i]);
	}
	memset(f, 0x3f, sizeof(f));
	int MS = (1 << n) - 1;
	for(int i = 0; i < n; ++i) {
		f[i][(1 << i)] = dis[0][g[i + 1]];
	}
	for(int S = 1; S <= MS; ++S) {
		for(int i = 0; i < n; ++i) {
			if(f[i][S] > 1e9)continue;
			if(S >> i & 1) {
				for(int j = 0; j < n; ++j) {
					if(S >> j & 1)continue;
					f[j][S | (1 << j)] = min(f[j][S | (1 << j)], f[i][S] + dis[i + 1][g[j + 1]]);
				}
			}
		}
	}
	int ans = 1e9;
	for(int i = 0; i < n; ++i)ans = min(ans, f[i][MS]);
	printf("%d\n", ans);
	return 0;
}

code抄袭吴队爽

Powered by Gridea RSS