2024“钉耙编程”中国大学生算法设计超级联赛（3）

IR101 · 2024-07-28 20:42:59 · 个人记录

比特跳跃

思路：由于到达每个点，其实只需要使用一次穿越，且如果使用穿越，必然是从其子集来到当前点，不然的话肯定是从1到当前点更优，那么先跑一次djstl，然后枚举子集即可，复杂度nlogn，后面再进行一次djstl跑完图，得到答案必然是最优的

diamond：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
vector<PII>mp[150005];
int n,m,k;
int dist[150001];
bool st[155001];
void djstl(){
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>q;
    for (int i = 1; i <=n ; ++i) {
        st[i]=0;
        if(dist[i]!=1e15)q.push({dist[i],i});
    }
    q.push({0,1});
    while(!q.empty()){
        auto t=q.top();
        q.pop();
        int ver=t.second,ds=t.first;
        if(st[ver])continue;
        st[ver]= true;
        for (int i = 0; i <mp[ver].size() ; ++i) {
            auto p=mp[ver][i];
            if(dist[p.first]>ds+p.second){
                dist[p.first]=ds+p.second;
                q.push({dist[p.first],p.first});
            }
        }
    }
}
void solve(){
    cin>>n>>m>>k;
    for (int i = 1; i <=n ; ++i) {
        mp[i].clear();
        dist[i]=1e15;
    }
    for (int i = 0; i <m ; ++i) {
        int x,y,z;
        cin>>x>>y>>z;
        mp[x].push_back({y,z});
        mp[y].push_back({x,z});
    }
    djstl();
    for (int i = 1; i <=n ; ++i) {
        dist[i]=min(dist[i],(i|1)*k);
        for (int j = (i-1)&i; j  ; j=(j-1)&i) {
            dist[i]=min(dist[i],dist[j]+i*k);
        }
    }
    djstl();
    for (int i = 2; i <=n ; ++i) {
        cout<<dist[i]<<" ";
    }
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

单峰数列

思路：线段树维护区间是否为升序和降序，由于合并时需要用到区间的端点的值，那么再维护一个最大值最小值，然后判断单峰用到最大值左边升序，右边降序即可

diamond：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define N 100003
#define LD (o<<1)
#define RD (o<<1|1)
#define INF 0x7fffffff
struct Node{
    int l,r;
    int maxv,minv,issheng,isjiang;
    int add;
};
int n;
struct Tree{
    Node t[N<<2];
    int a[N];
    inline void pushup(Node &o,Node &ld,Node &rd){
        o.maxv=max(ld.maxv,rd.maxv);
        o.minv=min(ld.minv,rd.minv);
        if(ld.issheng and rd.issheng and ld.maxv<rd.minv){
            o.issheng=1;
        }
        else o.issheng=0;
        if(ld.isjiang and rd.isjiang and ld.minv>rd.minv){
            o.isjiang=1;
        }
        else o.isjiang=0;

    }
    inline void pushdown(Node &o,Node &ld,Node &rd){
        ld.add+=o.add;ld.maxv+=o.add;
        rd.add+=o.add;rd.maxv+=o.add;
        ld.minv+=o.add;
        rd.minv+=o.add;
        o.add=0;
    }
    void build(int o,int l,int r){
        t[o].l=l;t[o].r=r;t[o].add=0;
        if(l==r){t[o]={l,r,a[l],a[r],1,1,0};return;}
        int mid=(l+r)>>1;
        build(LD,l,mid);
        build(RD,mid+1,r);
        pushup(t[o],t[LD],t[RD]);
    }
    void update(int o,int l,int r,int v){
        if(l<=t[o].l&&t[o].r<=r){t[o].add+=v;t[o].maxv+=v,t[o].minv+=v;return;}
        pushdown(t[o],t[LD],t[RD]);
        int mid=(t[o].l+t[o].r)>>1;
        if(mid>=l)update(LD,l,r,v);
        if(mid<r)update(RD,l,r,v);
        pushup(t[o],t[LD],t[RD]);
    }
    int querymax(int o,int l,int r){
        if(l<=t[o].l&&t[o].r<=r)return t[o].maxv;
        pushdown(t[o],t[LD],t[RD]);
        int ans=LLONG_MIN/2,mid=(t[o].l+t[o].r)>>1;
        if(mid>=l)ans=max(ans,querymax(LD,l,r));
        if(mid<r)ans=max(ans,querymax(RD,l,r));
        pushup(t[o],t[LD],t[RD]);
        return ans;
    }
    int querymin(int o,int l,int r){
        if(l<=t[o].l&&t[o].r<=r)return t[o].minv;
        pushdown(t[o],t[LD],t[RD]);
        int ans=LLONG_MAX/2,mid=(t[o].l+t[o].r)>>1;
        if(mid>=l)ans=min(ans,querymin(LD,l,r));
        if(mid<r)ans=min(ans,querymin(RD,l,r));
        pushup(t[o],t[LD],t[RD]);
        return ans;
    }
    int querysheng(int o,int l,int r){
        if(l<=t[o].l&&t[o].r<=r)return t[o].issheng;
        pushdown(t[o],t[LD],t[RD]);
        int mid=(t[o].l+t[o].r)>>1;
        if(r<=mid){
            int d=querysheng(LD,l,r);
            pushup(t[o],t[LD],t[RD]);
            return d;
        }
        if(l>mid){
            int d=querysheng(RD,l,r);;
            pushup(t[o],t[LD],t[RD]);
            return d;
        }
        int d1= querysheng(LD,l,r);
        int d2= querysheng(RD,l,r);
        pushup(t[o],t[LD],t[RD]);
        if(d1 and d2 and querymax(LD,l,r)< querymin(RD,l,r)){
            return 1;
        }
        return 0;
    }
    int queryjiang(int o,int l,int r){
        if(l<=t[o].l&&t[o].r<=r)return t[o].isjiang;
        pushdown(t[o],t[LD],t[RD]);
        int mid=(t[o].l+t[o].r)>>1;
        if(r<=mid){
            int d=queryjiang(LD,l,r);
            pushup(t[o],t[LD],t[RD]);
            return d;
        }
        if(l>mid){
            int d=queryjiang(RD,l,r);;
            pushup(t[o],t[LD],t[RD]);
            return d;
        }
        int d1= queryjiang(LD,l,r);
        int d2= queryjiang(RD,l,r);
        pushup(t[o],t[LD],t[RD]);
        if(d1 and d2 and querymin(LD,l,r)> querymax(RD,l,r)){
            return 1;
        }
        return 0;
    }

}A;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int q;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>A.a[i];
    A.build(1,1,n);
    cin>>q;
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            int x;
            cin>>x;
            A.update(1,l,r,x);
        }
        else if(op==2){
            cout<<(A.querymax(1,l,r)==A.querymin(1,l,r))<<endl;
        }
        else if(op==3){
            cout<<A.querysheng(1,l,r)<<endl;
        }
        else if(op==4) {
            cout<<A.queryjiang(1,l,r)<<endl;
        }
        else{
            int L=l+1,R=r-1;
            int ans=-1;
            int ma=A.querymax(1,l+1,r-1);
            while(L<=R){
                int mid=L+R>>1;
                if(A.querymax(1,l+1,mid)>=ma){
                    ans=mid;
                    R=mid-1;
                }
                else L=mid+1;
            }
            if(ans==-1){
                cout<<"0\n";
            }
            else{
                cout<<(A.querysheng(1,l,ans) and A.queryjiang(1,ans,r))<<endl;
            }
        }

    }
    return 0;
}