2
20
2015
0

Bzoj 题一览 IV [2015.2.12 - 2015.3.2]

也即寒假?..

2015.2.18

Bzoj 1143 [CTSC2008]祭祀 river
流动性->传递闭包(二元组关系的传递)->二分图最大独立子集
求第二问题面?..
#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
    
const int Inf = 20150218 , N = 110;
 
#define Rep(i,x,y) for (i=x;i<=y;i++)
  
int n,m,A[N][N],T=0,i,j,k,x,y,Pr[N];
bool V[N];
 
bool Dfs(int x) {
    int i;
    Rep(i,1,n) if (!V[i]&&A[x][i]) { V[i]=1; if (!Pr[i]||Dfs(Pr[i])) { Pr[i]=x; return 1; } }
    return 0;
}
 
int main(){
    scanf("%d%d",&n,&m);
    Rep(i,1,m) { scanf("%d%d",&x,&y); A[x][y]=1; }
    Rep(i,1,n) Rep(j,1,n) Rep(k,1,n) A[i][j]|=(A[i][k]&A[k][j]);
    Rep(i,1,n) { memset(V,0,sizeof(V)); if (Dfs(i)) ++T; }
    printf("%d\n",n-T);
    return 0;
}
 
2015.2.19
 
Bzoj 1196  [HNOI2006]公路修建问题
答案具有单调性二分花费最多的公路的长度
Kruskal验证答案合法性
·一级公路条数是否符合要求
·并查集维护图的连通性(生成树)
#include <cstdio>
#include <algorithm>
  
using namespace std;
     
const int Inf = 20150219 , N = 20010;
  
#define Rep(i,x,y) for (i=x;i<=y;i++)
   
int n,R,Ans,K,m,F[N/2],L,x[N],y[N],C1[N],C2[N],i,j,Mid;
bool used[N];
 
int Find(int x) { return F[x]==x?x:F[x]=Find(F[x]); }
 
bool Ok(int C) {
    int i,k=0,p,q;
    Rep(i,1,n) F[i]=i;
    Rep(i,1,m) used[i]=0;
    Rep(i,1,m) 
       if (C1[i]<=C) { 
          p=Find(x[i]); q=Find(y[i]); 
           if (p!=q) F[p]=q,++k,used[i]=1;
        }
    if (k<K) return 0;
    Rep(i,1,m) {
        if (k==n-1) break;
        if (used[i]) continue;
        if (C2[i]<=C) {
            p=Find(x[i]); q=Find(y[i]); //其实C1连过 C2必然不会连
            if (p!=q) F[p]=q,++k;
        }
    }
    return k==n-1;
}
 
int main(){
    scanf("%d%d%d",&n,&K,&m);
    Rep(i,1,m-1) scanf("%d%d%d%d",&x[i],&y[i],&C1[i],&C2[i]);
    L=1; R=30001;
    while (L+1<R) { Mid=(L+R)>>1; if (Ok(Mid)) R=Mid,Ans=Mid; else L=Mid+1; }
    if (Ok(L)) Ans=L;
    printf("%d\n",Ans);
    return 0;
}
 
Bzoj 1218 [HNOI2003]激光炸弹
枚举前缀和 O(n^2) 
可能是二维线段树动态开结点可以做到 O(nlog2(n)^2)
#include <cstdio>
#include <algorithm>
 
using namespace std;
    
const int Inf = 20150219 , N = 5110;
 
#define Rep(i,x,y) for (i=x;i<=y;i++)
  
int n,R,T,A[N+1][N+1],i,j,x,y,z;
 
int main(){
    scanf("%d%d",&n,&R);
    Rep(i,1,n) { scanf("%d%d%d",&x,&y,&z); ++x; ++y; A[x][y]+=z;  }
    Rep(i,1,N) Rep(j,1,N) A[i][j]+=A[i-1][j]+A[i][j-1]-A[i-1][j-1];
    Rep(i,R,N) Rep(j,R,N) T=max(T,A[i][j]-A[i-R][j]-A[i][j-R]+A[i-R][j-R]);
    printf("%d\n",T);
    return 0;
}
 
Bzoj 1197 [HNOI2006]花仙子的魔法
http://vfleaking.blog.163.com/blog/static/174807634201321193348312/
注意空间维度上的降维
F[i][1]=2 F[1][i]=2 * i
F[i][j]=F[i][j-1]+F[i-1][j-1]
#include <iostream>
#include <algorithm>
 
using namespace std;
    
const int Inf = 20150219 , N = 101;
 
#define Rep(i,x,y) for (i=x;i<=y;i++)
 
int n,m,i,j;
long long F[N][N];
 
int main(){
    cin>>m>>n;
    Rep(i,1,n) F[i][1]=2;
    Rep(i,1,m) F[1][i]=2 * i;
    Rep(i,2,n) Rep(j,2,m) F[i][j]=F[i][j-1]+F[i-1][j-1];
    cout<<F[n][m]<<endl;
    return 0;
}

 

Category: 题目 | Tags: 二分 数学 图论 二分图 并查集 数据范围认识 | Read Count: 315

登录 *


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