@exut 2024-11-14T02:52:36.000000Z 字数 4019 阅读 143

11.12

刷题

CF915E

第一眼板子，第二眼还是板子

做法可以考虑ODT，但是那样太玄乎了算了吧

考虑动态开点线段树

非常简单好写，但是空间有点申比

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int ls[N*33],rs[N*33];
int sum[N*33];
int idx;
int tag[N*33];
void pushup(int rt){
    sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
#define mid (l+r>>1)
void pushdown(int rt,int l,int r){
    if(tag[rt]==-1) return;
    if(!ls[rt]) ls[rt]=++idx;
    if(!rs[rt]) rs[rt]=++idx;
    tag[ls[rt]]=tag[rs[rt]]=tag[rt],tag[rt]=-1;
    sum[ls[rt]]=(mid-l+1)*tag[ls[rt]];
    sum[rs[rt]]=(r-mid)*tag[rs[rt]];
}
void modi(int& rt,int l,int r,int L,int R,bool k){
    if(l>R or L>r) return;
    if(!rt) rt=++idx;
    if(L<=l and r<=R){
        tag[rt]=k;
        sum[rt]=(r-l+1)*k;
        return; 
    }
    pushdown(rt,l,r);
    modi(ls[rt],l,mid,L,R,k);
    modi(rs[rt],mid+1,r,L,R,k);
    pushup(rt);
}
int rot;
int n,q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    memset(tag,-1,sizeof tag);
    modi(rot,1,n,1,n,1);
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        if(k==1) modi(rot,1,n,l,r,0);
        else modi(rot,1,n,l,r,1);
        cout<<sum[rot]<<"\n";
    }
}

CF731E

考虑到这个放一个串代替一段前缀的过程没有什么很大的意义其实，直接可以转化成每次取的位置严格单调即可

设 $dp_{i,j}$ 表示取到 $i$ ，是 $j$ 这个人操作的答案，显然两个人对答案分别作正和负贡献

复杂度 $O(n^2)$ ，考虑优化

注意到转移点都是前面的dp值+前缀和的最大值或者最小，可以开两个线段树优化，但是注意到这里是前缀最值，所以树状数组也是个好的选择

应该可做，但是复杂了一点，尤其边界貌似有点奇怪

考虑到这个人这一维并不重要，我们只在乎得分差，而且边界貌似也是从后往前更好考虑来着（一口气拿完）

我们设 $dp_{i}$ 表示从 $i$ 到 $n$ 的最优答案

则有 $dp_{i}=\max\limits_{j>i} (pre_j-dp_j)$

转移发现后面那一坨始终是一样的，记录最优点惰性转移就行，当然你闲得蛋疼写个树状数组应该也没事就是了

CF865D

经典带悔贪心板子

但是我贪心真的很差，一直不太能理解这种玩意，考贪心那就寄了，悲，甚至贪心比dp还差

CF1439C

某P教练终于找到好玩的题了/kk

感觉比较神秘

这个单调性质很猛，而且修改不会破坏，直接可以考虑上线段树二分，于是操作1是ez的

考虑操作2，直接在线段树上跑，如果一个区间右端点小于x则贡献为0直接返回

如果一个区间的和都小于y就贡献为区间长度，也返回，此时把y减去区间和，然后继续递归

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
#define int long long
int n,q,a[N];
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
int sum[N*4],mi[N*4],tag[N*4];
void pushup(int rt){
    sum[rt]=sum[ls]+sum[rs];
    mi[rt]=min(mi[ls],mi[rs]);
}
void build(int rt,int l,int r){
    if(l==r){
        sum[rt]=mi[rt]=a[l];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(rt);
}
void pushdown(int rt,int l,int r){
    if(tag[rt]){
        tag[ls]=tag[rs]=tag[rt],tag[rt]=0;
        sum[ls]=tag[ls]*(mid-l+1);
        mi[ls]=tag[ls];
        sum[rs]=tag[rs]*(r-mid);
        mi[rs]=tag[rs];
    }
}
int query_pos(int rt,int l,int r,int val){
    if(l==r){
        if(val>mi[rt])return l;
        return l+1;
    }
    pushdown(rt,l,r);
    if(mi[ls]>=val) return query_pos(rs,mid+1,r,val);
    return query_pos(ls,l,mid,val);
}
int query(int rt,int l,int r,int L,int& y){
    if(y<mi[rt] or r<L) return 0;
    if(l>=L and y>=sum[rt]){
        y-=sum[rt];
        return min(n,r)-l+1;
    }
    pushdown(rt,l,r);
    return query(ls,l,mid,L,y)+query(rs,mid+1,r,L,y);
}
void modi(int rt,int l,int r,int L,int R,int k){
    if(L<=l and r<=R){
        sum[rt]=(r-l+1)*k;
        mi[rt]=k;
        tag[rt]=k;
        return;
    }
    if(L>r or l>R) return;
    pushdown(rt,l,r);
    modi(ls,l,mid,L,R,k);
    modi(rs,mid+1,r,L,R,k);
    pushup(rt);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            int l=query_pos(1,1,n,y);
            if(l<=x) modi(1,1,n,l,x,y);
        }
        else cout<<query(1,1,n,x,y)<<"\n";
    }
}

CF893E

首先质因数分解，假设出现过的次幂依次为 $e_{1\to k}$

正负重要吗？不重要，只需要最后乘上 $2^{y-1}$ 即可，也就是前面任选最后一个来补上位置

对于每个质因子单独考虑，插板可得方案数为 $\binom{e_i+y-1}{y-1}$ ，质因数分解然后乘起来就好了

CF388C

永远会讨厌贪心的，但是这题还简单

猜一下结论，先手开始拿一堆之后，必将会先后手交替拿这一堆拿完位置

然后当前操作手拿剩下能摸到的最大的那个所在的那一堆

看着不太对，但是手玩样例都过了，怪，写一下看看

好的，WA on test 12，我就知道

感觉问题出在当前活动手拿哪一堆上面，只是拿最大值所在堆有点太肤浅了

我们考虑到偶数堆谁先手谁后手是无所谓的，而且也不会交换先后手

对于奇数堆，这才是需要考虑的，现在考虑每次拿收益最大的堆而不是最大值的堆

然后又寄了，这次WA on test 6

然后我们考虑到按我们的贪心，前半段和后半段貌似不是需要考虑的东西，对于奇数堆来说有影响的貌似只是最中间那一个牌而已，于是先处理偶数的堆，然后剩下的按中间那张牌大小互相贪心拿

过了

我不会贪心，但是不妨碍我能猜/kk

吐槽一下这道题样例真的非常弱小，根本测不出任何问题，但是实际上上面两种错误写法都非常好hack

值得一提的是本题的数据范围太小了，其实完全可以加大

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> s[105];
bool cut[105];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int wc;
        cin>>wc;
        for(int j=1;j<=wc;j++){
            int x;
            cin>>x;
            s[i].push_back(x);
        }
    }
    int ans1=0,ans2=0;
    bool di=1;//谁操
    int pos=0;
    for(int i=1;i<=n;i++){
        if(s[i].size()%2==0){
            cut[i]=1;
            int l=0,r=s[i].size()-1;
            while(l<=r){
                if(di) ans1+=s[i][l++],di^=1;
                else ans2+=s[i][r--],di^=1;
            }
        }
    }
    while(1){
        int mx=-1;
        pos=0;
        for(int i=1;i<=n;i++){
            if(cut[i]) continue;
            if(mx<s[i][s[i].size()/2]) pos=i,mx=s[i][s[i].size()/2];
        }
        if(!pos){
            cout<<ans1<<" "<<ans2;
            return 0;
        }
        cut[pos]=1;
        int l=0,r=s[pos].size()-1;
        while(l<=r){
            if(di) ans1+=s[pos][l++],di^=1;
            else ans2+=s[pos][r--],di^=1;
        }
    }
    return 0;
}

存在实现难度但是说实话不高真的

收工，疑似首次把题单做完，喜