首页 > 其他分享 >2024.9.9

2024.9.9

时间：2024-09-09 22:04:00浏览次数：1  
标签：oo itn head int 2024.9 long num

DATE #:20240909

ITEM #:DOC

WEEK #:MONDAY

DAIL #:捌月初柒

TAGS 
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=2623834004&auto=0&height=66" width="330"></iframe>
< BGM = "沧浪行 南海 沧澜主题" >
< theme = oi-contest >
< [NULL] >
< [空] > 
< [空] >

醉后不知天在水,满船清梦压星河 -- 唐珙《题龙阳县青草湖》

A. Count

得益于这两天的可持久化数据结构复习，这道题做的并不难

//2024.9.9
//by white_ice
#include <bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define itn int
constexpr int oo=3000006;
int n,m,typ;
int ans,tot,top;
int nl[oo],nr[oo],le[oo],num[oo],st[oo],rt[oo];
struct sag{int ls,rs,sum;}s[oo*30];
struct nod{int v,nxt;}ed[oo];int head[oo],cnt;
void add(int a,int b){ed[++cnt]=(nod){b,head[a]},head[a]=cnt;}
void insert(int x,int& y,int l,int r,int pos){
    if (!y||y==x) y=++tot,s[y].sum=s[x].sum;
    s[y].sum++;
    if (l==r) return;
    int mid=l+r >> 1;
    if (pos<=mid)
        s[y].rs=(!s[y].rs)?s[x].rs:s[y].rs,insert(s[x].ls,s[y].ls,l,mid,pos);
    else s[y].ls=(!s[y].ls)?s[x].ls:s[y].ls,insert(s[x].rs,s[y].rs,mid+1,r,pos);
}
int query(int x,int y,int l,int r,int a,int b){
    if (a<=l&&r<=b) return s[y].sum-s[x].sum;
    int mid=l+r >> 1;
    if (b<=mid) return query(s[x].ls,s[y].ls,l,mid,a,b);
    if (a >mid) return query(s[x].rs,s[y].rs,mid+1,r,a,b);
    return query(s[x].ls,s[y].ls,l,mid,a,b)+query(s[x].rs,s[y].rs,mid+1,r,a,b);
}
main(void){
    //fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> typ;
    for (itn i=1;i<=n;i++) cin >> num[i];
    for (int i=1;i<=n;i++){
        while (top&&num[st[top]]<num[i])
            nr[st[top--]]=i;
        if (top) le[i]=st[top];
        st[++top]=i;
    }
    while (top) nr[st[top--]]=n+1;
    for (int i=1;i<=n;i++){
        while (top&&num[st[top]]<=num[i]) top--;
        if (top) nl[i]=st[top];
        st[++top]=i;
        if (nl[i]&&nl[i]==le[i])
            add(nr[i],nl[i]);
    }
    for (itn i=1;i<=n;i++){
        if (i>1) insert(rt[i-1],rt[i],1,n,i-1);
        for (itn j=head[i];j;j=ed[j].nxt)
            insert(rt[i-1],rt[i],1,n,ed[j].v);
    }
    for (int a,b,i=1;i<=m;i++){
        cin >> a >> b;
        a=(a+ans-1)%n+1,b=(b+ans-1)%n+1;
        if (a>b) swap(a,b);
        printf("%d\n",ans=query(rt[a-1],rt[b],1,n,a,b)),ans *= typ;
    }
    exit (0);
}

B. Abs

树链剖分，重要的是对线段树的应用，

如何在支持修改前提下求出区间绝对值和？

我们发现加上一个正整数，每个负数变号只有一次机会，所以我们建立两颗线段树，分别维护正数和负数

每次查找是否可能增加到正数，暴力修改单点即可

//2024.9.9
//by white_ice
#include<bits/stdc++.h>
// #include"../../../need.cpp"
using namespace std;
#define itn long long
#define int long long 
constexpr itn oo = 100010;
itn n,m; itn num[oo];
itn dis[oo],f[oo][21];
struct nod{int v,nxt;}st[oo<<1];int head[oo],cnt;
__inline void adds(itn a,itn b){st[++cnt]=(nod){b,head[a]};head[a]=cnt;}
inline namespace change{
    __inline void dfs(itn x,itn fa){
        dis[x]=dis[fa]+1; f[x][0]=fa;
        for(itn j=1;j<=20;j++)
            f[x][j]=f[f[x][j-1]][j-1];
        for(itn i=head[x];~i;i=st[i].nxt){
            itn v=st[i].v;
            if(v==fa) continue;
            dfs(v,x);
        }
    }
    __inline itn lca(itn x,itn y){
        if(dis[x]<dis[y]) swap(x,y);
        for(itn j=20;j>=0;j--){
            if(dis[f[x][j]]>=dis[y]){
                x=f[x][j];
            }
        }
        if(x==y) return x;
        for(itn j=20;j>=0;j--){
            if(f[x][j]!=f[y][j]){
                x=f[x][j];
                y=f[y][j];
            }
        }
        return f[x][0];
    }
    __inline void update(itn x,itn c,itn k){
        while(x!=c){num[x]+=k; x=f[x][0];}}
    __inline itn query(itn x,itn c){
        itn res=0;
        while(x!=c){
            res+=abs(num[x]);
            x=f[x][0];
        }
        return res;
    }
};
main(void){
    // fre();
    cin.tie(0)->sync_with_stdio(0);
	memset(head,-1,sizeof(head));
	cin >> n >> m;
	for(itn i=1;i<=n;i++) cin >> num[i];
	for(itn i=1;i<n;i++){
		itn x,y; cin >> x >> y;
		adds(x,y),adds(y,x);
	}
	dfs(1,0);
	while(m--){
		itn op,x,y,k;
		cin >> op >> x >> y;
		if(op==1){
			cin >> k; itn c=lca(x,y);
			update(x,c,k); update(y,c,k);
			num[c]+=k;
		}
        else{
			itn c=lca(x,y);
			cout << query(x,c)+query(y,c)+abs(num[c]) << '\n';
		}
	}	
    cout << flush;
	exit (0);
}
//2024.9.9
//by white_ice
#include<bits/stdc++.h>
// #include"../../../need.cpp"
using namespace std;
#define itn long long
#define int long long 
constexpr itn oo = 100010;
itn n,m; itn num[oo];
itn dis[oo],f[oo][21];
struct nod{int v,nxt;}st[oo<<1];int head[oo],cnt;
__inline void adds(itn a,itn b){st[++cnt]=(nod){b,head[a]};head[a]=cnt;}
inline namespace change{
    __inline void dfs(itn x,itn fa){
        dis[x]=dis[fa]+1; f[x][0]=fa;
        for(itn j=1;j<=20;j++)
            f[x][j]=f[f[x][j-1]][j-1];
        for(itn i=head[x];~i;i=st[i].nxt){
            itn v=st[i].v;
            if(v==fa) continue;
            dfs(v,x);
        }
    }
    __inline itn lca(itn x,itn y){
        if(dis[x]<dis[y]) swap(x,y);
        for(itn j=20;j>=0;j--){
            if(dis[f[x][j]]>=dis[y]){
                x=f[x][j];
            }
        }
        if(x==y) return x;
        for(itn j=20;j>=0;j--){
            if(f[x][j]!=f[y][j]){
                x=f[x][j];
                y=f[y][j];
            }
        }
        return f[x][0];
    }
    __inline void update(itn x,itn c,itn k){
        while(x!=c){num[x]+=k; x=f[x][0];}}
    __inline itn query(itn x,itn c){
        itn res=0;
        while(x!=c){
            res+=abs(num[x]);
            x=f[x][0];
        }
        return res;
    }
};
main(void){
    // fre();
    cin.tie(0)->sync_with_stdio(0);
	memset(head,-1,sizeof(head));
	cin >> n >> m;
	for(itn i=1;i<=n;i++) cin >> num[i];
	for(itn i=1;i<n;i++){
		itn x,y; cin >> x >> y;
		adds(x,y),adds(y,x);
	}
	dfs(1,0);
	while(m--){
		itn op,x,y,k;
		cin >> op >> x >> y;
		if(op==1){
			cin >> k; itn c=lca(x,y);
			update(x,c,k); update(y,c,k);
			num[c]+=k;
		}
        else{
			itn c=lca(x,y);
			cout << query(x,c)+query(y,c)+abs(num[c]) << '\n';
		}
	}	
    cout << flush;
	exit (0);
}
//2024.9.9
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long
constexpr int oo = 100005;
constexpr int inf = 1e16;
int n,m;int num[oo];
struct nod{int v,nxt;}st[oo<<1];int head[oo],cnt;
__inline void add(int u,int v){st[++cnt]=(nod){v,head[u]};head[u]=cnt;}
inline namespace treecut{
    int fat[oo],son[oo];
    int siz[oo],dis[oo];
    void dfs1(int x,int fa){
        dis[x] = dis[fat[x]=fa]+(siz[x]=1);
        for(int v,i=head[x];~i;i = st[i].nxt)
            if((v=st[i].v) != fa){
                dfs1(v,x);siz[x] += siz[v];
                if(siz[v]>siz[son[x]]) son[x] = v;
            }
    }
    int top[oo],new_num[oo],cnt_dfs;
    int dfn[oo];
    void dfs2(int x,int topx){
        top[x] = topx; dfn[x]=++cnt_dfs;
        new_num[cnt_dfs] = num[x];
        if(son[x]) dfs2(son[x],topx);
        for(int v,i = head[x];~i;i = st[i].nxt)
            if((v=st[i].v) != fat[x]&&v != son[x])
                dfs2(v,v);
    }
}
struct sumtree{
	int tree[oo<<2],laz[oo<<2];
    int siz[oo<<2];
	inline void push_up(int x){tree[x] = tree[x<<1]+tree[x<<1|1];siz[x] = siz[x<<1]+siz[x<<1|1];}
    void build(int x,int l,int r){
		if(l==r){
			tree[x] = new_num[l]>=0?new_num[l]:0;
			siz[x] = new_num[l]>=0?1:0;
			return void();
		}
		int mid = (l+r) >> 1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		push_up(x);
	}
    inline void addtag(int x,int p){laz[x] += p;tree[x] += siz[x]*p;}
	inline void push_down(int x){
		if(laz[x]){
			addtag(x<<1,laz[x]);
			addtag(x<<1|1,laz[x]);
			laz[x] = 0;
		}
	}
	void updata(int x,int l,int r,int nl,int nr,int val){
		if(nl==l&&nr==r){addtag(x,val);return void();}
		int mid = (l+r) >> 1;
		push_down(x);
		if(nr<=mid) updata(x<<1,l,mid,nl,nr,val);
		else if(nl>mid) updata(x<<1|1,mid+1,r,nl,nr,val);
		else updata(x<<1,l,mid,nl,mid,val),updata(x<<1|1,mid+1,r,mid+1,nr,val);
		push_up(x);
	}
	void modify(int x,int l,int r,int nl,int val){
		if(l==r){tree[x] = val,siz[x] = 1;return void();}
		int mid = (l+r) >> 1;
		push_down(x);
		if(nl<=mid) modify(x<<1,l,mid,nl,val);
		else modify(x<<1|1,mid+1,r,nl,val);
		push_up(x);
	}
	int query(int x,int l,int r,int nl,int nr){
		if(nl==l&&nr==r) return tree[x];
		int mid = (l+r) >> 1;
		push_down(x);
		int out;
		if(nr<=mid) out = query(x<<1,l,mid,nl,nr);
		else if(nl>mid) out = query(x<<1|1,mid+1,r,nl,nr);
		else out = query(x<<1,l,mid,nl,mid)+query(x<<1|1,mid+1,r,mid+1,nr);
		push_up(x);
		return out;
	}
}treesum;
struct maxtree{
    struct nods{
        int val,id;nods(){}
        nods(int v,int x):val(v),id(x){}
        inline nods operator +(const nods &b)const{
            if(val<b.val) return b;return *this;}
    };
	nods maxn[oo<<2];
	int tree[oo<<2],laz[oo<<2];int siz[oo<<2];
	inline void push_up(int x){
		tree[x] = tree[x<<1]+tree[x<<1|1];
		maxn[x] = maxn[x<<1]+maxn[x<<1|1];
		siz[x] = siz[x<<1]+siz[x<<1|1];
	}
    void build(int x,int l,int r){
		if(l==r){
			maxn[x] = nods(new_num[l]<0?new_num[l]:-inf,l);
			siz[x] = new_num[l]<0?1:0;
			tree[x] = new_num[l]<0?new_num[l]:0;return;
		}
		int mid = (l+r) >> 1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		push_up(x);
	}
	inline void push_down(int x){
		if(laz[x]){
			laz[x<<1] += laz[x];tree[x<<1] += siz[x<<1]*laz[x];maxn[x<<1].val += laz[x];
			laz[x<<1|1] += laz[x];tree[x<<1|1] += siz[x<<1|1]*laz[x];maxn[x<<1|1].val += laz[x];
			laz[x] = 0;
		}
	}
	void updata(int x,int l,int r,int nl,int nr,int val){
		if(nl==l&&nr==r){
			tree[x] += siz[x]*val;
			laz[x] += val;
			maxn[x].val += val;
			return;
		}
		int mid = (l+r) >> 1;
		push_down(x);
		if(nr<=mid) updata(x<<1,l,mid,nl,nr,val);
		else if(nl>mid) updata(x<<1|1,mid+1,r,nl,nr,val);
		else updata(x<<1,l,mid,nl,mid,val),updata(x<<1|1,mid+1,r,mid+1,nr,val);
		push_up(x);
	}
	void modify(int x,int l,int r,int nl){
		if(l==r){
			tree[x] = siz[x] = 0,maxn[x].val = -inf;return;
		}
		int mid = (l+r) >> 1;
		push_down(x);
		if(nl<=mid) modify(x<<1,l,mid,nl);
		else modify(x<<1|1,mid+1,r,nl);
		push_up(x);
	}
	nods querymx(int x,int l,int r,int nl,int nr){
		if(nl==l&&nr==r) return maxn[x];
		int mid = (l+r) >> 1;
		push_down(x);
		nods out;
		if(nr<=mid) out = querymx(x<<1,l,mid,nl,nr);
		else if(nl>mid) out = querymx(x<<1|1,mid+1,r,nl,nr);
		else out = querymx(x<<1,l,mid,nl,mid)+querymx(x<<1|1,mid+1,r,mid+1,nr);
		push_up(x);
		return out;
	}
	int querysum(int x,int l,int r,int nl,int nr){
		if(nl==l&&nr==r) return tree[x];
		int mid = (l+r) >> 1;
		push_down(x);
		int out;
		if(nr<=mid) out = querysum(x<<1,l,mid,nl,nr);
		else if(nl>mid) out = querysum(x<<1|1,mid+1,r,nl,nr);
		else out = querysum(x<<1,l,mid,nl,mid)+querysum(x<<1|1,mid+1,r,mid+1,nr);
		push_up(x);
		return out;
	}
	void add(int l,int r,int val){
		if(r<l) return;
		nods out = querymx(1,1,n,l,r);
		if(out.val+val>=0){
			modify(1,1,n,out.id);
			treesum.modify(1,1,n,out.id,out.val+val);
			add(l,out.id-1,val);
			add(out.id+1,r,val);
		}
		else updata(1,1,n,l,r,val);
	}
}treemax;
main(void){
    //fre();
	memset(head,-1,sizeof(head));
	cin >> n >> m;
	for(int i = 1;i<=n;++i) cin >> num[i];
	for(int x,y,i = 1;i<n;++i){
		cin >> x >> y;
        add(x,y),add(y,x);
    }
    function<void(int,int,int)>plusit=[&](int u,int v,itn d){
        while(top[u]!=top[v]){
            if(dis[top[u]]<dis[top[v]]) swap(u,v);
            treesum.updata(1,1,n,dfn[top[u]],dfn[u],d);
            treemax.add(dfn[top[u]],dfn[u],d);
            u = fat[top[u]];
        }
        if(dis[u]<dis[v]) swap(u,v);
        treesum.updata(1,1,n,dfn[v],dfn[u],d);
        treemax.add(dfn[v],dfn[u],d);
    };
    function<int(int,int)>findit=[&](int u,int v){
        int out = 0;
        while(top[u]!=top[v]){
            if(dis[top[u]]<dis[top[v]]) swap(u,v);
            out += - treemax.querysum(1,1,n,dfn[top[u]],dfn[u])+treesum.query(1,1,n,dfn[top[u]],dfn[u]);
            u = fat[top[u]];
        }
        if(dis[u]<dis[v]) swap(u,v);
        return out - treemax.querysum(1,1,n,dfn[v],dfn[u])+treesum.query(1,1,n,dfn[v],dfn[u]);
    };
	dfs1(1,0),dfs2(1,1);
	treemax.build(1,1,n);
	treesum.build(1,1,n);
	int op,u,v,d;
	while(m--){
		cin >> op >> u >> v;
		if(op==1) cin >> d,plusit(u,v,d);
		else cout << findit(u,v) << '\n';
	}
    exit (0);
}

C. 普通计算姬

注意到询问的区间是连续的，我们可以使用分块维护，两边使用树状数组维护

其中一个重要思路&技巧:记f[i][j]为从根到i中出现在第j块中节点的个数

//2024.9.9
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define itn long long  
#define int long long
constexpr int oo = 100005;
int n,m;int val[oo];int f[oo],wei[oo];
struct nod{int v,nxt;}st[oo];int head[oo],cnt;
__inline void add(itn a,int b){st[++cnt]=(nod){b,head[a]};head[a] = cnt;}
itn root;
main(void){
    //fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++) cin >> val[i];
    for(itn a,b,i=1;i<=n;i++){
        cin >> a >> b;
        if (a==0)root = b;
        else add(a,b),add(b,a);
    }
    function<void(int,int)>dfs=[&](itn x,int fa){
        wei[x] = val[x];
        for (itn i=head[x];~i;i=st[i].nxt){
            int v = st[i].v;
            if (v==fa) continue;
            f[v] = x;
            dfs(v,x);
            wei[x]+=wei[v];
        }
    };
    dfs(root,0);
    int op,l,r;
    while (m--){
        cin >> op >> l >> r;
        if (op == 1){
            int p = r-val[l];
            while (l!=root){
                wei[l] += p;
                l = f[l];
            }
            //wei[root] += p;
        }
        else {
            int out = 0;
            for (itn i=l;i<=r;i++)out += wei[i];
            cout << out << '\n';
        }
    }
    exit(0);
}

D. Road

打开了dijkstra的新思路：在求出最短路的同时，会对最短路距离进行排序

我们便可依靠此多次求最短路，使用数据结构，枚举通过的边和途径点的个数

//2024.9.9
//by white_ice
//#1484. 【BZOJ2750】Road
#include<bits/stdc++.h>
//#include"../../need.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr int oo = 5003;
constexpr int mod = 1000000007;
int n,m;int a[oo],b[oo],out[oo];
struct nod{int v,nxt,w,id;}st[oo];int head[oo],top;
__inline void add(int u,int v,int w,int id){st[++top]=(nod){v,head[u],w,id};head[u]=top;}
int dis[oo],cnt,c[oo];bool vis[oo];
__inline void dijkstra(int s){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> >q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f3f3f,sizeof(dis));
    dis[s]=0; q.push(make_pair(0,s));
    cnt=0;
    while(!q.empty()){
        int x=q.top().second; q.pop();
        if(vis[x]) continue; vis[x]=1; c[++cnt]=x;
        for(int k=head[x];k;k=st[k].nxt)
            if(dis[x]+st[k].w<dis[st[k].v]) {
                dis[st[k].v]=st[k].w+dis[x];
                q.push(make_pair(dis[st[k].v],st[k].v));
            }
    }
    memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
    for(itn i=1;i<=cnt;i++) b[c[i]]=1;  a[s]=1;
    for(itn i=1;i<=cnt;i++)
        for(int k=head[c[i]];k;k=st[k].nxt)
            if(dis[c[i]]+st[k].w==dis[st[k].v])
                (a[st[k].v]+=a[c[i]])%=mod;
    for(int i=cnt;i;i--)
        for(int k=head[c[i]];k;k=st[k].nxt)
            if(dis[c[i]]+st[k].w==dis[st[k].v])
                (b[c[i]]+=b[st[k].v])%=mod;
    for(itn i=1;i<=n;i++)
        for(int k=head[i];k;k=st[k].nxt)
            if(dis[i]+st[k].w==dis[st[k].v])
                (out[st[k].id]+=a[i]*b[st[k].v])%=mod;
}
main(void){
    //fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int u,v,w,i=1;i<=m;i++){
        cin >> u >> v >> w;
        add(u,v,w,i);
    }
    for(int i=1;i<=n;i++)  dijkstra(i);
    copy(out+1,out+m+1,ostream_iterator<int>(cout,"\n"));
    exit(0);
}

写了一套初赛题

复习了数据结构部分，树状数组，线段树，主席树，并查集（带修，带权，可合并

标签：oo,itn,head,int,2024.9,long,num
From： https://www.cnblogs.com/white-ice/p/18405434

相关文章

  • 2024.9.9报告
    正式开学第一天今天上午上了《算法与数据结构》的第一节课，刘丹老师先是给我们讲了这个课程重要性，然后讲了一些数据结构的概念。紧接着上了陈晶晶的《马克思主义原理》，讲了一些事实作为引子，下节课准备讲课本上的内容。下午，验收暑期的Java学习成果，进行Java的测验。这是我在课上......
  • 2024.9.9杂记
    P1088[NOIP2004普及组]火星人题目描述人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一......
  • 关于我2020年7月至今(2024.9)的“炒股”经历和感受
    声明：我远不是一个成熟的投资者(这个名词太大了，我那三瓜两枣似乎完全配不上投资者这三个字，或者“小小散”更加贴切)。本文不构成任何入(股)市的引导或者买卖股票的建议。  “炒股”这个词，相信绝大多数人看来都-是一个贬义词，它背后似乎有：“赌博”、“亏钱”、“频繁的买卖(......
  • 2024.9.8 CSP-S 模拟赛
    T1现在你站在坐标轴的一个整点上，给你\(n\)种技能，每个技能是整数对\((p,c)\)的形式，学会它需要花费\(c\)，但是学会了可以无限用。用的意思是可以向左或向右\(p\)个单位长度。求最小的学技能开销，使得你可以访问到坐标轴的所有整点。\(n\leq10^5,x\leq10^9\)随便玩了一下......
  • 2024.9。7
    DATE#:20240907ITEM#:DOCWEEK#:SATURDSYDAIL#:捌月初伍TAGS<BGM="深渊--易耀申"><theme=oi-contest><[NULL]><[空]><[空]>只有怪物才有资格被称为好人写了一套质量真的真的很高的模拟赛题T1A.数正方体时间限制:1s 内存限制:1024......
  • 2024.9
    9.6来到了北京大学，总之预科生活开始了！宿舍条件很差，我阳台呢？室友是zphqiuly云浅。爸妈陪我来的，帮我买了点生活用品后就走了。哎呀为啥打出上一句话有一种莫名的心悸，果然以后还是要独自面对生活吗。会赢的，一定。吃完晚饭（好吧我没吃）jt和cjz来我宿舍玩，可爱捏。然后和z......
  • 2024.9.6 近期练习
    P5044[IOI2018]meetings会议对于\(h_i\le20\)的数据，我们每个点维护单调栈，其代价为\(x\)的时候，取的位置是一个区间。很显然已经有一个莫队算法，支持区间加，区间查询即可。然而不优。其实单调栈与笛卡尔树是相似的，考虑建出笛卡尔树。我们假设就对\([l,r]\)dp，那么取出最......
  • [2024.9.6鲜花] 去码头整点热干面
    [2024.9.6鲜花]去码头整点热干面前情提要：写了几版了，都感觉太消沉了，于是写个奇怪的（？）写在开学前的鲜花，也许什么都聊，但主要聊这一个月来的破事吧相比于这段时间来说，\(NOI\)刚结束的那段时间，也就是七月底八月初的样子，反正是我状态最好的时候，各种意义上的状态我试图找出原因，......
  • 2024.9.6 模拟赛
    A对于一个子矩阵\((x_1,y_1),(x_2,y_2)\)，其元素和为\(\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}S_i\cdotS_j=(\sum_{i=x_1}^{x_2}S_i)(\sum_{j=y_1}^{y_2}S_j)\)，\(O(n^2)\)枚举一下\(S\)的所有子区间的和放进一个桶里再检验一下即可。即对于一个子区间和为\(S_1\)，需要累加和......
  • 2024.9.6 CF1307 模拟赛记录
    A：各捆干草间互相独立，所以优先移动距\(1\)近的。点击查看代码#include<bits/stdc++.h>#defineintlonglong#definepsbkpush_back#definefstfirst#definescdsecond#defineumapunordered_map#definepqueuepriority_queue#definevcvector#defineendl'\n'......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99