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

题目分析

要求在给定的图上选择一个连通块，使得该连通块到其他点的距离和最小。

考虑贪心的选取，我们可以将图展开，然后从叶节点开始按照逆$BFS$序进行删点，删完$n-k$个为止。可以用拓扑排序实现这个过程，设$dis[i]$表示该点子树的边数(边权和)，在排序过程中更新最大值即可。

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

题目分析

要求在给定的覆盖$[1,m]$区间的线段树上找$q$条路径(自行构造)，使覆盖的点的数目最大。

首先可以肯定的是，当$q\ge m$时，我们可以选取$m$个叶子节点进行$ADD$操作，从而使得整颗线段树被覆盖。

考虑$q\le m$时，如何选取叶节点使得覆盖点数目最大。

如下图为覆盖区间为$[1,12]$的线段树，我们可以发现贪心选取的规律：

• 对于第一层(共$1$个节点)，当操作数$p\ge 1$时可以全部覆盖，否则最多覆盖$q$个节点(即$0$个节点)；
• 对于第二层(共$2$个节点)，当操作数$p\ge 2$时可以全部覆盖，否则最多覆盖$q$个节点；
• 对于第三层(共$4$个节点)，当操作数$p\ge 4$时可以全部覆盖，否则最多覆盖$q$个节点；
• 对于第三层(共$8$个节点)，当操作数$p\ge 8$时可以全部覆盖，否则最多覆盖$q$个节点；

Note: 可以通过求$arg\_ma{x}_i(2^i\le m)$求得最后一个完整层的深度

最后一层由于可能非完整层情况，因此需要进行讨论：当前最后一层共有$12-8=4$棵子树：

• $q\le 4$，最多选$q$棵子树被选$1$个节点(保证根节点被贪心选中)；
• $4\le q\le 8$，所有子树均选择$1$个节点；
• 否则全部选中。

那么按照以上贪心的思路选择即可。

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

题目分析

给定$n$堆石子，轮流取石子，不能操作的输。每次选一堆至少取$1$个，剩余的石子可以分配给其它堆。每轮游戏给定询问，要求回答$[l,r]$区间的游戏结果。

全$0$的时候，先手必败，那么考虑能够到达该状态的状态：仅有$1$堆石子->先手必胜。

再继续归纳，两堆$1$个石子，此时先手必败，推广该状态，发现任意$A,B$满足$A\ne B$，均为先手必胜。

推广：发现当$m$堆石子，$m$为奇数时，先手必败，然后可以猜测仅有偶数堆石子时，先手可能会胜利。

然后继续猜测：设$f(x)$表示数字$x$在区间$[l,r]$的出现次数。 先手必败当且仅当$\forall x,f(x)\equiv 0(mod2)$。

具体证明见官方题解…

那么求区间数字出现次数是否全为偶数，直接莫队离线询问即可。

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

题目分析

打表找规律，可以发现当$n\ge 3$时，有且仅有$1$组答案满足，为$2,3$。

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

单独见博客：

题目分析

给定一棵树，包含$n$个节点和$k$条带权路径，要求支持操作：

• 删除最小的带权路径
• 对于给定的节点$x$，输出所有不经过$x$的带权路径中的最小值

两种思路，整体二分的待补，线段树维护堆的方法见：[P3250 HNOI2016] 网络 + [NECPC2022] F.Tree Path 树剖+线段树维护堆_HeartFireY的博客-CSDN博客

Code - 树剖+树上差分+整体二分

//待补

Code - 树剖+线段树维护补集

//见：https://blog.csdn.net/yanweiqi1754989931/article/details/125575597

G.Hot Water Pipe

题目分析

给定一段由$n$段构成的热水管，每一段都有$1$单位的容积，这$n$段水管从$1$到$n$从左向右编号，水从左向右流动。初始状态下每段水管$i$都会有一个温度$a_i$，每分钟温度会下降$1$，当温度下降的$T_{min}$时会被立即加热到$T_{max}$。当第$n$段水管中的用光后，水就会从左向右流动。现在问你间隔一段时间后用水，所取到水的平均温度。

用一个双端队列模拟进水出水过程即可，对于用水量大于总水量的情况单独讨论即可。

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

题目分析

初始状态下给定$n$，每次将$n$变为$[1,n]$中的一个数字，经过有限次操作将变为$1$。求变为$1$的操作次数的期望。

设$dp[n]$表示当前数字为$n$，期望$dp[n]$次变为$1$。则有转移方程：
$$dp[n]=\frac{dp[1]}{n}+\frac{dp[2]}{n}+\cdots +\frac{dp[n]}{n}+1$$
如何理解？当前数字$n$可以向$[1,n]$中的任何一个数字转移，转移概率均为$\frac{1}{n}$，转移占用一步，所以要$+1$。

其中，由于$dp[1]$表示当前数字为$1$，已经无法再转移，此时操作已经终止。因此期望为$0$即$dp[1]=0$

移项，整理可得：
$$ndp[n]=\sum _{i=1}^{n}dp[i]+n$$
利用错位相减法可以求得$dp[n]-dp[n-1]=\frac{1}{n-1}$，则可得$dp[2]=2$，则求和式为：
$$1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$$
调和级数求和：$1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=\ln (n)+\gamma$，其中$\gamma$为欧拉常数。则对于较大数据可以用该式子求得近似值。

Code

Note: 欧拉常数用Python打表至$1e8$即可。打表程序如下：

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

题目分析

给定$n\times n$大小迷宫，要求从左上角走到右下角，期间不能经过障碍物，且不能沿同一方向连续行走超过$m$步。

考虑使用$dis[x][y][face][step]$表示当前在$(x,y)$点面向$face$方向已经连续行走了$step$步时的最大距离。则可以得到转移方程：
$$dis[x^{\prime }][y^{\prime }][fac{e}^{\prime }][ste{p}^{\prime }]=dis[x][y][face][step]+1,s.t.ste{p}^{\prime }=(step+1)if(fac{e}^{\prime }=face)else(1)$$
那么直接$BFS$搜索即可。

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

题目分析

给定$n$条线段以及每条线段的长度，要求判断能否构成多边形。

考虑多边形构成条件。只需要求边长和然后挨个检验一下就可以了。

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