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

和队友开的 7-1138

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

A

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

#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 为中心点即可

代码队友写的捏

#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 来保存当前状态能否到达，感谢潘神在最后时刻点出我的问题拯救了本场比赛。

#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

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

#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}，计算个数非常好写，只需要算一下整段和散段的和就可以了。

#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

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

#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。

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

#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();
}