[gym103660] the 19th Zhejiang University City College Programming Contest vp/s

I went to bed after eating for the next two hours …

GYM103660A.Who is The 19th ZUCCPC Champion

Topic ideas

Fight fast

Code

print("Monster Tower")

GYM103660B.Jiubei and Overwatch

Topic ideas

Injury is group injury , Therefore, we can directly find the maximum value to discuss .

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;
int a[N], s[N];

inline void solve(){
    
    int n, k, x, y; cin >> n >> k >> x >> y;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int maxx = *max_element(a + 1, a + 1 + n), ans = 0;
    if(k * x >= maxx) {
    
        ans = maxx / x + (maxx % x == 0 ? 0 : 1);
    } else {
    
        maxx -= k * x;
        ans = k + maxx / y + (maxx % y == 0 ? 0 : 1);
    }
    cout << ans << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

GYM103660C.Ah, It’s Yesterday Once More

Topic ideas

It is required to construct a sequence , The number of exchange operations when the two sorts are executed is the same .

Easy to find , Execute in two sorts , The execution order of exchange operations is related to the number of reverse pairs . Then directly construct a $n\to 1$ The reverse sequence of .

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;
int a[N], s[N];

inline void solve(){
    
    int n = 0; cin >> n;
    for(int i = n; i >= 1; i--) cout << i << " \n"[i == 1];
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

GYM103660D.Reflection

Topic ideas

Given $n$ A mirror , Calculate whether each incident light can be emitted / Circular reflection .

The question is awesome

Memory search , It's more difficult to write .

GYM103660E.Disjoint Path On Tree

Topic ideas

Given a tree , Find the logarithm of disjoint paths on the tree .

Excuse me ： Disjoint path logarithm = Total path logarithm - Intersection path logarithm

Consider how to calculate the logarithm of intersecting paths ： Enumeration points $i$ As a path $LCA$, Then the number of intersection schemes at this time is $i$ And $LCA$ be not in $i$ The number of paths × $LCA $by$i $The\; number\; of\; paths+$LCA$All\; in$i$ Path logarithm of .

Then count directly on the tree and then exclude .

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
vector<signed> g[N];

int sz[N], ans = 0;
int n = 0;

void dfs(int u, int fa){
    
    int res = 0;
    sz[u] = 0;
    for(auto v : g[u]){
    
        if(v == fa) continue;
        dfs(v, u);
        (res += sz[v] * sz[u]) %= MOD;
        sz[u] += sz[v];
    }
    sz[u]++;
    int t = (res + sz[u]) % MOD;
    (ans += ((n - sz[u]) * sz[u] % MOD * t % MOD)) %= MOD;
    (ans += (t * (t + 1) / 2) % MOD) %= MOD;
}

inline void solve(){
    
    cin >> n; ans = 0;
    for(int i = 1; i <= n; i++) g[i].clear();
    for(int i = 1; i <= n - 1; i++){
    
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1, 0);
    int path = ((n * (n + 1)) / 2) % MOD, all = ((path * (path + 1)) / 2) % MOD;
    ans = ((all - ans) % MOD + MOD) % MOD;
    cout << ans << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

GYM103660F.Sum of Numerators

Topic ideas

Given $n,k$, Find the molecular sum of the simplest form of the following formula ：
$$\frac{1}{2^k},\frac{2}{2^k},\frac{3}{2^k},\frac{4}{2^k},\dots ,\frac{n}{2^k}$$
Simplify once , Turn into ：
$$\frac{1}{2^k},\frac{1}{2^{k-1}},\frac{3}{2^k},\frac{2}{2^{k-1}},\dots ,\frac{n}{2^k}$$
Find the difference ：
$$det=\frac{(n-1)\times ((n-1)+1)}{2}$$
Then simplify it directly and calculate the difference value , Simplify at most each time $31$ Time . The complexity is acceptable .

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;



inline void init(){
    
    
}

inline void solve(){
    
    int n = 0, k = 0; cin >> n >> k;
    if(k == 0) cout << (n + 1) * n / 2 << endl;
    else{
    
        int ans = (n + 1) * n / 2;
        while(n && k){
    
            n >>= 1, k--;
            ans -= (1 + n) * n / 2;
        }
        cout << ans << endl;
    }
}

signed main(){
    
    init();
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

GYM103660G.Guaba and Computational Geometry

Topic ideas

Given some rectangles on the two-dimensional plane , And give the weights of these rectangles , Select two non intersecting rectangles from these rectangles , Make the sum of weights maximum .

Two rectangles are found not to intersect , It's in $x,y$ The projections on the axes do not intersect . So you can extract $x$ Axis and $y$ Axis and sort , Then find the maximum suffix by two points to find the answer .

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 3e5 + 10;
int a[N], b[N], c[N], d[N], w[N], p[N];

struct line{
    
    int st, ed, w;
    const bool operator< (const line &x) const {
     return st < x.st; } 
}lines[N];

inline void solve(){
    
    int n = 0, ans = -1; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
    for(int i = 1; i <= n; i++) cin >> w[i];
    auto calc = [&](){
    
        p[n] = lines[n].w;
        for(int i = n - 1; i >= 1; --i) p[i] = max(p[i + 1], lines[i].w);
        for(int i = 1; i < n; i++){
    
            int k = upper_bound(lines + 1, lines + 1 + n, line{
    .st = lines[i].ed, .ed = 0, .w = 0}) - lines;
            if(k == n + 1) continue;
            ans = max(ans, lines[i].w + p[k]);
        }
    };
    for(int i = 1; i <= n; i++){
    
        lines[i] = line{
    .st = a[i], .ed = c[i], .w = w[i]};
    }
    sort(lines + 1, lines + 1 + n);
    calc();
    for(int i = 1; i <= n; i++){
    
        lines[i] = line{
    .st = b[i], .ed = d[i], .w = w[i]};
    }
    sort(lines + 1, lines + 1 + n);
    calc();
    cout << ans << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

GYM103660H.Distance

Topic ideas

Definition $dist(l,r,x)$ Is a point $x$ To the interval $[l,r]$ Distance of ( If included, the distance is $0$). seek $x$ bring ${\sum }_{i=1}^{k}dist(l_i,r_i,x)$ Minimum .

It's not hard to find out , In fact, for a given set of intervals , Find a vertical line , Make it cross as many intervals as possible , And the distance from the unpaved interval should be as small as possible . Consider how to deal with areas that have not been crossed ：

• Initially, we insert an interval , At this time, the axis is in the interval , Insert an endpoint into the left and right stacks ;
• For the newly inserted interval , If the right end point is more left than the rightmost end of the current left , It means that the axis should move to the left , Make it cross the newly inserted interval ;
• If the newly inserted interval , If the left end point is more right than the leftmost end of the current right , It means that the axis should move to the right , Make it cross the newly inserted interval ;
• otherwise , Axis does not need to move , Because the left and right queues are in balance . Then insert the left and right endpoints into the left and right queues respectively .

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long 
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;

priority_queue<int, vector<int>, less<int>> leftq;
priority_queue<int, vector<int>, greater<int>> rightq;


inline void solve(){
    
    int n = 0, ans = 0; cin >> n;
    leftq.emplace(-INT_MAX);
    rightq.emplace(INT_MAX);
    for(int i = 1; i <= n; i++){
    
        int l, r; cin >> l >> r;
        if(r < leftq.top()){
    
            ans += leftq.top() - r;
            rightq.emplace(leftq.top()); leftq.pop();
            leftq.emplace(l), leftq.emplace(r);
        } else if(l > rightq.top()){
    
            ans += l - rightq.top();
            leftq.emplace(rightq.top()); rightq.pop();
            rightq.emplace(l), rightq.emplace(r);
        } else {
    
            leftq.emplace(l), rightq.emplace(r);
        }
        cout << ans << endl;
    }
    

}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

GYM103660I.Array Division

Topic ideas

Two lengths are given $n$ Array of $a$ and $b$, The request will $1,2,3,\dots ,n$ Divide into $k$ End continuous interval , Make each section meet ${\sum }_{i=l}^r{a}_i>{\sum }_{i=l}^r{b}_i$.

Consider legal solutions ： Make $c_i=a_i-b_i$, Obviously, it satisfies the interval $\sum a_i>\sum b_i$ The meet $\sum c_i>0$. Might as well $c[]$ Do prefixes and , Get prefix and array $d[i]$, So the interval that satisfies the condition $[l,r]$ Turn into $d[r]-d[l]>0$ That is to say $d[r]\ge d[l]$. So the problem can be turned into right $d[]$ Find the length of the longest ascending subsequence .

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 6e3 + 10;
int a[N], b[N], c[N], dp[N];

inline void solve(){
    
    int n = 0; cin >> n;
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) c[i] = a[i] - b[i], c[i] += c[i - 1];
    for(int i = 1; i <= n; i++){
    
        for(int j = 1; j <= i; j++){
    
            if(c[i] - c[j - 1] >= 0 && c[j - 1] >= 0) dp[i] = max(dp[i], dp[j - 1] + 1);
        }
    }
    if(c[n] < 0) cout << "-1" << endl;
    else cout << dp[n] << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

GYM103660J.Substring Inversion (Easy Version)

Topic ideas

Find the quaternion that meets the condition $[a,b,c,d]$ Number ：

• $1\le a\le b\le n$
• $1\le c\le d\le n$
• $a\le c$
• $s[a:b]$ The lexicographic order of is strictly greater than $s[c:d]$

The simple version can be directly searched by violence , If you find a prefix that meets the requirements, you can count it directly .

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;


inline void solve(){
    
    int n = 0; string s;
    cin >> n >> s;
    int ans = 0;
    for (int i = 0; i < n; i++){
    
        for (int j = i + 1; j < n; j++){
    
            for (int l = 1; j + l - 1 < n; l++){
    
                if (s[i + l - 1] < s[j + l - 1]) break;
                if (s[i + l - 1] > s[j + l - 1]){
    
                    int len1 = n - i - l + 1, len2 = n - j - l + 1;
                    ans = (ans + (len1 * len2 % mod)) % mod;
                    break;
                }
                if (s[i + l - 1] == s[j + l - 1]) ans = (ans + n - i - l) % mod;
            }
        }
    }
    cout << ans << '\n';
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

GYM103660L.Monster Tower

Topic ideas

There is a high $n$ Tower on the first floor , There is a monster on each floor of the tower , Monsters have $a_i$ HP , Initial health is $x$, Defeat number $i$ After this layer, you can get the blood volume of the monster in this layer ( namely $x+=a[i]$), If and only if $x\ge a[i]$ Only then can we defeat the monster . Only the bottom can be selected at a time $k$ Tier monsters attack . Ask the smallest $x$.

It is easy to find that the answer is monotonous , So consider the dichotomous answer .$check$ When using the priority queue to maintain the bottom $k$ The monster's HP of layer , It is illegal when the health at the top of the heap is greater than the current health .

An array is 2e5

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
int a[N], s[N];

inline void solve(){
    
    int n = 0, k = 0; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    auto check = [&](int mid){
    
        priority_queue<int, vector<int>, greater<int>> pq;
        int stn = mid;
        int pos = 1; while(pos <= k) pq.emplace(a[pos++]);
        while(pq.size()){
    
            if(stn < pq.top()) return false;
            else{
    
                stn += pq.top();
                pq.pop();
                if(pos <= n) pq.emplace(a[pos++]);
            }
        }
        return true;
    };
    int l = 0, r = *max_element(a + 1, a + 1 + n), ans = 0;
    while(l <= r){
    
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;

}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}