danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29173

[BZOJ 1086][SCOI2005]王室联邦

2017年2月01日 20:28 | Comments(0) | Category:题解 | Tags:

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

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

代码:

/**************************************************************
    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 1009][HNOI2008]GT考试

2017年2月01日 17:05 | Comments(0) | Category:题解 | Tags:

好劲啊这题……

首先先想DP的做法,我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex],有多少种方案使得追加上一个数后匹配[tex][1,j][/tex],这个用KMP可以很方便的求出(事实上暴力也可以)

然后再来看DP的做法,转移方程大致是这样的:

[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]

但是n非常大,这么做注定要TLE。

不过看这个转移方程,是不是和矩阵乘法的定义很像?是的。

我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值,我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现:

[tex]D_i\times P=D_{i+1}[/tex]

由于矩阵乘法满足结合律,所以:

[tex]D_n=D_0\times P^n[/tex]

很明显可以快速幂搞出来。

代码:

/**************************************************************
    Problem: 1009
    User: danihao123
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
 
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    register int i,j,k;
    Matrix C;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
    Matrix a,temp;
    register int i;
    CL_ARR(a,0);
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    REP(i,m){
        temp[i][i]=1;
    }
    while(p){
        if(1&p){
            MatrixMul(temp,a,m,m,m,temp);
        }
        p>>=1;
        MatrixMul(a,a,m,m,m,a);
    }
    CP_ARR(temp,res);
}
 
char buf[25];
int f[25];
int main(){
    register int i,u,j;
    register ull ret=0;
    ull n;
    int m;
    Matrix ans,P;
    scanf("%llu%d%llu",&n,&m,&MOD);
    scanf("%s",buf+1);
    CL_ARR(ans,0);
    ans[0][0]=1;
    CL_ARR(P,0);
    P[0][0]=9;P[0][1]=1;
    // f[0]=f[1]=0;
    for(i=1;i<m;i++){
        u=f[i];
        while(u && buf[u+1]!=buf[i+1]){
            u=f[u];
        }
        if(buf[u+1]==buf[i+1]){
            f[i+1]=u+1;
        }else{
            f[i+1]=0;
        }
        for(j=0;j<10;j++){
            u=i;
            while(u && buf[u+1]!=j+'0'){
                u=f[u];
            }
            if(buf[u+1]==j+'0'){
                P[i][u+1]=(P[i][u+1]+1)%MOD;
            }else{
                P[i][0]=(P[i][0]+1)%MOD;
            }
        }
    }
    MatrixPow(P,m,n,P);
    MatrixMul(ans,P,1,m,m,ans);
    for(i=0;i<m;i++){
        ret=(ret+ans[0][i])%MOD;
    }
    printf("%llu\n",ret);
    return 0;
}

[BZOJ 1798]维护序列

2016年12月18日 14:08 | Comments(0) | Category:题解 | Tags:

万年不更的zzs出现了……

这个题以前竟然没做……近几天做了一下,首交竟然unAC……看样子是我真不会线段树了。

这题不难,唯一需要注意的是乘法标记对加法标记也有影响,而且下传要乘法优先。

代码(警告:此代码exciting):

/**************************************************************
    Problem: 1798
    User: danihao123
    Language: C++
    Result: Accepted
    Time:7696 ms
    Memory:10980 kb
****************************************************************/
 
#include <cstdio>
typedef long long ll;
const int maxn=100005;
ll ha;
struct Node{
    ll sumv;
    int L,R;
    ll addv,mulv;
    Node *lc,*rc;
    Node(ll v,int pos){
        sumv=v%ha;
        addv=0;
        mulv=1;
        L=R=pos;
        lc=rc=NULL;
    }
    Node(Node *l,Node *r,int Le,int Ri){
        sumv=0;
        addv=0;
        mulv=1;
        L=Le;
        R=Ri;
        lc=l;
        rc=r;
    }
    void paint_add(ll v){
        v=v%ha;
        addv=(addv+v)%ha;
        ll add_v=(v*((R-L+1)%ha))%ha;
        sumv=(sumv+add_v)%ha;
    }
    void paint_mul(ll v){
        v=v%ha;
        addv=(addv*v)%ha;
        mulv=(mulv*v)%ha;
        sumv=(sumv*v)%ha;
    }
    void maintain(){
        if(lc!=NULL && rc!=NULL){
            sumv=(lc->sumv+rc->sumv)%ha;
        }
    }
    void pushdown(){
        if(mulv!=1){
            if(lc!=NULL){
                lc->paint_mul(mulv);
            }
            if(rc!=NULL){
                rc->paint_mul(mulv);
            }
            mulv=1;
        }
        if(addv!=0){
            if(lc!=NULL){
                lc->paint_add(addv);
            }
            if(rc!=NULL){
                rc->paint_add(addv);
            }
            addv=0;
        }
    }
};
 
ll A[maxn];
void build_tree(Node* &o,int L,int R){
    if(L==R){
        o=new Node(A[L],L);
    }else{
        int M=L+(R-L)/2;
        Node *lc,*rc;
        build_tree(lc,L,M);
        build_tree(rc,M+1,R);
        o=new Node(lc,rc,L,R);
        o->maintain();
    }
}
Node *root;
int ql,qr;
ll v;
ll query_sum(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        return o->sumv;
    }else{
        int M=L+(R-L)/2;
        ll ans=0;
        if(ql<=M){
            ans=(ans+query_sum(o->lc))%ha;
        }
        if(qr>M){
            ans=(ans+query_sum(o->rc))%ha;
        }
        return ans;
    }
}
void update_add(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        o->paint_add(v);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M){
            update_add(o->lc);
        }
        if(qr>M){
            update_add(o->rc);
        }
        o->maintain();
    }
}
void update_mul(Node *o){
    int L=o->L,R=o->R;
    o->pushdown();
    if(ql<=L && R<=qr){
        o->paint_mul(v);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M){
            update_mul(o->lc);
        }
        if(qr>M){
            update_mul(o->rc);
        }
        o->maintain();
    }
}
 
int main(){
    register int i;
    int n,m,op;
    scanf("%d%lld",&n,&ha);
    // ha=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    build_tree(root,1,n);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d",&op,&ql,&qr);
        if(ha==1){
            if(op==3){
                puts("0");
            }else{
                scanf("%lld",&v);
            }
            continue;
        }
        if(op==1){
            scanf("%lld",&v);
            update_mul(root);
        }else{
            if(op==2){
                scanf("%lld",&v);
                update_add(root);
            }else{
                printf("%lld\n",query_sum(root));
            }
        }
    }
    return 0;
}

[BZOJ 2186]沙拉公主的困惑

2016年10月11日 21:59 | Comments(0) | Category:题解 | Tags:

这个题啊……亦可赛艇!

答案是[tex]\varphi(m!)*n!/m![/tex]。原因很简单,把[tex][1,n!][/tex]分成长度为[tex]m![/tex]的若干段,除去第一段外每一段中与[tex]m![/tex]互质的数[tex]k[/tex]肯定满足[tex](k\bmod m!,m!)=1[/tex](否则,[tex]k[/tex]和[tex]m![/tex]就会有大于一的公因子了)。所以说每一段内与[tex]m![/tex]互质的数都有[tex]\varphi(m!)[/tex]个。

麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数,它的所有因子在前面都有了,只能把他自己贡献出来;如果这个数是质数(假设为[tex]p[/tex]),出了贡献自己以外还会贡献一个[tex](1-1/p)[/tex],最后乘起来就是贡献了[tex]p-1[/tex]。筛一遍素数再递推一下就好辣~

并且……[tex]n-m[/tex]可能非常大,所以说除去[tex]m![/tex]那块要用逆元做。

(顺便说下阶乘也要递推)

代码:

/**************************************************************
    Problem: 2186
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9408 ms
    Memory:166836 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
typedef unsigned long long ull;
const int maxn=10000000;
ull R;
bool vis[maxn+5];
inline void sievePrime(){
    register int i,j,m=sqrt(maxn+0.5);
    for(i=2;i<=m;i++)
        if(!vis[i])
            for(j=i*i;j<=maxn;j+=i)
                vis[j]=true;
}
ull fac[maxn+5];
inline void sieveFac(){
    register int i;
    fac[0]=1%R;
    for(i=1;i<=maxn;i++)
        fac[i]=(fac[i-1]*(i%R))%R;
}
ull phifac[maxn+5];
inline void sievePhiFac(){
    register int i;
    phifac[1]=1%R;
    for(i=2;i<=maxn;i++){
        if(vis[i])
            phifac[i]=(phifac[i-1]*(i%R))%R;
        else
            phifac[i]=(phifac[i-1]*((i%R-1%R+R)%R))%R;
    }
}
void exgcd(ull a,ull b,ull& d,ull& x,ull& y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }else{
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
ull inv(ull a){
    ull d,x,y;
    exgcd(a,R,d,x,y);
    return (x+R)%R;
}
int main(){
    int T;
    int n,m;
    scanf("%d%llu",&T,&R);
    sievePrime();
    sieveFac();
    sievePhiFac();
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%llu\n",(phifac[m]*((fac[n]*inv(fac[m]))%R))%R);
    }
    return 0;
}

[BZOJ 1433]假期的宿舍

2016年9月27日 13:06 | Comments(0) | Category:题解 | Tags:

这几乎是个二分图匹配的裸题了……

不过有很多细节问题,比如说题面里提到的那些。还有多组数据的话注意清理数组。

代码:

/**************************************************************
    Problem: 1433
    User: danihao123
    Language: C++
    Result: Accepted
    Time:68 ms
    Memory:824 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=55;
bool G[maxn][maxn];
int n,m;
int Pei[maxn];
bool vis[maxn];
bool DFS(int x){
    int i;
    for(i=1;i<=m;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!Pei[i] || DFS(Pei[i])){
                Pei[i]=x;
                return true;
            }
        }
    return false;
}
int Hungray(){
    register int i,ans=0;
    memset(Pei,0,sizeof(Pei));
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}
 
int Per[maxn],Bed[maxn];
bool isStudent[maxn],Back[maxn];
int main(){
    int T,N,u,v;
    register int i,j;
    scanf("%d",&T);
    while(T--){
        n=m=0;
        scanf("%d",&N);
        memset(G,0,sizeof(G));
        memset(Per,0,sizeof(Per));
        memset(Bed,0,sizeof(Bed));
        memset(isStudent,0,sizeof(isStudent));
        memset(Back,0,sizeof(Back));
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            isStudent[i]=u;
        }
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            if(isStudent[i]){
                Back[i]=u;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                Bed[i]=++m;
                if(!Back[i]){
                    Per[i]=++n;
                }
            }else{
                Per[i]=++n;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                G[Per[i]][Bed[i]]=true;
            }
            for(j=1;j<=N;j++){
                scanf("%d",&v);
                if(v && isStudent[j]){
                    G[Per[i]][Bed[j]]=true;
                }
            }
        }
        if(Hungray()==n)
            puts("^_^");
        else
            puts("T_T");
    }
    return 0;
}

[BZOJ 1051]受欢迎的牛

2016年9月23日 13:06 | Comments(0) | Category:题解 | Tags:

Tarjan缩点第一题……

很容易想到找出度为0的点(当且仅当这样的点有一个时有解),但是在有环图上这个方法会失效。

处理方法是,用Tarjan的强联通分量算法求出所有SCC,然后把每个SCC缩成一个点,然后再在缩点之后的图上求解即可(这个图是DAG。原因很简单,要是有环还能接着缩)。

代码:

/**************************************************************
    Problem: 1051
    User: danihao123
    Language: C++
    Result: Accepted
    Time:72 ms
    Memory:1692 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=50005;
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 pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn];
stack<int> S;
int dfs_clk=0,scc_cnt=0;
void dfs(int x){
    dfs_clk++;
    pre[x]=low[x]=dfs_clk;
    S.push(x);
    int i,u;
    for(i=first[x];i;i=next[i]){
        u=to[i];
        if(!pre[u]){
            dfs(u);
            low[x]=min(low[x],low[u]);
        }else{
            if(!sccno[u])
                low[x]=min(low[x],pre[u]);
        }
    }
    if(low[x]==pre[x]){
        scc_cnt++;
        sccsiz[scc_cnt]=0;
        while(true){
            u=S.top();
            S.pop();
            sccno[u]=scc_cnt;
            sccsiz[scc_cnt]++;
            if(u==x)
                break;
        }
    }
}
int n;
inline void Tarjan(){
    register int i;
    for(i=1;i<=n;i++)
        if(!pre[i])
            dfs(i);
}
 
bool Out[maxn];
int main(){
    int m,u,v;
    register int i,j,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
    }
    Tarjan();
    for(i=1;i<=n;i++){
        for(j=first[i];j;j=next[j]){
            u=to[j];
            if(sccno[i]!=sccno[u])
                Out[sccno[i]]=true;
        }
    }
    for(i=1;i<=scc_cnt;i++){
        if(!Out[i]){
            if(ans){
                ans=0;
                break;
            }
            ans=sccsiz[i];
        }
    }
    if(n==1)
        ans=0;
    printf("%d\n",ans);
    return 0;
}

[BZOJ 3172]单词

2016年9月17日 13:26 | Comments(0) | Category:题解 | Tags:

首先……出题人语文不太好……估计和我这种语文很差的人还有差距……

这个提的意思是,给你若干个单词,输出每个单词在所有单词(而不是把所有单词连起来)中出现的次数。

然后肯定要AC自动机上失配函数搞一波辣……把BFS序倒过来搜,传递出现次数即可。还有这个题的数据范围好像也比给出的小很多……

代码:

/**************************************************************
    Problem: 3172
    User: danihao123
    Language: C++
    Result: Accepted
    Time:232 ms
    Memory:115080 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=205;
const int maxnode=1*1e6+5;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int cnt[maxnode];
 
namespace ACAutomate{
    // Trie
    const int sigma_size=26;
    int Tree[maxnode][sigma_size];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    void InitAC(){
        siz=0;
        CL_ARR(Tree[0],0);
    }
    int Insert(char *s){
        register int i,n=strlen(s);
        register int u=0,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
            cnt[u]++;
        }
        return u;
    }
    // AC Automate
    int f[maxnode];
    int Q[maxnode];
    void InitFail(){
        register int i,u,x,v,head=0,tail=0;
        f[0]=0;
        REP(i,sigma_size){
            u=Tree[0][i];
            if(u){
                f[u]=0;
                Q[tail++]=u;
            }
        }
        while(head<tail){
            u=Q[head];
            head++;
            REP(i,sigma_size){
                x=Tree[u][i];
                if(!x){
                    continue;
                }
                Q[tail++]=x;
                v=f[u];
                while(v && !Tree[v][i])
                    v=f[v];
                f[x]=Tree[v][i];
            }
        }
        for(i=tail-1;i>=0;i--)
            cnt[f[Q[i]]]+=cnt[Q[i]];
    }
};
 
char buf[maxnode];
int pos[maxn];
int main(){
    int n;
    register int i;
    scanf("%d",&n);
    ACAutomate::InitAC();
    REP_B(i,n){
        scanf("%s",buf);
        pos[i]=ACAutomate::Insert(buf);
    }
    ACAutomate::InitFail();
    REP_B(i,n){
        printf("%d\n",cnt[pos[i]]);
    }
    return 0;
}

[BZOJ 1212]L语言

2016年9月15日 15:06 | Comments(0) | Category:题解 | Tags:

这个感觉本质上和那个Remember a Word很像吧……

不过这个只是求最长可行前缀,递推即可。

代码:

/**************************************************************
    Problem: 1212
    User: danihao123
    Language: C++
    Result: Accepted
    Time:660 ms
    Memory:45072 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1048581;
const int maxW=4005,maxL=105;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
 
vector<int> AnsList;
namespace Trie{
    const int maxnode=400005;
    const int sigma_siz=26;
    int Tree[maxnode][sigma_siz];
    int val[maxnode];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    inline void InitTrie(){
        siz=0;
        val[0]=0;
        CL_ARR(Tree[0],0);
    }
    void Insert(char *s,int v){
        register int u=0,n=strlen(s);
        register int i,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                val[siz]=0;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
        }
        val[u]=v;
    }
    void Query(char *s,int len){
        register int i,c,u=0;
        AnsList.clear();
        REP(i,len){
            if(!s[i])
                break;
            c=idx(s[i]);
            if(!Tree[u][c])
                break;
            u=Tree[u][c];
            if(val[u])
                AnsList.push_back(val[u]);
        }
    }
};
 
char Text[maxn];
int len[maxW];
char buf[maxL];
bool d[maxn];
int main(){
    int n,m;
    int length;
    register int i,j,k;
    bool flag;
    Trie::InitTrie();
    scanf("%d%d",&n,&m);
    REP_B(i,n){
        scanf("%s",buf);
        len[i]=strlen(buf);
        Trie::Insert(buf,i);
    }
    REP_B(i,m){
        scanf("%s",Text);
        length=strlen(Text);
        CL_ARR(d,0);
        d[0]=true;
        for(j=0;j<=length;j++){
            if(d[j]){
                Trie::Query(Text+j,length-j);
                REP(k,AnsList.size()){
                    d[j+len[AnsList[k]]]=true;
                }
            }
        }
        flag=false;
        for(j=length;j>=0;j--){
            if(d[j]){
                flag=true;
                printf("%d\n",j);
                break;
            }
        }
        if(!flag)
            puts("0");
    }
    return 0;
}

[BZOJ 1217]消防局的设立

2016年9月10日 19:36 | Comments(0) | Category:题解 | Tags:

很明显可以看出消防局距离为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;
}

[BZOJ 1191]超级英雄

2016年9月04日 19:18 | Comments(0) | Category:题解 | Tags:

看样子是裸的二分图匹配。

不过注意,选手按顺序答题,只要有一个题打不下来,就淘汰了。这个要做特殊处理,这样的话好像匈牙利算法就比较方便了。

代码:

/**************************************************************
    Problem: 1191
    User: danihao123
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:1812 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1005;
bool G[maxn][maxn];
int Pei[maxn];
bool vis[maxn];
int n,m;
bool DFS(int x){
    int i;
    for(i=0;i<n;i++){
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!Pei[i] || DFS(Pei[i])){
                Pei[i]=x;
                return true;
            }
        }
    }
    return false;
}
inline int Hungray(){
    register int i,ans=0;
    for(i=1;i<=m;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
        else
            break;
    }
    return ans;
}
int main(){
    int u,v;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        G[i][u]=true;
        G[i][v]=true;
    }
    printf("%d\n",Hungray());
    return 0;
}