[BZOJ 1086][SCOI2005]王室联邦

最近想捉一下树分块,这道题肯定是要做的啦~

这个题的方法就是蜜汁贪心,在其他树分块的题目中也有应用。

代码:

/**************************************************************
    Problem: 1086
    User: danihao123
    Language: C++
    Result: Accepted
    Time:16 ms
    Memory:880 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
using std::stack;
const int maxn=1005;
const int maxm=maxn*2;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
  graph_cnt++;
  next[graph_cnt]=first[u];
  first[u]=graph_cnt;
  to[graph_cnt]=v;
}
 
int belong[maxn],cap[maxn];
int block_cnt=0;
stack<int> S;
int B;
void DFS(int u,int fa){
  int siz=S.size();
  for(int i=first[u];i;i=next[i]){
    int v=to[i];
    if(v==fa){
      continue;
    }
    DFS(v,u);
    if((S.size()-siz)>=B){
      block_cnt++;
      cap[block_cnt]=u;
      while(S.size()>siz){
        int x=S.top();S.pop();
        belong[x]=block_cnt;
      }
    }
  }
  S.push(u);
}
int main(){
  register int i;
  bool OK;
  int n,u,v;
  scanf("%d%d",&n,&B);
  for(i=1;i<=(n-1);i++){
    scanf("%d%d",&u,&v);
    AddEdge(u,v);
    AddEdge(v,u);
  }
  if(n<B){
    puts("0");
    return 0;
  }
  DFS(1,0);
  while(!S.empty()){
    int x=S.top();S.pop();
    belong[x]=block_cnt;
  }
  printf("%d\n",block_cnt);
  OK=false;
  for(i=1;i<=n;i++){
    if(OK){
      putchar(' ');
    }
    OK=true;
    printf("%d",belong[i]);
  }
  putchar('\n');
  OK=false;
  for(i=1;i<=block_cnt;i++){
    if(OK){
      putchar(' ');
    }
    OK=true;
    printf("%d",cap[i]);
  }
  putchar('\n');
  return 0;
}

[BZOJ 1217]消防局的设立

很明显可以看出消防局距离为5的话最划算……然后贪心就行了,顺便注意下根节点处理

代码:

/**************************************************************
    Problem: 1217
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:844 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int ans=0;
int d[maxn];
void dfs(int x,int fa=-1){
    int maxq=-maxn,minq=maxn;
    int i;
    GRAPH_REP(i,x)
        if(to[i]!=fa){
            dfs(to[i],x);
            maxq=max(maxq,d[to[i]]);
            minq=min(minq,d[to[i]]);
        }
    if(minq+maxq<=3)
        d[x]=minq+1;
    else
        d[x]=maxq+1;
    if(minq==maxn)
        d[x]=3;
    if(d[x]==5){
        ans++;
        d[x]=0;
    }else{
        if(fa==-1 && d[x]>2)
            ans++;
    }
}
 
int main(){
    int n,v;
    register int i;
    scanf("%d",&n);
    for(i=1;i<=(n-1);i++){
        scanf("%d",&v);
        AddEdge(i+1,v);
        AddEdge(v,i+1);
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

[CF 711D]Directed Roads

这个题啊……其实不难。

首先你注意,他告诉你你可以把边弄反。

其次注意,这个图不一定就有一个环。

然后每个环的取反法有[tex]2^x[/tex]种(假设环中有[tex]x[/tex]条边),但是空集不行,全集也不行,因此每个环爆掉的方案有[tex]2^x-2[/tex]种。然后环之外的边随便弄,乘法原理乱搞即可。

然后你是不是感觉这个题似曾相识?是的似乎这个题就是NOIP D1T2的翻版。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=200001;
const ll MOD=1000000007;
int G[maxn];
int in[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
    register int i;
    bool ans=false;
    for(i=1;i<=n;i++){
        if(!vis[i] && !in[i]){
            ans=true;
            in[G[i]]--;
            vis[i]=true;
            G[i]=0;
        }
    }
    return ans;
}
ll dfs(int x,int y){
    if(x==y && vis[x]){
        return 0;
    }else{
        vis[x]=true;
        return dfs(G[x],y)+1;
    }
}
ll pow_mod(ll a,ll b){
    if(!b){
        return 1;
    }else{
        ll ans=pow_mod(a,b/2);
        ans=ans*ans%MOD;
        if(1&b){
            ans=(ans*(a%MOD))%MOD;
        }
        return ans;
    }
}
inline ll solve(){
	register int i;
	register ll Huan,temp=0,ans=1;
	while(jianz());
	for(i=1;i<=n;i++)
		if(!vis[i]){
			Huan=dfs(i,i);
			temp+=Huan;
			ans=(ans*(pow_mod(2,Huan)+MOD-2))%MOD;
		}
	ans=(ans*pow_mod(2,n-temp))%MOD;
	return ans;
}
int main(){
	register int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&G[i]);
		in[G[i]]++;
	}
	printf("%I64d\n",solve());
	return 0;
}

[BZOJ 4325]斗地主

是的你没有看错!就是这道坑提!

这题基本是个半成品,歧义真的,真的,真的很大。

至于方法?我们注意到同样的牌能一起出就尽可能避免拆开。例如,四带二分成炸弹加两单点(对子)肯定不好。三带一或者三带二也如此。先考虑不出顺子的最优解,并据此进行深度限制,再考虑出顺子。

然后,DFS暴搜即可。

顺便讲一下坑点:

  1. 顺子可以有A。
  2. 三带一,三带二,四代二都可以有头。但是大小头要区别开。

代码:

/**************************************************************
    Problem: 4325
    User: danihao123
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans;
int cnt[5],hand[15];
void dfs(int x){
    if(x>ans)
        return;
    int i,j,rest=0;
    memset(cnt,0,sizeof(cnt));
    for(i=0;i<=14;i++){
        cnt[hand[i]]++;
    }
    while(cnt[4]>0){
        cnt[4]--;
        rest++;
        if(cnt[2]>=2)
            cnt[2]-=2;
        else
            if(cnt[1]>=2)
                cnt[1]-=2;
    }
    while(cnt[3]>0){
        cnt[3]--;
        rest++;
        if(cnt[2]>0)
            cnt[2]--;
        else
            if(cnt[1]>0)
                cnt[1]--;
    }
    if(hand[0] && hand[1] && cnt[1]>=2)
        rest--;
    ans=min(ans,cnt[1]+cnt[2]+rest+x);
    for(i=3;i<=10;i++){
        for(j=i;j<=14 && hand[j];j++){
            hand[j]--;
            if(j-i+1>=5)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]++;
    }
    for(i=3;i<=12;i++){
        for(j=i;j<=14 && hand[j]>=2;j++){
            hand[j]-=2;
            if(j-i+1>=3)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=2;
    }
    for(i=3;i<=13;i++){
        for(j=i;j<=14 && hand[j]>=3;j++){
            hand[j]-=3;
            if(j-i+1>=2)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=3;
    }
}
int main(){
    int T,u,v;
    register int i;
    scanf("%d%d",&T,&n);
    while(T--){
        ans=n;
        memset(hand,0,sizeof(hand));
        for(i=1;i<=n;i++){
            scanf("%d%d",&u,&v);
            if(!u){
                if(v==2)
                    hand[1]++;
                else
                    hand[0]++;
            }else{
                if(u==1)
                    hand[14]++;
                else
                    hand[u]++;
            }
        }
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

[洛谷 P2661]信息传递

bi了doge了……图论基本不会了……

这提可以直接循环删除所有入度为0的边,这样就只剩环了。然后DFS嘿嘿嘿。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200001;
int G[maxn];
int to[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
    register int i;
    bool ans=false;
    for(i=1;i<=n;i++){
        if(!vis[i] && !to[i]){
            ans=true;
            to[G[i]]--;
            vis[i]=true;
            G[i]=0;
        }
    }
    return ans;
}
int dfs(int x,int y){
    if(x==y && vis[x]){
        return 0;
    }else{
        vis[x]=true;
        return dfs(G[x],y)+1;
    }
}
int getchen(){
    register int i,ans=0x5ffffff;
    while(jianz());
    for(i=1;i<=n;i++)
        if(!vis[i])
            ans=min(ans,dfs(i,i));
    return ans;
}
int main(){
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&G[i]);
        to[G[i]]++;
    }
    printf("%d\n",getchen());
    return 0;
}

[BZOJ 1232]安慰奶牛

这题要用到DFS欧拉遍历树(胡编词汇)的一个特征:每一条边都经过2遍。这样似乎每个边度数就可以确定了,然后……

但是,起点也要算啊……

代码:

/**************************************************************
    Problem: 1232
    User: danihao123
    Language: C++
    Result: Accepted
    Time:248 ms
    Memory:2056 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10001,maxm=100001;
// Djoin set
int p[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void union_set(int x,int y){
    p[find_set(x)]=find_set(y);
}
bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
// Graph
struct Edge{
    int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
    return a.d<b.d;
}
int n,m;
int c[maxn];
Edge E[maxm];
int mst(){
    register int i,cnt=0,ans=0;
    for(i=1;i<=n;i++)
        p[i]=i;
    sort(E,E+m,cmp);
    for(i=0;cnt<(n-1) && i<m;i++){
        if(!is_same(E[i].u,E[i].v)){
            union_set(E[i].u,E[i].v);
            ans+=E[i].d;
            cnt++;
        }
    }
    return ans;
}
int main(){
    register int i,kkk=0x5fffffff;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&c[i]);
        kkk=min(kkk,c[i]);
    }
    for(i=0;i<m;i++){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
        E[i].d+=E[i].d+c[E[i].u]+c[E[i].v];
    }
    printf("%d\n",kkk+mst());
    return 0;
}

[BZOJ 1603]打谷机

啊啊啊啊我又活过来了……

然而这也就是一道脑残题……

代码:

/**************************************************************
    Problem: 1603
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1001;
struct Edge{
    int u,v;
    bool type;
};
vector<Edge> edges;
vector<int> G[maxn];
void Add_Edge(int u,int v,bool type){
    edges.push_back((Edge){u,v,type});
    G[u].push_back(edges.size()-1);
}
bool ans[maxn],vis[maxn];
void dfs(int x){
    vis[x]=true;
    int i;
    for(i=0;i<G[x].size();i++){
        Edge& e=edges[G[x][i]];
        if(!vis[e.v]){
            ans[e.v]=e.type?(!ans[x]):ans[x];
            dfs(e.v);
        }
    }
}
int main(){
    register int i;
    int n,u,v,d;
    scanf("%d",&n);
    for(i=0;i<(n-1);i++){
        scanf("%d%d%d",&u,&v,&d);
        Add_Edge(u,v,(bool)d);
        Add_Edge(v,u,(bool)d);
    }
    dfs(1);
    printf("%d\n",ans[n]?1:0);
    return 0;
}

[BZOJ 1053]反素数

终于A了……

此题坑点多~

据说只需要预处理12个素数,然而我预处理了4648个……so sad

然后DFS就可以了

我无力吐槽了……我就是智商感人啊

代码:

继续阅读