# Changsha College 2022 Summer Training Competition (1)

2022-08-06 09:32:27

#### The rich woman's value is maximized！

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

Let the prefix sum be sum[i].

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

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

Points with small point weights point to points with large point weights,Point-in-degree with large point weight ++.

Each point is enqueued once and dequeued once,复杂度 O(N).

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

#### 异世界

k warriors from different positions a i a_i 出发,寻找在 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.

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

First find the shortest number of moves to get to the treasure when all sides are built mina,多源 bfs.

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

2 ≤ n ≤ 1 0 18 2≤n≤10^{18}

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.

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