4
25
2015
1

【最近的一些题】P2

啊啊啊学校不能上isprogrammer不开心

【3816】不说了都懂的

【3922】每个公差建棵线段树

#include <cstdio>
#include <algorithm>
#include <cmath>
 
#define ls (x<<1)
#define rs (x<<1^1)
#define L (tree[i][x].l)
#define R (tree[i][x].r)
#define M (tree[i][x].m)
#define D (tree[i][x].d)
#define mid (tree[i][x].Mid)
#define Tl tree[i][ls]
#define Tr tree[i][rs]
#define K (20)
using namespace std;
 
struct node{int l,r,m,d,Mid;}tree[K+5][300005];
int a[100005],b,c,d,e,f[K+5][100005],F[K+5][100005],g,h,i,j,k,l,m,n;
void ask(int x,int l,int r){
    if(l==L&&r==R){
        h=max(h,M);
        return;
    }
    if(r<=mid)ask(ls,l,r);
    else if(l>mid)ask(rs,l,r);
    else ask(ls,l,mid),ask(rs,mid+1,r);
}
void add(int x){
    if(L==R){
        D=M=a[F[i][L]];
        return;
    }
    if(f[i][c]<=mid)add(ls);else add(rs);
    M=max(Tl.m,Tr.m);
}
void build(int x,int l,int r){
    L=l;R=r;mid=(l+r)>>1;
    if(l==r){
        D=M=a[F[i][l]];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    M=max(Tl.m,Tr.m);
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    k=min((int)sqrt(n),K);
    for(l=1;l<=k;l++){
        d=0;
        for(i=1;i<=l;i++)
        for(j=i;j<=n;j+=l){
            f[l][j]=++d;
            F[l][d]=j;
        }
    }
    for(i=1;i<=k;i++)build(1,1,n);
    scanf("%d",&m);
    for(;m;m--){
        scanf("%d",&b);
        if(b==0){
            scanf("%d%d",&c,&d);
            a[c]+=d;
            for(i=1;i<=k;i++)add(1);
        }
        else{
            scanf("%d%d",&c,&d);h=-2147483647;
            if(d<k){
                i=d;
                ask(1,f[i][c],f[i][(n-c)/d*d+c]);
            }
            else{
                for(i=c;i<=n;i+=d)h=max(h,a[i]);
            }
            printf("%d\n",h);
        }
    }
    return 0;
}
 
【2243】&【2325】树链剖分+线段树
怎么维护yy一下差不多了
#include <cstdio>
#include <algorithm>
#define MN 400005
#define L ll[x]
#define R rr[x]
#define M mid[x]
#define F fu[x]
#define S tr[x].s
#define SL tr[x].sl
#define SR tr[x].sr
#define ls (x<<1)
#define rs (x<<1^1)
#define Ls tr[ls]
#define Rs tr[rs]
using namespace std;
struct node{int s,sl,sr;}tr[MN];
int ll[MN],rr[MN],mid[MN],fu[MN];
int a[MN],b,c,d,e,f,g,h,i,j,k,l,m,n,tot;
int size[MN],deep[MN],fa[MN],son[MN],T[MN],TT[MN],top[MN];
int way[MN],next[MN],last[MN];
void dfs1(int x){
	size[x]=1;deep[x]=deep[fa[x]]+1;
	for(int i=last[x];i;i=next[i]){
		int s=way[i];if(s==fa[x])continue;
		fa[s]=x;dfs1(s);size[x]+=size[s];
		if(size[s]>size[son[x]])son[x]=s;
	}
}
void dfs2(int x,int Top){
	T[x]=++tot;TT[tot]=x;top[x]=Top;
	if(son[x])dfs2(son[x],Top);
	for(int i=last[x];i;i=next[i]){
		int s=way[i];
		if(s!=fa[x]&&s!=son[x])dfs2(s,s);
	}
}
inline node turn(node a){return (node){a.s,a.sr,a.sl};}
inline node merge(node a,node b){
	node k;
	k.s=a.s+b.s-(a.sr==b.sl);
	k.sl=a.sl;k.sr=b.sr;
	return k;
}
inline void up(int x){
	S=Ls.s+Rs.s-(Ls.sr==Rs.sl);
	SL=Ls.sl;SR=Rs.sr;
}
inline void down(int x){
	if(!F)return;
	fu[ls]=fu[rs]=Ls.sl=Rs.sl=Ls.sr=Rs.sr=F;
	Ls.s=Rs.s=1;
	F=0;
}
void build(int x,int l,int r){
	L=l;R=r;M=(l+r)>>1;
	if(l==r){
		S=1;SL=SR=a[TT[L]];
		return;
	}
	build(ls,l,M);build(rs,M+1,r);
	up(x);
}
void change(int x,int l,int r){
	if(L==l&&R==r){
		S=1;SL=SR=F=d;
		return;
	}
	down(x);
	if(r<=M)change(ls,l,r);
	else if(l>M)change(rs,l,r);
	else change(ls,l,M),change(rs,M+1,r);
	up(x);
}
node ask(int x,int l,int r){
	if(L==l&&R==r)return tr[x];
	node ans;
	down(x);
	if(r<=M)ans=ask(ls,l,r);
	else if(l>M)ans=ask(rs,l,r);
	else ans=merge(ask(ls,l,M),ask(rs,M+1,r));
	up(x);
	return ans;
}
inline void make(int a,int b){
	way[++tot]=b;next[tot]=last[a];last[a]=tot;
	way[++tot]=a;next[tot]=last[b];last[b]=tot;
}
inline int in(){
	int x=0,ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)a[i]=in();
	for(i=1;i<n;i++){
		b=in();c=in();
		make(b,c);
	}
	dfs1(1);
	tot=0;dfs2(1,1);
	build(1,1,n);
	for(;m;m--){
		char ch;for(ch=getchar();ch!='C'&&ch!='Q';ch=getchar());
		if(ch=='C'){
			int p,q;
			p=in();q=in();d=in();
			while(top[p]!=top[q]){
				if(deep[top[p]]<deep[top[q]])swap(p,q);
				change(1,T[top[p]],T[p]);
				p=fa[top[p]];
			}
			if(deep[p]<deep[q])swap(p,q);
			change(1,T[q],T[p]);
		}
		else{
			int p,q;
			p=in();q=in();
			node P,Q;P=Q=(node){0,0,0};
			while(top[p]!=top[q]){
				if(deep[top[p]]<deep[top[q]]){swap(p,q);swap(P,Q);}
				P=merge(ask(1,T[top[p]],T[p]),P);
				p=fa[top[p]];
			}
			if(deep[p]<deep[q]){swap(p,q);swap(P,Q);}
			P=merge(ask(1,T[q],T[p]),P);
			P=merge(turn(P),Q);
			printf("%d\n",P.s);
		}
	}
	return 0;
}
#include <cstdio>
#include <algorithm>
#define MN 200005
#define inf 10000000
#define X tree[x]
#define L ll[x]
#define R rr[x]
#define M mid[x]
#define A1 tree[x].a1
#define A2 tree[x].a2
#define A3 tree[x].a3
#define A4 tree[x].a4
#define B1 tree[x].b1
#define B2 tree[x].b2
#define B3 tree[x].b3
#define B4 tree[x].b4
#define ls (x<<1)
#define rs (x<<1^1)
#define Ls tree[ls]
#define Rs tree[rs]
//L,R,M
//A1,A2,A3,A4,B1,B2,B3,B4
//左上到右上,左上到右下,左下到右上,左下到右下
using namespace std;

struct node{int a1,a2,a3,a4,b1,b2,b3,b4;}tree[MN];
int ll[MN],rr[MN],mid[MN];
int a[MN][2],b,c,d,e,f,g,h,i,j,k,l,m,n,tot;
int size[MN],deep[MN],fa[MN],son[MN],T[MN],TT[MN],top[MN];
int way[MN],next[MN],last[MN];
char s[5];
void dfs1(int x){
	size[x]=1;deep[x]=deep[fa[x]]+1;
	for(int i=last[x];i;i=next[i]){
		int s=way[i];if(s==fa[x])continue;
		fa[s]=x;dfs1(s);size[x]+=size[s];
		if(size[s]>size[son[x]])son[x]=s;
	}
}
void dfs2(int x,int Top){
	T[x]=++tot;TT[tot]=x;top[x]=Top;
	if(son[x])dfs2(son[x],Top);
	for(int i=last[x];i;i=next[i]){
		int s=way[i];
		if(s!=fa[x]&&s!=son[x])dfs2(s,s);
	}
}
inline node turn(node a){
	return (node){a.a1,a.a3,a.a2,a.a4,a.b3,a.b4,a.b1,a.b2};
}
inline node merge(node a,node b){
	node k;
	k.a1=max(max(a.a1+b.a1,a.a2+b.a3),-inf);
	k.a2=max(max(a.a1+b.a2,a.a2+b.a4),-inf);
	k.a3=max(max(a.a3+b.a1,a.a4+b.a3),-inf);
	k.a4=max(max(a.a3+b.a2,a.a4+b.a4),-inf);
	k.b1=max(max(a.a1+b.b1,a.a2+b.b2),a.b1);
	k.b2=max(max(a.a3+b.b1,a.a4+b.b2),a.b2);
	k.b3=max(max(a.b3+b.a1,a.b4+b.a3),b.b3);
	k.b4=max(max(a.b3+b.a2,a.b4+b.a4),b.b4);
	return k;
}
void build(int x,int l,int r){
	L=l;R=r;M=(l+r)>>1;
	if(l==r){
		//a[TT[l]][0-1];
		A1=A2=A3=A4=B1=B2=B3=B4=-inf;
		if(a[TT[L]][0]>0)A1=B1=B3=1;
		if(a[TT[L]][1]>0)A4=B2=B4=1;
		if(a[TT[L]][0]>0&&a[TT[L]][1]>0)A2=A3=B1=B2=B3=B4=2;
		return;
	}
	build(ls,l,M);
	build(rs,M+1,r);
	X=merge(Ls,Rs);
}
void change(int x){
	if(L==R){
		A1=A2=A3=A4=B1=B2=B3=B4=-inf;
		if(a[TT[L]][0]>0)A1=B1=B3=1;
		if(a[TT[L]][1]>0)A4=B2=B4=1;
		if(a[TT[L]][0]>0&&a[TT[L]][1]>0)A2=A3=B1=B2=B3=B4=2;
		return;
	}
	if(T[i]<=M)change(ls);
	else if(T[i]>M)change(rs);
	X=merge(Ls,Rs);
}
node ask(int x,int l,int r){
	if(L==l&&R==r){
		return tree[x];
	}
	node ans;
	if(r<=M)ans=ask(ls,l,r);
	else if(l>M)ans=ask(rs,l,r);
	else ans=merge(ask(ls,l,M),ask(rs,M+1,r));
	X=merge(Ls,Rs);
	return ans;
}
inline void make(int a,int b){
	way[++tot]=b;next[tot]=last[a];last[a]=tot;
	way[++tot]=a;next[tot]=last[b];last[b]=tot;
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++){
		scanf("%d%d",&b,&c);
		make(b,c);
	}
	for(i=1;i<=n;i++){
		scanf("%s",&s);
		if(s[0]=='.')a[i][0]=1;else a[i][0]=-inf;
		if(s[1]=='.')a[i][1]=1;else a[i][1]=-inf;
	}
	dfs1(1);
	tot=0;dfs2(1,1);
	build(1,1,n);
	for(;m;m--){
		char ch;
		for(ch=getchar();ch!='C'&&ch!='Q';ch=getchar());
		if(ch=='C'){
			scanf("%d",&i);scanf("%s",s);
			if(s[0]=='.')a[i][0]=1;else a[i][0]=-inf;
			if(s[1]=='.')a[i][1]=1;else a[i][1]=-inf;
			change(1);
		}
		else{
			int p,q;
			scanf("%d%d",&p,&q);
			if(a[p][0]<0&&a[p][1]<0){printf("0\n");continue;}
			node P,Q;P=Q=(node){0,0,0,0,0,0,0,0};g=0;
			while(top[p]!=top[q]){
				if(deep[top[p]]<deep[top[q]]){swap(p,q);swap(P,Q);g++;}
				P=merge(ask(1,T[top[p]],T[p]),P);
				p=fa[top[p]];
			}
			if(deep[p]<deep[q]){swap(p,q);swap(P,Q);g++;}
			P=merge(ask(1,T[q],T[p]),P);
			P=merge(turn(P),Q);
			if(g&1)printf("%d\n",max(P.b3,P.b4));
			else printf("%d\n",max(P.b1,P.b2));
		}
	}
	return 0;
}
【3969】二分+贪心
很水对吧那我不说了
网上找不到题解那我代码先不发了
(ZJOI2014D1讲课内容
【3931】一眼的水题对吧不说了
/*--------------------------------dinic-----------------------------------------*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
#define maxlongint 214748233333333333
#define maxn 4005
#define maxm 2000005
#define id(x,y) ((x)+(y)*n)
using namespace std;
long long Ans;
long long a,b,c,d,e,g,h,i,j,k,l,m,n,Dis[maxn],Flag,S,T,Tot,r,tot;
long long Way[maxm],Last[maxn],Next[maxm],Cost[maxm];
long long way[maxm],last[maxn],next[maxm],cost[maxm],dis[maxn],dl[maxn],vis[maxn];
long long min(long long a,long long b){if (a<b)return a;return b;}
void Spfa(){
	long long Now,Head,Tail,Dl[maxn],Flag[maxn];
	memset(Dis,0x7f,sizeof(Dis));
	memset(Flag,0,sizeof(Flag));
	Head=1;Tail=1;Dis[S]=0;Dl[1]=S;
	for (;Head<=Tail;++Head){
		Now=Dl[Head];
		Flag[Now]=1;
		for (long long i=Last[Now];i;i=Next[i])
		if ((Cost[i])&&(Dis[Way[i]]>Dis[Now]+1)){
			Dis[Way[i]]=Dis[Now]+1;
			if (!Flag[Way[i]]){Dl[++Tail]=Way[i];Flag[Way[i]]=1;}
		}
	}
}
void spfa(){
	memset(dis,0x7f,sizeof(dis));
	dl[l=r=1]=1;vis[1]=1;dis[1]=0;
	for(;l<=r;l++){
		long long s=dl[l];
		for(long long i=last[s];i;i=next[i])
		if(dis[s]+cost[i]<dis[way[i]]){
			dis[way[i]]=dis[s]+cost[i];
			if(!vis[way[i]]){vis[way[i]]=1;dl[++r]=way[i];}
		}
		vis[s]=0;
	}
}
long long Dfs(long long x,long long Flow){
	if (Flow==0)return 0;
	if (x==T){Flag=1;return Flow;}
	long long Sum=0,Tmp=0;
	for (long long i=Last[x];i;i=Next[i])
	if (Dis[Way[i]]==Dis[x]+1){
		Tmp=Dfs(Way[i],min(Flow-Sum,Cost[i]));
		Sum+=Tmp;
		Cost[i]-=Tmp;
		Cost[i^1]+=Tmp;
		if (Sum>=Flow)return Flow;
	}
	return Sum;
}
inline void make(long long a,long long b,long long c){
	way[++tot]=b;next[tot]=last[a];last[a]=tot;cost[tot]=c;
	way[++tot]=a;next[tot]=last[b];last[b]=tot;cost[tot]=c;
}
inline void Make(long long a,long long b,long long c){
	Way[++Tot]=b;Next[Tot]=Last[a];Last[a]=Tot;Cost[Tot]=c;
	Way[++Tot]=a;Next[Tot]=Last[b];Last[b]=Tot;Cost[Tot]=0;
}
int main(){
	Tot=1;tot=1;
	scanf("%d%d",&n,&m);S=2*n+1;T=S+1;
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		make(a,b,c);
	}
	spfa();
	for(i=2;i<=tot;i++){
		if(dis[way[i]]-dis[way[i^1]]==cost[i])
		{Make(id(way[i^1],1),id(way[i],0),maxlongint);
		}
	}
	for(i=1;i<=n;i++){
		scanf("%d",&a);
		Make(id(i,0),id(i,1),a); 
	}
	Make(S,id(1,1),maxlongint);
	Make(id(n,0),T,maxlongint);
	Flag=1;Ans=0;
	for (;Flag;){
		Spfa();
		Flag=0;
		Ans+=Dfs(S,maxlongint);
	}
	printf("%lld\n",Ans);
	return 0;
}

【3916】在左边在右边在中间,然后匹配

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a,b,c,d,e,f,g,h,i,j,k,l,m,n;
char s[2001000];
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	m=n/2;
	if(!(n&1)){
		printf("NOT POSSIBLE");
		return 0;
	}

	for(i=1;i<=m&&s[i+m]==s[i];i++);
	for(;i<=m&&s[i+m+1]==s[i];i++);
	if(i>m)a=1;

	for(i=0;i<m&&s[n-i]==s[n-i-m];i++);
	for(;i<m&&s[n-i]==s[n-i-m-1];i++);
	if(i>=m)b=1;

	if(a&b){
		for(i=1;i<=m&&s[i]==s[i+m+1];i++);
		if(i<=m)printf("NOT UNIQUE");
		else for(i=1;i<=m;i++)putchar(s[i]);
	}
	else if(a)for(i=1;i<=m;i++)putchar(s[i]);
	else if(b)for(i=m+2;i<=n;i++)putchar(s[i]);
	else printf("NOT POSSIBLE");
	return 0;
}

【3943】解表示成生成树然后就是最大生成树了

#include <cstdio>
#include <algorithm>
using namespace std;
int a[2005],b,c,d,e,f,g,i,j,k,l,m,n,dis[2005],vis[2005];
long long h;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	vis[1]=1;
	for(i=1;i<=n;i++)dis[i]=a[1]^a[i];
	for(l=2;l<=n;l++){
		for(j=1,k=0;j<=n;j++)if(!vis[j]&&dis[j]>dis[k])k=j;
		h=h+dis[k];
		vis[k]=1;
		for(j=1;j<=n;j++)dis[j]=max(dis[j],a[k]^a[j]);
	}
	printf("%lld",h);
	return 0;
}

【3885】找到包含H的子矩阵然后把边界切掉

#include <cstdio>
#include <algorithm>
using namespace std;
int ans,N,M,a,b,c,d,e,f[1005][1005],g,h[1005][1005],i,j,k,l[1005][1005],m,n,r[1005][1005],A[1005][1005];
int calc(int a,int b,int c,int d){
	return A[c][d]+A[a][b]-A[c][b]-A[a][d];
}

int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&a,&b);a++;b++;
		N=max(N,a);M=max(M,b);
		char ch;
		for(ch=getchar();ch!='H'&&ch!='G';ch=getchar());
		f[a][b]=(ch=='G');A[a][b]=(ch=='H');
	}
	for(i=1;i<=N;i++)
	for(j=1;j<=M;j++)
	A[i][j]=A[i][j]+A[i][j-1]+A[i-1][j]-A[i-1][j-1];
	for(j=1;j<=M;j++)
	for(i=1,k=0;i<=N;i++){h[i][j]=k;if(f[i][j])k=i;}
	for(i=1;i<=N;i++){
		for(j=1,k=0;j<=M;j++){l[i][j]=k;if(f[i][j])k=j;}
		for(j=M,k=M+1;j;j--){r[i][j]=k;if(f[i][j])k=j;}
	}
	for(i=2;i<=N;i++)
	for(j=1;j<=M;j++)if(!f[i][j]){
		l[i][j]=max(l[i][j],l[i-1][j]);
		r[i][j]=min(r[i][j],r[i-1][j]);
	}
	
	//for(i=1;i<=N;i++){for(j=1;j<=N;j++)printf("%d ",l[i][j]);printf("\n");}
	//for(i=1;i<=N;i++){for(j=1;j<=N;j++)printf("%d ",r[i][j]);printf("\n");}
	for(i=1;i<=N;i++)
	for(j=1;j<=M;j++)if(!f[i][j]){
		if(i==9&&j==4){
			a=0;
		}
		int X1=h[i][j],Y1=l[i][j],X2=i,Y2=r[i][j]-1,L,R,mid;
		g=calc(X1,Y1,X2,Y2);
		if(g<ans||!g)continue;
		if(g>ans){ans=g;d=1<<30;}
		for(L=X1,R=X2-1,mid=(L+R+1)/2;L<R;mid=(L+R+1)/2){
			if(calc(X1,Y1,mid,Y2))R=mid-1;
			else L=mid;
		}
		X1=L;
		for(L=Y1,R=Y2-1,mid=(L+R+1)/2;L<R;mid=(L+R+1)/2){
			if(calc(X1,Y1,X2,mid))R=mid-1;
			else L=mid;
		}
		Y1=L;
		for(L=Y1+1,R=Y2,mid=(L+R)/2;L<R;mid=(L+R)/2){
			if(calc(X1,mid,X2,Y2))L=mid+1;
			else R=mid;
		}
		Y2=L;
		d=min(d,(X2-X1-1)*(Y2-Y1-1));
	}
	printf("%d\n%d\n",ans,d);
	return 0;
}

啊啊啊怎么只有那么点题不能浪了

Category: BZOJ | Tags: | Read Count: 696
jnanabhumiap.in 说:
2024年1月22日 14:41

JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who are passionate about providing engaging content that is accurate, interesting, and worthy to read. We are more like a web community where you can find different information, resources, and topics on day-to-day incidents or news.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com