天天看点
返回

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表达式

继续阅读