current position:Home>Changsha College 2022 Summer Training Competition (1)

Changsha College 2022 Summer Training Competition (1)

2022-08-06 09:32:27Small dimples.

The rich woman's value is maximized!

题意
给定长度为 n 的序列 a[],A continuous interval can be selected each time.
一共 m 个询问,第 i A query is indicated before k i k_i ki 个位置中,The total number of intervals that can get the maximum value of the interval?
1 ≤ n , m ≤ 1 0 6 ,   − 1 0 9 ≤ a i ≤ 1 0 9 ,   1 ≤ k i ≤ n 1≤n,m≤10^6,\ −10^9≤a_i≤10^9,\ 1≤k_i≤n 1n,m106, 109ai109, 1kin

思路
经典模型,最大子段和.
Let the prefix sum be sum[i].
以第 i The maximum value of the interval with the position as the right endpoint is sum[i] - sum[j],其中 sum[j]1~i Minimum sum of positional prefixes.

Then go from front to back,走到当前位置 i

  • If say the maximum value of the interval ending at the current position sum[i] - sum[j] Greater than the maintained interval maximum value,Then the number of satisfied intervals is satisfied that the prefix sum is the minimum value sum[j] 的位置个数 cnt.
  • 如果说 sum[i] - sum[j] Equal to the maintained interval maximum value,Then inherit the state of the previous position,The number of satisfied intervals is the number of answers in the previous position + Satisfy that the prefix sum is the minimum value sum[j] 的位置个数 cnt.
  • 然后更新当前 sum[i] is the minimum value,如果比最小值小,更新最小值,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 a_i ai.
Find the longest chain,Satisfy that the point weight on the chain is strictly increasing from front to back.
Output the longest chain length.

1 ≤ n ≤ 1 0 6 ,   0 ≤ a 1 , … , a n ≤ 1 0 9 1≤n≤10^6,\ 0≤a_1,…,a_n≤10^9 1n106, 0a1,,an109

思路
拓扑序 + dp
Points with small point weights point to points with large point weights,Point-in-degree with large point weight ++.
把入度为 0 的点放到队列中,Points with higher weights are updated with points with lower weights in the queue.
Each point is enqueued once and dequeued once,复杂度 O(N).

树形 DP
The official problem solution is a tree shapeDP,Maintain the longest ascending sequence rooted at each point f[i, 0] and the longest descending sequence f[i, 1],两者相加 -1 is the longest strictly increasing chain through the node,很妙.

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 条边的无向图,Each edge has a construction time w i w_i wi.
k warriors from different positions a i a_i ai 出发,寻找在 x A treasure of location.

If a side has been constructed,Then its transit time is 1,否则不能通过.Several edges can be built at the same time,That is, when multiple edges need to be built,The construction time is the maximum construction time among all sides.

游戏开始后,Each hero will go to the treasure with the optimal strategy at the same time.After a brave man got the treasure,游戏结束.

If the construction can ensure that the shortest time for the hero to get the treasure is not destroyed, the construction side has the shortest duration,输出两者之和.

1 ≤ k , x ≤ n ≤ 2 × 1 0 5 ,   0 ≤ w ≤ 2 × 1 0 5 ,   1 ≤ a i ≤ n 1≤k,x≤n≤2×10^5,\ 0≤w≤2×10^5,\ 1≤a_i≤n 1k,xn2×105, 0w2×105, 1ain

思路
多源bfs + 二分答案
First find the shortest number of moves to get to the treasure when all sides are built mina,多源 bfs.
然后,Two minutes of construction time,You can go anywhere within this time,Otherwise you can't go.跑多源 bfs 判断是否能在 mina Get treasure within steps.如果可以继续分.

from multiple points,Put these points in the queue first,Each time you take out one update other nodes,The number of steps reached for the first time must be the shortest number of steps.

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;
}

The minimum distance from the plane

题意
给定 n Put the dots on the chessboard,How to arrange so that the two points with the largest Manhattan distance have the smallest distance,Output the minimum value of the maximum distance.
2 ≤ n ≤ 1 0 18 2≤n≤10^{18} 2n1018

思路

The distance is the smallest when enclosing a rhombus,When adding points to this rhombus,If the number of points added does not exceed the length of the middle row,距离+1,否则距离+2,Go to the next diamond.

The first point of two points is greater than n 的菱形,Then decide whether it is this one or the previous one.

不太好想,draw more!

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;
}

copyright notice
author[Small dimples.],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/218/202208060914254859.html

Random recommended