POI1999
T3 空立方体问题 一道线段树扫描线的模板题，只要把一维排序，一维建线段树，一维做权值，很明显这个权值是单调不降的，很好维护；但是BZOJ上的翻译有些坑，如果体积一样要取x尽量小的，再相同取y尽量小的，就需要多写一些；而且这题还要离散化，非常恶心；更恶心的是这题$n\leq5000$，根本不需要线段树，直接暴力就可以了。。所以我把这题数据的加强版放到OJ上了，欢迎来肏
#include<cstdio>
#include<algorithm>
#define W 1000000
#define N 400400
using namespace std;typedef long long LL;
int i,j,n,ux,uy,uz,cnt,v[N],w[3];LL ans;
struct P{int x,y,z;}p[N];
struct T{LL lv,rv,r,v,la,a,b;}t[N<<2];
bool cmp(P a,P b){return a.z<b.z;}
void add(int k,int z){t[k].b=t[k].la=t[k].lv=t[k].rv=z;t[k].v=t[k].r*z;t[k].a=t[k].r;}
void pd(int k){if(t[k].la)add(k<<1,t[k].la),add(k<<1|1,t[k].la),t[k].la=0;}
void ps(int k){
t[k].v=max(t[k<<1].v,t[k<<1|1].v);
if(t[k<<1].v>t[k<<1|1].v||t[k<<1].v==t[k<<1|1].v&&t[k<<1].a<t[k<<1|1].a)t[k].a=t[k<<1].a,t[k].b=t[k<<1].b;else t[k].a=t[k<<1|1].a,t[k].b=t[k<<1|1].b;
t[k].lv=t[k<<1].lv;t[k].rv=t[k<<1|1].rv;
}
void cha(int k,int l,int r,int x,int z){
if(x>cnt)return;
pd(k);if(t[k].lv<=z)return;
if(t[k].rv>z&&x<=l){add(k,z);return;}
int mid=l+r>>1;if(x<=mid)cha(k<<1,l,mid,x,z);
cha(k<<1|1,mid+1,r,x,z);ps(k);
}
void bt(int k,int l,int r){
t[k].a=t[k].r=v[r];t[k].b=t[k].lv=t[k].rv=W;t[k].v=t[k].r*W;
if(l==r)return;int mid=l+r>>1;
bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
}
void get(LL w,int x,int y,int z){if(w>ans||w==ans&&x<ux||w==ans&&x==ux&&y<uy)ans=w,ux=x,uy=y,uz=z;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z),v[i]=p[i].x;
p[++n]=P{W,W,W};v[n]=W;sort(p+1,p+n+1,cmp);sort(v+1,v+n+1);cnt=unique(v+1,v+n+1)-(v+1);
for(bt(1,1,cnt),i=1;i<=n;i++)get(t[1].v*p[i].z,t[1].a,t[1].b,p[i].z),cha(1,1,cnt,lower_bound(v+1,v+cnt+1,p[i].x)-v+1,p[i].y);
printf("%d %d %d",ux,uy,uz);
}
T4 多边形之战 $n$是偶数显然可行，我切一个使得答案不能让你切，你就输了
$n$是奇数只有黑色三角形在最外面能赢，否则下一步$n$就变成偶数了
#include<cstdio>
#include<algorithm>
int n,b[3];
int main(){
scanf("%d%d%d%d",&n,&b[0],&b[1],&b[2]);std::sort(b+1,b+2+1);
puts((((b[1]-b[0]==n-2)||(b[2]-b[1]==n-2)||(b[2]-b[0]==2))||(!(n&1)))?"TAK":"NIE");
}
T6 洞穴攀行 傻逼网络流
#include<cstdio>
#define N 222
#define M 44444
#define inf 1e9
int n,m,k,s,t,u,x,tot,flow,now,i,tmp,fir[N],pre[N],cur[N],nb[N],d[N],la[M],va[M],ne[M];
void ins(int x,int y,int z){
la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;
la[++tot]=x;va[tot]=0;ne[tot]=fir[y];fir[y]=tot;
}
int main(){
for(scanf("%d",&n),s=tot=i=1,t=n;i<n;i++)for(scanf("%d",&k);k--;){
scanf("%d",&x);if(i==1||x==n)ins(i,x,1);else ins(i,x,inf);
}
for(i=1;i<=t;i++)cur[i]=fir[i];u=s;nb[0]=t;
while(d[s]<t){
if(u==t){
for(now=inf,i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];
for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=now,va[cur[i]^1]+=now;
flow+=now;
}
for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
if(0==--nb[d[u]])break;
for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])if(d[la[i]]<tmp&&va[i])tmp=d[la[i]];
++nb[d[u]=tmp+1];
if(u!=s)u=pre[u];
}
}
printf("%d",flow);
}
T9 树的染色问题 傻逼树形DP
#include<cstdio>
#include<algorithm>
#define N 10100
int i,tot,l[N],r[N],f[N][3],g[N][3];
using namespace std;
void get(int x){
char ch=getchar();
if(ch=='1'||ch=='2')get(l[x]=++tot);
if(ch=='2')get(r[x]=++tot);
f[x][0]=max(f[l[x]][1]+f[r[x]][2],f[l[x]][2]+f[r[x]][1])+1;
f[x][1]=max(f[l[x]][2]+f[r[x]][0],f[l[x]][0]+f[r[x]][2]);
f[x][2]=max(f[l[x]][0]+f[r[x]][1],f[l[x]][1]+f[r[x]][0]);
g[x][0]=min(g[l[x]][1]+g[r[x]][2],g[l[x]][2]+g[r[x]][1])+1;
g[x][1]=min(g[l[x]][2]+g[r[x]][0],g[l[x]][0]+g[r[x]][2]);
g[x][2]=min(g[l[x]][0]+g[r[x]][1],g[l[x]][1]+g[r[x]][0]);
}
int main(){
get(tot=1);
printf("%d %d",max(f[1][0],max(f[1][1],f[1][2])),min(g[1][0],min(g[1][1],g[1][2])));
}
T10 地图 傻逼DP，算代价利用前面条件算就行了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 3030
using namespace std;
int n,m,i,j,k;long long f[N][11],g[N][N],a[N];
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+n+1);
for(i=1;i<=n;i++)for(j=i-1;j;j--)g[j][i]=g[j+1][i]+a[(i+j+1)/2]-a[j];
for(memset(f,63,sizeof(f)),f[0][0]=0,i=1;i<=n;i++)
for(j=1;j<=m;j++)for(k=0;k<=i;k++)f[i][j]=min(f[i][j],f[k][j-1]+g[k+1][i]);
printf("%d",f[n][m]);
}
T11 原始生物 连好边，就是用最少的边使该图存在欧拉回路，把每个联通的分量分开处理，一个有向图存在欧拉回路的充要条件是图中有且只有一个连通分支且每一点的出度等于入度。假设图中只存在一个连通分支，则至少增加的边数k＝每个点出度入度之差的绝对值之和的二分之一。如果图中存在多个连通分支，则对于每个连通分支，按一个连通分支的方法求其至少的加边数，再加上本来就存在欧拉回路的连通分支的个数，就是k的值
#include<cstdio>
#define N 1010
#define inf 1e9
int n=1000,m,i,x,y,p,ans,fa[N],du[N],a[N];bool v[N];
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
for(i=1;i<=n;i++)fa[i]=i,a[i]=inf;
for(scanf("%d",&m),ans=m;m--;)scanf("%d%d",&x,&y),fa[gf(x)]=gf(y),v[x]=v[y]=1,du[x]--,du[y]++;
for(i=1;i<=n;i++)if(v[i]){
if(a[p=gf(i)]==inf)a[p]=0;
if(du[i]>0)a[p]+=du[i];
}
for(i=1;i<=n;i++)if(a[i]!=inf)ans+=a[i]+(a[i]==0?1:0);
printf("%d",ans);
}
T13 降水 并查集从小到大把点加入，如果小的点没有连在边缘上，则对答案贡献$sz[p]*(h[q]-h[p])$，累加即可。。写挂了两发真不爽。。
#include<cstdio>
#include<vector>
#define N 10100
using namespace std;
int n,m,i,j,x,p,fa[N],sz[N],h[N],ans;bool b[N],u[N];
vector<int>v[N];vector<int>::iterator it;
int get(int x,int y){return x*m-m+y;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void uni(int x,int y){
int p=gf(x),q=gf(y);if(p==q)return;
fa[p]=q;sz[q]+=sz[p];b[q]|=b[p];
if(!b[p])ans+=sz[p]*(h[q]-h[p]);
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
scanf("%d",&p);
x=get(i,j);v[p].push_back(x);
fa[x]=x;sz[x]=1;h[x]=p;
if(i==1||i==n||j==1||j==m)b[x]=1;
}
for(i=1;i<=10000;i++)
for(it=v[i].begin();it!=v[i].end();it++){
x=*it;u[x]=1;
if(x%m!=1&&u[x-1])uni(x-1,x);
if(x%m&&u[x+1])uni(x+1,x);
if(x>m&&u[x-m])uni(x-m,x);
if(x+m<=n*m&&u[x+m])uni(x+m,x);
}
printf("%d",ans);
}
T14 步兵问题 每个点建一个新点$i'$，用$f[i][j]$表示把$i~j$区间合并的合法性，f[i][j]|=f[i][k]&&f[k][j]&&(map[i][k]||map[j][k])，最后对于每个点i,如果f[i][i']则合法
#include<cstdio>
#define N 222
int n,m,i,j,a[N][N];char s[N];bool f[N][N],v[N][N];
bool dp(int l,int r){
if(r-l<=1)return 1;
if(v[l][r])return f[l][r];
v[l][r]=1;
for(int i=l+1;i<r;i++)if(dp(l,i)&&dp(i,r)&&(a[l][i]||a[r][i]))return f[l][r]=1;
return f[l][r]=0;
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%s",s+1),j=1;j<=n;j++)
a[i][j]=a[i][j+n]=a[i+n][j]=a[i+n][j+n]=s[j]-'0';
for(dp(1,2*n),i=1;i<=n;i++)if(dp(i,i+n))m++;
for(printf("%d\n",m),i=1;i<=n;i++)if(f[i][i+n])printf("%d\n",i);
}
评论 (0)
