POI2016
T2 Korale 先来解决第一问，可以用堆，排序后用一个二元组$(x,y)$表示当前物品价值为$x$，最大的物品编号是$y$，那么这个元素取出后能扩展到$(x+v[x+1],y+1)$和$(x+v[x+1]-v[x],y+1)$，相当于一颗二叉树上选点，时间复杂度$O(nlgn+klgk)$
然后解决第二问，先统计出当前答案是相同价值中排第几的，然后进行暴力搜索
对于每个数我们要知道其后面第一个小于等于它的数，可以用二分+RMQ处理，时间复杂度$O(klgn)$
#include<bits/stdc++.h>
#define N 1001000
using namespace std;typedef long long LL;int n,m,i,j,w,t,a[N],q[N],g[N][21],h[N];LL f[N];
struct P{LL x;int y;bool operator<(P a)const{return a.x<x;}};priority_queue<P>Q;
LL G(int x,int y){int t=h[y-x+1];return min(g[x][t],g[y-(1<<t)+1][t]);}
void dfs(int x,LL z,int o){
int i,ans,l,r,mid;if(!w)return;if(z<0)return;
if(!z){if(!--w)for(i=1;i<o;i++)printf("%d ",q[i]);return;}
for(;x<=n;x++){
for(r=n;x<r;)if(G(x,mid=x+r>>1)<=z)r=mid;else x=mid+1;
if(x>n)return;q[o]=x;dfs(x+1,z-g[x][0],o+1);
}
}
int main(){
for(scanf("%d%d",&n,&m),h[0]--,m--,i=1;i<=n;i++)scanf("%d",&a[i]),g[i][0]=a[i],h[i]=h[i>>1]+1;
if(!m)return puts("0"),0;
for(j=1;j<=20;j++)for(i=1;i+(1<<j)-1<=n;i++)g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]);
for(sort(a+1,a+n+1),Q.push(P{a[1],1}),i=1;i<=m;i++){
P x=Q.top();Q.pop();f[i]=x.x;
if(x.y<n)Q.push(P{f[i]+a[x.y+1],x.y+1}),Q.push(P{f[i]+a[x.y+1]-a[x.y],x.y+1});
}
for(printf("%lld\n",f[i=m]);f[i--]==f[m];w++);dfs(1,f[m],1);
}
T3 Nadajniki
在一颗树的点上建立WIFI，要求每条边至少满足两个条件之一：连该边的两点有WIFI，连该边两点的邻点至少有两个WIFI。$n\leq200000$。
$f[i][x][y][z][o]$表示$i$点选$x$个，其父亲选$y$个，其儿子要选$z$个，已经选$o$个的最小代价。然后直接暴力转移，枚举每个儿子，用$f[j][a][x][b][b]$来转移，同时判断转移的合法性，即$x>0\ or\ a>0\ or\ z+y+b\geq2$。但是直接暴力转移时间复杂度$O(3^6n)$，可以通过前缀和优化到$O(3^5n)$，再特判剪枝可以做到$O(2^2*3^3n)$的复杂度。单点0.5S左右，可是BZOJ上还是T了。。
#include<bits/stdc++.h>
#define N 200200
using namespace std;int n,i,j,x,y,A,tot,fir[N],la[N*2],ne[N*2],f[N][3][3][3][3],h[3],g[N][3][3][3];
char ch;inline void rd(int&x){for(ch=getchar();ch<'0'||ch>'9';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
inline void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
inline void dfs(int x,int fa){
int i,y,X,Y,Z,A,B,C;
for(X=0;X<3;X++)for(Y=0;Y<3;Y++)for(Z=0;Z<3;Z++)f[x][X][Y][Z][0]=X;
for(i=fir[x];i;i=ne[i])if(la[i]!=fa)for(dfs(y=la[i],x),X=0;X<3;X++)
for(Y=0;Y<3;Y++)for(Z=0;Z<3;memcpy(f[x][X][Y][Z],h,sizeof h),Z++)
if(Z<2){
for(h[0]=h[1]=h[2]=1e9,A=0;A<=Z;A++)for(B=0;A+B<=Z;B++)
h[A+B]=min(h[A+B],f[x][X][Y][Z][B]+g[y][A][X][(X||A||Z+Y>=2)?0:2-Z-Y]);
}else{
for(h[0]=h[1]=h[2]=1e9,A=0;A<3;A++)for(B=0;B<3;B++)
h[min(A+B,Z)]=min(h[min(A+B,Z)],f[x][X][Y][Z][B]+g[y][A][X][(X||A||Z+Y>=2)?0:2-Z-Y]);
}
for(A=0;A<3;A++)for(B=0;B<3;B++)for(g[x][A][B][2]=f[x][A][B][2][2],C=1;~C;C--)g[x][A][B][C]=min(g[x][A][B][C+1],f[x][A][B][C][C]);
}
int main(){
for(memset(f,63,sizeof f),rd(n),i=1;i<n;i++)rd(x),rd(y),ins(x,y),ins(y,x);
for(dfs(1,0),A=1e9,i=0;i<3;i++)for(j=0;j<3;j++)A=min(A,f[1][i][0][j][j]);
printf("%d",A);
}
T4 Nim z utrudnieniem 由于石子的总和不太大，可以排序后对当前最大能到达的异或区间进行处理，转移就很简单啦，可以$O(md)$转移，不过这题卡内存，滚内存还是不行，再加一个单调性滚内存才行
#include<bits/stdc++.h>
#define M 1000000007
#define N 1048576
int n,i,j,k,d,w,x,a[N],f[10][N],g[N],h[N];
int main(){
for(scanf("%d%d",&n,&d),i=1;i<=n;i++,a[x]++)scanf("%d",&x);
for(f[0][0]=w=i=1;i<=1000000;i++){
if(w<=i)w*=2;
for(;a[i]--;){
for(k=0;k<w;k++)h[k]=(f[d-1][k]+f[0][k^i])%M;
for(j=d-1;j;j--){
for(k=0;k<w;k++)g[k]=f[j][k];
for(k=0;k<w;k++)f[j][k]=(f[j-1][k]+g[k^i])%M;
}
for(k=0;k<w;k++)f[0][k]=h[k];
}
}
printf("%d",(f[0][0]-((n%d)?0:1)+M)%M);
}
T5 Park wodny 大暴力，有几种情况可能是优的，枚举每个联通块判断即可
①联通块往外扩一个点，这样可能和1~3个其它联通块接触，枚举两个扩的点，判断这两个点去重以后的贡献
②往一个方向连走两步，这样这个方向上的第三个点的联通块对答案有贡献，连走的两边对答案也有贡献
③在一个角上，先走一步，再垂直走一步，这样的话有两个联通块是有贡献的
注意：特判$l==r,u==d$的情况，因为这样的话有更多的联通块合法
#include<bits/stdc++.h>
#define N 1111
using namespace std;
int n,i,j,k,o,u,d,l,r,w,t,cnt,ans,sz[N*N],xa[N*N],xb[N*N],ya[N*N],yb[N*N],a[N][N],bl[N][N],q[4444][3];bool v[N][N];char s[N];
void get(int x,int y,int z){
v[x][y]=1;sz[z]++;bl[x][y]=z;xb[z]=max(xb[z],x);yb[z]=max(yb[z],y);
if(a[x+1][y]&&!v[x+1][y])get(x+1,y,z);
if(a[x][y+1]&&!v[x][y+1])get(x,y+1,z);
}
void up(int x,int y,int z){if(!x&&!y&&!z)return;q[++t][0]=x;q[t][1]=y;q[t][2]=z;}
void G(int x){w=max(w,x);}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%s",s+1),j=1;j<=n;j++)a[i][j]=s[j]-'A';
for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i][j]&&!v[i][j])xa[++cnt]=i,ya[cnt]=j,get(i,j,cnt);
if(cnt==0)return printf("%d\n",min(2,n*n)),0;if(cnt==1)return printf("%d\n",min(n*n,sz[1]+2)),0;
for(i=1;i<=cnt;ans=max(ans,w+sz[i]+2),i++){
w=t=0;u=xa[i];d=xb[i];l=ya[i];r=yb[i];
for(j=u;j<=d;j++){
if(a[j][l-2])up(bl[j][l-2],0,0);else G(sz[bl[j][l-3]]+(sz[bl[j-1][l-2]]|sz[bl[j-1][l-1]])+(sz[bl[j+1][l-2]]|sz[bl[j+1][l-1]]));
if(a[j][r+2])up(bl[j][r+2],0,0);else G(sz[bl[j][r+3]]+(sz[bl[j-1][r+2]]|sz[bl[j-1][r+1]])+(sz[bl[j+1][r+2]]|sz[bl[j+1][r+1]]));
}
for(j=l;j<=r;j++){
if(a[u-2][j])up(bl[u-2][j],0,0);else G(sz[bl[u-3][j]]+(sz[bl[u-2][j-1]]|sz[bl[u-1][j-1]])+(sz[bl[u-2][j+1]]|sz[bl[u-1][j+1]]));
if(a[d+2][j])up(bl[d+2][j],0,0);else G(sz[bl[d+3][j]]+(sz[bl[d+2][j-1]]|sz[bl[d+1][j-1]])+(sz[bl[d+2][j+1]]|sz[bl[d+1][j+1]]));
}
if(a[u-1][l-1])up(bl[u-1][l-1],bl[u-2][l],0),up(bl[u-1][l-1],bl[u][l-2],0);
if(a[d+1][l-1])up(bl[d+1][l-1],bl[d+2][l],0),up(bl[d+1][l-1],bl[d][l-2],0);
if(a[u-1][r+1])up(bl[u-1][r+1],bl[u-2][r],0),up(bl[u-1][r+1],bl[u][r+2],0);
if(a[d+1][r+1])up(bl[d+1][r+1],bl[d+2][r],0),up(bl[d+1][r+1],bl[d][r+2],0);
if(l==r)up(bl[u-2][l],bl[u-1][l-1],bl[u-1][l+1]),up(bl[d+2][l],bl[d+1][l-1],bl[d+1][l+1]);
if(u==d)up(bl[u][l-2],bl[u-1][l-1],bl[u+1][l-1]),up(bl[u][r+2],bl[u-1][r+1],bl[u+1][r+1]);
for(j=1;j<=t;j++)for(k=j+1;k<=t;k++)G(sz[q[j][0]]+sz[q[j][1]]+sz[q[j][2]]+(q[j][0]!=q[k][0]&&q[j][1]!=q[k][0]&&q[j][2]!=q[k][0]?sz[q[k][0]]:0)+(q[j][0]!=q[k][1]&&q[j][1]!=q[k][1]&&q[j][2]!=q[k][1]?sz[q[k][1]]:0)+(q[j][0]!=q[k][2]&&q[j][1]!=q[k][2]&&q[j][2]!=q[k][2]?sz[q[k][2]]:0));
if(u>1&&l>1&&!a[u-1][l-1])G(sz[bl[u-1][l-2]]+(sz[bl[u-2][l]]|sz[bl[u-2][l-1]])+(l==r?sz[bl[u-1][l+1]]:0)),G(sz[bl[u-2][l-1]]+(sz[bl[u][l-2]]|sz[bl[u-1][l-2]])+(u==d?sz[bl[u+1][l-1]]:0));
if(u>1&&r<n&&!a[u-1][r+1])G(sz[bl[u-1][r+2]]+(sz[bl[u-2][r]]|sz[bl[u-2][r+1]])+(l==r?sz[bl[u-1][r-1]]:0)),G(sz[bl[u-2][r+1]]+(sz[bl[u][r+2]]|sz[bl[u-1][r+2]])+(u==d?sz[bl[u+1][r+1]]:0));
if(d<n&&l>1&&!a[d+1][l-1])G(sz[bl[d+1][l-2]]+(sz[bl[d+2][l]]|sz[bl[d+2][l-1]])+(l==r?sz[bl[d+1][l+1]]:0)),G(sz[bl[d+2][l-1]]+(sz[bl[d][l-2]]|sz[bl[d+1][l-2]])+(u==d?sz[bl[d-1][l-1]]:0));
if(d<n&&r<n&&!a[d+1][r+1])G(sz[bl[d+1][r+2]]+(sz[bl[d+2][r]]|sz[bl[d+2][r+1]])+(l==r?sz[bl[d+1][r-1]]:0)),G(sz[bl[d+2][r+1]]+(sz[bl[d][r+2]]|sz[bl[d+1][r+2]])+(u==d?sz[bl[d-1][r+1]]:0));
}
printf("%d",ans);
}
评论 (0)
