Hile_Meow's Blog

2020CCPC东北四省赛

2021-10-15 分类 组队训练 作者 Hile_Meow ~10.53K 字

10.15打的组队赛，感觉自从使用了战术之后发挥稳定了不少，出了9/12题。

战术：Hile_Meow非必要不上机，Hile_Meow所读题意必让队友确认（经典wa签到+读歪题）

A. Micro Structure Thread

构造+MST。待补

B. Team

网络流。考虑通过源汇点的流量控制$m$个组合，然后$B$向$A$建边，$A$向$C$建边，流量为1，费用为预处理的$f(u,v)$，$A$拆点控制流量为1。

虽然是求最大权值，但是因为所有路径长度相同，我们可以令每条边的权值为$M-f(u,v)$，然后跑dijkstra费用流，或者直接边权取反上spfa费用流（可处理负权边）。

C. Function

数学。显然$f(x)\le x$，而且根据这个后缀积的不可构造性，猜测大概率会收敛到一个$f(x)=x$的值（如$k000001$或一个个位数），看榜上过的挺快就直接冲了一发记忆化+暴力，跑得飞快。

D. Fall Guys

签到。Boboge秒了。

E. Liner vectors

构造。首先显然$n=k$且$n\ne 1$时无解，然后考虑当$k\%2=0$时，每一维度形成的列向量异或为0，说明任意列向量都等于其他$n-1$个列向量的异或和，矩阵不满秩。

接下来就好构造了，前$k+1$个向量的前$k+1$位形成一个对角线为0的矩阵，后面的行直接对前面$n-k-1$位每行分配一个$1$，每行剩下的$1$全放在最低的$k-1$位。

赛中写的唯一一道题，还被n=1,k=1卡了一发

Code
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
void run() {
    scanf("%d%d",&n,&k);
    if(n==1){
        printf("1\n");
    }
    else if(k%2==0||n==k){
        printf("-1\n");
    }else{
        vector<ll> ve;
        ll tmp=1LL<<(k+1);
        tmp--;
        for(int i=0;i<k+1;i++){
            ve.push_back(tmp^(1LL<<i));
        }
        tmp>>=2;
        for(int i=k+1;i<n;i++){
            ve.push_back(tmp^(1LL<<i));
        }
        sort(ve.begin(),ve.end());
        for(int i=1;i<=n;i++){
            printf("%lld%c",ve[i-1],i==n?'\n':' ');
        }
    }
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--) {
        run();
    }
    return 0;
}

F. Splendor

贪心+大模拟的防ak。貌似不太可做

G. Halli Galli

签到。Boboge秒了。

H. PepperLa’s String

贪心。既然要优先最短，其次字典序最小。

分两类位置：

  1. 使字符串长度变短：删单个字符，删两个字符之一，删$16^k$个连续字符一端
  2. 使字符串长度不变：删连续相同字符一端

有第一类优先删第一类，如果能让字典序变小则删第一个能让字典序变小的，否则删最后一个第一类位置。

如果没有第一类位置，则删第一个字符。

Code
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+7;
const int MOD = 1e9+7;
string s;
int len[N];
string tohex(int x){
    stringstream ss;
    ss<<hex<<x;
    string t;
    ss>>t;
    for(auto &i:t){
        if(islower(i)){
            i+='A'-'a';
        }
    }
    return t;
}
void solve(){
    int cnt=1;
    s.push_back('0');
    vector<pair<int,int>> p;
    for(int i=1;i<s.size();i++){
        if(s[i-1]!=s[i]){
            p.push_back({s[i-1],cnt});
            cnt=1;
        }else cnt++;
    }
    int flag=0,les=N,mor=-1;
    for(int i=0;i<p.size();i++){
        if(p[i].second==1){
            if(i+1==p.size()||p[i].first>p[i+1].first){
                les=min(les,i);
            }else{
                mor=i;
            }
            flag=1;
        }else if(p[i].second==2){
            mor=i;
            flag=1;
        }else if(len[p[i].second-1]!=len[p[i].second]){
            mor=i;
            flag=1;
        }
    }
    if(flag){
        if(les<N){
            p[les].second--;
        }else{
            p[mor].second--;
        }
    }else{
        p[0].second--;
    }
    for(auto i:p){
        char ch=i.first;
        int  cnt=i.second;
        if(!cnt)continue;
        cout<<ch;
        string tmp=tohex(cnt);
        if(tmp!="1")cout<<tmp;
    }
    cout<<'\n';
}
int main(){
    len[0]=1;
    for(int i=1;i<N;i++){
        len[i]=len[i/16]+1;
    }
    ios::sync_with_stdio(false);
    while(cin>>s){
        solve();
    }
}

I. PepperLa’s Cram School

图论，小坑。由于边长相同，答案即为$d[i][j]$中最小值出现次数$/2$（一条边贡献两次），注意最小边权不一定是$1$。

J. Color the blocks

签到。从$(x,y)$到$(x+1,y+2),(x-1,y+2),(x+3,y),(x-3,y)$建边，答案即为$2^{连通块数}$，显然$n\ge4$时答案为$4$，其他手算一下就好了。

K. PepperLa’s Boast

dp。考虑$f[i][j]$表示在$(i,j)$处的答案，则每次转移只会从左、上、左上移动过来或者从以$(i,j)$为右下角的一个$k\times k$的矩形转移而来，也就是说要$O(1)$求出左上矩形内的最大值，这就是二维单调队列裸题了。

二维单调队列：对每行和每列都开一个单调队列，先把答案更新到该列中，再用该列的答案更新该行。

Code
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+7;
const int MOD = 1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,u,a[N][N];
int dx[3]={1,0,1};
int dy[3]={0,1,1};
ll f[N][N];
deque<pair<ll,ll>> col[N],row[N];
bool ok(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}
void initQ(int n,int m){
    for(int i=1;i<=n;i++){
        while(row[i].size()){
            row[i].pop_back();
        }
    }
    for(int i=1;i<=m;i++){
        while(col[i].size()){
            col[i].pop_back();
        }
    }
}
void push(deque<pair<ll,ll>> &q,pair<ll,ll> x){
    while(q.size()&&q.back().first<=x.first){
        q.pop_back();
    }
    q.push_back(x);
}
ll top(deque<pair<ll,ll>> &q,ll x){
    while(q.size()&&q.front().second<=x)q.pop_front();
    if(q.size())return q.front().first;
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>k>>u){k++;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
                f[i][j]=-INF;
            }
        }
        initQ(n,m);
        f[1][1]=a[1][1];
        push(col[1],{f[1][1],1});
        push(row[1],{f[1][1],1});
        for(int i=1;i<=n;i++){
            for(int j=1+(i==1);j<=m;j++){
                if(a[i][j]<=0){
                    f[i][j]=-1;
                }else{
                    for(int t=0;t<3;t++){
                        if(ok(i-dx[t],j-dy[t])&&f[i-dx[t]][j-dy[t]]>=0){
                            f[i][j]=max(f[i][j],f[i-dx[t]][j-dy[t]]+a[i][j]);
                        }
                    }
                    ll t=max(top(row[i],j-k),top(col[j],i-k));
                    if(t>=0)f[i][j]=max(f[i][j],t+a[i][j]-u);
                }
                push(col[j],{f[i][j],i});
                push(row[i],{top(col[j],i-k),j});
            }
        }
        cout<<max(-1LL,f[n][m])<<"\n";
    }
}

L. PepperLa’s Express

搜索。首先遇到$\min$和$\max$来回套的题，第一反应必是二分答案。考虑二分了一个答案$mid$，可以先做一个bfs把所有已经和’@’距离在$mid$内的’*‘搞掉，然后考虑求出距离每个位置最远的’*‘，如果存在某个空格最远距离小于$mid$，说明可以把新的’@’放在这里使答案不大于$mid$。

赛中其实讨论了一个憨批做法，对于每一维来回扫一遍，从一维更新到三维，复杂度$O(8XYZ)$，但是写起来有点恶心，而且好像会爆空间，赛中没写完。

看出题人的方法有点牛，既然是找距离最远的点，那必然是$|x_i-x_j|+|y_i-y_j|+|z_i-z_j|$最大，我们可以把里面的正负号拆开，$i,j$各存$2^3$种，我们可以直接在为长为3的二进制互为补集的两种组合中求答案。

感觉这个拆绝对值符号的思路挺好，而且代码写起来也很简洁。

Code
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200+7;
const int MOD = 1e9+7;
const int INF = 10000;
int h,n,m;
char s[N][N][N];
int d[N][N][N];
int f[N][N][N];
int g[8];
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int sgn[2]={-1,1};
bool ok(int x,int y,int z){
    return x>=1&&x<=n&&y>=1&&y<=m&&z>=1&&z<=h;
}
struct node{
    int x,y,z;
};
void bfs(){
    queue<node> q;
    for(int k=1;k<=h;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!d[k][i][j]){
                    q.push({i,j,k});
                }
            }
        }
    }
    while(q.size()){
        node p=q.front();
        q.pop();
        for(int t=0;t<6;t++){
            int x=p.x+dx[t];
            int y=p.y+dy[t];
            int z=p.z+dz[t];
            if(ok(x,y,z)&&d[z][x][y]==-1){
                d[z][x][y]=d[p.z][p.x][p.y]+1;
                q.push({x,y,z});
            }
        }
    }
}
bool check(int mid){
    for(int k=0;k<=h+1;k++){
        for(int i=0;i<=n+1;i++){
            for(int j=0;j<=m+1;j++){
                f[k][i][j]=-INF;
            }
        }
    }
    memset(g,-0x3f,sizeof g);
    for(int k=1;k<=h;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[k][i][j]=='*'&&d[k][i][j]>mid){
                    for(int t=0;t<8;t++){
                        g[t]=max(g[t],k*sgn[(t)&1]+i*sgn[(t>>1)&1]+j*sgn[(t>>2)&1]);
                    }
                }
            }
        }
    }
    int cnt=0;
    for(int k=1;k<=h;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[k][i][j]=='.'){
                    int res=0;
                    cnt++;
                    for(int t=0;t<8;t++){
                        res=max(res,g[t^7]+k*sgn[(t)&1]+i*sgn[(t>>1)&1]+j*sgn[(t>>2)&1]);
                    }
                    if(res<=mid){
                        return 1;
                    }
                }
            }
        }
    }
    return !cnt;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>h>>n>>m){
        for(int k=1;k<=h;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    cin>>s[k][i][j];
                    d[k][i][j]=-1;
                    if(s[k][i][j]=='@'){
                        d[k][i][j]=0;
                    }
                }
            }
        }
        bfs();
        int l=0,r=h+n+m,ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }else l=mid+1;
        }
        cout<<ans<<"\n";
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2021-10-19