发表更新解题报告

CCPC2022 威海站 个人简要题解

没有写题欲望……来补补题整理一下思路

和队友开的 7-1138

Dashboard - 2022 China Collegiate Programming Contest (CCPC) Weihai Site - Codeforces

A

会读题就会做。考虑对于每个位置求出来一个 $\min{P_i}$ 代表打这个位置的人数，那么最多冠军选手为 $\sum c_i$，两个东西取个 min 就做完了。

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
#include<bits/stdc++.h>

#define int long long 
#define endl '\n'
#define x first
#define y second

using namespace std;

const int N=1e6+10;

set<string> se;

int f[10][2];
void slove(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=5;j++){
            string s;cin>>s;se.insert(s);
        }
    }

    int m;cin>>m;
    for(int i=1;i<=m;i++){
        string s;cin>>s;int op;cin>>op;
        if(se.count(s)){
            f[op][0]++;
        }else f[op][1]++;
    }

    int ans=0;
    for(int i=1;i<=5;i++){
        int mx=1e9+10;
        for(int j=1;j<=5;j++)
        if(i!=j){
            mx=min(f[j][0]+f[j][1],mx);//别的位置能删的最多的 
        }
        int no=min(f[i][0],mx);
        ans+=no;
        f[i][0]-=no;
        for(int j=1;j<=5;j++)
        if(i!=j){
            if(f[j][1]>=no) f[j][1]-=no;
            else {
                f[j][0]-=(no-f[j][1]);
                f[j][1]=0;
            } 
        }
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T=1;
    while(T--) slove();
}

C

分类讨论不难发现：其实只需要存在五点不共线就可以了。

如果不存在三点共线：选 $AB,CD$ 两条直线，然后找一个点 $E$ 为中心点显然成立

三点共线：考虑直线 $ABC$，直接选点 $B$ 为中心点即可

四点共线：对于直线 $ABCD$，找一点 $E$ 为中心点即可

代码队友写的捏

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
#include<bits/stdc++.h>

#define int long long 
#define endl '\n'
#define x first
#define y second

using namespace std;

const int N=2e5+10;
const double eps=1e-9;

typedef pair<int,int> PII;
typedef pair<double,double> PDD;

PII a[N];
PII c[10];

void slove(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}
    if(n<5){
        cout<<"NO"<<endl;
        return ;
    }
    for(int i=1;i<=5;i++) c[i]=a[i];
    for(int i=6;i<=n;i++){
        if((a[i-1].y-a[i-2].y)*(a[i].x-a[i-2].x)!=(a[i].y-a[i-2].y)*(a[i-1].x-a[i-2].x)){
            int num=5;
            for(int j=i;j>i-5;j--) c[num--]=a[j];
            break;
        }
    }
    set<PDD> se;
    int ji=0;

//    for(int i=1;i<=5;i++){
//        cout<<c[i].x<<" "<<c[i].y<<endl;
//    }

    for(int i=1;i<=5;i++){//ÒÔiΪ»ùµã 
        se.clear();
        bool ok=true;
        for(int j=1;j<=5;j++)
        if(j!=i){
            int x=c[i].x-c[j].x,y=c[i].y-c[j].y;
            double len=sqrtl(x*x*1.0+y*y*1.0);
            double x1=x*1.0/len,y1=y*1.0/len;
            if(se.size()){
                for(auto zz:se){
                    if(fabs(zz.x-x1)<eps&&fabs(zz.y-y1)<eps){
                        ok=false;
                        break;
                    }
                }
            }
            se.insert({x1,y1});
            if(!ok) break;
        }
        if(ok){
            ji=i;
            break;
        }
    } 
    if(ji){
        cout<<"YES"<<endl;
        cout<<c[ji].x<<" "<<c[ji].y<<endl;
        for(int i=1;i<=5;i++)if(i!=ji){
            cout<<c[i].x<<" "<<c[i].y<<endl;
        }
    }
    else cout<<"NO"<<endl;
}
/*
1
6
1 1
2 2
3 3
5 5
6 7
6 6
*/
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T=1;cin>>T;
    while(T--) slove();
}

D

神秘跳棋题……

这个题发现，实际上有用的情况至多只有 $2^{19}$ 种，对于每个询问记忆化搜索一下就做完了。

但是要注意的是，前两排，第三排，后两排对应的六联通坐标不一样，很坑人。

以及记得这个题的状态 $s$ 是存在 $f_s = 0$ 的情况的，所以务必记得用一个 $vis$ 来保存当前状态能否到达，感谢潘神在最后时刻点出我的问题拯救了本场比赛。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
#define pii pair<int,int>
#define mp make_pair
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int a[10][10],f[N],qwq[10][10];
bool vis[N];
const int dx1[6] = {1,-1,-1,1,0,0};
const int dy1[6] = {1,-1,0,0,-1,1};


const int dx2[6] = {1,-1,-1,1,0,0};
const int dy2[6] = {0,0,1,-1,-1,1};

const int dx3[6] = {1,-1,-1,1,0,0};
const int dy3[6] = {0,-1,0,-1,-1,1};
pii sta[20];

bool valid(int x,int y) {
    if (x < 1 || y < 1 || x > 5 || y > 5) return 0;
    int r = 2;
    if (x <= 3) r += x;
    else if (x == 4) r += 2;
    else r++;
    if (y <= r) return 1;
    else return 0;
}

pii getnxt(int x,int y,int typ) {
    if (x < 3) {
        int nx = dx1[typ] + x,ny = y + dy1[typ];
        return mp(nx,ny);
    } else if (x > 3){
        int nx = dx2[typ] + x,ny = y + dy2[typ];
        return mp(nx,ny);
    } else {

        int nx = dx3[typ] + x,ny = y + dy3[typ];
        return mp(nx,ny);
    }
}

int dfs(int now) {
    if (vis[now]) return f[now];
    int ans = 0;
    int ma[10][10];
    vector <pii> st;
    for (int i = 0;i < 20;++i) {
        pii ps = sta[i];
        if (now & (1 << i)) {
            ma[ps.first][ps.second] = 1;
            st.push_back(ps);
        } else {
            ma[ps.first][ps.second] = 0;
        }
    }
    if (st.size() == 1) {
        f[now] = 0;
        vis[now] = 1;
        return 0;
    }

    /*cout << "nowst:" << now << ":\n";
    for (int i = 1;i <= 5;++i) {
        int r = 2;
        if (i <= 3) r += i;
        else if (i == 4) r += 2;
        else r += 1;
        for (int j = 1;j <= r;++j) {
            cout << ma[i][j];
        }
        cout <<"\n";
    }*/

    for (auto p : st) {
        int x = p.first,y = p.second;
        for (int i = 0;i < 6;++i) {
            pii np = getnxt(x,y,i);
            int nx = np.first,ny = np.second;
            //for (int j = 0;j < 6;++j) {
            pii npp = getnxt(np.first,np.second,i);
            int nxx = npp.first,nyy = npp.second; 
            //printf("i:%d (%d,%d)->(%d,%d)->(%d,%d)\n",i,x,y,nx,ny,nxx,nyy);
            if (valid(nx,ny) && valid(nxx,nyy) && ma[nx][ny] > 0 && (!(nxx == x && nyy == y))){
                //printf("i:%d (%d,%d)->(%d,%d)->(%d,%d)\n",i,x,y,nx,ny,nxx,nyy);
                int jpst = now;
                jpst -= (1 << qwq[x][y]);
                jpst -= (1 << qwq[nx][ny]);
                jpst |= (1 << qwq[nxx][nyy]);
                if (f[jpst]) ans = max(ans,f[jpst] + a[nx][ny]);
                else ans = max(ans,dfs(jpst) + a[nx][ny]);
            }
            //}
        }
    }
    //cout << "ans = " << ans << "\n";
    vis[now] = 1;
    return f[now] = ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int cnt = 0;
    for (int i = 1;i <= 5;++i) {
        int r = 2;
        if (i <= 3) r += i;
        else if (i == 4) r += 2;
        else r += 1;
        for (int j = 1;j <= r;++j) {
            cin >> a[i][j];
            qwq[i][j] = cnt;
            sta[cnt++] = mp(i,j);
        }
    }
    int q;cin >> q;

    //cout << dfs(17408);
    //return 0;

    while (q--) {
        int cnt = 0;
        int stat = 0;
        for (int i = 1;i <= 5;++i) {
            int r = 2;
            if (i <= 3) r += i;
            else if (i == 4) r += 2;
            else r += 1;
            for (int j = 1;j <= r;++j) {
                char c;cin >> c;
                if (c == '#') stat += (1 << cnt);
                ++cnt;
            }
        }
        if (vis[stat]) cout << f[stat] << "\n";
        else cout << dfs(stat) << "\n";
    }
    return 0;
}

/*
9 2 2
3 3 7 2
0 3 6 8 5
4 7 7 5
8 0 7
1
...
..#.
..##.
....
...

*/

E

发现这东西是收敛很快的一次分段函数，暴力计算就完了。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n,a[N],k; 
signed main() {
    cin >> n >> k;
    for (int i = 1;i <=n;++i) cin >> a[i];
    int pos = 0;
    for (int i = 1;i <= n;++i) {
        if (a[i] < k) {
            pos = i;
            break;
        }
    }
    if (pos) {
        printf("Python 3.%d will be faster than C++",pos);
        return 0;
    }
    int qwq = a[n] - a[n-1];
    if (qwq >= 0) {
        puts("Python will never be faster than C++");
    } else {
        for (int i = n+1;i <= 200000;++i) {
            a[i] = max(0,2*a[i-1] - a[i-2]);
            //cout << a[i] << " " << i << "\n";
            if (a[i] < k) {
                pos = i;
                break;
            }
        }
        printf("Python 3.%d will be faster than C++",pos);
    }
    return 0;
}

G

神秘打表题。

主要是得发现，这个东西有一个 $2^{\lceil \log_2 x \rceil}$ 的循环节，然后可以先暴力把这个循环节打出来。接下来对询问进行差分，每次就是查询 $cnt_{1,r} - cnt_{1,l-1}$，计算个数非常好写，只需要算一下整段和散段的和就可以了。

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
#include<bits/stdc++.h>

#define int long long 
#define endl '\n'
#define x first
#define y second

using namespace std;

const int N=4e6+10;

int s[N]; 
int p=1;

int check(int r){
    return s[p]*(r/p)+s[r%p];
}

void slove(){
    int x,n;cin>>x>>n;
    while(p<x) p*=2;
    //cout<<p<<endl;
    for(int i=1;i<=p;i++){
        int no=__gcd((i*x)^x,x);
        if(no==1) s[i]=1;
        else s[i]=0;
    }
    for(int i=1;i<=p;i++) s[i]+=s[i-1];
    int ans=0;
    while(n--){
        int l,r;cin>>l>>r;
        cout<<check(r)-check(l-1)<<endl;
    }
}
/*
999999 1
1 1000000000000
462890624994
*/

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T=1;
    while(T--) slove();
}

I

好厉害的贪心题！叶天帝写的，摆了。

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
#include<bits/stdc++.h>

#define int __int128
#define ll long long
#define endl '\n'
#define x first
#define y second

using namespace std;

const int N=5e4+10;

int a[N],b[N],c[N];
int po[N];
ll n,k;

bool check(int x){
    for(int i=0;i<=k;i++) c[i]=b[i];
    priority_queue<int,vector<int>, less<int>> heap;
    for(int i=1;i<=n;i++){
        if(x)heap.push(a[i]*x);
    }
    int num=0;
    for(int i=k-1;i>=0;i--){//从高位往低位填充 
//        cout<<po[i]<<" "<<endl;
        while(heap.size()){
            int p=heap.top();
//            cout<<(ll)p<<" ";
            heap.pop();
            if(p<po[i]&&c[i]){
                c[i]--;
                p=0;
//                continue;
            }
            int no=p/po[i];
            if(c[i]>=no){
//                cout<<(ll)p<<endl;
                c[i]-=no;
                p-=no*po[i];
            }else {
                p-=c[i]*po[i];
                c[i]=0;
            }
//            cout<<(ll)p<<" "<<(ll)i<<" "<<c[i]<<" "<<endl;
            if(p) heap.push(p);
            if(!c[i]) break;
        } 
    }
    if(heap.size()) return false;
    return true;
}

void slove(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        ll x;cin>>x;a[i]=x;
    }
    for(int i=0;i<k;i++){
        ll x;cin>>x;b[i]=x;
    }
    int l=0,r=1e18;
//    cout<<check(5)<<endl;
    while(l<r){
        int mid=(l+r+1)/2;
//        cout<<mid<<" "<<check(mid)<<" "<<l<<" "<<r<<endl;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    ll ans=l;
    cout<<ans<<endl; 
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    po[0]=1;
    for(int i=1;i<=30;i++) po[i]=po[i-1]*2;
    ll T=1;cin>>T;
    while(T--) slove();
}

J

潘哥给的思路，但是写不出来被硬控 1h。

其实发现可以计算出最优方案的答案，然后看奇偶性就好了

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
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define ll long long
#define int long long
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
//偶数为0 

typedef pair<int,int> PII;

int n,k;
int a[N];
PII li[N];
map<int,int> num,c;

void solve() {
    cin >> n >> k;
    num.clear(),c.clear(); 
    for(int i=1;i<=n;i++){cin>>a[i];}
    sort(a+1,a+1+n);

    for(int i=1;i<=k;i++)cin>>li[i].x>>li[i].y;
    sort(li+1,li+1+k);

    vector<PII> val;
    int ls=-1;//-1不能等于0 
    for(int i=1;i<=k;i++){
        if(li[i].y==0){
            val.push_back({ls,li[i].x-1});
            ls=li[i].x;
        }
    }
    val.push_back({ls,1e9});//多设一点 
    for(int i=1;i<=k;i++) num[li[i].x]=li[i].y;//限制 
    //找处于这个区间内的数
    int l=0;
    int step=0;
    for(int i=1;i<=n;i++){
        int st=i;
        int lst=val[l].x+1;//能放的位置
        while(a[st]<val[l].x&&st<=n) st++; 
        if(st>n){
            break;
        }
//        cout<<val[l].x<<" "<<val[l].y<<endl;
        while(1){
            if(st>n) break;
            if(lst>val[l].y)break; 
            if(a[st]>val[l].y) break;
            if(!num[lst]) num[lst]=1e9;
            //把a[i]变成lst 
            c[lst]++;
            step+=a[st]-lst;
//            cout<<st<<" "<<lst<<endl; 
            if(c[lst]==num[lst])lst++;
            st++;
        }    
        l++;
        i=st-1;
    } 
//    cout<<step<<endl;
    if(step%2) cout<<"Pico"<<endl;
    else cout<<"FuuFuu"<<endl;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;cin >> T;
    while (T--) solve();
}

CCPC2022 威海站 个人简要题解

https://doubeecat.cn/post/CCPC2022-威海站-个人简要题解/

作者

Doubeecat

发布于

2024-10-15

更新于

2025-09-18

许可协议

关注我

链接

分类

最新文章

归档

标签

2-SAT1
BFS1
BSGS1
CDQ分治1
CV7
CV , transformer1
CV, 分割1
CV, 多模态1
CV,Transformer1
CV,分割2
CV,机器学习1
DFS序1
DL2
DP20
Dijkstra1
Dirchlet 卷积1
ETT1
Kruskal2
Kruskal 重构树2
LCA1
MST2
NTT1
RMQ1
Tarjan4
Transformer2
bitset1
codeforces1
hash1
nim游戏1
transformer1
二分3
二分图1
二维数点1
位运算2
决策单调性1
凸包1
分块2
分治2
分治NTT1
割点1
区间DP2
单调栈3
博弈论1
图论12
多项式1
字符串1
容斥原理2
差分1
差分约束1
并查集2
思维8
扫描线2
拉格朗日插值1
拓扑排序2
搜索1
数位DP2
数学10
数据结构5
数论5
数论分块1
整体二分1
暴力3
最大流2
最小割2
最小环1
最小费用最大流1
最短路3
杜教筛1
构造3
枚举1
树1
树上问题8
树形DP3
树状数组3
树链剖分2
根号分治2
欧拉函数1
毒瘤1
状压DP1
矩阵1
神经网络1
积性函数1
线性DP3
线性基1
线段树8
线段树分治1
组合数学1
缩点1
网络流2
背包5
莫比乌斯反演1
计数问题2
负环1
贪心1
递归2
闵可夫斯基和1
×