做题记录

Eucatastrophe‌

2026-05-06 13:38:42

发布于：浙江

34阅读

0回复

0点赞

$\huge{5.5}$

P1198：

绿

期望耗时：20min

耗时：3h

实际耗时：15min 左右

做法：线段树，板板

代码：

//直接板子复制过来的，很多变量都是棍母不用管
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=800005;
int d,n,t,cnt;
vector<int> a(N);
struct node{
    int lazy=0,data;
}tree[N];
int left_child(int now){//取左孩子，返回的是索引
    return 2*now;
}int right_child(int now){//取右孩子
    return 2*now+1;
}long long query(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
    if(ql>r or qr<l)return LLONG_MIN;
    if(ql<=l and qr>=r)return tree[now].data;
    int mid=l+(r-l)/2;
    return max(query(left_child(now),l,mid,ql,qr),query(right_child(now),mid+1,r,ql,qr));
}void update(int now,int l,int r,int idx,int val){//单点更新
    if(l==r){
        tree[now].data=val;
        return ;
    }int mid=l+(r-l)/2; 
    if(idx<=mid){
        update(left_child(now),l,mid,idx,val);
    }else{
        update(right_child(now),mid+1,r,idx,val);
    }tree[now].data=max(tree[left_child(now)].data,tree[right_child(now)].data);
}
signed main(){
    cin >> n >> d;
    t=0,cnt=0;
    for(int i=1;i<=n;i++){
        char c;
        int x;
        cin >> c >> x;
        if(c=='A'){
            cnt++;
            update(1,1,n,cnt,(x+t+d)%d);
        }else{
            t=query(1,1,n,cnt-x+1,cnt);
            cout << t << endl;
        }
    }
    return 0;
}

P1775

难度：黄

石子合并弱化，上课学的。直接贴代码

#include <cstdio>
const long long INF=0x3f3f3f3f; 
#define enter putchar_unlocked('\n')
inline void read(long long&x){
    x=0;
    int f=1;
    char ch=getchar_unlocked();;
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;ch=getchar_unlocked();
    }while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar_unlocked();;
    }x*=f;
}
inline void write(long long x){
    if(x<0){
        putchar_unlocked('-');
        x=-x;
    }if(x>9)write(x/10);
    putchar_unlocked(x%10+'0');
}
long long dp[1005][1005],n,a[1005],sum[1005];
long long min(long long a,long long b){
    return a>b?b:a;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        sum[i]=sum[i-1]+a[i];
        dp[i][i]=0;
    }for(int l=2;l<=n;l++){
        for(int i=1,j=l;j<=n;i++,j++){
            dp[i][j]=INF;
            for(int k=i;k<j;k++){
                long long next=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                dp[i][j]=min(dp[i][j],next);
            }
        }
    }write(dp[1][n]);
    return 0;
}

P1122

难度：黄

实际用时：1s（

双倍经验

帮 wcqk 调代码顺手 AC，这里贴 wcqk 代码😋😋😋

#include<bits/stdc++.h>
using namespace std;

int a[100010],n;
long long dp[100010];
vector<int> g[100010];

void dfs(int u,int fa){
    dp[u]=a[u];
    for(int v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u]+=max(dp[v],0LL);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    long long maxx=INT_MIN;
    for(int i=1;i<=n;i++){maxx=max(maxx,dp[i]);}
    cout<<maxx;
}

P1880

石子合并强化版。

难度：绿

做法：

在弱化版的基础上再在后面加一圈，然后开两个 $dp$ 数组存最大值最小值，然后就没了。

#include <cstdio>
const long long INF=0x3f3f3f3f3f; 
#define enter putchar_unlocked('\n')
inline void read(long long&x){
    x=0;
    int f=1;
    char ch=getchar_unlocked();;
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar_unlocked();
    }while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar_unlocked();;
    }x*=f;
}
inline void write(long long x){
    if(x<0){
        putchar_unlocked('-');
        x=-x;
    }if(x>9)write(x/10);
    putchar_unlocked(x%10+'0');
}long long dp[1005][1005],n,a[1005],sum[1005],dp2[1005][1005];
long long min(long long a,long long b){
    return a>b?b:a;
}long long max(long long a,long long b){
    return a<b?b:a;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        a[n+i]=a[i];
    }int len=(n<<1)-1;
    for(int i=1;i<=len;i++){
        sum[i]=sum[i-1]+a[i];
    }for(int l=2;l<=len;l++){
        for(int i=1,j=l;j<=len;i++,j++){
            dp[i][j]=INF;
            for(int k=i;k<j;k++){
                long long next=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                dp[i][j]=min(dp[i][j],next);
                next=dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1];
                dp2[i][j]=max(dp2[i][j],next);
            }
        }
    }long long mn=INF,mx=-INF;
    for(int i=1;i<=n;i++)mn=min(mn,dp[i][i+n-1]),mx=max(dp2[i][i+n-1],mx);
    write(mn);
    enter;
    write(mx);
    return 0;
}

P6136

难度：蓝

实际用时：10min

思路：

平衡树板子，就加了个强制在线，根据题意修改即可，不难，10min 杀穿，但是之前我 Treap 为啥老被炸。注意有些变量要开 long long。这里选择了速度较快的红黑树实现。

#include <cstdio>
const int INF=1000000000;
const bool red=1;
const bool black=0;
inline void readll(long long&x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}x*=f;}
inline void writell(long long x){if(x<0){putchar('-');x=-x;}if(x>9)writell(x/10);putchar(x%10+'0');}
inline void read(int&x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}x*=f;}
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
template<typename T>
class Redblacktree{
private:
    struct rbt{T key,cnt,siz;bool color;rbt*l,*r,*fa;}*root,*nil;
    rbt* newnode(T key){
        rbt*p=new rbt;
        p->key=key,p->cnt=1,p->siz=1,p->color=red;
        p->l=p->r=p->fa=nil;
        return p;
    }void pushup(rbt*u){
        u->siz=u->cnt;
        if(u->l!=nil)u->siz+=u->l->siz;
        if(u->r!=nil)u->siz+=u->r->siz;
    }void zig(rbt*u){
        rbt*lc=u->l;
        u->l=lc->r;
        if(lc->r!=nil)lc->r->fa=u;
        lc->fa=u->fa;
        if(u->fa==nil)root=lc;
        else if(u==u->fa->l)u->fa->l=lc;
        else u->fa->r=lc;
        lc->r=u,u->fa=lc;
        pushup(u),pushup(lc);
    }void zag(rbt*u){
        rbt*rc=u->r;
        u->r=rc->l;
        if(rc->l!=nil)rc->l->fa=u;
        rc->fa=u->fa;
        if(u->fa==nil)root=rc;
        else if(u==u->fa->l)u->fa->l=rc;
        else u->fa->r=rc;
        rc->l=u,u->fa=rc;
        pushup(u),pushup(rc);
    }void insertfix(rbt*x){
        while(x->fa->color==red){
            if(x->fa==x->fa->fa->l){
                rbt*unc=x->fa->fa->r;
                if(unc->color==red){
                    x->fa->color=black;
                    unc->color=black;
                    x->fa->fa->color=red;
                    x=x->fa->fa;
                }else{
                    if(x==x->fa->r){
                        x=x->fa,zag(x);
                    }
                    x->fa->color=black;
                    x->fa->fa->color=red;
                    zig(x->fa->fa);
                }
            }else{
                rbt*unc=x->fa->fa->l;
                if(unc->color==red){
                    x->fa->color=black;
                    unc->color=black;
                    x->fa->fa->color=red;
                    x=x->fa->fa;
                }else{
                    if(x==x->fa->l){
                        x=x->fa,zig(x);
                    }
                    x->fa->color=black;
                    x->fa->fa->color=red;
                    zag(x->fa->fa);
                }
            }
        }root->color=black;
    }void transplant(rbt*u,rbt*v){
        if(u->fa==nil)root=v;
        else if(u==u->fa->l)u->fa->l=v;
        else u->fa->r=v;
        v->fa=u->fa;
    }rbt* findmin(rbt*u){
        while(u->l!=nil)u=u->l;
        return u;
    }void delfix(rbt*x){
        while(x!=root&&x->color==black){
            if(x==x->fa->l){
                rbt*bro=x->fa->r;
                if(bro->color==red){
                    bro->color=black;
                    x->fa->color=red;
                    zag(x->fa);
                    bro=x->fa->r;
                }
                if(bro->l->color==black&&bro->r->color==black){
                    bro->color=red;
                    x=x->fa;
                }else{
                    if(bro->r->color==black){
                        bro->l->color=black;
                        bro->color=red;
                        zig(bro);
                        bro=x->fa->r;
                    }
                    bro->color=x->fa->color;
                    x->fa->color=black;
                    bro->r->color=black;
                    zag(x->fa);
                    x=root;
                }
            }else{
                rbt*bro=x->fa->l;
                if(bro->color==red){
                    bro->color=black;
                    x->fa->color=red;
                    zig(x->fa);
                    bro=x->fa->l;
                }
                if(bro->r->color==black&&bro->l->color==black){
                    bro->color=red;
                    x=x->fa;
                }else{
                    if(bro->l->color==black){
                        bro->r->color=black;
                        bro->color=red;
                        zag(bro);
                        bro=x->fa->l;
                    }
                    bro->color=x->fa->color;
                    x->fa->color=black;
                    bro->l->color=black;
                    zig(x->fa);
                    x=root;
                }
            }
        }x->color=black;
    }
public:
    void init(){
        nil=new rbt;
        nil->color=black;
        nil->l=nil->r=nil->fa=nil;
        nil->cnt=nil->siz=0;
        root=nil;
    }void push(T key){
        rbt*now=root,*last=nil;
        while(now!=nil){
            last=now;
            if(key==now->key){
                now->cnt++;
                pushup(now);
                rbt*cur=now;
                while(cur->fa!=nil){
                    cur=cur->fa;
                    pushup(cur);
                }return;
            }else if(key<now->key)now=now->l;
            else now=now->r;
        }
        now=newnode(key);
        now->fa=last;
        if(last==nil)root=now;
        else if(key<last->key)last->l=now;
        else last->r=now;
        insertfix(now);
        rbt*cur=now;
        while(cur!=nil){
            pushup(cur);
            cur=cur->fa;
        }
    }void del(T key){
        rbt*now=root;
        while(now!=nil){
            if(key==now->key)break;
            else if(key<now->key)now=now->l;
            else now=now->r;
        }if(now==nil)return;
        if(now->cnt>1){
            now->cnt--;
            pushup(now);
            rbt*cur=now;
            while(cur->fa!=nil){
                cur=cur->fa;
                pushup(cur);
            }return;
        }
        rbt*y=now,*x;
        bool ycol=y->color;
        if(now->l==nil){
            x=now->r;
            transplant(now,now->r);
        }else if(now->r==nil){
            x=now->l;
            transplant(now,now->l);
        }else{
            y=findmin(now->r),ycol=y->color,x=y->r;
            if(y->fa==now)x->fa=y;
            else{
                transplant(y,y->r);
                y->r=now->r,now->r->fa=y;
            }
            transplant(now,y);
            y->l=now->l,now->l->fa=y,y->color=now->color;
        }
        delete now;
        rbt*cur=x->fa;
        while(cur!=nil){
            pushup(cur);
            cur=cur->fa;
        }if(ycol==black)delfix(x);
    }int getrank(T x){
        rbt*u=root;
        int res=0;
        while(u!=nil){
            if(x<u->key)u=u->l;
            else if(x>u->key)res+=u->l->siz+u->cnt,u=u->r;
            else{res+=u->l->siz;break;}
        }
        return res;
    }T getkth(int k){
        rbt*u=root;
        while(u!=nil){
            int ls=u->l->siz;
            if(k<=ls)u=u->l;
            else if(k<=ls+u->cnt)return u->key;
            else k-=ls+u->cnt,u=u->r;
        }
        return 0;
    }T getpre(T x){
        rbt*u=root;
        T res=-INF;
        while(u!=nil){
            if(u->key<x)res=u->key,u=u->r;
            else u=u->l;
        }
        return res;
    }T getsuc(T x){
        rbt*u=root;
        T res=INF;
        while(u!=nil){
            if(u->key>x)res=u->key,u=u->l;
            else u=u->r;
        }
        return res;
    }
};
int main() {
    Redblacktree<int> tr;
    tr.init();
    int t,n;
    read(n),read(t);
    while(n--){
        int x;
        read(x);
        tr.push(x);
    }
    long long last=0;
    long long ans=0;
    while(t--){
        int op,x;
        read(op),read(x);
        x^=last;
        if(op==1)tr.push(x);
        if(op==2)tr.del(x);
        if(op==3)ans^=(tr.getrank(x)+1),last=(tr.getrank(x)+1);
        if(op==4)ans^=tr.getkth(x),last=tr.getkth(x);
        if(op==5)ans^=tr.getpre(x),last=tr.getpre(x);
        if(op==6)ans^=tr.getsuc(x),last=tr.getsuc(x);
    }write(ans);
    return 0;
}

还是跑了 9.5s，太慢了

P2820

刷到十倍经验看见的，MST 板子。

难度：黄

思路：边权总和减去 MST

实际用时：1min

#include <bits/stdc++.h>
using namespace std;
#define int long long
int sum=0;
const int N=2e5+5;
int n,m,ans=0,k;
struct node{
    int u,v,w;
}sz[N];
bool cmp(node a,node b){
    return a.w<b.w;
}void Kruskal(){
     class FA{
        private:
            int fa[N],h[N];
        public:
            int find(int x){
                if(fa[x]==x)return x;
                else return fa[x]=find(fa[x]);
            }void merge(int x,int y){
                x=find(x),y=find(y);
                if(x==y)return;
                if(h[y]<h[x])swap(x,y);
                if(h[x]==h[y])h[y]=h[x]+1;
                fa[y]=x;
            }void init(int n){
                for(int i=1;i<=n;i++)fa[i]=i,h[i]=1;
            }
    };FA fa;
    fa.init(n);
    sort(sz****z+1+m,cmp);
    for(int i=1;i<=m;i++){
        int x=fa.find(sz[i].u),y=fa.find(sz[i].v);
        if(x!=y){
            ans+=sz[i].w;
            fa.merge(x,y);
            if(++k==n-1){
                break;
            }
        }
    }if(k<n-1)cout << "-1";
    else cout << sum-ans;
}
signed main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){cin >> sz[i].u >> sz[i].v >> sz[i].w;sum+=sz[i].w;}
    Kruskal();
    return 0;
}

P1669

难度：黄

思路：

最大生成树

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,ans=0,k;
struct node{
    int u,v,w;
}sz[N];
bool cmp(node a,node b){
    return a.w>b.w;
}void Kruskal(){
     class FA{
        private:
            int fa[N],h[N];
        public:
            int find(int x){
                if(fa[x]==x)return x;
                else return fa[x]=find(fa[x]);
            }void merge(int x,int y){
                x=find(x),y=find(y);
                if(x==y)return;
                if(h[y]<h[x])swap(x,y);
                if(h[x]==h[y])h[y]=h[x]+1;
                fa[y]=x;
            }void init(int n){
                for(int i=1;i<=n;i++)fa[i]=i,h[i]=1;
            }
    };FA fa;
    fa.init(n);
    sort(sz****z+1+m,cmp);
    for(int i=1;i<=m;i++){
        int x=fa.find(sz[i].u),y=fa.find(sz[i].v);
        if(x!=y){
            ans+=sz[i].w;
            fa.merge(x,y);
            if(++k==n-1){
                break;
            }
        }
    }if(k<n-1)cout << "-1";
    else cout << ans;
}
signed main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++)cin >> sz[i].u >> sz[i].v >> sz[i].w;
    Kruskal();
    return 0;
}

总结：

黄+=3

绿+=2

蓝++

有帮助，赞一个

去预览

0/2000

全部评论 8

Eucatastrophe‌
d

3天前来自浙江
1
- 超赛
  回复
  Eucatastrophe‌
  d
  
  3天前来自山西
  0
Eucatastrophe‌
这次不会烂尾了，写详细点

3天前来自浙江
1
𝓮𝓽𝓱𝓮𝓻𝓮𝓪𝓵
D

2天前来自浙江
0
Zhang Yiyao
daff

2天前来自浙江
0
Zhang Yiyao
asfs

2天前来自浙江
0
prediction
%%%

2天前来自浙江
0
Xylophone
指针的实现就是又臭又长，暴论

3天前来自广东
0
- Eucatastrophe‌
  回复
  Xylophone
  我就爱看这种东西😋
  
  3天前来自浙江
  0
Eucatastrophe‌
@wcqk

3天前来自浙江
0
- Eucatastrophe‌
  回复
  Eucatastrophe‌
  我去艾特错了
  
  3天前来自浙江
  1

5.5\huge{5.5}5.5

P1198：

P1775

P1122

P1880

P6136

P2820

P1669

总结：

全部评论 8

热门讨论

$\huge{5.5}$