信友队 2023 暑期集训提高 2A 班第二次测试赛后总结

温家浩 · 2023 年7 月 25 日 01:41

信友队 2023 暑期集训提高 2A 班第二次测试赛后总结

T1 第二饭堂

题意简述

已知一个字符串被称为 k-回文串的充要条件是它自身是回文串，并且它长为 ⌊n/2⌋ 的前缀和后缀是 (k-1)-回文串。根据定义，任意字符串（包括空串）都是 0-回文串。

一个字符串的回文度数就是这个字符串的 k 的最大值。

而对于一个给定的字符串，它的和谐程度就是其所有前缀的回文度数之和。求出给定字符串的和谐程度。

思路

哈希+模拟即可。

先对输入的整个字符串做哈希，然后从头至尾对所有前缀做哈希，再从尾至头对所有后缀做哈希。

依次枚举所有点，比较所有点的前缀与后缀（比较哈希值），若相同则说明以 i 为中心的字符串是一个 k-回文串（$k > 0$），将其记录。

最后再枚举所有点，如果此字符串是 k-回文串，则把前缀与后缀的值向上加。在此过程中维护答案即可。

代码

代码中的一些变量、数组名解释

$s[1,n]$：给定字符串。
$pre[1,n]$：所有前缀的 Hash 值。
$pre2[1,n]$：所有后缀的 Hash 值。
$vis[1,n]$：第 i 个位置为中心的子串是否是 k-回文串（$k > 0$）。
$f[1,n]$：第 i 个位置为中心的子串的最大 k 值。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000010;
const int MOD = 1e9 + 7;
const int MOD2 = 570000004;
int n;
long long tmp = 1, ans, f[MAXN], pre[MAXN], pre2[MAXN], hush[MAXN];
bool vis[MAXN];
char s[MAXN];

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	hush[0] = 1;
	for (int i = 1; i <= n; i++) hush[i] = (hush[i - 1] * MOD2) % MOD;
	for (int i = 1; i <= n; i++) {
		pre[i] = (pre[i - 1] + s[i] * tmp) % MOD;
		tmp = (tmp * 100) % MOD;
	}
	tmp = 1;
	for (int i = n; i >= 1; i--) {
		pre2[i] = (pre2[i + 1] + s[i] * tmp) % MOD;
		tmp = (tmp * 100) % MOD;
	}
	vis[1] = 1;
	for (int i = 2; i <= n; i++) {
		long long l = pre[i / 2];
		long long r = ((pre2[(i + 1) / 2 + 1] - pre2[i + 1] + MOD) % MOD) * hush[n - i] % MOD;
		if (l == r) vis[i] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i]) {
			f[i] = f[i / 2] + 1;
			ans += f[i];
		}
	}
	printf("%lld\n", ans);
	return 0;
}

T2 JLOI2011飞行路线

题意简述

有一张 n 个点 m 条边的无向图，边有边权，点无点权，但你可以选择 k 条边，将其边权设为 $0$。问对于给定的结点 $s,t$，从 s 到 t 的最短路的长度。

思路

分层图最短路。

各层内部正常连边，各层之间从上到下连权值为 0 的边。每向下一层，相当于免费搭一次飞机。跑一遍最短路，求出 s 到 t + n \times k 的最短路即可。

代码

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500010;
int n,m,k,s,t,dis[MAXN];
bool vis[MAXN];
struct node{
	int v;
	int w;
};
vector<node> g[MAXN];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
//first:dis(w);second:v(now)
void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	q.push(make_pair(0,s));
	while (!q.empty()){
		pair<int,int> now = q.top();
		q.pop();
		if (!vis[now.second]){
			vis[now.second] = 1;
			for (int i = 0;i < g[now.second].size();i++){
				int v = g[now.second][i].v;
				if (dis[v] > dis[now.second] + g[now.second][i].w){
					dis[v] = dis[now.second] + g[now.second][i].w;
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
}

int main(){
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
	for (int i = 1,u,v,w;i <= m;i++){
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back({v,w});
		g[v].push_back({u,w});
		for (int j = 1;j <= k;j++){   //第i个分层图 
			g[u + (j - 1) * n].push_back({v + j * n,0});  //把它与上一张分层图链接 
			g[v + (j - 1) * n].push_back({u + j * n,0});
			g[u + j * n].push_back({v + j * n,w});  //把它内部节点链接 
			g[v + j * n].push_back({u + j * n,w});
		}
	}
	for (int i = 1;i <= k;i++) g[t + (i - 1) * n].push_back({t + i * n,0});
	dijkstra();
	printf("%d",dis[t + k * n]);
	return 0;
}

T3 最大半连通子图

题意简述

[ZJOI2007] 最大半连通子图

题目描述

一个有向图 G=\left(V,E\right) 称为半连通的，如果满足：对于图中任意两点 $u,v$，存在一条 u 到 v 的有向路径或者从 v 到 u 的有向路径。

若 G'=\left(V',E'\right) 满足 $V’\subseteq V$，$E’$ 是 E 中所有跟 V' 有关的边，则称 G' 是 G 的一个导出子图。若 G' 是 G 的导出子图，且 G' 半连通，则称 G' 为 G 的半连通子图。若 G' 是 G 所有半连通子图中包含节点数最多的，则称 G' 是 G 的最大半连通子图。

给定一个有向图 $G$，请求出 G 的最大半连通子图拥有的节点数 $K$，以及不同的最大半连通子图的数目 $C$。

思路

先 Tarjan 缩点，再枚举半连通子图，统计答案。

由于 Tarjan 缩点后的图的点编号是按逆拓扑序来排的，所以不用再做拓扑排序，但相应地，要倒序搜索。

代码

代码中的一些变量、数组名解释

$top,cnt,dfn[1,n],low[1,n],b[1,n],sz[1,n],vis[1,n],st$：与 Tarjan 模板含义相同。
$ans1[1,n]$：第 i 个半连通子图的大小。
$ans2[1,n]$：有几个子图大小与第 i 个半连通子图大小相同。
$check[1,n]$：判断第 i 个半连通子图是否已经处理好。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;
int n, m, mod, top, cnt, answer1, answer2, dfn[MAXN], low[MAXN], b[MAXN], sz[MAXN], ans1[MAXN], ans2[MAXN], check[MAXN];
bool vis[MAXN];
stack<int> st;
vector<int> g[MAXN];
vector<int> g2[MAXN];

void tarjan(int x) {
	dfn[x] = low[x] = ++top;
	vis[x] = 1;
	st.push(x);
	for (int i = 0; i < g[x].size(); i++) {
		int v = g[x][i];
		if (!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x], low[v]);
		} else if (vis[v]) low[x] = min(low[x], dfn[v]);
	}
	if (dfn[x] == low[x]) {
		cnt++;
		while (st.top() != x) {
			vis[st.top()] = 0;
			b[st.top()] = cnt;
			sz[cnt]++;
			st.pop();
		}
		vis[x] = 0;
		b[x] = cnt;
		sz[cnt]++;
		st.pop();
	}
}

void scc() {
	for (int u = 1; u <= n; u++) {
		ans1[u] = sz[u];
		ans2[u] = 1;
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if (b[u] != b[v]) g2[b[u]].push_back(b[v]);
		}
	}
}

void solve() {
	for (int u = cnt; u >= 1; u--) {
		for (int i = 0; i < g2[u].size(); i++) {
			int v = g2[u][i];
			if (check[v] == u) continue;
			check[v] = u;
			if (ans1[v] < ans1[u] + sz[v]){
				ans1[v] = ans1[u] + sz[v];
				ans2[v] = ans2[u];
			}
			else if (ans1[v] == ans1[u] + sz[v]) ans2[v] = (ans2[v] + ans2[u]) % mod;
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &mod);
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) tarjan(i);
	}
	scc();
	solve();
	for (int i = 1;i <= cnt;i++){
		if (ans1[i] > answer1) answer1 = ans1[i],answer2 = ans2[i];
		else if (ans1[i] == answer1) answer2 = (answer2 + ans2[i]) % mod;
	}
	printf("%d\n%d\n",answer1,answer2);
	return 0;
}

T4 种树

题意简述

对于给定的 $k_i,c_i$，请你构造一组 \sum^n_{i=1}a_i 最小的方案，使得对于所有 $a_i$，均满足以下不等式组：

\left\{\begin{matrix} sum_i - sum_{i - 1} \ge 0 \\ sum_{i - 1} - sum_i \ge -k \\ sum_r - sum_{l - 1} \ge c \end{matrix}\right.

其中，$sum_i=\sum^i_{k=1}a_k$。

你只需要给出那组数据的 sum_n 即可。

思路

差分约束。

把形如 x_i - x_j \ge a_k 的式子转化为从第 i 个点出发，到第 j 个点有一条边权为 a_k 的边。然后在图上跑最长路即可（反之亦可）。

代码

完整代码

#include <bits/stdc++.h>
using namespace std;

int n,m,vis[500010],dis[500010];
struct node {
	int v;
	int num;
};
vector<node> g[500010];

void spfa(int start) {
	for (int i = 1; i <= n; i++) dis[i] = -1e9;
	dis[start] = 0;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		vis[now] = 0;
		for (int i = 0; i < g[now].size(); i++) {
			int v = g[now][i].v;
			if (dis[v] < dis[now] + g[now][i].num) {
				dis[v] = dis[now] + g[now][i].num;
				if (!vis[v]){
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for (int i = 1,k; i <= n; i++) {
		scanf("%d",&k);
		g[i].push_back({i - 1,-k});
		g[i - 1].push_back({i,0});
	}
	for (int i = 1,l,r,c; i <= m; i++) {
		scanf("%d%d%d",&l,&r,&c);
		g[l - 1].push_back({r,c});
	}
	spfa(0);
	printf("%d",dis[n]);
}

T5 区间染色

题意简述

有一个长度为 n 的画板，每个区间都画了不同的颜色。使用笔刷一次可以将任意长度的区间刷成同样的颜色。后刷的颜色会覆盖先刷的颜色。求出最少要多少次可以画出这幅简单的油画。

思路

简单的区间动态规划。

设 dp[i][j] 是指区间 [i,j] 的最少染色次数。

考虑初始状态：

如果 $i=j$，那么 $dp[i][j]=1$，因为区间 [i,j](i=j) 的代价是且仅是 $1$。
如果 $i\ne j$，那么 $dp[i][j]=INF$，因为需要动态规划求最小值。

考虑状态转移：

如果 $s_i = s_j$，则区间 [i,j] 可由区间 [i + 1,j] 或区间 [i,j - 1] 得到，并且转移无需代价（因为如果颜色相同那么多包含一个点就是笔多画一点的事）。
如果 $s_i \ne s_j$，则区间 [i,j] 就是有两个被完全包含的区间组成的。所以我们可以枚举断点 $k$，区间 [i,j] 的代价就是区间 [i,k] 与区间 [k+1,j] 的代价加和的最小值。

代码

完整代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 510;
int n,dp[MAXN][MAXN];
char ch[MAXN];

int main(){
	scanf("%s",ch + 1);
	n = strlen(ch + 1);
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++){
			if (i != j) dp[i][j] = 1e9;
			else dp[i][j] = 1;
		}
	}
	for (int i = 1;i < n;i++){
		for (int l = 1,r = i + 1;r <= n;l++,r++){
			if (ch[l] == ch[r]) dp[l][r] = min(dp[l + 1][r],dp[l][r - 1]); 
			else {
				for (int k = l;k < r;k++) dp[l][r] = min(dp[l][r],dp[l][k] + dp[k + 1][r]);
			}
		}
	}
	printf("%d",dp[1][n]);
	return 0;
}

T6 JOIOJI

题意简述

对于给定的长度为 n 的字符串 $S$，由 J,O,I 三种字母组成。请你求出 S 中最长的、包含同样数目的 J,O,I 三种字母的连续子串。

思路

数学推导+模拟。

首先令 s1_i,s2_i,s3_i 分别表示区间 [1,i] 中 J,O,I 的个数，那么对于区间 $[l,r]$，满足题设条件的条件为：

$$s1_j-s1_{i-1}=s2_j-s2_{i-1}=s3_j-s3_{i-1}$$

令 $x_i=s2_i-s1_i,y_i=s2_i-s1_i$，那么满足题设条件的条件就变成：

\left\{\begin{matrix} x_{i-1}=x_j \\ y_{i-1}=y_j \end{matrix}\right.

如果当前字符是 $J$，即 $s1_i=s1_{i-1}+1,s2_i=s2_{i-1},s3_i=s3_{i-1}$，则 $x_i=x_{i-1}-1,y_i=y_{i-1}-1$；
如果当前字符是 $O$，即 $s2_i=s2_{i-1}+1,s1_i=s1_{i-1},s3_i=s3_{i-1}$，则 $x_i=x_{i-1}+1,y_i=y_{i-1}$；
如果当前字符是 $I$，即 $s3_i=s3_{i-1}+1,s1_i=s1_{i-1},s2_i=s2_{i-1}$，则 $x_i=x_{i-1},y_i=y_{i-1}+1$。

那么令一个点 i 为 $(x_i,y_i)$，点权为 $i$，那么就相当于查询最大的相同位置的差。快排然后扫一遍即可。

代码

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200010;
int n,ans;
char ch[MAXN]; 
struct node{
	int x;
	int y;
	int id;
}a[MAXN];

bool cmp(node x,node y){
	if (x.x != y.x) return x.x < y.x;
	else if (x.y != y.y) return x.y < y.y;
	else return x.id < y.id;
}

int main(){
	scanf("%d",&n);
	scanf("%s",ch + 1);
	for (int i = 1;i <= n;i++){
		a[i].id = i;
		if (ch[i] == 'J') {
			a[i].x = a[i - 1].x - 1;
			a[i].y = a[i - 1].y - 1;
		}
		else if (ch[i] == 'O'){
			a[i].x = a[i - 1].x + 1;
			a[i].y = a[i - 1].y;
		}
		else if (ch[i] == 'I'){
			a[i].x = a[i - 1].x;
			a[i].y = a[i - 1].y + 1;
		}
	}
	sort(a,a + n + 1,cmp);
	int now = a[0].id;
	for (int i = 1;i <= n;i++){
		if (a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) ans = max(ans,a[i].id - now);
		else now = a[i].id;
	}
	printf("%d",ans);
	return 0;
}

考试总结

	T1	T2	T3	T4	T5	T6	Total
考试时期望得分	0	60	0	100	30	40	230
考试时实际得分	0	0	0	45	0	40	85
考试后订正得分	100	100	100	100	100	100	600

本来就菜，还挂大分。

错误分析

T1

考试时没有理解题意；
考试前也没有及时复习相关内容。

T2

考试前没有搞明白正解，dp 推不出来，分层图完全不会。
考试时一紧张 SPFA 的板子敲错了（和 Dijkstra 搞混了），后来又调了好久。

T3

码量太大，调不出来。

T4

唯一十分钟敲出来并通过样例的题目，但后来发现拓扑排序板子又敲错了（又和 Dijkstra 搞混了）。

T5

完全没思路，暴力也敲不出来（貌似这题没有部分分？）。

T6

五分钟想到暴力做法，快速敲完，发现始终无法优化。
没有想到推式子的思路。

总结

考试前多复习板子，多敲几遍。
练习码量。
复习。

正好 10618 字。