The 16th Harbin Engineering University Collegiate Programming Contest

EdGrass / 2023-05-08 / 原文

The 16th Harbin Engineering University Collegiate Programming Contest

A. stral Reflection

用右界覆盖左界为下标的数组构成一个以i为左界，a[i]为右界的数组以此表示区间

对于每一个陨石都尽可能找左界<=自己，右界尽可能大的一个区间，那么反映在上面的数组就是最大的一个前缀值

用线段树维护就行（说的容易，自己调了半天也没对）

对于已选区间要去掉可以到达的数，学习官方解答利用vector的back() （我自己都从来没用过这个函数）

注：官方解答的线段树写的也比我漂亮很多，悲，拉过来当板子了

struct node{
    int l,r, max;
}tr[N*4];
void pushup(node &u,node &l,node &r){
    u.max=max(l.max,r.max);
}
void pushup(int u){
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
    if(l==r){
        tr[u]={l,l,0};
    }
    else {
        tr[u]={l,r};
        int mid=l+r >>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int x,int w){
    if (tr[u].l == x && tr[u].r == x) tr[u]= {x, x, max(tr[u].max,w)};
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, w);
        else modify(u << 1 | 1, x, w);
        pushup(u);
    }
}
int ask(int u,int l,int r){
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].max;
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return ask(u << 1, l, r);
        else if (l > mid) return ask(u << 1 | 1, l, r);
        else{
            int lans = ask(u << 1, l, r);
            int rans = ask(u << 1 | 1, l, r);
            int res=max(lans,rans);
            return res;
        }
    }
}
void solve(){
    int n=read(),m=read();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int x=read();
        if(x==1){
            int left=read(),right=read();
            int w=read();
            modify(1,left,right);
        }else {
            int k=read();
            vector<int>a(k);
            for(int i=0;i<k;i++) a[i]=read();
            sort(a.begin(),a.end(),greater<int>());
            int ans=0;
            while(a.size()){
                int x=ask(1,1,a.back());
                if(x<a.back()){
                    ans=-1;
                    break;
                }
                ans++;
                while(a.size()&&x>=a.back()) a.pop_back();
            }
            cout<<ans<<'\n';
        }
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. lazing Riff

map<char,int>mp;
void solve(){
    string s;
    cin>>s;
    int cnt=0;
    for(int i=0;i<s.size();i++){
        if(mp[s[i]]==0)cnt++,mp[s[i]]=1;
    }
    puts(cnt>1?"2":"-1");
}

C. hivalric Blossom

更像一个模拟，每次分配颜色，如果是以一系列的任务的第一个就从stack里分配颜色，如果是最后一个就把他的颜色用完后放回stack，如果是又有前置又有后置的任务就与前置颜色相同

int l[N],r[N],ans[N];
void solve(){
    int n=read(),m=read();
    stack<int>st;
    for(int i=n;i>=1;i--) st.push(i);
    
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        r[x]=y;
        l[y]=x;
    }
    for(int i=1;i<=n;i++){
        if(l[i]){
            ans[i]=ans[l[i]];
            if(!r[i]) st.push(ans[i]);
        }else {
            ans[i]=st.top();
            if(r[i]) st.pop();
        }
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

D. andelion Knight

对于两个a,b数组求前缀和

我们对记录b数组中i这个数字出现的左界l[i]和右界r[i]

对于a中每个前缀和x都有l[x]~r[x]可以满足要求，所以从x+l[x]~x+r[x]的f(i)都会多出一个方案，这里用差分实现区间加

int a[N],b[N],pra[N],prb[N],cntl[N],cntr[N],ans[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        pra[i]=pra[i-1]+a[i];
    }
    memset(cntl,-1,sizeof(cntl));
    memset(cntr,-1,sizeof(cntr));
    cntl[0]=0;cntr[0]=0;
    for(int i=1;i<=n;i++){
        b[i]=read();
        prb[i]=prb[i-1]+b[i];
        if(cntl[prb[i]]==-1)cntl[prb[i]]=i;
        cntr[prb[i]]=i;
    }
    for(int i=0;i<=n;i++){
        if(cntl[pra[i]]==-1)break;
        ans[i+cntl[pra[i]]]++;
        ans[i+cntr[pra[i]]+1]--;
    }
    int res=0;
    for(int i=0;i<=2*n;i++){
        res+=ans[i];
        cout<<res<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

E. clipsing Star

博弈论问题，首先正向思考无果，就反向思考

对于最后一轮，先手必全部拿走。那么倒数第二轮的先手必会衡量当前的a[n-1]和a[n]，全部拿走大的一个。所以最后两轮的策略是确定的，那么可以向上推，已知最后两轮的策略，倒数第三轮的先手会衡量当前的a[n-2]和abs(a[n]-a[n-1])，拿走大的一种。倒数第四轮的先手会考虑a[n-3]和abs(abs(a[n]-a[n-1])-a[n-2])，所以我们只需一直反推就可以得到所谓的收益差

int a[N];
void solve(){
    int n=read(),ans=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=n;i>=1;i--){
        ans=abs(a[i]-ans);
    }
    cout<<abs(ans)<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

F. leeing Sunlight

double l[N],r[N];
int n,m;
bool check(double x) {
    double fin=0;
    for(int i=1;i<=n;i++){
        if(x>r[i]) fin+=1;
        else if(x>l[i]){
            fin+=(x-l[i])/(r[i]-l[i]);
        }
    }
    return fin>=m;
}
double bs3(double l, double r)
{
    const double eps = 1e-6;  
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}
void solve(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    cout<<bs3(0,1000000000)<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

I. cy Resurrection

void solve(){
    int n=read();
    cout<<n<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

J. uvenile Galant

int ans[N];
void yuchuli(){
    ans[0]=1;
    ans[1]=0;
    ans[2]=1;
    ans[3]=2;
    ans[4]=1;
    for(int i=5;i<N;i++){
            ans[i]=(ans[i-3]*2%mod+ans[i-2])%mod;
    }
}
void solve(){
    int n=read();
    cout<<ans[n-2]<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

N. anikore

void solve(){
    puts("NO");
    //puts(ans>0?"Yes":"No");
}