第二十届西南科技大学ACM程序设计竞赛_牛客

E-又双叒叕分糖果_第二十届西南科技大学ACM程序设计竞赛（同步赛） (nowcoder.com)

思路："丢"糖果的话分类讨论非常麻烦！！"拿"的话贪心拿！

int n;
int x,y;
void solve(){               ////D--题解:!贪心+思维!,,,自己的想法非常麻烦,想不清楚。
////我的想法是"丢"，题解是"拿"。
////"拿"比"丢"好些得多得多
    cin>>n>>x>>y;
    set<int> bag1,bag2;
    for(int i=1;i<=x;i++){
        int w,num; cin>>w>>num;
        bag1.emplace(w);
    }
    ////num是没用的
    int same=0;
    for(int i=1;i<=y;i++){
        int w,num; cin>>w>>num;
        bag2.emplace(w);
        if(bag1.count(w)) same++;
    }
    cout<<min( min((int)bag1.size()-same,n/2)+min((int)bag2.size()-same,n/2)+same ,n)<<endl;
    ////bag1独有的为bag1.size()-same;
    ////bag2独有的为bag2.size()-same;
    ////优先拿了独有的之后,再去拿共有的
}

M-简单动态规划_第二十届西南科技大学ACM程序设计竞赛（同步赛） (nowcoder.com)

思路：三分好题。三分a1的取值，那么剩下的值也可以确定了，问题是要发现有三分的性质(单峰函数)。

三分要注意的点：
一：循环退出条件
二：midl和midr
三：check传入的参数
四：l,r的赋值
五：遍历附近值

int n;
int arr[100005];
int check1(int x){          ////a1为奇数
    int cost=0,cur=x;
    for(int i=1;i<=n;i++){
        cost+=abs(arr[i]-cur)/2;
        if(arr[i]%2==0) cost+=100;
        cur+=2;
    }
    return cost;
}
int check2(int x){         ////a1为偶数
    int cost=0,cur=x;
    for(int i=1;i<=n;i++){
        cost+=abs(arr[i]-cur)/2;
        if(arr[i]%2!=0) cost+=100;
        cur+=2;
    }
    return cost;
}
////key:要发现有三分的性质，即答案和ans是函数，是一个开口向上的单峰函数。
////三分好题。
////三分要注意的点：
////一：循环退出条件
////二：midl和midr
////三：check传入的参数
////四：l,r的赋值
////五：遍历附近值
void solve(){           ////M--按理来说是动态规划，但是三分也可以.
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    sort(arr+1,arr+n+1);   ////显而易见，因为交换位置是无代价的。所以开始先排序，很明显是更优的.

    ////三分a1为奇数
    int l=-1e10-10,r=1e10+10;    ////负的ai也取得到!!
    while(l<r-10){                      ////(x/2)+1 并不能保证结果是奇数。。。直接乘2加1才一定是奇数
        int midl=l+(r-l)/3;     ////key
        int midr=r-(r-l)/3;
        if(check1(midl*2-1)>=check1(midr*2-1)) l=midl+1;     ////key:这里就不用midl*2+1了!!不然会死循环
        else r=midr-1;        ////r=midr*2-1
    }
    int ans=LONG_LONG_MAX;
    for(int i=l*2-101;i<=r*2+101;i+=2) ans=min(ans,check1(i));        ////附近

    ////三分a1为偶数
    l=-1e10-10,r=1e10+10;         ////负的ai也取得到!!
    while(l<r-10){
        int midl=l+(r-l)/3;     ////key
        int midr=r-(r-l)/3;
        if(check2(midl*2)>=check2(midr*2)) l=midl+1;            ////key:这里就不用midl*2+1了!!不然会死循环
        else r=midr-1;
    }
    for(int i=l*2-100;i<=r*2+100;i+=2) ans=min(ans,check2(i));        ////附近

    cout<<ans<<endl;
}

C-图腾_第二十届西南科技大学ACM程序设计竞赛（同步赛） (nowcoder.com)

思路：用set维护图腾的位置。每次放置图腾，在set中二分找到前,后一个图腾的位置。在map[位置,权值]中查找图腾的权值。然后用线段树进行区间修改[l+1,cur-1]和[cur+1,r-1].并且区间要是合法的。

#define lc p<<1
#define rc p<<1|1
typedef struct node{
    int l,r,sum;
    int tag;
}node;
const int N=300005;
node tr[4*N];
int n,m,q,init=0;
set<int> position;
unordered_map<int,int> totem;
void build(int p,int l,int r){
    tr[p]={l,r,init,-1};
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void pushup(int p){
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int p){
    if(tr[p].tag!=-1){          ////不能以0为初始值
        tr[lc].sum=(tr[lc].r-tr[lc].l+1)*tr[p].tag;
        tr[rc].sum=(tr[rc].r-tr[rc].l+1)*tr[p].tag;
        tr[lc].tag=tr[p].tag;
        tr[rc].tag=tr[p].tag;
        tr[p].tag=-1;
    }
}
void update(int p,int l,int r,int x){
    if(tr[p].l>=l&&tr[p].r<=r){
        tr[p].sum=(tr[p].r-tr[p].l+1)*x;
        tr[p].tag=x;
        return;
    }
    pushdown(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(mid>=l) update(lc,l,r,x);
    if(mid<r) update(rc,l,r,x);
    pushup(p);
}
int query(int p,int l,int r){
    if(tr[p].l>=l&&tr[p].r<=r) return tr[p].sum;
    int res=0;
    pushdown(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(mid>=l) res+=query(lc,l,r);
    if(mid<r) res+=query(rc,l,r);
    return  res;
}
void process(int pos,int val){
    auto lesser=--position.lower_bound(pos);
    auto bigger=position.upper_bound(pos);
    int ll=*lesser,rr=*bigger;
    int numl=totem[ll],numr=totem[rr];
    if(ll+1<=pos-1) update(1,ll+1,pos-1,numl*val);
    if(pos+1<=rr-1) update(1,pos+1,rr-1,val*numr);
    update(1,pos,pos,0);
}
void solve(){               ////C---线段树
    cin>>n>>m>>q;
    vector<int> a;
    for(int i=0;i<m;i++){
        int x; cin>>x;
        a.emplace_back(x);
        position.emplace(x);
    }
    for(int i=0;i<m;i++){
        int x; cin>>x;
        totem[a[i]]=x;
    }
    init=totem[1]*totem[m];
    build(1,1,n);
    update(1,1,1,0),update(1,n,n,0);  ////init
    for(int i=1;i<m-1;i++){
        int pos=a[i],val=totem[a[i]];
        process(pos,val);
    }
    while(q--){
        int op,x,y; cin>>op>>x>>y;
        if(op==1){
            position.emplace(x),totem[x]=y;
            process(x,y);
        }
        else if(op==2) cout<<query(1,x,y)<<endl;
    }
}