526互联

The 2023 ICPC Nanjing Regional Contest G,F

发布时间 2023-11-11 13:36:44作者: ycllz

G. 背包
我们要是选一个集合出来 并且免除k个宝石的话
我们一定是选最贵的k个宝石免费
这样我们的做法就是对wi排序
然后前面的做背包 后面直接贪心选vi最大的k个 这样是一定包含了最优解的
当然你可以用二分bit 也可以直接维护另一个dp

int n,tr1[200010],tr2[200010],idx;
map<int,int>mp;
int lowbit(int x){
    return x&-x;
}
void add(int x,int c,int tr[]){
    for(int i=x;i<=idx;i+=lowbit(i))tr[i]+=c;
}
int query(int x,int tr[]){
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}
void solve(){
    int w,k;cin>>n>>w>>k;
    vector<PII>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i].first>>a[i].second;
        mp[a[i].second]++;
    }
    vector<int>mpp(n+1);
    for(auto [pos,w]:mp){
        mp[pos]=++idx;
        mpp[idx]=pos;
    }
    sort(all(a));
    int dp[n+1][w+1];
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++){
        auto [wi,vi]=a[i-1];
        for(int j=1;j<=w;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=wi)dp[i][j]=max(dp[i][j],dp[i-1][j-wi]+vi);
        }
    }
    int ans=dp[n][w];
    for(int i=n;i>=0;i--){
        int mx=*max_element(dp[i],dp[i]+w+1);
        int l=1,r=idx;
        while(l<r){
            int mid=l+r>>1;
            int x=mid;
            if(query(idx,tr1)-query(x-1,tr1)<=k)r=mid;
            else l=mid+1;
        }
        int cnt=query(idx,tr1)-query(l-1,tr1);
        if(cnt>=k){
            ans=max(ans,mx+query(idx,tr2)-query(l-1,tr2)-mpp[l]*(cnt-k));
        }else{
            ans=max(ans,mx+query(idx,tr2)-query(l-1,tr2));
        }
//        cout<<mx<<' '<<query(idx,tr2)-query(l-1,tr2)<<' '<<l<<endl;
        if(i) {
            auto [wi,vi]=a[i-1];
            add(mp[vi], 1, tr1);
            add(mp[vi], vi, tr2);
        }
    }
    cout<<ans<<endl;
}

int g[5010][5010];
void solve(){
    int w,k;cin>>n>>w>>k;
    vector<PII>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i].first>>a[i].second;
        mp[a[i].second]++;
    }
    vector<int>mpp(n+1);
    for(auto [pos,w]:mp){
        mp[pos]=++idx;
        mpp[idx]=pos;
    }
    sort(all(a));
    int dp[n+1][w+1];
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++){
        auto [wi,vi]=a[i-1];
        for(int j=1;j<=w;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=wi)dp[i][j]=max(dp[i][j],dp[i-1][j-wi]+vi);
        }
    }
    int ans=dp[n][w];
    for (int i = n; i; i--) {
        for (int j = k; j >= 0; j--) {
            if (j >= 1) g[i][j] = max(g[i + 1][j], g[i + 1][j - 1] + a[i-1].second);
            else g[i][j] = g[i + 1][j];
        }
        ans = max(ans, dp[i - 1][w] + g[i][k]);
    }
    cout<<ans<<endl;
}

F. 等价重写
我们发现我们该点的一位 只和最后这一位是什么联系
也就是最后一位必须在最后 这样我们就可以把当前与最后连起来 表示我该点必须在这个点之前
其他我都可以不管
然后拓扑排序 要是有一层是两个入队 表示我这两个谁前谁后都可以 就可以交换顺序

void solve(){
    int n,m;cin>>n>>m;
    vector<int>v[n+1],last(m+1);
    vector<int>g[n+1],deg(n+1);
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        while(x--){
            int pos;cin>>pos;
            v[i].push_back(pos);
            last[pos]=i;
        }
    }
    for(int i=1;i<=n;i++){
        for(auto pos:v[i]){
            if(i!=last[pos]){
                g[i].push_back(last[pos]);
                deg[last[pos]]++;
            }
        }
    }
    vector<int>q;
    for(int i=1;i<=n;i++){
        if(!deg[i])q.push_back(i);
    }
    while(q.size()){
        if(q.size()>=2){
            cout<<"Yes"<<endl;
            int mx=max(q[0],q[1]),mn=min(q[0],q[1]);
            for(int j=1;j<=n;j++){
                if(mx==j)continue;
                if(j==1){
                    if(j==mn){
                        cout<<mx<<' '<<mn;
                    }else{
                        cout<<j;
                    }
                }
                else {
                    if(j==mn){
                        cout<<' '<<mx<<' '<<mn;
                    }else{
                        cout<<' '<<j;
                    }
                }
            }cout<<endl;
            return;
        }
        vector<int>nq;
        while(q.size()){
            auto u=q.back();q.pop_back();
            for(auto v:g[u]){
                deg[v]--;
                if(deg[v]==0){
                    nq.push_back(v);
                }
            }
        }
        q=nq;
    }
    cout<<"No"<<endl;
}