16届东北四省赛题解

发表于 阅读次数： Changyan：

2022东北四省赛题解

A. Encryption

SA+二分

B. Capital Program

贪心+树形+二分

在一棵树上选择k个相连的点，要求最小化离这k个城市最远的城市的距离

首先我们贪心的想，当这棵树的根节点是直径中点的时候，一定有其他所有城市离根开始延申的城市的距离最小。

然后就是做一遍树型DP求出来每个点往下延申的最长深度，接着二分答案最小化的城市距离，一遍dfs，如果当前点到往下延伸的点的距离大于k意味着当前点也需要被选上，check最终选的点的数量是否<=k即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
const int N=200010,M=N*2,mod=1e9+7;
vector<int> edge[N];
int n,m,dep[N],color[N],depth,f[N],poi=1;

void dfs(int u,int pre){
    dep[u]=dep[pre]+1;
    for(auto v:edge[u]){
        if(v==pre) continue;
        dfs(v, u);
    }
}

bool find(int u,int pre, int depth){
    color[u]=1;
	for(auto v:edge[u]){
		if(v==pre) continue;
		if(find(v,u,depth)) return true;
	}
	if(dep[u]==depth) return true;
	else {
		color[u]=0;
		return false;
	}
}

void dfs_init(int u,int pre){
	f[u]=max(dep[u],f[u]);
	for(auto v:edge[u]){
		if(v==pre) continue;
		dfs_init(v, u);
		f[u]=max(f[u], f[v]);
	}
}

bool check(int x){
	if(depth<x) return 1;
	int ans=1;
	for(int i=1;i<=n;++i){
		if(i==poi) continue;
		if(f[i]-dep[i]>=x) ans++;
	}
	return ans<=m;
}

void solve(){
	n=read(),m=read();
    rep(i,1,n-1){
        int u=read(),v=read();
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1, 0);
    poi=1;
    for(int i=1;i<=n;++i){
        if(dep[i]>dep[poi]) poi=i;
    }
    memset(dep,0,sizeof dep);
    dfs(poi, 0);
    depth=0;
    for(int i=1;i<=n;++i){
        depth=max(depth, dep[i]);
    }
    find(poi,0,depth);
    for(int i=1;i<=n;++i){
        if(color[i]&&dep[i]==(1+depth)/2) poi=i;
    }
    memset(dep,0,sizeof dep);
	dfs(poi, 0);
	dfs_init(poi,0);
	int l=0,r=depth;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    print(l);
}

C. Segment Tree

找规律题。手动模拟下线段树叶子节点的增加情况可以发现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(){
    LL ans=0;
    n=read(),q=read();
    q=min(q, n);
    int h = (int)(log2(n)), k = (int)(log2(q));
    if (q <= n-(1ll<<h)) {
        ans = (1 << (k + 1)) - 1 + (h - k + 1) * q;
    } 
    else if (q <= (1 << h)) {
        ans=(1ll<<(k + 1))-(1ll<<h)-1+(h-k)*q+n;
    } 
    else {
        ans=n+q-1;
    }
    print(ans);
}

D. Game

随机化/莫队

我们很容易发现如果[l,r]中出现的个数都是偶数个则先手必败。正常做可以使用莫队，但是VP的时候我们是用随机化过的，因为给每个数随机出一个比较大的数可以防止出现a^b^c=0的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N=200010,M=N*2,mod=1e9+7;
int n,m,q,a[N],s[N],rd[N];

void solve(){
	n=read(),q=read();
    for(int i=1;i<=100000;++i) rd[i]=rand();
    rep(i,1,n) a[i]=read();
    
    rep(i,1,n) s[i]=s[i-1]^rd[a[i]];
    while(q--){
        int l=read(),r=read();
        int x=s[r]^s[l-1];
        if((x)==0) puts("Bob");
        else puts("Alice");
    }
}

E. Plus

签到+诈骗+打表

VP的时候先猜了一个结论：这个解很少，然后打了一个表发现只有p=2,q=3为解。

1
2
3
4
5
6
7
8
9
10
11
12
13
#define int LL
const int N=200010,M=N*2,mod=1e9+7;
int n,m,k,a[N];
string p;

void solve(){
    n=read();
    if(n<3) print(0);
    else{
        print(1);
        printf("2 3\n");
    }
}

G. Hot Water Pipe

这是一道复杂度分析题，通过分析每一次操作我们可以发现这道题完全可以暴力。我们只需要暴力维护每一段即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#define int LL
const int N=1000010,M=N*2,mod=1e9+7;
int n,m,k,a[N];
int tmn,tmx;
deque<pair<int,int>> q;

int get(int x){
    int len=(tmx-tmn+1);
    x-=tmn;
    return (x%len+len)%len+tmn;
}

void solve(){
	n=read(),m=read(),tmn=read(),tmx=read();
    rep(i,1,n) {
        a[i]=read();
        q.push_front({a[i], 1});
    }
    int delta=0;
    while(m--){
        LL ans =0 ;
        int t=read(),k=read();
        delta += t;
        int now = 0;
        while(q.size()){
            if(now == k) break;
            auto u=q.front(); q.pop_front();
            if(u.y+now<=k){
                ans += 1ll*u.y*get(u.x-delta);
                now += u.y ;
            }
            else{
                ans += 1ll*(k-now)*get(u.x-delta);
                u.y -= k-now;
                q.push_front(u);
                now = k;
            }
        }
        if(now!=k) ans += 1ll*(k-now)*tmx;
        q.push_back({get(tmx+delta), min(n,k)});
        print(ans);
    }
}

I. Generator

签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
double a[1000000];
const double t = 0.57721566490153287;
int main() {
    int n;
    cin >> n;
    double ans = 1;
    if (n <= 1000000) {
        for (int i = 2; i <= n; i++) {
            ans += 1.0 / (i - 1);
        }
    } else {
        ans = 1 + log(n) + 1.0 / (2 * n) + t;
    }
    cout << fixed << setprecision(10) << ans << '\n';
    return 0;
}

K.Maze

分层图BFS，签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define int LL
const int N=110,M=N*2,mod=1e9+7;
int n,m,k;
struct Node{
    int x,y,z,p,o;
};
Node q[N*N*N];
int hh,tt;
char str[N];
int g[N][N],st[N][N][N][4]; //0表示向下 1表示向右 2表示向上 3表示向左

void solve(){
	n=read(),m=read();
    rep(i,1,n){
        scanf("%s",str+1);
        rep(j,1,n){
            g[i][j]=(str[j]=='.');
        }
    }
    int ans=0x3f3f3f3f;
    hh=0,tt=-1;
    if(g[1][2]) q[++tt]={1,2,1,1,1},st[1][1][1][1]=1;
    if(g[2][1]) q[++tt]={2,1,1,1,0},st[2][1][1][0]=1;
    while(hh<=tt){
        auto u=q[hh++];
        int x=u.x,y=u.y,z=u.z,p=u.p,o=u.o;
        if(x==n&&y==n) {
            ans=min(ans,z);
        }
        for(int i=0;i<4;++i){
            int xx=x+mov[i][0],yy=y+mov[i][1];
            if(xx<1||xx>n||yy<1||yy>n||g[xx][yy]==0) continue;
            if(i==o){
                if(p+1>m||st[xx][yy][p+1][o]) continue;
                st[xx][yy][p+1][o]=1;
                q[++tt]={xx,yy,z+1,p+1,o};
            }
            else{
                if(st[xx][yy][1][i]) continue;
                st[xx][yy][1][i]=1;
                q[++tt]={xx,yy,z+1,1,i};
            }
        }
    }
    if(ans==0x3f3f3f3f) print(-1);
    else print(ans);
    rep(i,1,n) rep(j,1,n) rep(k,1,m) st[i][j][k][0]=st[i][j][k][1]=st[i][j][k][2]=st[i][j][k][3]=0;
}

L. Polygon

签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 2e5 + 10;
int n;
int a[maxn];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    int mx = *max_element(a + 1, a + 1 + n);
    if (sum - mx > mx) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
    return 0;
}