【游记】qbxt腾飞营划水测day7

[官方题解]（https://files.cnblogs.com/files/wweiyi2004/试题讲评.pptx）

慢慢的，慢慢的，夏风来了，离开的脚步近了。经过七天的学习，我在济南这个地方也就住了6天多了。qwq 然而，这一天，极不平凡。斜风卷着乌云，雨滴夹着雷电，在中国河南这个地方突如其来地落下了自己的印记，全网轰动，就在这时，我们进行了qbxt腾飞营的划水测，非常友好，所以，我们还是继续开心的进行了我们可爱的测试，于是我就可爱的没了，总此思考，我决定，写下这七天的游记中的最后一篇，划水测day7

T1 K子棋

题目描述

有一个n×mn\times m的棋盘，从左上角定义为(1,1)(1,1)，右下角为(n,m)(n,m)。每个格子上有两种状态，有棋子和无棋子。我们称KK个位置为一个K星连珠，当且仅当这些位置上都有棋子，且这些格子的坐标构成一条经过(1,1)(1,1)的直线。举例来说，K=3K=3时，三枚棋子分别在(2,3),(3,5),(5,9)(2,3),(3,5),(5,9)上就构成了一个3星连珠，因为三个位置都在直线y=2x−1y=2x-1上。两个K星连珠被视为不同的当且仅当他们包含的点集不同。

这个问题中，你需要对于一个特定的棋盘和给定的KK，计算其中有多少个不同的K星连珠，输出答案对998244353998244353取模的结果。

输入格式

从文件connectk.in\texttt{connectk.in}读取数据。

第一行三个正整数n,m,Kn,m,K。

第二行五个整数A,x0,b,p,lA,x_0,b,p,l，保证pp是质数。

棋盘由如下方式生成：

首先先生成一个数列xi{x_i}，其中x0x_0已经给出，xi=(Axi−1+b)%px_i=(Ax_{i-1}+b)\%p。

若x(i−1)∗m+j≤lx_{(i-1)*m+j}\leq l，则棋盘上(i,j)(i,j)位置有棋子，否则没有。

输出格式

输出到文件connectk.out\texttt{connectk.out}。

一行一个数，表示K星连珠个数对998244353998244353取模的结果。

样例 1 输入

1
2
3 5 3
3 4 2 7 3

样例 1 输出

1
6

样例 2 输入

1
见ex_connectk2.in

样例 2 输出

1
见ex_connectk2.ans

提示

第一组样例解释：

生成的棋盘如下，’#‘表示有棋子，’.'表示没有。

1
2
3
###.#
.###.
#.###

六个3星连珠分别是：

(1,1),(1,2),(1,3)(1,1),(1,2),(1,3)

(1,1),(1,2),(1,5)(1,1),(1,2),(1,5)

(1,1),(1,3),(1,5)(1,1),(1,3),(1,5)

(1,2),(1,3),(1,5)(1,2),(1,3),(1,5)

(1,1),(2,2),(3,3)(1,1),(2,2),(3,3)

(1,1),(2,3),(3,5)(1,1),(2,3),(3,5)

本题总共有2020组数据。

对于全部数据，2≤n,m≤50002\leq n,m\leq 5000，1≤K≤min(n,m)1\leq K\leq min(n,m)，2≤A<p2\leq A<p，0≤x0,b,l<p0\leq x_0,b,l<p，2≤p≤1092\leq p\leq 10^9且pp是质数。

对于20%20\%的数据：n,m≤5n,m\leq 5。

对于40%40\%的数据：n,m≤50n,m\leq 50。

对于60%60\%的数据：n,m≤200n,m\leq 200。

对于80%80\%的数据：n,m≤1000n,m\leq 1000。

对于90%90\%的数据：n,m≤2000n,m\leq 2000。

思路

算法1

随便数一数，然后枚举一哈~，大概能过20%的数据吧?qaq

期望得分20分？

算法2

对于每一对(i,j)(i,j),的gcd直接调用系统函数，然后直接对着每一条线用组合数计算

为什么使用组合数呢，我们可以先固定两个，然后对于后面的，直接变成几选几的问题了，一直往后推也非常好理解

期望得分90分

算法3

限制了算法2的想象的主要是gcd的调用太慢了，所以运用@Hazyknight的话，我们可以直接进行递推就可以把一堆gcd给算出来了，即：
g[i][j]=(i>j?)g[i−1][j]:g[i][j−1]; g[i][j]=(i>j?) g[i-1][j]:g[i][j-1];

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

期望得分100分

算法4

但是Hazyknight还有更nb的算法，但是我们已经得到一百分了，那就来欣赏一下

其实本题可以只用O(n)O(n)的空间。甚至不需要存储整个棋盘！

考虑平面0<=i<=n,0<=j<=n0<=i<=n , 0<=j<=n且i,j互质的数对在平面上的射线。

假设相邻两条射线的是(a,b) (c,d)那么一定满足∣ad−bc∣=1。|ad-bc|=1。

于是我们直接从(0,1)开始旋转枚举射线，和射线上的点然后预处理AnA^n快速计算对应格子是0还是1即可。

代码

std

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5005;
const ll MOD = 998244353;

int n,m,K;
int v[MAXN][MAXN];
int g[MAXN][MAXN];

ll A,b,x0,p,l,ans;
ll f[MAXN];
ll fac[MAXN];
ll inv[MAXN];

ll power(ll a,ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			(res *= a) %= MOD;
		(a *= a) %= MOD;
		b >>= 1;
	}
	return res;
}

ll C(int x,int y)
{
	return x < y ? 0 : fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}

void init()
{
	int N = max(n + 1,m + 1);
	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;i >= 1;i--)
		inv[i - 1] = inv[i] * i % MOD;
	for (int i = 1;i <= N;i++)
		f[i] = C(i,K);
}

int main()
{
	freopen("connectk.in","r",stdin);
	freopen("connectk.out","w",stdout);
	cin >> n >> m >> K >> A >> x0 >> b >> p >> l;
	n--,m--;
	init();
	for (int i = 0;i <= n;i++)
		for (int j = 0;j <= m;j++)
		{
			x0 = (A * x0 + b) % p;
			v[i][j] = (x0 <= l);
		}
	if (K == 1)
	{
		for (int i = 0;i <= n;i++)
			for (int j = 0;j <= m;j++)
				(ans += v[i][j]) %= MOD;
		cout << ans << endl;
		return 0;
	}
	for (int i = 0;i <= n;i++)
		for (int j = 0;j <= m;j++)
			if (!i || !j)
				g[i][j] = i | j;
			else
				g[i][j] = (i > j ? g[i - j][j] : g[i][j - i]);
	for (int i = n;i >= 0;i--)
		for (int j = m;j >= 0;j--)
			if ((i || j) && g[i][j] != 1)
			{
				v[i / g[i][j]][j / g[i][j]] += v[i][j];
				v[i][j] = 0;
			}
	for (int i = 0;i <= n;i++)
		for (int j = 0;j <= m;j++)
			if (g[i][j] == 1)
				(ans += f[v[i][j] + v[0][0]]) %= MOD;
	cout << ans << endl;
	return 0;
}

但是本蒟蒻考试的时候不知道怎么回事，想打一个暴力，至少能得一点分，但是一直re，也没有发现为什么（有没有大神帮我看一下

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
73
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=2005;
const int MOD=998244353;
int n,m,k;
int A,x[maxn],b,p,l;
bool map[maxn][maxn]={false};
bool vis[maxn][maxn]={true};
int C[maxn][maxn];
int line[maxn][maxn];
long long ans=0;
void pre()
{
	C[0][0]=1;
	for(int i=1;i<=max(n,m);i++)
	{
		C[i][0]=1; 
		for(int j=1;j<=k;j++)
			C[i][j]=(C[i-1][j]%MOD+C[i-1][j-1]%MOD)%MOD;
	}
}
void make()
{
	for(int i=1;i<=n*m+n;i++)
	x[i]=(A*x[i-1]+b)%p;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		if(x[(i-1)*m+j]<=l)
		map[i][j]=true,vis[i][j]=false;
	}
}
int main()
{
	int maxx=-9999999,maxy=-9999999;
	int minx=9999999,miny=9999999;
	cin>>n>>m>>k;
	cin>>A>>x[0]>>b>>p>>l;
	make();
	pre();
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==1&&j==1) continue;
			int a=(j-1)/(i-1);
			int z=j-i*k;
			for(int q=i;q<=m,a*q+z<=n;q++)
			{
				int x=q,y=a*q+z;
				if(map[x][y]==true)
				line[a][z]++;
			}
		}
	}
	for(int i=minx;i<=maxx;i++)
	{
		for(int j=miny;j<=maxy;j++)
		{
			if(line[i][j]+2<k) continue;
			int res=0;
			for(int r=line[i][j];r>2;r--)
			res=(res%MOD*C[r][k-2]%MOD)%MOD;
			ans=(ans+res)%MOD;
		}
	}
	cout<<ans<<endl;
	return 0;
}

T2 联邦

题目描述

一个联邦由很多城市组成，整个联邦的地图可以抽象为一个nn个点mm条边的无向连通图，一个点的集合SS被称为一个城市群当且仅当任取两个城市u,v∈Su,v\in S，任何从uu到vv的简单路径（点边不重复）上的所有点均在SS内。每座城市有一个重要程度值wiw_i，一个城市群的重要程度被定义为这个城市群中城市的重要程度和。给出qq次修改，每次修改一个城市的重要程度并询问所有城市群的权值总和，输出对998244353998244353取模。

输入格式

从文件federation.in\texttt{federation.in}中读取数据。

第一行两个整数nn，mm，表示点数和边数。

接下来一行nn个整数wiw_i，表示每个点的初始权值。

接下来mm行每行两个整数u,vu,v表示无向图的一条边，保证无向图没有重边和自环且连通。

接下来一行一个整数qq表示询问个数。

接下来qq行，每行两个整数x,yx,y表示将wxw_x修改为yy。

输出格式

输出到文件federation.out\texttt{federation.out}。

共qq行，每行一个数表示对应询问的答案mod 998244353mod~998244353。

样例 1 输入

1
2
3
4
5
6
7
8
9
10
11
4 4
1 1 1 1
1 2
2 3
3 1
1 4
4
1 2
2 2
3 2
4 2

样例 1 输出

1
2
3
4
17
20
23
26

样例 2 输入

1
见ex_federation2.in

样例 2 输出

1
见ex_federation2.ans

提示

第一组样例解释：

对于第一组询问w=(2,1,1,1)w=(2,1,1,1)。

一共有77个城市群：

(1)(1)，权值为22。

(2)(2)，权值为11。

(3)(3)，权值为11。

(4)(4)，权值为11。

(1,4)(1,4)，权值为2+1=32+1=3。

(1,2,3)(1,2,3)，权值为2+1+1=42+1+1=4。

(1,2,3,4)(1,2,3,4)，权值为2+1+1+1=52+1+1+1=5。

总权值为1717。

本题总共有2525组数据。

对于全部数据1≤n,m,q≤1061\leq n,m,q\leq 10^6，1≤wi,y≤1091\leq w_i,y\leq 10^9，1≤x,u,v≤1051\leq x,u,v\leq 10^5。输入数据量很大，建议使用读入优化。

对于12%12\%的数据，n,m,q≤10n,m,q\leq 10。

对于20%20\%的数据，n,m,q≤20n,m,q\leq 20。

对于36%36\%的数据，n,m,q≤5000n,m,q\leq 5000。

对于44%44\%的数据，n,q≤5000n,q\leq 5000。

对于68%68\%的数据，n,q≤105n,q\leq 10^5。

对于另外8%8\%的数据，图是一条链。

对于另外12%12\%的数据，图是一棵树。

思路

算法1

实际上就没有思路，直接大爆搜，枚举每个集合，再判断是不是城市群

期望得分20分

算法2

考虑城市群S到底是啥。

若u,v两个点在同一个点双连通分量中且全部属于S，则这个点双连通分量的所有点也一定都属于S。那么我们构建出原图的圆方树。一个合法的城市群一定是圆方树上一个全部在圆点与外界交接的连通块，直接对于每一次询问进行一次树形DP即可。

时间复杂度O(nq)O(nq)

期望得分44。

算法3

对于一条链和一棵树，大概可以通过一些结论DP出解。

能得到额外的8、12分。

期望得分64分

算法4

我们只需要求出对于每个点i，有多少个包含i的城市群即可。

我们采用两次dfs即可，第一次dfs计算fi表示i的子树和i有多少种可行的城市群方案，第二次计算gi表示i和i的父亲有多少种可行的城市群方案。gi用fi来更新即可（可能需要一个前缀后缀乘积）。

复杂度O(n+q)O(n+q)。

期望得分100分

代码

std

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline char gc()
{
	static char buf[524288],*p1 = buf,*p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,524288,stdin),p1 == p2) ? EOF : *p1++;
}

inline void read(int &v)
{
	v = 0;
	char c = gc();
	while (c < '0' || c > '9')
		c = gc();
	while (c >= '0' && c <= '9')
	{
		v = v * 10 + c - '0';
		c = gc();
	}
}

const int MAXN = 2000005;
const ll MOD = 998244353;

struct Edge
{
	int to;
	int nxt;
}edge[MAXN << 1];

int n,m,q,id,cc,ee,tot;
int w[MAXN];
int first[MAXN];
int dfn[MAXN];
int low[MAXN];
int bel[MAXN];
int U[MAXN];
int V[MAXN];

bool vis[MAXN];

ll f[MAXN];
ll g[MAXN];
ll pre[MAXN];
ll suf[MAXN];

stack<int> S;

void addE(int u,int v)
{
	edge[++id] = (Edge){v,first[u]};
	first[u] = id;
}

void tarjan(int u,int fa)
{
	dfn[u] = low[u] = ++id;
	vis[u] = 1;
	S.push(u);
	for (int i = first[u];i;i = edge[i].nxt)
		if (edge[i].to != fa)
		{
			int to = edge[i].to;
			if (!dfn[to])
			{
				tarjan(to,u);
				low[u] = min(low[u],low[to]);
				if (low[to] >= dfn[u])
				{
					cc++;
					ee++;
					U[ee] = u;
					V[ee] = cc + n;
					while (S.top() != to)
					{
						vis[S.top()] = 0;
						ee++;
						U[ee] = cc + n;
						V[ee] = S.top();
						S.pop();
					}
					vis[S.top()] = 0;
					ee++;
					U[ee] = cc + n;
					V[ee] = S.top();
					S.pop();
				}
			}
			else if (vis[to])
				low[u] = min(low[u],dfn[to]);
		}
}

void dfs1(int u)
{
	f[u] = 1;
	for (int i = first[u];i;i = edge[i].nxt)
	{
		dfs1(edge[i].to);
		(f[u] *= f[edge[i].to] + (u <= n)) %= MOD;
	}
}

void dfs2(int u)
{
	pre[0] = 1;
	int j = 1;
	for (int i = first[u];i;i = edge[i].nxt,j++)
	{
		pre[j] = pre[j - 1] * (f[edge[i].to] + (u <= n)) % MOD;
		S.push(i);
	}
	suf[j] = 1;
	while (!S.empty())
	{
		j--;
		int i = S.top();
		suf[j] = suf[j + 1] * (f[edge[i].to] + (u <= n)) % MOD;
		S.pop();
	}
	j = 1;
	for (int i = first[u];i;i = edge[i].nxt,j++)
		g[edge[i].to] = g[u] * pre[j - 1] % MOD * suf[j + 1] % MOD + (edge[i].to <= n);
	for (int i = first[u];i;i = edge[i].nxt)
	{
		(g[u] *= f[edge[i].to] + (u <= n)) %= MOD;
		dfs2(edge[i].to);
	}
}

int main()
{
	freopen("federation.in","r",stdin);
	freopen("federation.out","w",stdout);
	read(n),read(m);
	for (int i = 1;i <= n;i++)
		read(w[i]);
	for (int u,v,i = 1;i <= m;i++)
	{
		read(u),read(v);
		addE(u,v);
		addE(v,u);
	}
	id = 0;
	tarjan(1,0);
	id = 0;
	memset(first,0,sizeof(first));
	for (int i = 1;i <= ee;i++)
		addE(U[i],V[i]);
	dfs1(1);
	g[1] = 1;
	dfs2(1);
	ll ans = 0;
	for (int i = 1;i <= n;i++)
		(ans += g[i] * w[i]) %= MOD;
	read(q);
	while (q--)
	{
		int x,y;
		read(x),read(y);
		(ans += g[x] * (y - w[x])) %= MOD;
		w[x] = y;
		printf("%lld\n",(ans + MOD) % MOD);
	}
	return 0;
}

T3 能源供应

题目描述

一座城市主要由两种方式供应能源，火力发电和风力发电。其中，火电每次开启需要CC的代价，持续运行时每一天并且产生xx度电的代价是max(D,kx)max(D,kx)（因为就算不发电也需要维持开机状态，消耗至少为DD）。而风力发电在特定一天发xx度电的代价为vixv_ix（风力大小等因素会导致viv_i每一天可能不同），同时由于天气原因可能存在若干天并不能发电。两种方式都可以选择在任何时间开关以及每天发任意度的点。现在给出这座城市nn天的电力需求，求一个代价最小的满足电力需求的发电方案。

不过，火电站由于不受外界影响，预测相对准确；风力发电需要对天气的预告，具有不确定性。所以现在要求有qq次修改，每次修改修改一天的viv_i，每次修改后询问一次最小代价。注意，以上过程中任何电站只能发整数单位的电。

输入格式

从文件energy.in\texttt{energy.in}中读取数据。

第一行四个整数n,C,D,kn,C,D,k。

第二行nn个整数viv_i，表示第ii天风力发一度电的代价。

第三行nn个整数aia_i,表示每天需要的电量（度）。

第四行一个整数qq。

接下来qq行，每行两个整数x,yx,y，表示将vxv_x修改为yy。

输出格式

输出到文件energy.out\texttt{energy.out}。

共qq行，每一行一个整数AnsiAns_i表示最小花费

样例 1 输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 8 1 4
1 9 6 2 2
7 5 8 5 2
10
1 3
5 7
1 3
3 2
1 6
2 7
4 4
2 3
2 6
3 5

样例 1 输出

1
2
3
4
5
6
7
8
9
10
95
100
100
85
92
92
101
97
101
116

样例 2 输入

1
2
3
4
5
1 1 1000000000000 1
10000
10000
1
1 10000

样例 2 输出

1
100000000

样例 3 输入

1
2
3
4
5
5 8 9 7
6 10 10 6 9
7 1 9 5 8
1
3 10

样例 3 输出

1
210

样例 4 输入

1
见ex_energy4.in

样例 4 输出

1
见ex_energy4.ans

提示

第一组样例解释：

对于第一组询问，每一天使用风电的花费是(3,9,6,2,2)(3,9,6,2,2)，每一天的发电量需求是(7,5,8,5,2)(7,5,8,5,2)。

一种可行的方式如下：第一天全部使用风电，第二天开启火电站并全使用火电，第三天全使用火电后关闭火电站，第四、五天全部使用风电。

总花费为(3×7)+8+max(1,4×5)+max(1,8×5)+2×5+2×2=95(3\times 7)+8+max(1,4\times 5)+max(1,8\times 5)+2\times 5+2\times 2=95。

第二组样例解释：

这组讯问中，虽然开启火电站和用火电站发电都是非常便宜的，不过由于DD（每日最低代价）过高，所以全部使用风电。

第三组样例解释：

对于第一组询问，每一天使用风电的花费是(6,10,10,6,9)(6,10,10,6,9)，每一天的发电量需求是(7,1,9,5,8)(7,1,9,5,8)。

一种可行的方式如下：第一天全部使用风电，第二天开启火电站并全部用火电站发电，第三天全部用火电站发电，第四天用火电站发22度电并用风力发33度电，第五天全部用火电站发电。

总花费为6×7+8+max(9,7×1)+max(9,7×9)+max(9,7×2)+6×3+max(9,7×8)=2106\times 7+8+max(9,7\times 1)+max(9,7\times 9)+max(9,7\times 2)+6\times 3+max(9,7\times 8)=210。

本题总共有2020组数据。

对于全部数据，1≤n,q≤2×1051\leq n,q\leq 2\times 10^5，1≤C,D≤10121\leq C,D\leq 10^{12}，1≤k,vi,ai,y≤1061\leq k,v_i,a_i,y\leq 10^6，1≤x≤n1\leq x\leq n。

对于10%10\%的数据，n,q≤5n,q\leq 5，所有数不超过1010。

对于25%25\%的数据，n,q≤15n,q\leq 15。

对于40%40\%的数据，n,q≤200n,q\leq 200。

对于60%60\%的数据，n,q≤3×104n,q\leq 3\times 10^4。

对于另外20%20\%的数据，q=1q=1。

思路

算法1

直接枚举每一天是否开启火电站，和每天火电站发多少电，然而时间复杂度很大qaq

期望得分10分

算法2

可以发现，每天开不开火电站发电量是一定的，也就是说最优解是一定的

所以我们只关心每一天开不开火电站，直接枚举就好了

时间复杂度O(2nnq)O(2^nnq)

期望得分25分

算法3

实际上我们从最优解的角度来想，很容易就能想到这道题需要使用的算法为动态规划

对算法2进行DP优化，令f[i][0/1]f[i][0/1]表示前i天，最后一天是否开启火电站的最小花费，转移时候直接尝试下一天是否开火电站即可，每一次单独DP。

时间复杂度O(nq)O(nq)

期望得分60分

算法4

然而这样的DP并不能达到我们题目的要求，所以我们要进行DP优化

算法3中的DP可以优化。

考虑转移形式大概是视(fi0,fi1)为一个向量，用min代替+，用+代替*做一次矩阵乘法。

类似f[i+1][0]=min(f[i][0]+?,f[i][1]+?)f[i+1][0]=min(f[i][0]+?,f[i][1]+?)

可以发现min，+是floyd矩阵，满足结合律。

由于每一次只修改一天的代价，故用线段树维护矩阵连乘积。

复杂度O(qlogn)O(qlogn)。

期望得分100分

代码

std

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 200005;

struct Matrix
{
	ll a[2][2];
	
	Matrix()
	{
		memset(a,0,sizeof(a));
	}
	
	Matrix operator * (const Matrix &p)const
	{
		Matrix res;
		res.a[0][0] = min(a[0][0] + p.a[0][0],a[0][1] + p.a[1][0]);
		res.a[0][1] = min(a[0][0] + p.a[0][1],a[0][1] + p.a[1][1]);
		res.a[1][0] = min(a[1][0] + p.a[0][0],a[1][1] + p.a[1][0]);
		res.a[1][1] = min(a[1][0] + p.a[0][1],a[1][1] + p.a[1][1]);
		return res;
	}
}M[MAXN << 2];

int n,q;

ll C,D,k;
ll v[MAXN];
ll a[MAXN];
ll c0[MAXN];
ll c1[MAXN];

void buildtree(int o,int l,int r)
{
	if (l == r)
	{
		M[o].a[0][0] = M[o].a[1][0] = c0[l];
		M[o].a[0][1] = C + c1[l];
		M[o].a[1][1] = c1[l];
		return;
	}
	int mid = l + r >> 1;
	buildtree(o << 1,l,mid);
	buildtree(o << 1 | 1,mid + 1,r);
	M[o] = M[o << 1] * M[o << 1 | 1];
}

void modify(int o,int l,int r,int p)
{
	if (l == r)
	{
		M[o].a[0][0] = M[o].a[1][0] = c0[l];
		M[o].a[0][1] = C + c1[l];
		M[o].a[1][1] = c1[l];
		return;
	}
	int mid = l + r >> 1;
	if (mid >= p)
		modify(o << 1,l,mid,p);
	else
		modify(o << 1 | 1,mid + 1,r,p);
	M[o] = M[o << 1] * M[o << 1 | 1];
}

int main()
{
	freopen("energy.in","r",stdin);
	freopen("energy.out","w",stdout);
	scanf("%d%lld%lld%lld",&n,&C,&D,&k);
	for (int i = 1;i <= n;i++)
		scanf("%lld",&v[i]);
	for (int i = 1;i <= n;i++)
	{
		scanf("%lld",&a[i]);
		c0[i] = v[i] * a[i];
		c1[i] = min(min(D + max(0ll,a[i] - D / k) * v[i],(D / k + 1) * k + max(0ll,a[i] - D / k - 1) * v[i]),max(D,k * a[i]));
	}
	buildtree(1,1,n);
	scanf("%d",&q);
	bool ok = 0;
	while (q--)
	{
		int x;
		ll y;
		scanf("%d%lld",&x,&y);
		v[x] = y;
		c0[x] = v[x] * a[x];
		c1[x] = min(min(D + max(0ll,a[x] - D / k) * v[x],(D / k + 1) * k + max(0ll,a[x] - D / k - 1) * v[x]),max(D,k * a[x]));
		modify(1,1,n,x);
		printf("%lld\n",min(M[1].a[0][0],M[1].a[0][1]));
	}
	return 0;
}

T4 小K的数列

题目内容

给定两个长度为nn的序列{ai}\{a_i\}，{bi}\{b_i\}，其中{ai}\{a_i\}是一个排列（1...n1...n各出现一次），bi≥0b_i\geq 0。全局给定一个常数VV，定义一个区间[l,r] (1≤l≤r≤n)[l,r]~(1\leq l\leq r\leq n)合法当且仅当∑i=lrbi≥V\sum_{i=l}^r b_i\geq V。而一个区间的权值被定义为maxi=lraimax_{i=l}^r a_i。给出qq次修改，每次修改会使bxb_x增加yy，求修改后所有合法区间权值的最小值。

输入格式

从文件sequence.insequence.in中读取数据。

第一行两个整数n,Vn,V。

接下来一行nn个整数{ai}\{a_i\}。

接下来一行nn个整数{bi}\{b_i\}。

接下来一行一个整数qq。

接下来qq行，每行两个整数x,yx,y，表示将bxb_x增加yy。(原来是：表示将bxb_x增加为yy，删掉’为’字）

输出格式

输出到文件sequence.outsequence.out。

共qq行，每行一个整数表示修改后所有合法区间权值的最小值，若没有合法区间输出-1。

样例 1 输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 20
5 3 1 2 4
2 2 2 5 3
10
1 5
2 3
1 5
3 2
5 3
4 4
3 4
3 2
3 5
3 5

样例 1 输出

1
2
3
4
5
6
7
8
9
10
-1
5
5
5
4
4
3
3
2
1

样例 2 输入

1
见ex_sequence2.in

样例 2 输出

1
见ex_sequence2.ans

提示

本题共有2525组数据。

对于所有数据1≤n,q≤3×1051\leq n,q\leq 3\times 10^5，0≤V≤10180\leq V\leq 10^{18}，0≤bi≤1090\leq b_i\leq 10^9，保证{ai}\{a_i\}是排列，1≤x≤n1\leq x\leq n，1≤y≤1091\leq y\leq 10^9。注意，修改后的bib_i可能会超过int类型范围。

对于8%8\%的数据，1≤n,q≤5001\leq n,q\leq 500。

对于20%20\%的数据，1≤n,q≤30001\leq n,q\leq 3000。

对于44%44\%的数据，1≤n,q≤3×1041\leq n,q\leq 3\times 10^4。

对于另外12%12\%的数据，ai=ia_i=i。

对于另外12%12\%的数据，q=1q=1。

对于另外16%16\%的数据，保证任意时刻合法区间个数不超过3×1063\times 10^6。

思路

按理来说，这道题应该是我最有感触的一道题目了

但是，我却因为一个奇怪的bug这道题8->1，直接完了，所以，我究竟是怎么写挂的呢，让我们拭目以待

这道题目，我开始想的是首先，有个单点修改的操作，还有区间求和，于是我显而易见地想到了树状数组，然后又看到了区间的最大值，我又开心地想到了st表，来完成所有的操作

本来可以得八分的，但是我似乎加了个

1
std::ios:;sync_with_stdio(false)

就挂了，不知道为啥，不知道有没有大神能帮我解释一下

算法1

直接每次O(n2)O(n^2)扫所有区间，取合法的区间max最小的。

复杂度O(qn2)O(qn^2)。

期望得分8分

PS：为啥我用了个树状数组和ST表，连暴力的分都没有啊喂

算法2

可以发现对于一个i，向右第一个合法的区间[i,j]的j是单调的。故算法1可以用O(n)O(n)的时间计算一次询问。

复杂度O(qn)O(qn)。

期望得分32分

当然也有别的平方算法。

比如前面提到的树状数组加ST表，然后再加个二分，也是32分，别问我怎么知道的

我右前方有个哥们就用的这个算法，活生生比我多出32分

算法3

对于ai=i，对于一个区间[l,r]，[1,r]一定不会更差，因为sum变大了而且max没变。所以我们只需考虑所有的[1,x]的区间。

大概是维护一个序列后缀+，查找最后一个>=V的数，用你喜欢的数据结构可以完成。

O(nlogn)O(nlogn)或者O(nlog2n)O(nlog^2n)。

期望得分额外12分

算法4

上面的算法和一个部分分“合法区间不超过…”提示我们是不是可以维护极少的合法区间即可。

事实上，如果一个区间[l,r]满足l>1且a{l-1}比[l,r]内的a最大值要小，那么[l-1,r]答案一定不比[l,r]差。所以只需考虑两侧都比区间内所有数大的区间，这样的区间至多有n个，称他们为极大区间。

考虑建立一棵树，树根是a最大的节点，接下来往两侧递归建树。

这样一颗树的一个子树就是一个极大区间。

接下来问题变成，树上一个点到根加一个值，询问最小的满足值>=V的点。直接倍增+树状数组维护即可。

时间复杂度O((n+q)logn)O((n+q)logn)。

期望得分100。

代码

std

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 300005;

int n,q,ans,top;
int S[MAXN];
int a[MAXN];
int b[MAXN];
int l[MAXN];
int r[MAXN];
int pos[MAXN];
int fa[MAXN][20];

bool vis[MAXN];

ll V;
ll sum[MAXN];

void modify(int p,int x)
{
	while (p <= n)
	{
		sum[p] += x;
		p += p & -p;
	}
}

ll query(int p)
{
	ll res = 0;
	while (p >= 1)
	{
		res += sum[p];
		p -= p & -p;
	}
	return res;
}

int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	scanf("%d%lld",&n,&V);
	for (int i = 1;i <= n;i++)
	{
		scanf("%d",&a[i]);
		pos[a[i]] = i;
	}
	for (int i = 1;i <= n;i++)
	{
		scanf("%d",&b[i]);
		modify(i,b[i]);
	}
	a[0] = a[n + 1] = 1e9;
	S[++top] = 0;
	for (int i = 1;i <= n;i++)
	{
		while (a[S[top]] < a[i])
			top--;
		l[i] = S[top];
		S[++top] = i;
	}
	S[top = 1] = n + 1;
	for (int i = n;i >= 1;i--)
	{
		while (a[S[top]] < a[i])
			top--;
		r[i] = S[top];
		S[++top] = i;
	}
	for (int i = 1;i <= n;i++)
	{
		fa[i][0] = (a[l[i]] < a[r[i]] ? l[i] : r[i]);
		if (a[i] == n)
			fa[i][0] = 0;
	}
	for (int i = n;i >= 1;i--)
	{
		int u = pos[i];
		for (int j = 1;j <= 18;j++)
			fa[u][j] = fa[fa[u][j - 1]][j - 1];
	}
	ans = 1e9;
	for (int i = 1;i <= n;i++)
		if (query(r[i] - 1) - query(l[i]) >= V)
		{
			vis[i] = 1;
			ans = min(ans,a[i]);
		}
	scanf("%d",&q);
	while (q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		modify(x,y);
		int u;
		if (!vis[x])
		{
			do
			{
				u = x;
				for (int j = 18;j >= 0;j--)
					if (fa[u][j] && !vis[fa[u][j]])
						u = fa[u][j];
				if (query(r[u] - 1) - query(l[u]) >= V)
				{
					vis[u] = 1;
					ans = min(ans,a[u]);
				}
			}while (u != x && vis[u]);
		}
		printf("%d\n",ans == 1e9 ? -1 : ans);
	}
	return 0;
}

赛后总结

济南划水赛真的是在划水呢qaq

然而要合理分配时间，以及合理使用算法，不能只是因为自己看到了这个题目看似让自己用这个算法，实际上，这样得到的算法不一定会比暴力更优秀

还是那句话：

Practice makes perfect!

继续努力！