Logo

Menu

michaele
Published on 2025-04-30 / 12 Visits
0
0

2025 04 30 模拟赛题解

T1

传送门

题面

有 n 个城市，编号为 0\sim n - 1 ，小乐要去旅行，从 0 城市出发，终点为 n-1 节点，编号越大的城市距离 n-1 城市越近，每个城市有 h 条到达其他城市的路 (i, j,k) ，表示有一条从 i\to j\, 的路，到达j城市后至少需要停留 k 天（也就是说，小乐可以在走这条路后在 j 城市停留 k+1,\,k+2\dots 天），但不可以在0城市停留，第 i+1天停留城市的编号严格大于第i天停留的城市（忽略重点 j 编号小于等于i的路 i, j, k）

分别求在 1\sim m 天离开 n-1 城市的方案数，若方案数超过 5\times 10^{8} ，只需输出 5\times 10^{8}+1即可

n\leq 10^{4},\ m\leq 400,\ h\leq 100

题解

根据题意，我们需要求方案数，而后一个节点的方案数一定是由另一个编号更小的节点转移过来，所以我们可以进行DP

设 f[i][j] 表示在第 j 天离开 i 节点的方案数，边界f[0][1]=1
那么转移方程也不难得到

\displaystyle \begin{align} &f[v][j]=\sum_{(v,k)} f[u][j-k] \\ &条件：j>k \end{align}

另外，我们还要注意一个不太显眼的条件，到达j城市后至少需要停留 k 天，这个条件意味着，我们可以在这个城市多待几天，因此，有下面的转移方程

\displaystyle \begin{align} f[i][j] = \sum_{t=1}^{t-1}f[i][t] \end{align}

从小到大枚举每个节点 O(n)
枚举每个节点的出边 O(h)
枚举每个可能的k， O(m)

总时间复杂度 O(nmh)， 4\times 10^{8} 勉强能过，但原题数据很水，才82ms

code

typedef long long ll;

const int N = 1e6 + 10;
const int inf = 5e8;

int n, m, hh;
int h[N], ver[N], ne[N], e[N], tot;
ll f[10050][410];

void add (int x, int y, int z) {
	ver[++tot] = y;
	ne[tot] = h[x];
	e[tot] = z;
	h[x] = tot;
}

int main () {
	scanf("%d%d%d", &n, &m, &hh);
	for (int i = 0; i < n - 1; i++) {
		for (int j = 1; j <= hh; j++) {
			int y, z;
			scanf("%d%d", &y, &z);
			if (y > i) add (i, y, z); 
		}
	}
	
	f[0][1] = 1;
	//f[i][j]表示在第j天离开i城的方案数
	for (int i = 0; i < n - 1; i++) {
		//只要i不是起点，那么可以停留
		//也就是后一天离开的方案数加上前一天离开的方案数
		if (i != 0) {
			for (int j = 1; j <= m; j++) {
				f[i][j] += f[i][j - 1];
				if (f[i][j] > inf) f[i][j] = inf + 1;
			}
		}
		for (int j = h[i]; j; j = ne[j]) {
			int y = ver[j];
			int z = e[j];
			for (int k = z + 1; k <= m; k++) {
				f[y][k] += f[i][k - z];
				if (f[y][k] > inf) f[y][k] = inf + 1;
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		f[n - 1][i] += f[n - 1][i - 1];
		if (f[n - 1][i] > inf) 
			f[n - 1][i] = inf + 1;
	}
	for (int i = 1; i <= m; i++) {
		printf("%lld ", f[n - 1][i]);
	}
	return 0;
}

T2

传送门

题面

给定 n,\ k ，求满足下列条件的不同的序列a的数量

  • 若 a_{i}>a_{i+1} ，则 a_{i+1}<a_{i+2}
  • 若 a_{i}<a_{i+1} ，则 a_{i+1}>a_{i+2}
  • a_{1}=k
  • \sum_{i=1}^{m} a_{i}=n，m的值任意

1\leq k\leq n\leq 5000

题解

这题赛时想了一个区间dp的解法，mtx说这个解法太抽象，但我觉得还可以，当然，这种解法我还不太会优化，只能拿66pts

先说题解中的解法，能够进行前缀和优化到O(n^{2})

这题用dp应该是比较容易想出来的
定义 f[i][j][0/1] 表示前面（包括当前）已经有的数的和为 i ，当前数为 j 下一个数应该比当前数 小/大。

状态转移方程

\displaystyle \begin{align} &f[i][j][0]=\sum_{k=1}^{j-1}f[i-k][k][1] \\ &f[i][j][1]=\sum_{k=j+1}^{i-j}f[i-k][k][0] \\ \end{align}

code

const int N = 5e3 + 10, mod = 1e9 + 7;
typedef long long ll;

int n, k;
int f[N][N][2];
int sum[N][N][2];

int main () {
	scanf("%d%d", &n, &k);
	//特判
	if (n == k) {
		printf("1\n");
		return 0;
	}
	//在总价值为k的情况下当前元素为k的情况初始化为1
	f[k][k][0] = f[k][k][1] = 1;
	//记录总价值为k的前缀和
	for (int i = k; i <= n; i++) {
		sum[k][i][0] = sum[k][i - 1][0] + f[k][i][0];
		sum[k][i][1] = sum[k][i - 1][1] + f[k][i][1];
	}
	for (int i = k + 1; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			f[i][j][0] = sum[i - j][j - 1][1] % mod;
			f[i][j][1] = (sum[i - j][n][0] - sum[i - j][j][0] + mod) % mod;
		}
		//记录总价值为i的前缀和
		for (int j = 1; j <= n; j++) {
			sum[i][j][0] = (sum[i][j - 1][0] + f[i][j][0]) % mod;
			sum[i][j][1] = (sum[i][j - 1][1] + f[i][j][1]) % mod;
		}
	}
	printf("%d\n", (sum[n][n][0] + sum[n][n][1]) % mod);
	return 0;
}

DLC

我自己在赛时想出的思路

首先定义一个状态 f[i][j][0 / 1] 表示当前元素为 i ，还剩 j （包括当前元素）的价值没有用， 下一个元素更 小/大
我们把每个状态看作一个抽象的区间
手模样例发现每个大的区间都可以由一个更小的区间转移过来，于是用f[x][y][0]来证明一下

\displaystyle \begin{align} \\ &当k=x-1时 \\ &f[x][y][0]=\sum_{k=1}^{x-1} f[k][y-x][1] \\ &\because x-1\geq 1 \\ &\therefore x\geq 2 \\ &len=y-x+1 \\ &len'=(y-x)-(x-1)+1=y-2x+2 \\ &\because len-len'=x-1>0 \\ &\therefore len>len' \\ &当k=1时 \\ &len=y-x+1 \\ &len'=y-x-1+1=y-x \\ &\therefore len>len' \end{align}

f[x][y][1] 也是一样的这里不再证明

所以我们可以枚举区间长度，枚举左端点，枚举下一个数 k ，从而实现小区间到大区间的转移，时间复杂度O(n^{3})

DLC code

const int N = 5e3 + 10, mod = 1e9 + 7;
typedef long long ll;

int n, kk;
ll f[N][N][2];

int main () {

	scanf("%d%d", &n, &kk);
	//注意特判
	if (n == kk) {
		printf("1\n");
		return 0;
	}
	//当前元素与剩余价值相等，选择当前元素后就没有其它可能了，所以初始化为1
	for (int i = 1; i <= n; i++) {
		f[i][i][0] = f[i][i][1] = 1;
	}
	//枚举区间长度
	for (int len = 2; len <= n - kk + 2; len++) {
		//枚举左端点
		for (int i = 1; i + len - 1 <= n; i++) {
			//右端点
			int j = i + len - 1;
			//枚举下一个要选的元素
			for (int k = min(i - 1, j - i); k >= 1; k--) {
				f[i][j][0] += f[k][j - i][1];
				f[i][j][0] %= mod;
			}
			for (int k = i + 1; k <= min(j - i, n); k++) {
				f[i][j][1] += f[k][j - i][0];
				f[i][j][1] %= mod;
			}
		}
	}
	
	printf("%lld\n", (ll)(f[kk][n][0] + f[kk][n][1] + mod) % mod);
	return 0;
}

再附赠一个递归版本的，66pts

const int N = 5e3 + 10, mod = 1e9 + 7;
typedef long long ll;

int n, kk;
ll f[N][N][2];

ll solve(int x, int y, int tag) {
	if (x == y) return 1;
	if (x > y) return 0;
	if (f[x][y][tag]) return f[x][y][tag];
	ll sum = 0;
	if (tag == 0) {
		for (int i = min(x - 1, y - x); i >= 1; i--) {
			sum += solve(i, y - x, 1);
			sum %= mod;
		}
		f[x][y][0] = sum;
	} else {
		for (int i = x + 1; i <= y - x; i++) {
			sum += solve(i, y - x, 0);
			sum %= mod;
		}
		f[x][y][1] = sum;
	}
	return sum;
}

int main () {
	scanf("%d%d", &n, &kk);
	if(n == kk) {
		printf("1\n");
		return 0;
	}
	printf("%lld\n", (solve(kk, n, 0) + solve(kk, n, 1) + mod) % mod);
	return 0;
}

T3

传送门

题面

有一种程序，可以执行下面的三种语句

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

该程序输出序列 [1,2,2,1,2,2,1,2,2]。

现在给定输出的序列 a ，序列长度 n ，使用PRINT语句的限制数量 k ，求是否能够通过编写类似上面的程序，输出序列 a

多组数据
1\leq T\leq 100,\ 1\leq n\leq 100
1\leq a_{i}\leq k\leq 3

题解

这题的部分分 k=1 和 k=2 比较好打，但 k=3 的情况比较棘手，后来看到题解中的一句话，我才恍然大悟， k=3 情况可以由 k=1 和 k=2 的情况组合而成，那我打的部分分修改一下不就可以了吗

我们枚举 i 为 k=2 和 k=1 的分界，那么判断一下两边是否满足 k=2 和 k = 1 的条件即可

下面说一下如何判断一个序列是否满足 k=2 的条件

首先，我们知道有两个PRINT，那么在不考虑大循环的情况下的序列应该是形如 111222 或 111111。这样的话，我们直接扫一遍，看是否有大于1个 i 满足 a_{i}\neq a_{i+1}即可

那么现在的问题转化为如何才能不考虑最外层的大循环？
考虑上面所列举的子串为原串的一个循环节，那么我们只需枚举 n 的因子，然后判断开头因子长度的字串是否符合我们上面所说的条件即可。

时间复杂度 O(n^{3}) 具体见代码
这种方法不需要什么脑子，不过你得有些耐心

code

const int N = 110;

int T, n, k;
int a[N];

bool check (string t) {
	int cnt = 0;
	for (int i = 0; i < (int)t.size() - 1; i++) {
		if (t[i] != t[i + 1]) {
			cnt++;
		}
	}
	if(cnt > 1) return false;
	return true;
}

//判断是否满足k=1的条件
bool check1 (string t) {
	int cnt = 0;
	for (int i = 0; i < (int)t.size() - 1; i++) {
		if (t[i] != t[i + 1]) {
			cnt++;
			break;
		}
	}
	if(cnt) return false;
	return true;
}
//判断是否满足k=2的条件
bool check2 (string ts, int n) {
	string s;
	vector<int> d;
	s = " " + ts;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			if (n / i == i) {
				d.push_back(i);
				continue;
			}
			d.push_back(i);
			d.push_back(n / i);
		}
	}
	bool ok = 0;
	for (int i = 0; i < (int)d.size(); i++) {
		string t = s.substr(1, d[i]);
		string tt = t;
		for (int j = 2; j <= n / d[i]; j++) {
			tt += t;
		}
		tt = " " + tt;
		if (tt == s && check(t)) {
			ok = 1;
			break;
		}
	}
	if (ok) return true;
	else return false;
}

int main () {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		if (k == 1) {
			for (int i = 1; i <= n; i++) {
				scanf("%d", &a[i]);
			}
			printf("YES\n");
		} else if(k == 2) {
			string s;
			for (int i = 1; i <= n; i++) {
				scanf("%d", &a[i]);
				s += (a[i] + '0');
			}
			if (check2(s, n)) {
				printf("YES\n");
			} else {
				printf("NO\n");
			}
		} else {
			string s;
			s = " " + s;
			for (int i = 1; i <= n; i++) {
				scanf("%d", &a[i]);
				s += (a[i] + '0');
			}
			vector<int> d;
			int mn = n;
			for (int i = 1; i * i <= n; i++) {
				if (n % i == 0) {
					if (n / i == i) {
						d.push_back(i);
						continue;
					}
					d.push_back(i);
					d.push_back(n / i);
				}
			}
			for (int i = 0; i < (int)d.size(); i++) {
				string t = s.substr(1, d[i]);
				string tt = t;
				for (int j = 2; j <= n / d[i]; j++) {
					tt += t;
				}
				tt = " " + tt;
				if (tt == s) {
					mn = min(mn, d[i]);
				}
			}
			s = " " + s.substr(1, mn);
			bool fn = 0;
			for (int i = 1; i <= mn; i++) {
				string t1 = s.substr(1, i);
				string t2 = s.substr(i + 1, mn - i);
				if ((check1(t1) && check2(t2, mn - i)) || (check1(t2) && check2(t1, i))) {
					fn = 1;
					break;
				}
			}
			if(fn) {
				printf("YES\n");
			} else {
				printf("NO\n");
			}
		}
	} 
	return 0;
}

T4

这题写过题解，考试时没有初始化，挂了20pts，这里不再写

16 ABC404 A ~ E 题解
13 ABC252G Pre-Or...

Comment