发表更新题解30 分钟读完 (大约4538个字)

杂题选做（2023.9.20）

主要是分析性质，然后解决问题的题。

ABC320G

题目描述：

给定 nn 个转盘，每个转盘上都有 mm 个 [0,9][0,9] 的数，设开始时为 00 时刻，在时刻 tt 我们可以选择至多一个转盘按下，或者不选择，如果我们选择了一个转盘，那么这个转盘就会停留在其第 (tmod  m)+1(t \mod m) + 1 个数上面，询问最小的时刻 tt 满足存在一种选择方案使得所有的转盘上停留下来的数字相同。

n≤100，m≤105n \le 100，m \le 10^5

题目分析：

因为只有 1010 种数字，所以我们可以考虑枚举最后保留下来的相同的数字是什么。
可以观察到答案具有可二分性，所以可以二分一个时刻 tt，然后转化为判断是否合法。
这个时候直接做好像不大行，所以考虑能不能发现一些性质。
枚举完了最后留下的数字之后，就相当于我们在每一个时刻可以选择一个转盘使得其合法，而每一个转盘也至多会被选择一次。
这个过程就是类似于匹配的过程，所以我们可以将转盘看作左部点，时刻看作右部点，这样当我们二分答案结束后，问题就转化为了左部点是否能完全匹配。
但是这样好像复杂度很爆表，因为我们左部点的个数为 O(n)O(n)，而时刻有 O(nm)O(nm) 个，所以我们的连边可能有 O(n2m)O(n^2m) 条，直接做的话显然不能通过。
但是注意到一点，这些连边中有用的连边并不多，对于任意一个左部点，我们其实只会关注其前 nn 条连边，因为只会匹配 nn 个字符串，而我们肯定是尽可能地靠前匹配，所以最劣情况下 nn 条边也足够了。
这样的话我们的连边数量就变成了 O(n2)O(n^2)，可以直接上匈牙利算法，算上二分的复杂度为 O(n3log⁡(nm))O(n^3 \log (nm))。
要注意的细节就是二分的上界，尽可能设大一点，我就是因为上界因为一些意外设成了 nm−1nm - 1 而挂掉，虽然我真的构造不出来答案为 nmnm 的情况。

代码：

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
vector<int> v[200][10];
int n,m;
map<int,int> match,vis;
char s[N];
bool dfs(int now,int limit,int num){
	for(auto x : v[now][num]){
		for(int to=x; to<=limit; to+=m){
			if(vis[to])	continue;
			vis[to] = true;
			if(!match[to] || dfs(match[to],limit,num)){
				match[to] = now;   //记录左部点匹配哪一个是没有意义的
				return true;
			}
		}
	}
	return false;
}
bool chk(int limit,int num){
	match.clear();
	for(int i=1; i<=n; i++){
		vis.clear();
		if(!dfs(i,limit,num))	return false;
	}
	return true;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);
		for(int j=1; j<=m; j++){
			v[i][s[j]-'0'].push_back(j);
		}
	}
	int tmp = n * m + 1;
	for(int x=0; x<=9; x++){
		int l = 1,r = n * m + 1,ans = n * m + 1;
		while(l <= r){
			int mid = (l + r) >> 1;
			if(chk(mid,x))	ans = mid,r = mid - 1;
			else	l = mid + 1;
		}
		tmp = min(tmp,ans);
	}
	if(tmp == n * m + 1)	printf("-1\n");
	else	printf("%d\n",tmp-1);  //因为 0 时刻对应第一个，所以要减一 
	return 0;
}

[CQOI2018] 交错序列

题目描述：

我们称一个仅由 0、1 构成的序列为”交错序列“，当且仅当序列中没有相邻的 1(可以有相邻的 0)。例如，000,001,101,都是交错序列，而 110 则不是。

对于一个长度为 nn 的交错序列，统计其中 0 和 1 出现的次数，分别记为 x 和 y。给定参数 a、b,定义一个交错序列的特征值为 xaybx^ay^b。注意这里规定任何整数的 0 次幂都等于 1(包括 00=10^0=1)。

显然长度为 n 的交错序列可能有多个。我们想要知道，所有长度为 n 的交错序列的特征值的和，除以 m 的余数。(m 是一个给定的质数)

例如，全部长度为 3 的交错串为: 000、001、010、100、101。当 a=1,b=2 时，可计算: 31×02+21×12+21×12+21×12+11×22=103^1\times0^2+2^1\times1^2+2^1\times1^2+2^1\times1^2+1^1\times2^2=10

对于 100%100\% 的数据，1≤n≤107，0≤a≤b≤45，1≤m≤1081 \le n \le 10^7，0 \le a \le b \le 45，1 \le m \le 10^8

题目分析：

做法一：
注意到 nn 只有 10710^7 所以我们可以考虑枚举一点东西。
因为要求 11 不能相邻，所以一个经典的想法就是枚举 11 的个数，然后认为序列里全部都是 11 之后通过将 00 插入进去得到方案数，而当 0,10,1 的数量确定之后特征值也确定了，所以就直接乘起来就好。
假设 11 的数量为 xx，则 00 的数量为 y=n−xy = n-x。
一开始就是通过 00 将 11 分开，也就是 y−(x−1)→yy - (x-1) \to y。
然后就是将 00 随意地插入到 11 之间的空袭中，也就是将 yy 个小球放到 x+1x+1 个盒子里，盒子允许为空地方案数，即 (x+yx)\binom{x+y}{x}。
所以这种情况下得到的特征值之和就是 (x+yy)×xa×yb\binom{x+y}{y} \times x^a \times y^b。
因为数据其实保证了 m>nm > n，也就是我们可以通过预处理阶乘的方式 O(1)O(1) 算组合数，但是其实题目并没有保证这一点，所以其实可以被卡掉。
如果快速幂算 xax^a 大概无法通过，但是注意到当 aa 为定值时 xax^a 为完全积性函数，所以可以提前线性筛筛出所有 xax^a 和 yby^b，这样就可以 O(1)O(1) 得到答案了。
这样的总复杂度就是 O(n)O(n)。

做法二：
一个直接的想法就是 dpdp 去做这个问题，dpdp 的决策显然就是每次新插入一个 00 或者一个 11，但是注意到我们插入的时候对于特征值的变化是一个二项式定理的形式，而且还有两维，就十分不可做。
先考虑把这个变成一维的形式，说不定就可以做了。

xayb=(n−y)ayb=∑i=0a(ai)ni(−y)a−iyb=∑i=0a(ai)ni(−1)a−iya+b−ix^ay^b = (n-y)^ay^b = \sum_{i=0}^a \binom{a}{i} n^i (-y)^{a-i} y^b = \sum_{i=0}^a \binom{a}{i} n^i (-1)^{a-i} y^{a+b-i}

可以发现除了 ya+b−1y^{a+b-1} 这一项其它的都是常数项，都可以直接忽略。
显然要使用 dpdp 去解决这个问题，因为我们的转移必然形如二项式定理的形式，所以为了可以转移就有了如下的状态：dp[i][j][0/1]dp[i][j][0/1] 表示考虑了前 ii 个位置，最后一个位置为 0/10/1，所有方案的 yjy^j 求和的结果。
转移的话就十分显然：

dp[i−1][j][0/1]→dp[i][j][0]∑k=0j(jk)dp[i−1][k][0]→dp[i][j][1]dp[i-1][j][0/1] \to dp[i][j][0] \\ \sum_{k=0}^j \binom{j}{k} dp[i-1][k][0] \to dp[i][j][1]

直接转移就是 O(n(a+b)2)O(n(a+b)^2) 不能通过，但是因为 nn 很大，所以肯定要想办法快速转移。
注意到转移可以写成一个矩阵乘法的形式，所以可以直接构造矩阵然后矩阵快速幂转移，复杂度 O((a+b)3log⁡n)O((a+b)^3 \log n)。
构造矩阵的一个小技巧就是转移矩阵的 (i,j)(i,j) 处的值相当于转移时 f[i]f[i] 对 f[j]f[j] 的贡献系数，所以根据这个构造起来就很简单了。

代码：

做法一：

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7+5;
int n,a,b,MOD,tot;
int fac[N],inv[N],pwa[N],pwb[N],prime[N];
bool flag[N];
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
int binom(int n,int m){
	if(n < m || n < 0 || m < 0)	return 0;
	return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}
void pre_work(int n){
	pwa[0] = a == 0 ? 1 : 0,pwb[0] = b == 0 ? 1 : 0;
	pwa[1] = 1,pwb[1] = 1; 
	for(int i=2; i<=n; i++){
		if(!flag[i]){
			pwa[i] = power(i,a);
			pwb[i] = power(i,b);
			prime[++tot] = i;
		}
		for(int j=1; prime[j]*i<=n&&j<=tot; j++){
			pwa[prime[j]*i] = pwa[prime[j]] * pwa[i] % MOD;
			pwb[prime[j]*i] = pwb[prime[j]] * pwb[i] % MOD;
			flag[prime[j]*i] = true;
			if(i % prime[j] == 0)	break;
		}
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld%lld%lld",&n,&a,&b,&MOD);
	pre_work(n);
	fac[0] = 1;
	for(int i=1; i<=n; i++)	fac[i] = fac[i-1] * i % MOD;
	inv[n] = power(fac[n],MOD-2);
	for(int i=n-1; i>=0; i--)	inv[i] = inv[i+1] * (i+1) % MOD;
	int ans = 0;
	for(int x=0; x<=n; x++){
		int y = n - x;
		if(y < x - 1)	continue;
		if(x != 0)	y -= x-1;
		ans = (ans + binom(x+y,x) * pwa[n-x]%MOD * pwb[x]%MOD)%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}

做法二：

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 305;
struct Matrix{
	int n,m;
	int a[N][N];
	Matrix(){
		memset(a,0,sizeof(a));
	}
};
int n,a,b,MOD,fac[N],inv[N],C[N][N];
Matrix operator * (Matrix a,Matrix b){
	Matrix c;
	c.n = a.n,c.m = b.m;
	for(int i=0; i<c.n; i++){
		for(int j=0; j<c.m; j++){
			for(int k=0; k<a.m; k++){
				c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]%MOD)%MOD;
			}
		}
	}
	return c;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld%lld%lld",&n,&a,&b,&MOD);
	int len = a + b + 1;
	C[0][0] = 1;
	for(int i=1; i<=2*len; i++){
		C[i][0] = 1;
		for(int j=1; j<=i; j++){
			C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
		}
	}
	Matrix tmp;
	tmp.n = tmp.m = 2 * len;
	for(int i=0; i<len; i++){
		//默认 < len 的位置存 0 
		//默认 >=len 的位置存 1 
		tmp.a[i][i]++;
		tmp.a[i+len][i]++;
		for(int j=i; j<len; j++)	tmp.a[i][j+len] = (tmp.a[i][j+len] + C[j][i])%MOD;
	}
	Matrix ans;
	ans.a[0][0] = 1;ans.n = 1,ans.m = 2 * len;
	int tn = n;
	while(tn){
		if(tn & 1)	ans = ans * tmp;
		tmp = tmp * tmp;
		tn >>= 1;
	}
	int res = 0;
	for(int i=0; i<=a; i++){
		int tmp1 = (ans.a[0][a+b-i] + ans.a[0][a+b-i+len])%MOD;
		tmp1 = tmp1 * C[a][i]%MOD * power(-1,a-i)%MOD * power(n,i)%MOD;
		res = (res + tmp1 + MOD)%MOD;
	}
	printf("%lld\n",res);
	return 0;
}

[雅礼集训2017] 蛐蛐国的修墙方案

题目描述：

给定一个长度为 nn 的排列 pp，要求构造一个合法括号序列 ss。
若 sis_i 为左括号，则连边 (i,pi)(i,p_i)，并将两个点的度数均加 11。
要求所有点的度数均为 11.

1≤n≤1001 \le n \le 100

题目分析:

看到这个东西，一个显然的想法就是连边 (i,pi)(i,p_i) 将排列转化为置换的形式。
连完边之后可以发现对于每一个置换环，其对应的 ss 一定是满足 ()()()(⋯()()()(\cdots 的形式，所以我们只需要确定了一个位置是什么其它的位置就都确定了，以及注意到如果一个环上有奇数个点则一定不合法。
直接这样做的复杂度就是 O(2n2)O(2^{\frac{n}{2}}) 比较爆炸。
但是注意到，对于一个长度为 22 的环，若其上面的两个点为 i,ji,j 且满足 i<ji < j，那么我们可以直接令 si=(s_i = (,sj=)s_j = )，这样就可以直接将这个长度为 22 的环忽略，因为这样可以直接认为 i,ji,j 匹配，就可以去掉这两个点了，这样就只剩下了长度大于等于 44 的环，而这种环最多有 O(n4)O(\frac{n}{4}) 个，所以直接暴力枚举每一个环是什么样子的，复杂度就是 O(2n4)O(2^{\frac{n}{4}}) 可以通过。
代码实现比较不行，复杂度比较高，但是依旧可以通过。

代码：

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
char s[N];
bool vis[N];
int n,pre[N],nxt[N];
bool flag = false;
void dfs(int now,int res){
	if(res < 0 || flag)	return;
	if(now == n + 1){
		if(res != 0)	return;
		for(int i=1; i<=n; i++)	printf("%c",s[i]);
		flag = true;
		return;
	}
	if(vis[now]){
		if(s[now] == '(')	dfs(now+1,res+1);
		else	dfs(now+1,res-1);
		return;
	}
	if(!vis[nxt[now]] && !vis[pre[now]]){
		vis[now] = true;
		s[now] = '(';
		dfs(now+1,res+1);
		s[now]=')';
		dfs(now+1,res-1);
		vis[now] = false;
	}
	
	if(vis[nxt[now]] && vis[pre[now]] && s[nxt[now]] != s[pre[now]])	return;
	
	if(vis[nxt[now]]){
		vis[now] = true;
		if(s[nxt[now]] == '(')	s[now] = ')',dfs(now+1,res-1);
		else s[now] = '(',dfs(now+1,res+1);
		vis[now] = false;
			
	}
	else if(vis[pre[now]]){
		vis[now] = true;
		if(s[pre[now]] == '(')	s[now] = ')',dfs(now+1,res-1);
		else	s[now] = '(',dfs(now+1,res+1);
		vis[now] = false;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%d",&nxt[i]);
		pre[nxt[i]] = i;
	}
	for(int i=1; i<=n; i++){
		if(nxt[nxt[i]] == i){
			if(i > nxt[i])	s[i] = ')',s[nxt[i]] = '(';
			else	s[i] = '(',s[nxt[i]] = ')';
			vis[i] = vis[nxt[i]] = true;
		}
	}
	dfs(1,0);
	return 0;
}

[JSOI2008] 球形空间产生器

题目描述：

有一个球形空间产生器能够在 nn 维空间中产生一个坚硬的球体。现在，你被困在了这个 nn 维球体中，你只知道球面上 n+1n+1 个点的坐标，你需要以最快的速度确定这个 nn 维球体的球心坐标，以便于摧毁这个球形空间产生器。

1≤n≤101 \le n \le 10

题目分析：

设球心坐标为 (x1,x2,x3,⋯ ,xn)(x_1,x_2,x_3,\cdots,x_n)，球的半径为 rr。
则球上一个点对这个东西的限制就是：

(x1′−x1)2+(x2′−x2)2+⋯+(xn′−xn)2=r2(x_1'-x_1)^2 + (x_2'-x_2)^2 + \cdots + (x_n'-x_n)^2 = r^2

但是我们关于解方程组只会高斯消元这种东西，可以发现的一点就是如果我们将 n+1n+1 个点的坐标都写出来，对于相邻的两个式子相减，就可以得到这样的一个 nn 元一次方程，这样构造出 n+1n+1 个方程就可以做了。

代码：

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 20;
int n;
double ans[MAXN],f[MAXN][MAXN];
double c[MAXN][MAXN];
void Gauss(){
	for(int i=1; i<=n; i++){
		int mx = i;
		for(int j=i+1; j<=n; j++){
			if(fabs(f[j][i]) > fabs(f[mx][i]))	mx = j;
		}
		if(mx != i){
			for(int j=i; j<=n+1; j++){
				swap(f[i][j],f[mx][j]);
			}
		}
		for(int j=i+1; j<=n; j++){
			double tmp = f[j][i] / f[i][i];
			for(int k=i; k<=n+1; k++){
				f[j][k] -= f[i][k] * tmp;
			}
		}
	}
	for(int i=n; i>=1; i--){
		double t = f[i][n+1];
		for(int j=n; j>i; j--){
			t-=ans[j] * f[i][j];
		}
		ans[i] = t /f[i][i];
	}
} 
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	cin>>n;
	for(int i=0; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin>>c[i][j];
		}
	}
	for(int i=1; i<=n; i++){
		for(int k=1; k<=n; k++){
			f[i][k] = (c[i][k] - c[i-1][k]) * 2;
			f[i][n+1] += c[i][k] * c[i][k] - c[i-1][k] * c[i-1][k];
		}
	}
	Gauss();
	
	for(int i=1; i<=n; i++){
		printf("%.3lf ",ans[i]);
	}
	return 0;
}

[CTSC2011] 幸福路径

题目描述：

有向图 GG 有 nn 个顶点 1,2,⋯ ,n1,2,\cdots,n，点 ii 的权值为 w(i)w(i)。现在有一只蚂蚁，从给定的起点 v0v_0 出发，沿着图 GG 的边爬行。开始时，它的体力为 11。每爬过一条边，它的体力都会下降为原来的 ρ\rho 倍，其中 ρ\rho 是一个给定的小于 11 的正常数。而蚂蚁爬到某个顶点时的幸福度，是它当时的体力与该点权值的乘积。

我们把蚂蚁在爬行路径上幸福度的总和记为 HH。很显然，对于不同的爬行路径，HH 的值也可能不同。小 Z 对 HH 值的最大可能值很感兴趣，你能帮助他计算吗？注意，蚂蚁爬行的路径长度可能是无穷的。
答案精确到小数点后 11 位。

对于 100%100\% 的数据， n≤100，m≤1000，ρ≤1–10−6，w≤100n \le 100， m \le 1000， \rho \le 1 – 10^{-6}， w \le 100。

题目分析：

做法一：
我们并没有找到什么性质，就是硬做。
一个想法就是注意到我们只需要一个近似的最优解就可以了，只要小数点后 11 位是对的即可，而 ρ108\rho^{10^8} 就已经是一个极小的数了，所以可以直接钦定走 10810^8 步找最优解。
直接一步步走肯定不行，所以可以直接倍增这样的话复杂度就很对了。

做法二：
最优的路径可能是无限长的，而无限长必然意味着我们在一个环上绕圈，所以可以发现我们的最优路径必然是先正常走一段路，然后跑到某个环上绕圈。
那么为什么不绕圈到一半再走出来呢，注意我们走出来意味着我们认为绕圈得到的收益不如出来多，而我们每次绕圈都会使得 ρ\rho 减小，所以为什么要绕圈而非直接走出去呢。
对于前面正常走一段路我们就可以考虑暴力一步步地走，然后更新。
对于绕圈我们就是要对于每一个点找到一个最优的环，而我们发现按照上面的暴力一步步走，如果走出来的是一个环，则必然是这个长度下最优的环，所以直接做就好了。
如果一个环上点的权值分别是 a1,a2,a3,⋯ ,ana_1,a_2,a_3,\cdots,a_n，默认我们一开始就绕圈，那么无限绕圈对应的权值就是 a1+a2ρ+a3ρ2+⋯+anρn−1+a1ρn+⋯a_1 + a_2\rho + a_3\rho^2 + \cdots + a_n\rho^{n-1} + a_1\rho^{n} + \cdots，设 S=a1+a2ρ+a3ρ2+⋯+anρn−1S = a_1 + a_2\rho + a_3\rho^2 + \cdots + a_n\rho^{n-1}，则这个贡献就相当于 S+ρnS+ρ2nS+⋯S + \rho^{n} S + \rho^{2n}S + \cdots 使用等比数列求和公式这个东西的值就等于 S1−ρn\frac{S}{1-\rho^n}，如果不是一开始就绕圈，那么乘以对应的 ρx\rho^x 即可。
每走一步复杂度为 O(n+m)O(n+m)，而我们一开始处理最优环的时候是让每个点都走了 O(n)O(n) 步，所以总时间复杂度为 O(n2(n+m))O(n^2(n+m))
（这份代码目前是洛谷上的最优解代码）

代码：

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
const int INF = 1e9;
int n,m,s;
double p,w[N],dis[N],diss[N],cir[N];
vector<int> G[N];
double get(int x){
	for(int i=1; i<=n; i++)	dis[i] = -INF;
	dis[x] = w[x];
	double ans = 0,tmp = p;
	for(int i=1; i<=100; i++){
		for(int now=1; now<=n; now++)	diss[now] = dis[now];
		for(int now=1; now<=n; now++){
			for(int to : G[now]){
				diss[to] = max(diss[to],dis[now] + w[to] * tmp);
			}
		}
		for(int now=1; now<=n; now++)	dis[now] = diss[now];
		ans = max(ans,(dis[x] - w[x] * tmp) / (1.0 - tmp));
		tmp = tmp * p;
	}
	return ans;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)	scanf("%lf",&w[i]);
	scanf("%d",&s);
	scanf("%lf",&p);
	for(int i=1; i<=m; i++){
		int u,v;scanf("%d%d",&u,&v);
		G[u].push_back(v);
	}
	for(int i=1; i<=n; i++)	cir[i] = get(i);
	
	double ans = 0;
	for(int i=1; i<=n; i++)	dis[i] = -INF;
	double tmp = p;dis[s] = w[s];
	for(int i=1; i<=100; i++){
		for(int now=1; now<=n; now++)	diss[now] = dis[now];
		for(int now=1; now<=n; now++){
			for(int to : G[now]){
				diss[to] = max(diss[to],dis[now] + w[to] * tmp);
			}
		}
		for(int now=1; now<=n; now++)	dis[now] = diss[now];
		for(int now=1; now<=n; now++)	ans = max(ans,dis[now] - w[now] * tmp + cir[now] * tmp);
		tmp = tmp * p;
	}
	printf("%.1f",ans);
	return 0;
}

杂题选做（2023.9.20）

http://linyihdfj.github.io/2023/09/21/practice-2023-9-20/

作者

linyihdfj

发布于

2023-09-21

更新于

2023-09-21

许可协议

×