A - Programming Contest

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int y1;
        cin>>y1;
        int n;
        cin>>n;
        vector<int> vis(2e4+10);
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            vis[x]=1;
        }
        int y2;
        cin>>y2;
        int ans=0;
        for(int y=y1;y<=y2;y++)
            if(!vis[y]) ans++;
        cout<<ans<<'\n';
    }
    return 0;
}

C - Trading

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int N=1e5+10;
pair<int,int> p[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int l=0,r=0;
        for(int i=1;i<=n;i++){
            cin>>p[i].fi>>p[i].se;
            r+=p[i].se;
        }
        int cnt=r;
        // cout<<r<<'\n';
        sort(p+1,p+n+1);
        int cnt_buy=r/2;
        int ans=0;
        int now=0;
        int i=1;
        for(;i<=n;i++){
            if(now+p[i].se<cnt_buy){
                ans-=p[i].fi*p[i].se;
                now+=p[i].se;
            }
            else{
                ans-=p[i].fi*(cnt_buy-now);
                ans+=p[i].fi*(p[i].se-(cnt_buy-now));
                now=cnt_buy;
                break;
            }
        }
        if(cnt%2) ans-=p[i].fi;
        for(i=i+1;i<=n;i++)
            ans+=p[i].fi*p[i].se;
        cout<<ans<<'\n';
    }
    return 0;
}

D - New Houses

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        vector<int> a(n+1),b(n+1),tmp(n+1);
        int sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i];
            tmp[i]=a[i]-b[i];
            sum+=b[i];
        }
        sort(next(tmp.begin()),tmp.end(),greater<int>());
        int ans=0;
        if(2*n-1<=m) ans=sum;
        //枚举有邻居的人的个数
        sum+=tmp[1];
        for(int i=2;i<=n;i++){
            sum+=tmp[i];
            if(2*n-i<=m) ans=max(ans,sum);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

K - Peg Solitaire

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
int n,m,k;
int g[10][10];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int ans;
bool check(int x,int y){
    if(1<=x&&x<=n&&1<=y&&y<=m) return 1;
    return 0;
}
void dfs(){
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]==1) cnt++;
        }
    }
    ans=min(ans,cnt);
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            if(g[x][y]==1){
                for(int k=0;k<4;k++){
                    int tx=x+dx[k],ty=y+dy[k];
                    int ttx=tx+dx[k],tty=ty+dy[k];
                    if(check(tx,ty)&&check(ttx,tty)&&g[tx][ty]==1&&g[ttx][tty]==0){
                        g[x][y]=0;
                        g[tx][ty]=0;
                        g[ttx][tty]=1;
                        dfs();
                        g[x][y]=1;
                        g[tx][ty]=1;
                        g[ttx][tty]=0;
                    }
                }
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                g[i][j]=0;
        }
        for(int i=1;i<=k;i++){
            int x,y;
            cin>>x>>y;
            g[x][y]=1;
        }
        ans=n*m;
        dfs();
        cout<<ans<<'\n';
    }
    return 0;
}

I - Path Planning

There is a grid with $n$ rows and $m$ columns. Each cell of the grid has an integer in it, where $a_{i, j}$ indicates the integer in the cell located at the $i$ -th row and the $j$ -th column. Each integer from $0$ to $(n \times m - 1)$ (both inclusive) appears exactly once in the grid.

Let $(i, j)$ be the cell located at the $i$ -th row and the $j$ -th column. You now start from $(1, 1)$ and need to reach $(n, m)$ . When you are in cell $(i, j)$ , you can either move to its right cell $(i, j + 1)$ if $j < m$ or move to its bottom cell $(i + 1, j)$ if $i < n$ .

Let $\mathbb{S}$ be the set consisting of integers in each cell on your path, including $a_{1, 1}$ and $a_{n, m}$ . Let $\text{mex}(\mathbb{S})$ be the smallest non-negative integer which does not belong to $\mathbb{S}$ . Find a path to maximize $\text{mex}(\mathbb{S})$ and calculate this maximum possible value.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e6+5;
int n,m;
struct node{
    int val[MAXN];
    int* operator[](int x){
        return val+x*m;
    }
}g;
bool check(int x){
    int last=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]<x){
                if(j<last) return 0;
                last=j;
            }
        }
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>g[i][j];
            }
        }
        int l=0,r=n+m-1;
        int ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1; 
        }
        cout<<ans<<'\n';
    }
    return 0;
}

2023 CCPC 广州