当前位置：首页 > article >正文

Codeforces Round 1000 (Div. 2)(A-D)

article 2025/1/24 10:14:24

题目链接：Dashboard - Codeforces Round 1000 (Div. 2) - Codeforces

A. Minimal Coprime

思路

除了[1,1]是特殊的，其他最小互质段都是[l,l+1]，所以个数为r-l

代码

void solve(){
    int l,r;
    cin>>l>>r;
    if(l==1&&l==r){
        cout<<"1\n";
    }else{
        cout<<r-l<<"\n";
    }
}

B. Subsequence Update

思路

选择是不连续的，我们可以把目标区间内的大数选出来，选区间外的小数选出来，将其倒过来，发现如果要实现大数换小数的话，我们只能选择目标区间左右两端中一端，那么我们把两边都计算求最小即可

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n,l,r;
    cin>>n>>l>>r;
    vi a(n+10);
    priority_queue<int> q,t;
    priority_queue<int,vector<int>,greater<int>> q1,q2;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i>=l&&i<=r) {q.push(a[i]);t.push(a[i]);}
        if(i<l) q1.push(a[i]);
        if(i>r) q2.push(a[i]);
    }

    while(!q1.empty()){
        int x=q.top();
        int y=q1.top();
        if(x>y){
            q.pop();
            q1.pop();
            q.push(y);
        }else{
            break;
        }
    }
    while(!q2.empty()){
        int x=t.top();
        int y=q2.top();
        if(x>y){
            t.pop();
            q2.pop();
            t.push(y);
        }else{
            break;
        }
    }
    int sum1=0,sum2=0;
    while(!q.empty()){
        int x=q.top();q.pop();
        sum1+=x;
    }
    while(!t.empty()){
        int x=t.top();t.pop();
        sum2+=x;
    }
    cout<<min(sum1,sum2)<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

C. Remove Exactly Two

思路

一个树，那么初始的连通分量数是1，我们发现第一个顶点的选择一定是度最大的即连接边最多的，关于第二个顶点的选择我们肯定也是选择去除第一个顶点之后度最大的，那么这样就能够实现连通分量数最多

这里有一个坑，如果一个度为3的点连着3个度为3的点，我们不能删这个点，因此只要度最大的顶点数>2直接输出删除两个最大度的顶点的答案即可

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

bool cmp(pll a,pll b){
    return a.first>b.first;
}

void solve(){
    int n;cin>>n;
    vector<vi> g(n+10);
    vi d(n+10);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        d[u]++;
        d[v]++;
    }
    vector<pll> v;
    for(int i=1;i<=n;i++){
        v.push_back({d[i],i});
    }
    
    sort(v.begin(),v.end(),cmp);

    int t=v[0].first;
    int cnt=0;
    for(int i=0;i<v.size();i++){
        if(v[i].first==t) cnt++;
        else break;
    }
    if(cnt>2){
        cout<<v[0].first*2-1<<"\n";
    }else if(cnt==2){
        bool f=false;
        for(auto x:g[v[0].second]){
            if(x==v[1].second){
                f=true;break;
            }
        }
        if(f){
            cout<<v[0].first*2-2<<"\n";
        }else{
            cout<<v[0].first*2-1<<"\n";
        }
    }else if(cnt==1){
        for(auto x:g[v[0].second]){
            d[x]--;
        }
        int mx=0;
        for(int i=1;i<=n;i++){
            if(i==v[0].second) continue;
            if(mx<d[i]) mx=d[i];
        }
        cout<<v[0].first+mx-1<<"\n";
    }
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

D. Game With Triangles

思路

还是第一次做到除模板以外的三分题

根据题意我们可以发现，每次增加的三角形的面积，其实就是选择为底边的两点的距离，要求最大每次选两端点的点即可最大化，进一步思考可以发现关于两点的选择会随着k的增大而有一些限制

为方便理解我们设 $g(p,q)$ 为在y=0的这条线上选了p次，在y=2上选了q次时的值，得到 $g(p,q)=\sum_{i=1}^{p}(a[n+i-1]-a[i])+\sum_{i=1}^{q}(b[m+i-1]-b[i])$ （可以用前缀和）

那么 $f(k)=max(g(x,k-x))$ 枚举x的值求最大

现在还有问题要想清楚：1.关于x是有限制的，因为一条线上的点可能不够。2.我们要减少关于枚举时间复杂度。

1.为求得x的范围，我们可以回到 $g(p,q)$ 的定义得到：

2*p+q<=n
p+2*q<=m
p>=0
q>=0

将p=x，q=k-x代入得到：

2x+k-x<=n ----> x<=n-k
x+2*(k-x)<=m ----> x>=2*k-m
x>=0 ---> x>=0
k-x>=0 ---> x<=k

所以得到 $max(0,2*k-m)<=x<=min(k,n-k)$ 显然当左边界大于右边界时得到kmax

2.关于搜索的优化，我们发现 $g(x,k-x)$ 是一个关于x的凸函数，那么我们可以用三分查找来找到最大值，这里还有个要注意的点，我们是对整数的而不是实数的所以要进行调整偏差

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n,m;
    cin>>n>>m;
    vi a(n+1),b(m+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    sort(a.begin()+1,a.begin()+1+n);
    sort(b.begin()+1,b.begin()+1+m);

    vi as(n+10),bs(m+10);   //前缀和，便于g(p,q)的计算g(p,q)=as[p]+bs[q];
    for(int i=1;i<=n;i++) as[i]=as[i-1]+(a[n-i+1]-a[i]);
    for(int i=1;i<=m;i++) bs[i]=bs[i-1]+(b[m-i+1]-b[i]);

    auto g=[&](int k,int x){ return as[x]+bs[k-x]; };   //计算g(x,k-x)的值
    vi ans; //记录答案
    for(int k=1;max(0ll,2*k-m)<=min(k,n-k);k++){    //枚举k的值
       
        int L=max(0ll,2*k-m);
        int R=min(k,n-k);

        while(R-L>3){
            int mL=(2*L+R)/3;
            int mR=(L+2*R)/3;
            if(g(k,mL)>g(k,mR)) R=mR;
            else L=mL;
        }

        //对偏差进行调整
        int mx=0;
        for(int i=L;i<=R;i++){
            mx=max(mx,g(k,i));
        }

        ans.push_back(mx);
    }
    int kmax=(int)ans.size();
    cout<<kmax<<"\n";
    for(int i=0;i<kmax;i++){
        cout<<ans[i]<<" \n"[i==kmax-1];
    }
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

查看全文

http://www.kler.cn/a/516163.html