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

The 2024 ICPC Asia East Continent Online Contest (II) （6/9/12)

article 2025/2/11 11:01:20

补题链接

https://codeforces.com/gym/105358

https://qoj.ac/contest/1799

赛中通过

F. Tourist（签到）

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
int n,v;
ll sum;
int main(){
    sci(n);
    rep(i,1,n){
        sci(v);
        sum+=v;
        if(sum>=2500){
            pte(i);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

A. Gambling on Choosing Regionals（签到）

每个队肯定是选ci最少的场次，因为考虑这个队的时候这个队的报名优先级最高

那么就考虑其他学校的前ci个队和这个学校的前ci-1个队，哪些比当前队的分数大，统计个数

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10;
int n,k,c[N],mn,ans[N],rk;
map<string,int>now;
struct node{
    int w,id;
    string x;
}e[N];
bool operator<(node a,node b){
    return a.w>b.w;
}
int main(){
    sci(n);sci(k);
    mn=1e9;
    rep(i,1,k){
        sci(c[i]);
        mn=min(mn,c[i]);
    }
    rep(i,1,n){
        sci(e[i].w);
        e[i].id=i;
        cin>>e[i].x;
    }
    sort(e+1,e+n+1);
    rep(i,1,n){
        string &x=e[i].x;
        if(now[x]>=mn){
            if(now[x]==mn)ans[e[i].id]=rk;
            else ans[e[i].id]=rk+1;
            continue;
        }
        now[x]++;
        ans[e[i].id]=rk+1;
        rk++;
    }
    rep(i,1,n){
        pte(ans[i]);
    }
    return 0;
}

I. Strange Binary（构造）

由于不能有两个0连续，手玩发现，当二进制末位是00的时候，也就是n%4=0的时候，无解

否则，总可以将二进制里的一段00001，用1 -1 -1 -1 -1来表示，起到消去0的效果

n%4=2的时候，可以留一个0

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=32;
int t,n,a[N];
int main(){
    sci(t);
    while(t--){
        sci(n);
        if(n%4==0){
            puts("NO");
            continue;
        }
        //rep(n,0,100){
            //if(n%4==0)continue;
            int las=31;
            per(i,30,0){
                if(n>>i&1){
                    if(las==i){
                        a[i]=1;
                    }
                    else{
                        a[las]=1;
                        per(j,las-1,i)a[j]=-1;
                    }
                    las=i-1;
                }
                else{
                    a[i]=0;
                }
            }
            ll sum=0;
            rep(i,0,31)sum+=(a[i]*(1ll<<i));
            //per(i,31,0)printf("%d ",a[i]);puts("");
            //printf("n:%d sum:%lld\n",n,sum);
            assert(sum==n);
        //}
        puts("YES");
        rep(i,0,31){
            printf("%d%c",a[i]," \n"[i%8==7]);
        }
    }
    return 0;
}

J. Stacking of Goods（排序比较法）

因为最后是良序的，也就是任意两个大小关系可确定的，

所以排序时比较，只考虑两个元素时，保留体积更小的那种方案，最后按题意模拟求得总体积

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10;
int n;
ll ans,sw;
struct node{
    ll w,v,c;
    void read(){
        scanf("%lld%lld%lld",&w,&v,&c);
    }
}e[N];
bool operator<(node a,node b){
    return 1ll*a.v+1ll*(b.v-b.c*a.w)<1ll*b.v+1ll*(a.v-a.c*b.w);
}
int main(){
    sci(n);
    rep(i,1,n){
        e[i].read();
    }
    sort(e+1,e+n+1);
    rep(i,1,n){
        ans+=e[i].v-1ll*e[i].c*sw;
        sw+=e[i].w;
    }
    ptlle(ans);
    return 0;
}

G. Game（辗转相除博弈）

平的概率是没有用的，因为平的话会开下一把，所以令a0=a0/(a0+a1),a1=a1/(a0+a1)

然后考虑俩人的博弈过程，

当前筹码小的那一方，在对面的筹码没有比自己少之前，是不能输的

这类似求gcd时，大的那个数对小的那个数取模，然后递归到交换的情形，

交换时，Alice获胜概率，即等于1-Bob获胜概率

特别地，当俩人筹码相同时，Alice这局必须拿下，否则筹码输成0了没有后续了

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,mod=998244353;
int t,x,y,a0,a1,b;
int modpow(int x,int n,int mod){
    int res=1;
    for(;n;n/=2,x=1ll*x*x%mod){
        if(n&1)res=1ll*res*x%mod;
    }
    return res;
}
int sol(int x,int a0,int y,int a1){
    //printf("x:%d a0:%d y:%d a1:%d\n",x,a0,y,a1);
    int ans=0;
    if(x<y){
        int cnt=(y-x+x-1)/x;
        y-=cnt*x;
        int p=modpow(a0,cnt,mod);
        ans=1ll*(1+mod-sol(y,a1,x,a0))%mod*p%mod;
    }
    else if(x==y){
        return a0;
    }
    else{
       ans=(1+mod-sol(y,a1,x,a0))%mod;
    }
    //printf("x:%d a0:%d y:%d a1:%d ans:%d\n",x,a0,y,a1,ans);
    return ans;
}
int main(){
    //printf("%lld\n",1ll*49*modpow(100,mod-2,mod)%mod);
    sci(t);
    while(t--){
        sci(x),sci(y);
        sci(a0),sci(a1),sci(b);b=a0+a1;
        if(!a0){
            puts("0");
            continue;
        }
        if(!a1){
            puts("1");
            continue;
        }
        a0=1ll*a0*modpow(b,mod-2,mod)%mod;
        a1=1ll*a1*modpow(b,mod-2,mod)%mod;
        printf("%d\n",sol(x,a0,y,a1));
        // if(x<=y){
        //     a0=1ll*a0*modpow(b,mod-2,mod);
        //     int cnt=(y-x+x-1)/x+1;
        //     a0=modpow(a0,cnt,mod);
        //     printf("cnt:%d\n",cnt);
        //     pte(a0);
        // }
        // else{
        //     swap(x,y);swap(a0,a1);
        //     a0=1ll*a0*modpow(a0+a1,mod-2,mod);
        //     int cnt=(y-x+x-1)/x+1;
        //     a0=modpow(a0,cnt,mod);
        //     //a0=(1+mod-a0)%mod;
        //     pte(a0);
        // }
    }
    return 0;
}

L. 502 Bad Gateway（期望）

存在一个x，使得<=x的时候，直接等到结束即可，

＞x的时候，重新投一下更优，有式子如下：

$E=\frac{1}{n}*(1+...+x)+\frac{n-x}{n}*(1+E)$

观察这个式子发现，x<=1+E的时候直接等更优，

所以x=1+floor(E)，其中floor(E)表示E的下取整

代进去之后，floor(E)和E可以近似看成一个变量去解这个方程，

而实际的方程真实值不会与近似差太远，化简发现在sqrt(2*n)附近

拓展范围解一下附近的，然后求一下实际的分数即可

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef __int128 ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,mod=998244353;
//E=1/n*(1+...+x)+(n-x)/n*(1+E) 三分x或者解x
//E=x/2+(n/x)-1/2=(x^2+2*n-x)/2x,x<=1+E x<=floor(E)-1
//2E^2=E^2+2n-E E(E+1)=2n E=sqrt(2*n)
int t,n;
ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
void ck(P &x,P y){
    if(1ll*x.fi*y.se>1ll*x.se*y.fi)x=y;
}
P f(ll x,ll n){
    return P(1ll*x*x+2ll*n-x,2ll*x);
}
int main(){
    //printf("%lld\n",1ll*49*modpow(100,mod-2,mod)%mod);
    sci(t);
    while(t--){
        sci(n);
        // if(n<=3){
        //     if(n%2==0){
        //         printf("%d %d\n",n+1,2);
        //     }
        //     else{
        //         printf("%d %d\n",(n+1)/2,1);
        //     }
        //     continue;
        // }
        int v=sqrt(2*n),l=max(1,v-20),r=min(n,v+20);
        P ans=P(4e9,1);
        rep(x,l,r){
            P y=f(x,n);
            // printf("x:%d fi:%lld se:%lld\n",x,(long long)y.fi,(long long)y.se);
            // if(y.fi/y.se==x || y.fi/y.se==x+1){
            //     ck(ans,y);
            //}
            ck(ans,y);
            // if(x==l)ans=y;
            // else ck(ans,y);
        }
        ll g=gcd(ans.fi,ans.se);ans.fi/=g;ans.se/=g;
        printf("%lld %lld\n",(long long)ans.fi,(long long)ans.se);
    }
    return 0;
}