| [POI2015]Łasuchy |
一看以为是sb题 简单来说就是每个人获得热量要尽量多 不能找别人
首先这道题好像我自己找不到NIE的情况
很容易想到一个优化 如果一个数/2>另一个数 那么一定选这个数
然后我想着其他的话就随便分配一个 然后会得出下一个 其实这样做是错的 因为你选完之后不知道下一个会不会是来降低我当前选的那一个的热量使得我当前的原来最优变成不是最优
然后这样子 怎么办呢？？？ 废话 膜题解
膜拜Claris 我们既然不知道下一个会不会来降低热量 不妨把每个食物的状态都定下来 让它们去dp下一个合法的状态
定义F[i][0-3]表示当前食物 0是两边都不选它 1是左边选 2是右边选 3是都选
那么的话而且保证已经解决i-1个 记录前驱的状态是什么
但是有一个细节 就是1和N的处理 我是把1再插后面 枚举食物1的状态 如果最后面的1还能维持原来的状态很明显合法
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define Maxn 1000010 using namespace std; int F[Maxn][4]; int N,C[Maxn]; int ans[Maxn]; void Do(int last) { for(int i=N-1;i>=1;i--) { if(last==1) ans[i-1]=i; else if(last==2) ans[i]=i; else if(last==3) ans[i-1]=ans[i]=i; last=F[i][last]; } for(int i=1;i<N-1;i++) printf("%d ",ans[i]); printf("%d ",ans[N-1]); } void DP() { for(int i=2;i<=N;i++) { if((F[i-1][2]!=-1)&&(C[i-1]>=C[i])) F[i][0]=2; if((F[i-1][3]!=-1)&&(C[i-1]>=(C[i]*2))) F[i][0]=3; if((F[i-1][0]!=-1)&&(C[i-1]<=C[i])) F[i][1]=0; if((F[i-1][1]!=-1)&&(C[i-1]<=(C[i]*2))) F[i][1]=1; if((F[i-1][2]!=-1)&&((C[i-1]*2)>=C[i])) F[i][2]=2; if((F[i-1][3]!=-1)&&(C[i-1]>=C[i])) F[i][2]=3; if((F[i-1][0]!=-1)&&((C[i-1]*2)<=C[i])) F[i][3]=0; if((F[i-1][1]!=-1)&&(C[i-1]<=C[i])) F[i][3]=1; } } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d",&C[i]); N++; C[N]=C[1]; memset(F,-1,sizeof(F)); F[1][3]=1; DP(); if(F[N][3]!=-1){ans[1]=1; ans[N-1]=1; Do(F[N][3]); return 0;} memset(F,-1,sizeof(F)); F[1][1]=1; DP(); if(F[N][1]!=-1){ans[1]=2; ans[N-1]=1; Do(F[N][1]); return 0;} memset(F,-1,sizeof(F)); F[1][2]=1; DP(); if(F[N][2]!=-1){ans[1]=1; ans[N-1]=N; Do(F[N][2]); return 0;} memset(F,-1,sizeof(F)); F[1][0]=1; DP(); if(F[N][0]!=-1){ans[1]=2; ans[N-1]=N; Do(F[N][0]); return 0;} printf("NIE "); return 0; }
| [POI2015]Pieczęć |
题目的意思是要你用印章把原图的x盖满 枚举左上方的点和印章左上方的点对应 本来想写链表优化的 却发现没有我的暴力优...
然后复了一个读入优化 谢谢
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<vector> #define Maxn 1010 using namespace std; pair<int,int> Q[Maxn*Maxn]; int tail; int N,M; int A,B; int Tcase; int str[Maxn][Maxn]; int st[Maxn][Maxn]; bool bo[Maxn][Maxn]; inline int cread() { char ch = getchar(); for(; ch != 'x' && ch != '.'; ch = getchar()); return ch == 'x'; } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%d",&Tcase); while(Tcase--) { scanf("%d%d%d%d",&N,&M,&A,&B); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) str[i][j]=cread(); for(int i=0;i<A;i++) for(int j=0;j<B;j++) st[i][j]=cread(); pair<int,int>ST; bool bk=false; for(int i=0;i<A;i++){for(int j=0;j<B;j++) if(st[i][j]){ST=make_pair(i,j); bk=true; break;} if(bk) break;} tail=0; for(int i=0;i<A;i++) for(int j=0;j<B;j++) if(st[i][j]){Q[++tail]=make_pair(i-ST.first,j-ST.second);} memset(bo,0,sizeof(bo)); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(str[i][j]) bo[i][j]=1; bk=true; for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { if(bo[i][j]) { int k; for(k=1;k<=tail;k++) { if((i+Q[k].first>N)||(j+Q[k].second>M)) break; if(!bo[i+Q[k].first][j+Q[k].second]) break; bo[i+Q[k].first][j+Q[k].second]=0; } if(k!=tail+1){bk=false; break;} } } if(!bk) break; } if(!bk) printf("NIE "); else printf("TAK "); } return 0; }
| [POI2015]Logistyka |
这道题一看就知道猜想 但是上课的时候yy的一下好像把对的猜想出了一组给一不小心否认掉了草
就是大于等于s次的数自然每一个都可以选，个数为cnt 也就是剩下的小于s次的数要选c-cnt个
那么小的个数应该怎么取呢 其实很简单 就是加起来除于s就是答案这就是猜想
你可以想象很多堆数 我们为了均摊 都选最多的c个 那么最后一定会变成很多0和剩余的1 那么取得次数就是设小于s次的和为sum
那么就有sum>=c*s1 s1是最大的操作次数 那么的话加起来除于原来需要的操作次数就是我最多能选多少个正数 判断一下正数个数够不够即可
用权值线段树搞一下
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define inf 1000000000 #define Maxn 1000010 using namespace std; typedef unsigned long long LL; int lc[Maxn*8]; int rc[Maxn*8]; LL size[Maxn*8]; LL sum[Maxn*8]; int N,M; int last[Maxn]; int root,tot; void Link(int &u,int L,int R,int k,int c) { if(!u) u=++tot; if(L==R){size[u]+=c; sum[u]=size[u]*k; return ;} int mid=(L+R)>>1; if(k<=mid) Link(lc[u],L,mid,k,c); else Link(rc[u],mid+1,R,k,c); sum[u]=sum[lc[u]]+sum[rc[u]]; size[u]=size[lc[u]]+size[rc[u]]; } int Query_size(int &u,int L,int R,int l,int r) { if(L==l&&R==r) return size[u]; int mid=(L+R)>>1; if(r<=mid) return Query_size(lc[u],L,mid,l,r); else if(l>mid) return Query_size(rc[u],mid+1,R,l,r); else { return Query_size(lc[u],L,mid,l,mid)+Query_size(rc[u],mid+1,R,mid+1,r); } } LL Query_sum(int &u,int L,int R,int l,int r) { if(l>r) return 0; if(L==l&&R==r) return sum[u]; int mid=(L+R)>>1; if(r<=mid) return Query_sum(lc[u],L,mid,l,r); else if(l>mid) return Query_sum(rc[u],mid+1,R,l,r); else { return Query_sum(lc[u],L,mid,l,mid)+Query_sum(rc[u],mid+1,R,mid+1,r); } } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%d%d",&N,&M); tot=0; memset(last,-1,sizeof(last)); for(int i=1;i<=M;i++) { char str; scanf(" %c",&str); int x,y; scanf("%d%d",&x,&y); if(str=='U') { if(last[x]>0) Link(root,1,inf,last[x],-1); if(y!=0) Link(root,1,inf,y,1); last[x]=y; } else if(str=='Z') { int k=Query_size(root,1,inf,y,inf); x-=k; if(x>0) { LL sum=Query_sum(root,1,inf,1,y-1); x-=sum/y; } if(x>0) printf("NIE "); else printf("TAK "); } } return 0; } /* 3 8 U 1 5 U 2 7 Z 2 6 U 3 1 Z 2 6 U 2 2 Z 2 6 Z 2 1 */
| [POI2015]Modernizacja autostrady |
这道题是神题啊！！！！！！！
首先自己想到(Ai+B)%N<P 那么的话(Ai+B)%N的值一定都不一样 因为A<N A与N互质 这我不会证明 但我知道大概有这样的结论
之后我又想了一下 那么我剩下的表达是不是就是(A(i+1)+B)%N ... (A(i+M-1)+B)%N
然后呢 呵呵不会膜题解
对于每一个位置我们假设小串在大串中的位置为i 那么的话小串后面的值我们是知道的 (我们先不管0和1，只管小串的值,当然小串每个位可以取很多值) 那么我们只能在小串上做工夫 因为数据范围的给定
我们设小串对应大串的开头 数字为x
那么下一个就是我说的(x+a)%N (x+2a)%N ... (x+(M-1)a)%N
那么我们根据实际的0和1进行列出M条不等式 比如说样例 我们可以列得
p<=x%N<=N-1 (1)
0<=(x+a)%N<p (0)
p<=(x+2a)%N<=N-1 (1)
我们可以想想把所有合法区间取交集 但是这样很麻烦 所以我们变成所有不合法区间取并集的补集
所以要把不等式变成不合法的，自己列
还有两个细节 一是在最后面N-M+1到N-1所有的小串取不到的都要变成不合法的(是不连续的 因为变成不合法的是数不是位置) 最后扫一下区间的时候别忘了最后还有一个区间是maxr+1-N这个区间
还有这道题卡时间 我把乘号和mod都尽量改了 改成加号 然后把LL改成int就过了
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define Maxn 3000010 using namespace std; int N,A,B,M,P; char str[Maxn]; struct node{int l,r;}pr[Maxn*2]; int cnt; inline void Add(int l,int r) { if(l<=r){cnt++; pr[cnt].l=l; pr[cnt].r=r;} else{cnt++; pr[cnt].l=l; pr[cnt].r=N-1; cnt++; pr[cnt].l=0; pr[cnt].r=r;} } inline bool Cmp(const node &x,const node &y){if(x.l!=y.l) return x.l<y.l; return x.r>y.r;} int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%d%d%d%d%d",&N,&A,&B,&P,&M); cnt=0; int pre=0; char st=getchar(); for(int i=0;i<M;i++,pre=(pre+A)%N) { st=getchar(); if(st=='1') Add((0-pre+N)%N,((P-1)-pre+N)%N); if(st=='0') Add((P-pre+N)%N,((N-1)-pre+N)%N); } pre=B%N; for(int i=N-1;i>=N-M+1;i--){pre=(pre-A+N)%N; Add(pre,pre);} sort(pr+1,pr+cnt+1,Cmp); int maxr=-1; int ans=0; for(int i=1;i<=cnt;i++) { if(pr[i].l>maxr) ans+=pr[i].l-maxr-1; if(pr[i].r>maxr) maxr=pr[i].r; } printf("%d ",ans+(N-maxr-1)); return 0; }
| [POI2015]Modernizacja autostrady |
这道题写的呕心沥血 写了一个上午加一个下午加晚上一点点时间 写了6k和一个对拍1A 在没有看题解自己yy和liao的提点下做了很开心
bzoj评测机有点sb 我不想吐槽 在官网上ac然后一交TLE
难道每一次都要我复一个读入优化 每个函数加一个inline 然后把mod运算改了你才放心？？？？？
具体怎么做 好难说 好多细节 就是树形dp 然后像之前我们liao大神说的 这些要O(1)转移的 而且割掉之后要变成两个的 一般开一个F数组表示下面的 G数组表示除x这个子树外面的
然后突然想到了一句话 如果你让我再草这道题 我宁愿上树
然后的话关于F数组的维护我们开两个数组维护一下孩子的最长链和次长链 然后加起来 再和下面的比较一下就好了 (当然下面需要 我们不仅要开最长链和次长链 还要开第三长链)
关于G数组的维护就感人肺腑了 要维护除这棵子树外的最长链并且在上面的我们定义一个数组H来维护 那么H的维护我们是很容易想的
那么的话还要维护三条链因为H只维护了在上面的 没有维护fa的孩子 然后x有可能是fa的孩子
反正乱搞一下就好了
最后的话找到点最大的是max(F[i]+G[i]+1) 最小的是min(ceil(F[i]/2)+ceil(G[i]/2)+1)
至于最大的位置 我们再分别从i为根和Fa[i]为根的树再跑一次dfs搜一下两端的端点 记录一下 有点麻烦
最小的位置 我们记录端点后跑一次lca找出路径所有值 (找y的时候把y搜上去 然后swap一下就好) 然后返回中间的就好
至于代码题每年poi都会有一道左右好像 具体不懂看代码
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<climits> #pragma comment(linker, "/STACK:102400000,102400000") #define Maxn 500010 using namespace std; struct node{int x,y,next;}edge[Maxn*2]; int first[Maxn],len; inline void ins(int x,int y){len++;edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;} int W1[Maxn],W2[Maxn],W3[Maxn],F[Maxn],G[Maxn],dep[Maxn],Maxdep[Maxn],H[Maxn]; int F1[Maxn],F2[Maxn]; int Fa[Maxn]; inline void Dfs_dep(int x,int fa) { dep[x]=dep[fa]+1; Fa[x]=fa; for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa) Dfs_dep(y,x); } } inline void Dfs_Maxdep(int x,int fa) { Maxdep[x]=dep[x]; for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa){Dfs_Maxdep(y,x); Maxdep[x]=max(Maxdep[y],Maxdep[x]);} } } inline void Dfs_F(int x,int fa) { for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa) { int L=Maxdep[y]-dep[y]; if(W1[x]<L+1){W3[x]=W2[x]; W2[x]=W1[x]; W1[x]=L+1;} else if(W2[x]<L+1){W3[x]=W2[x]; W2[x]=L+1;} else if(W3[x]<L+1){W3[x]=L+1;} } } if(W1[x]&&W2[x]) F[x]=W1[x]+W2[x]; else if(W1[x]) F[x]=W1[x]; for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa) { Dfs_F(y,x); F[x]=max(F[y],F[x]); if(F[y]>F1[x]) F2[x]=F1[x],F1[x]=F[y]; else if(F[y]>F2[x]) F2[x]=F[y]; } } } inline void Dfs_H(int x,int fa) { if(x!=1) { H[x]=max(H[x],H[fa]+1); if(W1[fa]==Maxdep[x]-dep[x]+1){if(W2[fa]) H[x]=max(H[x],W2[fa]+1);} else if(W1[fa]) H[x]=max(H[x],W1[fa]+1); } for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa) Dfs_H(y,x); } } inline void Dfs_G(int x,int fa) { if(x!=1) { G[x]=G[fa]; int max1=0,max2=0; if(W1[fa]==Maxdep[x]-dep[x]+1) max1=W2[fa],max2=W3[fa]; else if(W2[fa]==Maxdep[x]-dep[x]+1) max1=W1[fa],max2=W3[fa]; else max1=W1[fa],max2=W2[fa]; if(H[fa]>max1){max2=max1; max1=H[fa];} else if(H[fa]>max2){max2=H[fa];} G[x]=max(G[x],max1+max2); if(F1[fa]==F[x]) G[x]=max(G[x],F2[fa]); else G[x]=max(G[x],F1[fa]); } for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa){Dfs_G(y,x);} } } int Ceil(int x,int y){return (x+1)/y;} int Maxpos[Maxn]; int fat[Maxn]; inline void Dfs(int x,int fa) { Maxdep[x]=dep[x]; Maxpos[x]=x; for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa) { dep[y]=dep[x]+1; fat[y]=x; Dfs(y,x); if(Maxdep[x]<Maxdep[y]) Maxdep[x]=Maxdep[y],Maxpos[x]=Maxpos[y]; } } } int f1[Maxn],f2[Maxn],f[Maxn]; pair<int,int>pos[Maxn]; int p1[Maxn],p2[Maxn]; int A,B,C,D; inline void Dfs1(int x,int fa) { for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa) { int L=Maxdep[y]-dep[y]+1; if(L>f1[x]) f2[x]=f1[x],f1[x]=L,p2[x]=p1[x],p1[x]=Maxpos[y]; else if(L>f2[x]) f2[x]=L,p2[x]=Maxpos[y]; } } if(f1[x]&&f2[x]) pos[x]=make_pair(p1[x],p2[x]),f[x]=f1[x]+f2[x]; else if(f1[x]) pos[x]=make_pair(p1[x],x),f[x]=f1[x]; else pos[x]=make_pair(x,x),f[x]=0; for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa) { Dfs1(y,x); if(f[y]>f[x]) pos[x]=pos[y],f[x]=f[y]; } } } int Q[Maxn]; int tail=0; inline int Mid(int x,int y) { int px,py; px=x; py=y; while(px!=py) { if(dep[px]>dep[py]) px=fat[px]; else py=fat[py]; } int lca=px; tail=0; while(x!=lca) Q[++tail]=x,x=fat[x]; Q[++tail]=lca; int p=tail+1; while(y!=lca) Q[++tail]=y,y=fat[y]; int size=tail; while(p<=tail) swap(Q[p],Q[tail]),p++,tail--; return Q[Ceil(size,2)]; } inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int N; read(N); len=0; memset(first,-1,sizeof(first)); for(int i=1;i<N;i++) { int x,y; read(x); read(y); ins(x,y); ins(y,x); } memset(dep,0,sizeof(dep)); Dfs_dep(1,0); memset(Maxdep,0,sizeof(Maxdep)); Dfs_Maxdep(1,0); memset(F,0,sizeof(F)); memset(W1,0,sizeof(W1)); memset(W2,0,sizeof(W2)); memset(F1,0,sizeof(F1)); memset(F2,0,sizeof(F2)); Dfs_F(1,0); memset(H,0,sizeof(H)); Dfs_H(1,0); memset(G,0,sizeof(G)); Dfs_G(1,0); int ans=INT_MAX,p; for(int i=2;i<=N;i++) if(ans>max(max(F[i],G[i]),Ceil(F[i],2)+Ceil(G[i],2)+1)) ans=max(max(F[i],G[i]),Ceil(F[i],2)+Ceil(G[i],2)+1),p=i; printf("%d ",ans); printf("%d %d ",p,Fa[p]); memset(Maxdep,0,sizeof(Maxdep)); memset(dep,0,sizeof(dep)); memset(fat,0,sizeof(fat)); Dfs(p,Fa[p]); Dfs(Fa[p],p); memset(f,0,sizeof(f)); memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2)); memset(p1,0,sizeof(p1)); memset(p2,0,sizeof(p2)); Dfs1(p,Fa[p]); A=pos[p].first; B=pos[p].second; Dfs1(Fa[p],p); C=pos[Fa[p]].first; D=pos[Fa[p]].second; int mid1=Mid(A,B); int mid2=Mid(C,D); printf("%d %d ",mid1,mid2); ans=0; p=0; for(int i=2;i<=N;i++) if(ans<F[i]+G[i]+1) ans=F[i]+G[i]+1,p=i; printf("%d ",ans); printf("%d %d ",p,Fa[p]); memset(Maxdep,0,sizeof(Maxdep)); memset(dep,0,sizeof(dep)); Dfs(p,Fa[p]); Dfs(Fa[p],p); memset(f,0,sizeof(f)); memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2)); memset(p1,0,sizeof(p1)); memset(p2,0,sizeof(p2)); Dfs1(p,Fa[p]); A=pos[p].first; B=pos[p].second; Dfs1(Fa[p],p); C=pos[Fa[p]].first; D=pos[Fa[p]].second; printf("%d %d ",A,C); return 0; }
| [POI2015]Myjnie |
这个spj可是把我给吓到了 一眼看上去很难
以为是一维dp二分搞搞，然后就不会了 纯属错误想法
其实看题解后感觉很厉害 用F[l][r][k]表示第l到r的区间最小值为k的最大消费额
然后就是想转移了 想了我很久 你想想 这个状态肯定是由k大的转到k小的
考虑F[l][r][k+1]转到现在 但是我们还要每个节点都去找找
至于每个儿子 我们还要想这个区间哪个点是最小值 然后再分成两个区间做 这样的话这个值一定要满足两个区间的值加起来加上中间点跨两个区间的贡献
那么这样的话 既然我们还要用深搜做一遍 那可不可以在dp里面进行合并的转移 再深搜出答案呢?
利用中链式 F[l][r][k]=max(G[l][x-1][k]+G[x+1][r][k]+H[x][k]) G[l][r][k]=max(F[l][r][k..m]) 因为我两边的区间都可以取大于这个值的
还有就是H[x][k]表示在l到r的区间里面 选x为中间点 值为离散化的k 能选跨过x的区间的个数 因为时间的关系 我们可以在每次l到r的时候做一遍 一遍的时间为O(M)要做x个
关于F选的中间点 G选的k是有多大 开多两个数组存一下方便搜索即可
总的时间是O(N^3M)
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<climits> #define Maxn 60 #define Maxm 4010 using namespace std; void read(int &x){char c; while(!((c=getchar()))>='0'&&c<='9'); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x*10)+c-'0';} int N,M; int F[Maxn][Maxn][Maxm]; int G[Maxn][Maxn][Maxm]; int H[Maxn][Maxm]; int preF[Maxn][Maxn][Maxm],preG[Maxn][Maxn][Maxm]; struct node { int x,y,c; }pos[Maxm]; int Hash[500010]; int tot; int Val[Maxm]; int ans[Maxn]; void Dfs(int l,int r,int k,int s) { if(l>r) return ; int x=preF[l][r][k]; if(x!=0) { ans[x]=Val[k]; Dfs(l,x-1,preG[l][x-1][k],Val[k]); Dfs(x+1,r,preG[x+1][r][k],Val[k]); } else { if(l==r){ans[l]=s; return ;} int mid=(l+r)>>1; Dfs(l,mid,preG[l][mid][k],s); Dfs(mid+1,r,preG[mid+1][r][k],s); } } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); read(N); read(M); memset(Hash,0,sizeof(Hash)); for(int i=1;i<=M;i++){read(pos[i].x); read(pos[i].y); read(pos[i].c); Hash[pos[i].c]=1;} tot=0; for(int i=1;i<=500000;i++) if(Hash[i]){Hash[i]=++tot; Val[tot]=i;} memset(H,0,sizeof(H)); for(int i=1;i<=M;i++) { if(pos[i].x==pos[i].y) { for(int j=pos[i].x;j<=pos[i].y;j++) H[j][Hash[pos[i].c]]++; } } for(int i=1;i<=N;i++) for(int j=tot;j>=1;j--) H[i][j]+=H[i][j+1]; memset(F,0,sizeof(F)); memset(G,0,sizeof(G)); memset(preF,0,sizeof(preF)); memset(preG,0,sizeof(preG)); for(int i=1;i<=N;i++) { for(int j=tot;j>=1;j--) { if(H[i][j]*Val[j]>F[i][i][j]) F[i][i][j]=H[i][j]*Val[j],preF[i][i][j]=i; if(F[i][i][j]<G[i][i][j+1]) G[i][i][j]=G[i][i][j+1],preG[i][i][j]=preG[i][i][j+1]; else G[i][i][j]=F[i][i][j],preG[i][i][j]=j; } } for(int L=2;L<=N;L++) { for(int l=1;l<=N-L+1;l++) { int r=l+L-1; memset(H,0,sizeof(H)); for(int i=1;i<=M;i++) { if(pos[i].x>=l&&pos[i].y<=r) { for(int j=pos[i].x;j<=pos[i].y;j++) H[j][Hash[pos[i].c]]++; } } for(int i=1;i<=N;i++) for(int j=tot;j>=1;j--) H[i][j]+=H[i][j+1]; for(int k=tot;k>=1;k--) { for(int x=l;x<=r;x++) { if(F[l][r][k]<G[l][x-1][k]+G[x+1][r][k]+H[x][k]*Val[k]) { F[l][r][k]=G[l][x-1][k]+G[x+1][r][k]+H[x][k]*Val[k]; preF[l][r][k]=x; } } if(G[l][r][k+1]>F[l][r][k]) { G[l][r][k]=G[l][r][k+1]; preG[l][r][k]=preG[l][r][k+1]; } else { G[l][r][k]=F[l][r][k]; preG[l][r][k]=k; } } } } printf("%d ",G[1][N][1]); Dfs(1,N,preG[1][N][1],Val[preG[1][N][1]]); for(int i=1;i<N;i++) printf("%d ",ans[i]); printf("%d ",ans[N]); return 0; } /* 7 5 1 4 7 3 7 13 5 6 20 6 7 1 1 2 5 */
| [POI2015]Odwiedziny |
今天不知道吃了什么屎 状态不是很好 居然都下去做课间操了 草了一道sb题
这道题大于√N的时候暴力跳 小于的时候找到lca 维护树上的前缀和 pre[x][i]表示第x个点往上面每次跳i步最多能跳的价值
然后就是小于的话就要搞一下在两个链的情况 求出个lca 找到lca下面的x跳C[i]步的点 然后转到y链上 往下跳
反正 这一道就是细节题 巨恶心 草了个倍增 网上的人都好厉害是O(N√N) 我好像自带常数log都过掉了而且速度不慢
为什么多一个log 就是再维护或者在跳的时候 找到x跳C[i]层后得父亲 我用倍增跳
细节题怎么做？ 其实有一个不是很实用的方法但我很依赖就是打补丁..
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define Maxn 50010 using namespace std; struct node { int x,y,next; }edge[Maxn*2]; int len,first[Maxn]; void ins(int x,int y) { len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len; } int N; int Val[Maxn]; int root=1; int B[Maxn]; int C[Maxn]; int ans; int Fa[Maxn][18]; int pre[Maxn][230]; int dep[Maxn]; int Findfa(int x,int d) { int p=x; for(int i=17;i>=0;i--) if((1<<i)<=d) p=Fa[p][i],d-=(1<<i); return p; } void Dfs(int x,int fa) { dep[x]=dep[fa]+1; Fa[x][0]=fa; for(int i=1;(1<<i)<=dep[x];i++) Fa[x][i]=Fa[Fa[x][i-1]][i-1]; for(int i=1;(i<=(int)sqrt(N))&&(i<=dep[x]);i++) pre[x][i]=pre[Findfa(x,i)][i]+Val[x]; for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; if(y!=fa) Dfs(y,x); } } int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); int d=dep[x]-dep[y]; for(int i=17;i>=0;i--) if((1<<i)<=d) x=Fa[x][i],d-=(1<<i); if(x==y) return x; for(int i=17;i>=0;i--) if(Fa[x][i]!=Fa[y][i]) x=Fa[x][i],y=Fa[y][i]; return Fa[x][0]; } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d",&Val[i]); len=0; memset(first,-1,sizeof(first)); for(int i=1;i<N;i++) { int x,y; scanf("%d%d",&x,&y); ins(x,y); ins(y,x); } for(int i=1;i<=N;i++) scanf("%d",&B[i]); for(int i=1;i<N;i++) scanf("%d",&C[i]); Dfs(root,0); for(int i=1;i<N;i++) { int st=B[i]; int ed=B[i+1]; ans=0; if(C[i]>(int)sqrt(N)) { int lca=LCA(st,ed); int x=st; int y=ed; ans=Val[x]; while(dep[x]-dep[lca]>=C[i]){x=Findfa(x,C[i]); ans+=Val[x];} if(dep[x]+dep[y]-2*dep[lca]>=C[i]) { x=Findfa(y,dep[ed]-dep[lca]-(C[i]-(dep[x]-dep[lca]))); ans+=Val[x]; } while(dep[y]-dep[x]>C[i]) x=Findfa(y,dep[y]-dep[x]-C[i]),ans+=Val[x]; if(x!=y) ans+=Val[y]; printf("%d ",ans); } else { int lca=LCA(st,ed); int x=st; int y=ed; int depx=dep[x]-dep[lca]; int xx=Findfa(x,depx-depx%C[i]); ans+=pre[x][C[i]]-pre[xx][C[i]]+Val[xx]; if(dep[xx]+dep[y]-2*dep[lca]>C[i]) { int depy=dep[y]-dep[lca]; int y1=Findfa(y,depy-(C[i]-(depx%C[i]))); int y2; if((dep[y]-dep[y1])%C[i]){y2=Findfa(y,(dep[y]-dep[y1])%C[i]); ans+=Val[y];} else y2=y; ans+=pre[y2][C[i]]-pre[y1][C[i]]+Val[y1]; printf("%d ",ans); } else { if(xx!=y)ans+=Val[y]; printf("%d ",ans); continue; } } } return 0; } /* 5 1 2 3 4 5 1 2 2 3 3 4 3 5 4 1 5 2 3 1 3 1 1 */
| [POI2015]Trzy wieże |
这是一道吃屁的题目
首先三个元素 我们要算一段区间内三个元素的个数不一样 那么的话我们想着记得做个三个元素只用管两个剩下一个就可以做出来 很快就可以想到了O(N^2) 但是这道题没这么简单 毕竟是poi的题 所以的话一看数据范围最多O(NlogN)吓尿了 然后我们再思考 如何枚举右端点快速找到左端点 那么的话我们可以发现
prefix[i][B]-prefix[j][B]不等于prefix[i][C]-prefix[j][C]不等于prefix[i][S]-prefix[j][S] 这样的话我们可以取j+1为左端点
移项之后 当我们定义 F[i][0],F[i][1],F[i][2]分别是以i为前缀 B-C B-S C-S 的个数 当我前面找到一个j使得三个值都与i的三个值都不一样的话 那么j+1就是答案
那么现在问题来了 我们怎么快速的找咧 然后就去膜ljmzlh了 果然好劲啊
先按所有的F[i][0]从小到大排序 然后的话每次就以F[i][1]开2个树状数组 每次找到比F[i][1]大和比F[i][1]小的树状数组位置 然后里面再存 一个z和d
d是表示这个数的位置 我们按d的大小来排序 而且还要存次大的 因为当z==z1时 要找到次大的 然后记得每次更新次大之后看看可不可以比最大的要大
那么再用x从大到小排一遍 然后用离散化降时间 应该讲得很清楚吧 就是x和y分别按比当前元素小的和大的做一遍就好了
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define inf 1000000 #define Maxn 1000010 using namespace std; struct node { int x,y,z,d; }A[Maxn],x,F; char str[Maxn]; int N; int Y[Maxn*2]; int cnt; struct E { int z1,d1,z2,d2; }tr[2][Maxn]; inline bool Cmpx1(const node &x,const node &y){return x.x<y.x;} inline bool Cmpx2(const node &x,const node &y){return x.x>y.x;} inline bool Cmp(const node &x,const node &y){return x.d<y.d;} inline int low_bit(int &x){return x&(-x);} inline void Add(int k,int y,int z,int d) { while(y<=cnt) { if(tr[k][y].z1==z){if(tr[k][y].d1>d) tr[k][y].d1=d;} else if(tr[k][y].z2==z) { if(tr[k][y].d2>d) tr[k][y].d2=d; if(tr[k][y].d2<tr[k][y].d1) swap(tr[k][y].d1,tr[k][y].d2),swap(tr[k][y].z1,tr[k][y].z2); } else { if(tr[k][y].d1>d){tr[k][y].d2=tr[k][y].d1; tr[k][y].z2=tr[k][y].z1; tr[k][y].d1=d; tr[k][y].z1=z;} else if(tr[k][y].d2>d){tr[k][y].d2=d; tr[k][y].z2=z;} } y+=low_bit(y); } } inline int Find(int k,int y,int z) { int minx=N+1; while(y>=1) { if(tr[k][y].z1==z) minx=min(minx,tr[k][y].d2); else minx=min(minx,tr[k][y].d1); y-=low_bit(y); } return minx; } int pre[Maxn]; int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%d",&N); for(int i=1;i<=N;i++) scanf(" %c",&str[i]); F.x=F.y=F.z=F.d=0; A[0]=F; Y[inf]=1; for(int i=1;i<=N;i++) { x=F; x.d++; if(str[i]=='B') x.x++,x.y++; else if(str[i]=='C') x.x--,x.z++; else if(str[i]=='S') x.y--,x.z--; A[i]=x; F=x; Y[x.y+inf]=1; } for(int i=1;i<=N+inf;i++) Y[i]+=Y[i-1],cnt=max(cnt,Y[i]); int last=0; for(int i=1;i<=N;i++) { pre[i]=N+1; if(str[i]!=str[i-1]) last=i,pre[i]=min(pre[i],i); else pre[i]=min(pre[i],last); } for(int i=1;i<=cnt;i++) tr[0][i].z1=tr[0][i].z2=tr[0][i].d1=tr[0][i].d2=tr[1][i].z1=tr[1][i].z2=tr[1][i].d1=tr[1][i].d2=N+1; sort(A,A+N+1,Cmpx1); last=0; for(int i=0;i<=N;i++) { if(A[i].x!=A[i-1].x&&i!=0) { for(int j=last;j<i;j++) Add(0,Y[A[j].y+inf],A[j].z,A[j].d),Add(1,cnt-Y[A[j].y+inf]+1,A[j].z,A[j].d); last=i; } pre[A[i].d]=min(pre[A[i].d],min(Find(0,Y[A[i].y+inf]-1,A[i].z),Find(1,cnt-Y[A[i].y+inf],A[i].z))+1); } for(int i=1;i<=cnt;i++) tr[0][i].z1=tr[0][i].z2=tr[0][i].d1=tr[0][i].d2=tr[1][i].z1=tr[1][i].z2=tr[1][i].d1=tr[1][i].d2=N+1; sort(A,A+N+1,Cmpx2); last=0; for(int i=0;i<=N;i++) { if(A[i].x!=A[i-1].x&&i!=0) { for(int j=last;j<i;j++) Add(0,Y[A[j].y+inf],A[j].z,A[j].d),Add(1,cnt-Y[A[j].y+inf]+1,A[j].z,A[j].d); last=i; } pre[A[i].d]=min(pre[A[i].d],min(Find(0,Y[A[i].y+inf]-1,A[i].z),Find(1,cnt-Y[A[i].y+inf],A[i].z))+1); } int L=1; for(int i=1;i<=N;i++) L=max(L,i-pre[i]+1); printf("%d ",L); return 0; } /* 9 CBBSSBCSC */
| [POI2015]Podział naszyjnika |
这道题的确很有思考价值 作为之前一届gdoi的晚练 然而我没有参加 我想这道题想了1.5个晚上 结果以失败告终
先说说我的想法吧 last[i]在长度<=N最远的一样的颜色 然后要求一段并集 顺时针逆时针搞一下 这样在打的过程中好像发现了问题
还有就是最开始想用括号序列搞一下的 显然错误就当我没说吧
然后怎么办? 去膜大神cys咯
盗commonc的图 每次找一个点 顺时针或者逆时针 (反正要同个方向)然后遇到一个点就+1 要绕一圈保证没有0的点 然后在所有值相同的地方切下
为什么呢 很显然 对于一个数来说它代表的是一种颜色 如果不相同 那么的话就说明了两个不相同的数之间肯定隔了这个数 因为没有0的情况 那么你就不能从两端切开了
而所有数字都相同 代表所有颜色都满足 然后就hash了 显然O(NK)是不行的
我们发现每经过一个颜色只会改变一个数字 那么我们直接在这个数字的位置加上一个数就好了
至于答案 方案数就用组合排列搞一下 然后的话最接近的话 将所有的hash和位置从小到大排 就用指针 找到前面刚好小于j-mid的 然后再-1就是大于j-mid的 然后比较一下就好了 这两个一定是最优的方案 这不用说了吧
至于卡hash我就不吐槽了 我用的每一位都乘于一个N+1然后Mod 3*10^12+7 还有前面会有一段是0的 要改为满的 绕一圈嘛
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<climits> #define Maxn 1000010 using namespace std; typedef long long LL; const LL Mod=3e12+7; LL N,K; LL A[Maxn]; LL sum[Maxn]; LL bit[Maxn]; LL hash[Maxn]; bool bo[Maxn]; pair<LL,LL>pr[Maxn]; bool Cmp(const pair<LL,LL> &x,const pair<LL,LL> &y){if(x.first!=y.first) return x.first<y.first; return x.second<y.second;} int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%lld%lld",&N,&K); for(LL i=1;i<=N;i++) scanf("%lld",&A[i]); memset(sum,0,sizeof(sum)); for(LL i=1;i<=N;i++) sum[A[i]]++; bit[1]=1; for(LL i=2;i<=N;i++) bit[i]=(bit[i-1]*(N+1))%Mod; memset(bo,1,sizeof(bo)); memset(hash,0,sizeof(hash)); for(LL i=1;i<=K;i++) hash[0]=(hash[0]+bit[i]*sum[i])%Mod; for(LL i=1;i<=N;i++) { hash[i]=hash[i-1]; if(bo[A[i]]){bo[A[i]]=0; hash[i]=((hash[i]-bit[A[i]]*sum[A[i]])%Mod+Mod)%Mod;} hash[i]=(hash[i]+bit[A[i]])%Mod; pr[i].first=hash[i]; pr[i].second=i; } sort(pr+1,pr+N+1,Cmp); LL last=0; LL ans=0; LL Minx=LONG_MAX; for(LL i=1;i<=N;i++) { if(pr[i].first!=pr[i-1].first) { ans+=(i-last)*(i-last-1)/2; LL x=last; for(LL j=last+1;j<i;j++) { while(pr[j].second-pr[x].second>N/2&&x<j-1) x++; if(x==last) Minx=min(Minx,abs((N-abs(pr[j].second-pr[x].second))-abs(pr[j].second-pr[x].second))); else Minx=min(min(Minx,abs((N-abs(pr[j].second-pr[x].second))-abs(pr[j].second-pr[x].second))), min(Minx,abs((N-abs(pr[j].second-pr[x-1].second))-abs(pr[j].second-pr[x-1].second)))); } last=i; } } ans+=(N+1-last)*(N-last)/2; LL x=last; for(LL j=last+1;j<=N;j++) { while(pr[j].second-pr[x].second>N/2&&x<j-1) x++; if(x==last) Minx=min(Minx,abs((N-abs(pr[j].second-pr[x].second))-abs(pr[j].second-pr[x].second))); else Minx=min(min(Minx,abs((N-abs(pr[j].second-pr[x].second))-abs(pr[j].second-pr[x].second))), min(Minx,abs((N-abs(pr[j].second-pr[x-1].second))-abs(pr[j].second-pr[x-1].second)))); } printf("%lld %lld ",ans,Minx); return 0; } /* 9 5 2 5 3 2 2 4 1 1 3 */
| [POI2015]Pustynia |
想了三十分钟然后草了出来
首先题目是要我们给定一个集合 然后在这个集合里面找一个子集 使得这个子集的任意一个数大于这个子集在集合中的补集
简单的 我们会想到 一个数比一个数大 这样会产生很多连锁的条件 那么我们会自然想到拓扑和差分约束
那么的话我们想 如果这个子集里面的任意一个数和外面的连边可不可以 那么的话肯定会超时 但是k的总和就300000 注意这个点
我们考虑优化 一个区间里面选一些点的话 剩下的点应该是很密集的 所以我想到了用线段树 因为线段树一个点就代表了一个区间 每个区间都有个编号 那么的话它管辖的点所用的边就Klogn个
这样的话 连几个点总比连很多点强 虽然一开始的边我们用多了
那么 怎么连呢 没有可能每一个点都连每一个区间吧 如果有k+1个区间k个点的话 简直吃屎
所以的话我们想到了用一个方法 就是建一个虚节点 然后让k个点都连向虚节点 虚节点连向k+1个区间 每次一个点管辖的区间是一样的 所以我们可以这么做
然后就是用 F[y]=min(F[x]-edge[k].d,Val[y是线段树的叶子节点]) 如果F[y]<y这个节点的权值 那么的话就无解了 或者有环 或者F[x]=0 F[i]表示第i个编号所能取的最大值
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<queue> #define Maxn 100010 using namespace std; struct node{int x,y,d,next;}edge[Maxn*45]; int len,first[Maxn*6]; void ins(int x,int y,int d){len++; edge[len].x=x; edge[len].y=y; edge[len].d=d; edge[len].next=first[x]; first[x]=len;} int tot; int Val[Maxn*6]; int lc[Maxn*6]; int rc[Maxn*6]; int root; int pos[Maxn*6]; int hash[Maxn*6]; void Link(int &u,int L,int R,int k) { if(!u) u=++tot; if(L==R){pos[k]=u; hash[u]=k; return ;} int mid=(L+R)>>1; if(k<=mid) Link(lc[u],L,mid,k); else Link(rc[u],mid+1,R,k); } void Link_INS(int u,int L,int R,int l,int r,int st) { if(l>r) return ; if(L==l&&R==r){ins(st,u,1); return ;} int mid=(L+R)>>1; if(r<=mid) Link_INS(lc[u],L,mid,l,r,st); else if(l>mid) Link_INS(rc[u],mid+1,R,l,r,st); else Link_INS(lc[u],L,mid,l,mid,st),Link_INS(rc[u],mid+1,R,mid+1,r,st); } queue<int>Q; int F[Maxn*6]; int ru[Maxn*6]; int N,S,M; bool bo[Maxn*6]; int main() { //freopen("a.in","r",stdin); //sfreopen("a.out","w",stdout); scanf("%d%d%d",&N,&S,&M); root=0; for(int i=1;i<=N;i++) Link(root,1,N,i); memset(bo,0,sizeof(bo)); for(int i=1;i<=S;i++) { int x,y; scanf("%d%d",&x,&y); Val[x]=y; bo[x]=1; } len=0; memset(first,-1,sizeof(first)); for(int i=1;i<=tot;i++) { if(lc[i]) ins(i,lc[i],0); if(rc[i]) ins(i,rc[i],0); } for(int i=1;i<=M;i++) { int L,R; scanf("%d%d",&L,&R); int last=L-1; int k; scanf("%d",&k); tot++; for(int j=1;j<=k;j++) { int x; scanf("%d",&x); Link_INS(root,1,N,last+1,x-1,tot); ins(pos[x],tot,0); last=x; } Link_INS(root,1,N,last+1,R,tot); } for(int i=1;i<=len;i++) ru[edge[i].y]++; for(int i=1;i<=tot;i++){if(!ru[i]) Q.push(i); F[i]=1000000000; if(bo[hash[i]]) F[i]=min(F[i],Val[hash[i]]);} while(!Q.empty()) { int x=Q.front(); for(int k=first[x];k!=-1;k=edge[k].next) { int y=edge[k].y; F[y]=min(F[x]-edge[k].d,F[y]); if(bo[hash[y]]&&F[y]<Val[hash[y]]){printf("NIE "); return 0;} if(!F[y]){printf("NIE "); return 0;} ru[y]--; if(!ru[y]) Q.push(y); } Q.pop(); } for(int i=1;i<=tot;i++) if(ru[i]){printf("NIE "); return 0;} printf("TAK "); for(int i=1;i<N;i++) printf("%d ",F[pos[i]]); printf("%d ",F[pos[N]]); return 0; } /* 5 2 2 2 7 5 3 1 4 2 2 3 4 5 1 4 TAK 6 7 1000000000 6 3 */