天天看點
傳回

[GYM103660] The 19th Zhejiang University City College Programming Contest 浙大城市學院校賽VP/S

後面倆小時吃飯睡覺去了…

A B C D E F G H I J K L
AC AC AC 補 補 AC AC AC AC AC – AC

GYM103660A.​​Who is The 19th ZUCCPC Champion​​

題目思路

拼手速

Code 

print("Monster Tower")

GYM103660B.​​Jiubei and Overwatch​​

題目思路

傷害為群體傷害，是以直接找到最大值讨論即可。

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​​

題目思路

要求構造一種序列，按照兩種排序執行時的交換操作次數一樣。

容易發現，按照兩種排序執行，交換操作的執行次序均與逆序對的數量有關。那麼直接構造一個的倒序序列即可。

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​​

題目思路

給定個鏡子，計算對于每個入射光線能否射出/循環反射。

題很牛逼

記憶化搜尋，寫起來比較麻煩。

GYM103660E.​​Disjoint Path On Tree​​

題目思路

給定一棵樹，求樹上不相交的路徑對數。

容斥一下：不相交路徑對數 = 總路徑對數 - 相交路徑對數

考慮如何計算相交路徑對數：枚舉點作為一條路徑的，則此時的相交方案數為經過且不在的路徑數 × $LCA i LCAi$的路徑對數。

那麼直接樹上計數然後容斥即可。

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​​

題目思路

給定，求下式最簡形式分子和：

化簡一次，變為：

發現內插補點：

那麼直接一遍化簡一邊求內插補點即可，每次最多化簡次。複雜度可以接受。

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​​

題目思路

給定二維平面上的一些矩形，并給定這些矩形的權值，從這些矩形中選擇兩個不相交的矩形，使權值和最大。

發現兩個矩形不相交，則其在軸上的投影均不相交。于是可以分别提取軸和軸并排序，然後求字尾最大值二分求答案即可。

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​​

題目思路

定義為點到區間的距離(如果包含則距離為)。求使得最小。

[GYM103660] The 19th Zhejiang University City College Programming Contest 浙大城市學院校賽VP/S

不難發現，實際上就是對于給定的一堆區間，尋找一個豎線，使之穿過的區間盡可能地多，且距離未穿過的區間的距離盡可能小。考慮如何處理未穿過的區間：

  • 初始我們插入一個區間，此時軸位于區間内，左右堆各插入一個端點；
  • 對于新插入的區間，如果右端點比目前左側最右端更靠左，說明軸應該往左移動，使之穿過新插入的區間；
  • 如果新插入的區間，如果左端點比目前右側最左端更靠右，說明軸應該向右移動，使之穿過新插入的區間；
  • 否則，軸不需要移動，因為左右兩側隊列處于平衡狀态。那麼左右端點分别插入左右隊列即可。

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​​

題目思路

給定兩個長度為的數組和，要求将分成端連續區間，使得每段區間滿足。

考慮合法的方案：令，顯然滿足區間即滿足。不妨對做字首和，得到字首和數組，于是滿足條件的區間變為即為。是以問題可以轉化為對求最長上升子序列的長度。

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)​​

題目思路

求滿足條件的四元組個數：

  • 的字典序嚴格大于

簡單版本直接暴力查找就可以，查到符合要求的字首直接計數即可。

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​​

題目思路

有一個高層的塔，塔的每層有一個怪獸，怪獸擁有的血量，初始血量為，擊敗第層後可以獲得該層怪獸的血量(即)，當且僅當時才可以擊敗該怪獸。每次隻能選擇底層的怪獸進行攻擊。問最小的。

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;
}
c++ 算法 開發語言 #define i++
上一篇: 部落格園樣式美化(相容為知筆記)部落格園樣式美化(相容為知筆記)
下一篇: call_user_func和call_user_func_array的差别[轉載]

繼續閱讀