天天看點
傳回

2022 東北四省賽 VP記錄/補題

VP情況

A B C D E F G H I J K L M
待補 AC AC(-6) AC AC 補題 補題 – AC(-2) – AC AC –

A.Encryption

–待補–

B.Capital Progra

題目分析

要求在給定的圖上選擇一個連通塊，使得該連通塊到其他點的距離和最小。

考慮貪心的選取，我們可以将圖展開，然後從葉節點開始按照逆序進行删點，删完個為止。可以用拓撲排序實作這個過程，設表示該點子樹的邊數(邊權和)，在排序過程中更新最大值即可。

Code 

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

const int N = 1e5 + 10;
vector<int> g[N];

int deg[N], dis[N];

inline void solve(){
    int n, k; cin >> n >> k;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        deg[u]++, deg[v]++;
    }
    if(n == k){ cout << 0 << endl; return; }
    queue<int> q;
    for(int i = 1; i <= n; i++) if(deg[i] == 1) dis[i] = 1, q.emplace(i);
    int cnt = 0, ans = -1;
    while(q.size()){
        int u = q.front(); q.pop();
        if(++cnt > n - k) break;
        ans = max(ans, dis[u]);
        for(auto v : g[u]){
            dis[v] = max(dis[v], dis[u] + 1);
            if(--deg[v] == 1) q.emplace(v);
        }
    }
    cout << ans << endl;
}

signed main(){
    solve();
    return 0;
}

C.SegmentTree

題目分析

要求在給定的覆寫區間的線段樹上找條路徑(自行構造)，使覆寫的點的數目最大。

首先可以肯定的是，當時，我們可以選取個葉子節點進行操作，進而使得整顆線段樹被覆寫。

考慮時，如何選取葉節點使得覆寫點數目最大。

如下圖為覆寫區間為的線段樹，我們可以發現貪心選取的規律：

2022 東北四省賽 VP記錄/補題
  • 對于第一層(共個節點)，當操作數時可以全部覆寫，否則最多覆寫個節點(即個節點)；
  • 對于第二層(共個節點)，當操作數時可以全部覆寫，否則最多覆寫個節點；
  • 對于第三層(共個節點)，當操作數時可以全部覆寫，否則最多覆寫個節點；
  • 對于第三層(共個節點)，當操作數時可以全部覆寫，否則最多覆寫個節點；
Note: 可以通過求求得最後一個完整層的深度

最後一層由于可能非完整層情況，是以需要進行讨論：目前最後一層共有棵子樹：

  • ，最多選棵子樹被選個節點(保證根節點被貪心選中)；
  • ，所有子樹均選擇個節點；
  • 否則全部選中。

那麼按照以上貪心的思路選擇即可。

Code 

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

void solve(){
    int m, q; cin >> m >> q;
    int ret = 1, sum = 0;
    for(ret = 1; ret < m; ret <<= 1) sum += std::min(ret, q);
    int sub = m - (ret >> 1);
    if(sub >= q) cout << sum + q << endl;
    else if((ret >> 1) >= q) cout << sum + sub << endl;
    else cout << sum + sub + min(sub, (q - (ret >> 1))) << endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
}

D.Game

題目分析

給定堆石子，輪流取石子，不能操作的輸。每次選一堆至少取個，剩餘的石子可以配置設定給其它堆。每輪遊戲給定詢問，要求回答區間的遊戲結果。

全的時候，先手必敗，那麼考慮能夠到達該狀态的狀态：僅有堆石子->先手必勝。

再繼續歸納，兩堆個石子，此時先手必敗，推廣該狀态，發現任意滿足，均為先手必勝。

推廣：發現當堆石子，為奇數時，先手必敗，然後可以猜測僅有偶數堆石子時，先手可能會勝利。

然後繼續猜測：設表示數字在區間的出現次數。 先手必敗當且僅當。

具體證明見官方題解…

那麼求區間數字出現次數是否全為偶數，直接莫隊離線詢問即可。

Code 

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

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

struct node{ 
    int l, r, id; 
    const bool operator<(const node &x) const { 
        int d1 = l / BLCOK_SIZE, d2 = x.l / BLCOK_SIZE;
        return d1 < d2 || (d1 == d2 && r < x.r);
    }
}ask[N];

int ans[N], cnt[N], nowAns = 0;

inline void op(int x){
    cnt[a[x]]++;
    cnt[a[x]] & 1 ? nowAns++ : nowAns--;
}

inline void solve(){
    int n = 0, q = 0; cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    BLCOK_SIZE = int(ceil(pow(n, 0.5)));
    for(int i = 1; i <= q; i++){
        cin >> ask[i].l >> ask[i].r, ask[i].id = i;
    }
    sort(ask + 1, ask + 1 + q);
    for(int i = 1, l = 1, r = 0; i <= q; i++){
        auto q = ask[i];
        while(l > q.l) op(--l);
        while(r < q.r) op(++r);
        while(l < q.l) op(l++);
        while(r > q.r) op(r--);
        ans[q.id] = nowAns;
    }
    for(int i = 1; i <= q; i++){
        if(ans[i]) cout << "Alice\n";
        else cout << "Bob\n";
    }

}   

signed main(){
    solve();
    return 0;
}

E.Plus

題目分析

打表找規律，可以發現當時，有且僅有組答案滿足，為。

Code 

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

inline void solve(){
    int n = 0; cin >> n;
    if(n >= 3) cout << "1" << endl << "2 3" << endl;
    else cout << "0\n" << endl;
}

signed main(){
    solve();
    return 0;
}

F.Tree Path

單獨見部落格：

題目分析

給定一棵樹，包含個節點和條帶權路徑，要求支援操作：

  • 删除最小的帶權路徑
  • 對于給定的節點，輸出所有不經過的帶權路徑中的最小值

Code - 樹剖+樹上差分+整體二分 

//待補

Code - 樹剖+線段樹維護補集 

//見：javascript:void(0)

G.Hot Water Pipe

題目分析

給定一段由段構成的熱水管，每一段都有機關的容積，這段水管從到從左向右編号，水從左向右流動。初始狀态下每段水管都會有一個溫度，每分鐘溫度會下降，當溫度下降的時會被立即加熱到。當第段水管中的用光後，水就會從左向右流動。現在問你間隔一段時間後用水，所取到水的平均溫度。

用一個雙端隊列模拟進水出水過程即可，對于用水量大于總水量的情況單獨讨論即可。

Code 

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

const int N = 1e6 + 10;
int a[N];

struct node{
    int vol, tem, t;
};

deque<node> q;


inline void solve(){
    int n, m, tmin, tmax; cin >> n >> m >> tmin >> tmax;
    auto calc = [&](int st, int time, int tem){
        time -= st;
        if(time < tem - tmin + 1) return tem - time;
        (time -= (tem - tmin + 1)) %= (tmax - tmin + 1);
        return tmax - time;
    };
    for(int i = 1, num = 0; i <= n; i++) cin >> num, q.emplace_front(node{1, num, 0});
    int time_cnt = 0;
    for(int i = 1; i <= m; i++){

        int t, k; cin >> t >> k;
        time_cnt += t;
        int ans = 0, kk = k;

        while(kk && q.size()){
            node now = q.front(); q.pop_front();
            int nvol = now.vol, ntm = now.tem, nst = now.t;
            if(nvol > kk) q.emplace_front(node{nvol - kk, ntm, nst}), nvol = kk;
            kk -= nvol;
            ans += nvol * calc(nst, time_cnt, ntm);
        }

        if(kk) ans += kk * tmax;

        cout << ans << endl;
        if(i != m) q.emplace_back(node{k - kk, tmax, time_cnt});
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    solve();
    return 0;
}

I.Generator

題目分析

初始狀态下給定，每次将變為中的一個數字，經過有限次操作将變為。求變為的操作次數的期望。

設表示目前數字為，期望次變為。則有轉移方程：

如何了解？目前數字可以向中的任何一個數字轉移，轉移機率均為，轉移占用一步，是以要。

其中，由于表示目前數字為，已經無法再轉移，此時操作已經終止。是以期望為即

移項，整理可得：

利用錯位相減法可以求得，則可得，則求和式為：

調和級數求和：，其中為歐拉常數。則對于較大資料可以用該式子求得近似值。

Code

Note: 歐拉常數用Python打表至即可。打表程式如下： 
import numpy as np
n = 100000000
logn_val = np.log(n)
sum = 0
for i in range(1, n + 1):
    sum += (1 / i)
print(sum - logn_val)

AC Code： 

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

const long double C = 0.5772156599001868;


inline void solve(){
    int n = 0; cin >> n, n--;
    if(n >= 20000000) cout << log(n) + 1 + C << endl;
    else{
        long double ans = 1;
        for(int i = 1; i <= n; i++) ans += 1.0 / (1.0 * i);
        cout << ans << endl;  
    }
}

signed main(){
    cout<<fixed<<setprecision(12);
    solve();
    return 0;
}

K.Maze

題目分析

給定大小迷宮，要求從左上角走到右下角，期間不能經過障礙物，且不能沿同一方向連續行走超過步。

考慮使用表示目前在點面向方向已經連續行走了步時的最大距離。則可以得到轉移方程：

那麼直接搜尋即可。

Code 

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;

const int dx[] = {0 ,0, 1, -1};
const int dy[] = {1, -1, 0 ,0};
const int INF = 1e9;

const int N = 2e5 + 10;
char g[110][110];
int dis[110][110][4][110], n, m;

struct node{ int x, y, face, step; };

inline int bfs(){
    memset(dis, 0x3f, sizeof(dis));
    queue<node> q;
    q.emplace(node{1, 1, 0, 0});
    for(int i = 0; i < 4; i++) dis[1][1][i][0] = 0;
    while(!q.empty()){
        node now = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            if(now.face != i || now.step <= m){
                int nx = now.x + dx[i], ny = now.y + dy[i], nxstep = now.step + 1;
                if(now.face != i) nxstep = 1;
                if(g[nx][ny] == '*' || nx > n || ny > n || nxstep > m || dis[nx][ny][i][nxstep] < INF) continue;
                dis[nx][ny][i][nxstep] = dis[now.x][now.y][now.face][now.step] + 1;
                if(nx == n && ny == n) return dis[nx][ny][i][nxstep];
                q.emplace(node{nx, ny, i, nxstep});
                //cout << "#DEBUG " << nx << ' ' << ny << ' ' << i << ' ' << nxstep << endl;  
            }
        }
    }
    return -1;
}

inline void solve(){
    cin >> n >> m; getchar();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> g[i][j];
        }
    }
    cout << bfs() << endl;
}

signed main(){
    int t = 1; cin >> t;
    for(int i = 1; i <= 100; i++) g[0][i] = '*';
    for(int i = 1; i <= 100; i++) g[i][0] = '*';
    while(t--) solve();
    return 0;
}

L.Polygon

題目分析

Code 

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

const int N = 2e5 + 10;
int a[N], sum = 0;
 
void solve(){
    int n = 0; cin >> n; sum = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
    for(int i = 1; i <= n; i++){
        if(sum - a[i] <= a[i]){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}
算法 圖論 c++ i++ 子樹
上一篇: 【ES8】新特性
下一篇: 《瘋狂Python講義》讀書筆記——第5章 函數和Lambda表達式目錄5.1 函數入門5.2 函數的參數5.3 局部函數5.4 函數的進階内容5.5 局部函數與lambda表達式

繼續閱讀