首页 > 其他分享 >Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) D

Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) D

时间:2022-12-25 22:24:07浏览次数:57  
标签:Manthan rated int tr everyone Div open

D. Restore Permutation

题链
不难看出我们应该从后往前做
我们设t[i]=i*(i-1)/2
最后一个i肯定能在t数组直接找到
比如我们找到了是3
那么要是我们下一个是5
我们就要把这个3从以后的t[4] t[5] ....中剪掉
注意这里剪掉之后我们t还是保持单调性 这里我们应该很敏感的可以知道查找一个t=a[i]可以用二分了
注意code里t[i]数组是tr[i]的前缀和

int n,tr[N];
int lowbit(int x){return x&-x;}
void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i]+=c;
    }
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}
void solve(){
    cin>>n;
    vector<int>a(n+1),ans(n+1);
    for(int i=1;i<=n;i++)cin>>a[i],add(i,i);
    for(int i=n;i>=1;i--){
        int l=1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(query(mid-1)<=a[i])l=mid;
            else r=mid-1;
        }
        ans[i]=l;
        add(l,-l);
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
}

标签:Manthan,rated,int,tr,everyone,Div,open
From: https://www.cnblogs.com/ycllz/p/17004756.html

相关文章

  • Codeforces Round #769 (Div. 2) B,C
    CodeforcesRound#769(Div.2)B,CBB这道题我在vp的时候一直没有想出来,一直不知道到底怎么写,只是想到和幂有关,wa了一发,后来看了大佬的题解,真是觉得自己太菜了,自愧不如......
  • Codeforces Round #814 (Div. 2)
    A核心思路:这题没什么好说的直接面向样例编程。#include<iostream>#include<cstring>#include<string>#include<vector>#include<math.h>#include<cmath>#inc......
  • Codeforces Round #586 (Div. 1 + Div. 2) D
    D.AlexandJulian题链很容易发现我们要是两个数互相不构成奇环的话=(a+b)/gcd(a,b)为偶数我们发现如果ab为奇数的时候一定可以并且奇偶一定不同组但是发现24这种又......
  • Educational Codeforces Round 122 (Rated for Div. 2),C,D
    EducationalCodeforcesRound122(RatedforDiv.2),C,DCC这道题就是普通的暴力,但是我在做的过程中第10组数据出现了数据溢出的错误我的错误代码,我在vp的时候没觉得......
  • Codeforces Round #589 (Div. 2) D
    D.CompleteTripartite题链与其他题解不同我首先发现的是没有相连的一定是同一组那么我们直接对于整个数组遍历一遍将与1同组的搞出来要是下一个位置已经有组了我......
  • POJ 1014 Dividing
    POJ1014Dividing题意:多重背包问题,给出若干物品,求是否能分成价值相同的两堆思考:求出总和\(sum\)之后,如果\(sum\)是奇数则一定不可能,然后如果我们能凑出\(sum/......
  • Codeforces Round #770 (Div. 2)B,C
    CodeforcesRound#770(Div.2)B,C还是惨绝人寰的只做了一个题,ε=(´ο`*)))唉BB这一道题大意是是首先有一个d,然后有n个操作,从1到n,每一次我们都需要选择让d=d+a[i]还是d......
  • 《Social Diversity and Social Preferences in Mixed-Motive Reinforcement Learning
    混合动机强化学习中的社会多样性与社会偏好总结:本质是在研究当智能体群体中的个体具有独特性质时在困境强化学习中对结果的影响。提出了一个社会价值偏向取向的概念来使......
  • Codeforces Round #836 (Div. 2)构造场
    今天的CF居然是这样的全是构造题,顺便把牛客上的一道构造写了C题待补链接......
  • Codeforces Round #837 (Div. 2)(持续更新)
    Preface补题ing上周由于疫情鸽了好多场,趁现在空下来尽量多写点吧A.HossamandCombinatoricsSB题,直接统计下最大的数和最小的数的个数即可注意所有数相同的情况要特......