长沙学院2022暑假训练赛（一）

富婆价值最大化！

题意
给定长度为 n 的序列 a[]，每次可以选择一段连续区间。
一共 m 个询问，第 i 个询问表示在前 $k_i$ 个位置中，能够得到区间最大值的区间个数一共有多少？
$1\le n,m\le 10^6,-10^9\le a_i\le 10^9,1\le k_i\le n$

思路
经典模型，最大子段和。
设前缀和为 sum[i]。
以第 i 个位置作为右端点的区间最大值为 sum[i] - sum[j]，其中 sum[j] 为 1~i 位置前缀和的最小值。

那么从前往后走，走到当前位置 i：

• 如果说以当前位置结尾的区间最大值 sum[i] - sum[j] 比维护的区间最大值大，那么满足的区间个数就为满足前缀和为最小值 sum[j] 的位置个数 cnt。
• 如果说 sum[i] - sum[j] 和维护的区间最大值相等，那么继承上一位置的状态，满足的区间个数就为上一位置的答案数 + 满足前缀和为最小值 sum[j] 的位置个数 cnt。
• 然后更新当前 sum[i] 是否为最小值，如果比最小值小，更新最小值，cnt = 1；如果等于最小值，cnt++。

Code

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 1000010, mod = 1e9+7;
int T, n, m;
int a[N], ans[N];

signed main(){
    
	Ios;
	cin >> n >> m;
	
	int mina = 0, maxa = -1e9;
	int cnt = 1, sum = 0;
	
	for(int i=1;i<=n;i++)
	{
    
		ans[i] = ans[i-1];
		
		int x;cin >> x;
		sum += x;
		if(sum - mina > maxa){
    
			maxa = sum - mina;
			ans[i] = cnt;
		}
		else if(sum - mina == maxa){
    
			ans[i] += cnt;
		}
		
		if(sum < mina){
    
			mina = sum;
			cnt = 1;
		}
		else if(sum == mina) cnt ++;
	}
	
	while(m--)
	{
    
		int x; cin >> x;
		cout << ans[x] << endl;
	}
	
	return 0;
}

Beautiful path

题意
给定一棵树，一共 n 个节点，每个节点有权值 $a_i$。
找到最长的一条链，满足从前往后链上点权严格递增。
输出最长链长度。

$1\le n\le 10^6,0\le a_1,\dots ,a_n\le 10^9$

思路
拓扑序 + dp
点权小的点指向点权大的点，点权大的点入度 ++。
把入度为 0 的点放到队列中，用队列中点权较小的点更新点权较大的点。
每个点入队一次出队一次，复杂度 O(N)。

树形 DP
官方题解给的是树形DP，维护以每个点为根的最长上升序列 f[i, 0] 和最长下降序列 f[i, 1]，两者相加 -1 便是经过该节点的最长严格递增链，很妙。

Code1

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 1000010, mod = 1e9+7;
int T, n, m;
PII a[N];
int w[N], ru[N], f[N];
vector<int> e[N];
int ans;

void topsort()
{
    
	queue<int> que;
	for(int i=1;i<=n;i++){
    
		if(ru[i] == 0) que.push(i), f[i] = 1;
	}
	
	while(que.size())
	{
    
		int x = que.front(); que.pop();
		
		for(int tx : e[x])
		{
    
			if(w[tx] <= w[x]) continue;
			ru[tx] --;
			f[tx] = max(f[tx], f[x] + 1);
			ans = max(ans, f[tx]);
			if(ru[tx] == 0) que.push(tx);
		}
	}
}

signed main(){
    
	Ios;
	cin >> n;
	for(int i=1;i<n;i++)
		cin >> a[i].fi >> a[i].se;
	
	for(int i=1;i<=n;i++) cin >> w[i];
	
	for(int i=1;i<n;i++)
	{
    
		int x = a[i].fi, y = a[i].se;
		e[x].push_back(y);
		e[y].push_back(x);
		if(w[x] < w[y]) ru[y]++;
		else if(w[x] > w[y]) ru[x] ++;
	}
	
	ans = 1;
	topsort();
	cout << ans;
	
	return 0;
}

Code2

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 1000010, mod = 1e9+7;
int T, n, m;
int a[N];
vector<int> e[N];
int w[N], ans;
int f[N][2];

void dfs(int x, int fa)
{
    
	f[x][0] = f[x][1] = 1;
	for(int tx : e[x])
	{
    
		if(tx == fa) continue;
		
		if(!f[tx][0]) dfs(tx, x);
		if(w[tx] > w[x]) f[x][0] = max(f[x][0], f[tx][0] + 1);
		else if(w[tx] < w[x]) f[x][1] = max(f[x][1], f[tx][1] + 1);
	}
	ans = max(ans, f[x][0] + f[x][1] - 1);
}

signed main(){
    
// Ios;
	scanf("%lld", &n);
	for(int i=1;i<n;i++){
    
		int x, y;scanf("%lld%lld", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	for(int i=1;i<=n;i++) cin >> w[i];
	
	dfs(1, 0);
	
	cout << ans;
	
	return 0;
}

异世界

题意
给定 n 个点 m 条边的无向图，每条边有修建时间 $w_i$。
k 个勇者从不同的位置 $a_i$ 出发，寻找在 x 位置的宝藏。

如果一条边被修建了，那么其通过时间为 1，否则不能通过。若干条边可以在同一时刻修建，也就是说当需要修建多条边时，修建的时间为所有边之中的最大修建时间。

游戏开始后，每个勇者同时将以最优策略往宝藏走。有一个勇者获得宝藏之后，游戏结束。

如果修建能够保证不破坏勇者拿到宝藏的最短时间的情况下的修建边的时长最短，输出两者之和。

$1\le k,x\le n\le 2\times 10^5,0\le w\le 2\times 10^5,1\le a_i\le n$

思路
多源bfs + 二分答案
首先在所有边都修建的情况下求出拿到宝藏的最短步数 mina，多源 bfs。
然后，二分修建时间，在这个时间内的边都能走，否则不能走。跑多源 bfs 判断是否能在 mina 步内拿到宝藏。如果可以继续分。

从多个点出发，把这些点都先放到队列中，每次取出一个更新其他节点，第一次到达的步数一定是最短步数。

Code

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], p[N];
vector<PII> e[N];
int en, k;
int mina;
int f[N];

int bfs(int mid)
{
    
	for(int i=1;i<=n;i++) f[i] = 0;
	
	queue<int> que;
	for(int i=1;i<=k;i++) f[p[i]] = 1, que.push(p[i]);
	
	while(que.size())
	{
    
		int x = que.front(); que.pop();
		if(x == en && mid == 2e5 + 10) return f[en];

		if(x == en && f[en] <= mina) return 1;
		
		for(auto it : e[x])
		{
    
			int tx = it.fi, time = it.se;
			if(time > mid) continue;
			if(f[tx]) continue;
			f[tx] = f[x] + 1;
			que.push(tx);
		}
	}
	return 0;
}

bool check(int mid)
{
    
	int x = bfs(mid);
	return x;
}

signed main(){
    
	Ios;
	cin >> n >> k >> en;
	
	for(int i=1;i<=k;i++) cin >> p[i];
	
	cin >> m;
	while(m--)
	{
    
		int x, y, z; cin >> x >> y >> z;
		e[x].push_back({
    y, z});
		e[y].push_back({
    x, z});
	}
	
	mina = bfs(2e5 + 10);
	
	if(!mina){
    
		cout << -1;
		return 0;
	}
	
	int l = 0, r = 2e5;
	while(l < r)
	{
    
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l + mina - 1 << endl;
	
	return 0;
}

平面最小距离

题意
给定 n 个点放到棋盘里，如何排列使得曼哈顿距离最大的两个点距离最小，输出最大距离的最小值。
$2\le n\le 10^{18}$

思路

当围成菱形的时候距离最小，当再往这个菱形加点时，如果加的点数不超过中间那行的长度的话，距离+1，否则距离+2，进入下一个菱形。

二分第一个点数大于 n 的菱形，然后判断是这一个还是上一个。

不太好想，得多画画！

Code

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

bool check(int mid)
{
    
	if(2 * mid * mid + 2 * mid + 1 >= n) return 1;
	return 0;
}

signed main(){
    
	Ios;
	
	cin >> n;
	
	int l = 0, r = 1e9;
	while(l < r)
	{
    
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	if(n - (2*(l-1)*(l-1) + 2*(l-1) + 1) > 2*(l-1) + 1) cout << 2 * l << " ";
	else cout << 2*l - 1 << " ";
	
	return 0;
}