2022 ICPC 亚洲区域赛沈阳站

C - Clamped Sequence

statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
int hpa[8],hpb[8];
int atka[8],atkb[8];
double wina,winb,pj;
int cnta[8],cntb[8];//攻击次数
int alivea,aliveb;
void dfs(int tag,double pos){
    if(alivea==0&&aliveb==0){
        pj+=pos;
        return ;
    }
    if(alivea==0&&aliveb!=0){
        winb+=pos;
        return ;
    }
    if(alivea!=0&&aliveb==0){
        wina+=pos;
        return ;
    }
    //A先攻击
    if(tag==1){
        int mn=LONG_LONG_MAX;
        for(int i=1;i<=8;i++) 
            if(hpa[i]>0){
                mn=min(mn,cnta[i]);
            }
        int id=-1;
        for(int i=1;i<=8;i++) 
            if(cnta[i]==mn&&hpa[i]>0){
                id=i;
                break;
            }
        if(id==-1) return ;
        cnta[id]++;
        for(int i=1;i<=8;i++)
            if(hpb[i]>0){
                if(hpb[i]<=atka[id]&&hpa[id]<=atkb[i]){
                    int tmpb=hpb[i];
                    aliveb--,hpb[i]=0;
                    int tmpa=hpa[id];
                    alivea--,hpa[id]=0;
                    dfs(tag^1,pos/(aliveb+1));
                    aliveb++,hpb[i]=tmpb;
                    alivea++,hpa[id]=tmpa;
                }
                else if(hpb[i]<=atka[id]&&hpa[id]>atkb[i]){
                    int tmpb=hpb[i];
                    aliveb--,hpb[i]=0;
                    int tmpa=hpa[id];
                    hpa[id]-=atkb[i];
                    dfs(tag^1,pos/(aliveb+1));
                    aliveb++,hpb[i]=tmpb;
                    hpa[id]=tmpa;
                }
                else if(hpb[i]>atka[id]&&hpa[id]<=atkb[i]){
                    int tmpb=hpb[i];
                    hpb[i]-=atka[id];
                    int tmpa=hpa[id];
                    hpa[id]=0,alivea--;
                    dfs(tag^1,pos/(aliveb));
                    alivea++,hpa[id]=tmpa;
                    hpb[i]=tmpb;
                }
                else{
                    int tmpb=hpb[i];
                    hpb[i]-=atka[id];
                    int tmpa=hpa[id];
                    hpa[id]-=atkb[i];
                    dfs(tag^1,pos/(aliveb));
                    hpb[i]=tmpb;
                    hpa[id]=tmpa;
                }
            }
        cnta[id]--;
    }
    //B先攻击
    else{
        int mn=LONG_LONG_MAX;
        for(int i=1;i<=8;i++) 
            if(hpb[i]>0){
                mn=min(mn,cntb[i]);
            }
        int id=-1;
        for(int i=1;i<=8;i++) 
            if(cntb[i]==mn&&hpb[i]>0){
                id=i;
                break;
            }
        if(id==-1) return ;
        cntb[id]++;
        for(int i=1;i<=8;i++)
            if(hpa[i]>0){
                if(hpa[i]<=atkb[id]&&hpb[id]<=atka[i]){
                    int tmpa=hpa[i];
                    alivea--,hpa[i]=0;
                    int tmpb=hpb[id];
                    aliveb--,hpb[id]=0;
                    dfs(tag^1,pos/(alivea+1));
                    aliveb++,hpb[id]=tmpb;
                    alivea++,hpa[i]=tmpa;
                }
                else if(hpa[i]<=atkb[id]&&hpb[id]>atka[i]){
                    int tmpa=hpa[i];
                    alivea--,hpa[i]=0;
                    int tmpb=hpb[id];
                    hpb[id]-=atka[i];
                    dfs(tag^1,pos/(alivea+1));
                    alivea++,hpa[i]=tmpa;
                    hpb[id]=tmpb;
                }
                else if(hpa[i]>atkb[id]&&hpb[id]<=atka[i]){
                    int tmpa=hpa[i];
                    hpa[i]-=atkb[id];
                    int tmpb=hpb[id];
                    hpb[id]=0,aliveb--;
                    dfs(tag^1,pos/(alivea));
                    aliveb++,hpb[id]=tmpb;
                    hpa[i]=tmpa;
                }
                else{
                    int tmpa=hpa[i];
                    hpa[i]-=atkb[id];
                    int tmpb=hpb[id];
                    hpb[id]-=atka[i];
                    dfs(tag^1,pos/(alivea));
                    hpa[i]=tmpa;
                    hpb[id]=tmpb;
                }
            }
        cntb[id]--;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    alivea=n,aliveb=m;
    for(int i=1;i<=n;i++){
        cin>>hpa[i];
        atka[i]=hpa[i];
    }
    for(int i=1;i<=m;i++){
        cin>>hpb[i];
        atkb[i]=hpb[i];
    }
    if(n>m) dfs(1,1);
    else if(n<m) dfs(0,1);
    else{
        dfs(0,0.5);
        dfs(1,0.5);
    }
    cout<<fixed<<setprecision(10)<<wina<<' '<<winb<<' '<<pj<<'\n';
    return 0;
}

C - Clamped Sequence

Given an integer sequence a_1, a_2, \ldots, a_n and a positive integer d, you need to clamp the sequence to a range [l,r] satisfying 0 \le r-l \le d that maximize \sum_{i=1}^{n-1}|a_i - a_{i+1}|, where |x| is the absolute value of x.
More specifically, clamping the sequence to the range [l,r] makes each element

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+10;
int a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++){
        int l1=a[i],r1=a[i]+d;
        int l2=a[i]-d,r2=a[i];
        int res1=0,res2=0;
        for(int i=2;i<=n;i++){
            int a1=a[i-1];
            int a2=a[i];
            if(a1<l1) a1=l1;
            else if(a1>r1) a1=r1;
            if(a2<l1) a2=l1;
            else if(a2>r1) a2=r1;
            res1+=abs(a2-a1);
            a1=a[i-1];
            a2=a[i];
            if(a1<l2) a1=l2;
            else if(a1>r2) a1=r2;
            if(a2<l2) a2=l2;
            else if(a2>r2) a2=r2;
            res2+=abs(a2-a1);
        }
        ans=max({ans,res1,res2});
    }
    cout<<ans<<'\n';
    return 0;
}

a_i := \left\{ \begin{array}{rcl} l, & a_i &lt; l; \\ a_i, & l \le a_i \le r; \\ r, & a_i &gt; r. \\ \end{array} \right.

Both l and r are arbitrary real numbers decided by you under the given constraints. It can be shown that the maximum sum is always an integer.

F - Half Mixed

题目大意：给出 n , m 求构造n行m列只包含 {0,1}的数列,要求全部纯净块的数量 = 全部混合块的数量。纯净块指子矩形内所有数字要么全部是 0，要么全部是 1，而混合块则相反：子矩形内要包括0,1两种数字，问是否能构造出，若是能打印你所构造的序列。

solutions
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int cal(int m,int sum){
    int l=1,r=m;
    if(l==r) return 1;
    int ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(m-mid<=sum-mid*(mid+1)/2) ans=mid,l=mid+1;
        else r=mid-1; 
    }
    return ans;
}
int row[N];
void solve(){
    int n,m;
    cin>>n>>m;
    if(n*(n+1)/2%2&&m*(m+1)/2%2) cout<<"No\n";
    else{
        cout<<"Yes\n";
        bool flag=0;
        if(m*(m+1)/2%2) swap(n,m),flag=1;
        int sum=m*(m+1)/4;
        // cout<<sum<<'\n';
        int tag=0;
        int tm=m;
        int cnt=0;
        while(1){
            int t=cal(tm,sum);
            for(int i=0;i<t;i++) row[cnt++]=tag;
            //cout<<t<<'\n';
            tm-=t;
            sum-=t*(t+1)/2;
            if(tm==0) break;
            tag^=1;
        }
        if(!flag){
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    cout<<row[j]<<' ';
                }
                cout<<'\n';
            }
        }
        else{
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    cout<<row[i]<<' ';
                }
                cout<<'\n';
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

参考题解

2022 第47届沈阳站部分题解_f. half mixed-CSDN博客
(23 封私信 / 80 条消息) 2022 ICPC沈阳 (L、F) - 知乎

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容