I - Counter

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> p(m+1); 
    for(int i=1;i<=m;i++) cin>>p[i].fi>>p[i].se;
    sort(next(p.begin()),p.end());
    for(int i=1;i<=m;i++){
        if(p[i].se>p[i-1].se){
            if(p[i].se-p[i-1].se!=p[i].fi-p[i-1].fi&&p[i].se>p[i].fi-p[i-1].fi-1){
                cout<<"No\n";
                return ;
            }
        }
        else if(p[i].se<p[i-1].se){
            if(p[i].se+1>p[i].fi-p[i-1].fi){
                cout<<"No\n";
                return ;
            }
        }
        else if(p[i].se==p[i-1].se){
            if(p[i-1].fi==p[i].fi) continue ;
            if(p[i].se+1>p[i].fi-p[i-1].fi){
                cout<<"No\n";
                return ;
            }
        }
    }
    cout<<"Yes\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

C - Primitive Root

#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 p,m;
        cin>>p>>m;
        int ans=m/p;
        for(int k=m/p;k<=(m+p-1)/p;k++)
            if(((k*p+1)^(p-1))<=m) ans++;
        cout<<ans<<'\n';
    }
    return 0;
}

G - Knapsack

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int N=5e3+10,inf=1e9;
pair<int,int> p[N];
int g[N],f[N<<1];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,W,k;
    cin>>n>>W>>k;
    for(int i=1;i<=n;i++) cin>>p[i].fi>>p[i].se;
    sort(p+1,p+n+1);
    priority_queue<int,vector<int>,greater<int>> heap;
    int sum=0;
    for(int i=n;i>=1;i--){
        heap.push(p[i].se);
        sum+=p[i].se;
        if(heap.size()>k){
            sum-=heap.top();
            heap.pop();
        }
        g[i]=sum;
    }
    int ans=g[1];
    for(int i=1;i<=n;i++){
        for(int j=W;j>=p[i].fi;j--){
            f[j]=max(f[j],f[j-p[i].fi]+p[i].se);
            ans=max(ans,f[j]+g[i+1]);
        }
    }
    cout<<ans<<'\n';
    return 0;
}

常见错解
hack:
5 10 1
1 1
2 2
3 3
4 4
100 100
错解输出104，正解是110

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+10,M=1e4+10;
int v[N],w[N];
int f[N][M];
bool vis[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,W,k;
    cin>>n>>W>>k;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
    for(int i=n;i>=1;i--){
        for(int j=0;j<=W;j++){
            f[i][j]=f[i+1][j];
            if(j>=w[i])
                f[i][j]=max(f[i][j],f[i+1][j-w[i]]+v[i]);
        }
    }
    int j=W;
    for(int i=1;i<=n;i++){
        if(j>w[i]&&f[i][j]==f[i+1][j-w[i]]+v[i]){
            vis[i]=1;
            j-=w[i];//选择了第i个物品，剩余容量要减少
        }
    }
    int ans=f[1][W];
    vector<int> res;
    for(int i=1;i<=n;i++)
        if(!vis[i]) res.push_back(v[i]);
    sort(res.begin(),res.end(),greater<int>());
    k=min(k,(int)res.size());
    for(int i=0;i<k;i++) ans+=res[i];
    cout<<ans<<'\n';
    return 0;
}

F - Equivalent Rewriting

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=2e6+10;
int h[N],ne[M],to[M],idx=0;
void add(int a,int b){
    to[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}
int n,m;
vector<int> g[N];
int last[N],d[N];
void toposort(){
    //用大根堆求字典序最大的拓扑序，如果字典序最大的拓扑序和字典序最小的拓扑序1,2,3...n相等则仅有唯一的方案
    priority_queue<int> q;
    for(int i=1;i<=n;i++)
        if(d[i]==0) q.push(i);
    vector<int> tp;
    while(q.size()){
        int x=q.top();q.pop();
        tp.push_back(x);
        for(int i=h[x];~i;i=ne[i]){
            int y=to[i];
            if(--d[y]==0) q.push(y);
        } 
    } 
    bool flag=1;
    for(int i=1;i<=n;i++)
        if(tp[i-1]!=i) flag=0;
    if(!flag){
        cout<<"Yes\n";
        for(int i=1;i<=n;i++)
            cout<<tp[i-1]<<' ';
        cout<<'\n'; 
    }
    else cout<<"No\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            g[i].clear();
            h[i]=-1;
            d[i]=0;
        }
        for(int i=1;i<=m;i++) last[i]=0;
        idx=0;
        for(int i=1;i<=n;i++){
            int num;
            cin>>num;
            for(int j=1;j<=num;j++){
                int x;
                cin>>x;
                g[i].push_back(x);
                last[x]=i;
            }
        }
        for(int i=1;i<=n;i++){
            int num=g[i].size();
            for(int j=0;j<num;j++){
                if(i!=last[g[i][j]]){
                    add(i,last[g[i][j]]);
                    d[last[g[i][j]]]++;
                }
            }
        }
        toposort();
    }
    return 0;
}