2012 ACM/ICPC 长春赛区网络赛解题报告汇总

九月 8th, 2012 | Posted by diaorui in ICPC 2012 亚洲区 | 信息聚合 | 解题报告
欢迎转载,转载请注明出处。




针对2012 ACM/ICPC 长春赛区9月8日网络赛,本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
非常感谢主办方对本汇总贴提供的支持。

题目链接

A A Simple Problem with Integers (HDU 4267)
数据结构
http://blog.csdn.net/kksleric/article/details/7958600
http://blog.csdn.net/acm_cxlove/article/details/7958633
http://blog.csdn.net/swrdlgc/article/details/7958615
http://www.cnblogs.com/staginner/archive/2012/09/08/2677023.html
http://www.cnblogs.com/programCaiCai/archive/2012/09/08/HDU4267.html
http://www.acforfun.com/?p=86
http://blog.csdn.net/diannaok/article/details/7959423

B Alice and Bob (HDU 4268)
贪心+数据结构
http://blog.csdn.net/troy_cornelius/article/details/7958821
http://blog.csdn.net/swrdlgc/article/details/7958615
http://www.cnblogs.com/programCaiCai/archive/2012/09/08/HDU4268.html
http://www.cnblogs.com/Yu2012/archive/2012/09/09/2677288.html

C Defend Jian Ge (HDU 4269)
模拟
http://zhyu.me/acm/hdu-4269.html
http://hi.baidu.com/buaa_babt/item/a42588e604155b1f570f1db4
http://blog.csdn.net/acceptedxukai/article/details/7959708
http://lujunda.tk/2012/09/09/hdu4269%E6%A8%A1%E6%8B%9F-defend-jian-ge/

D Dynamic Lover (HDU 4270)
后缀自动机
http://www.acforfun.com/?p=98
标程:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cassert>
using namespace std;
const int Maxn=200010;
struct Node
{
    int next[30],deep,fail,s,pos;
    void clear()
    {
        memset(next,0,sizeof(next));
        deep=fail=s=0;
    }
}node[Maxn<<1];
int size,end;
bool dlt[Maxn<<1];
int ID[Maxn];;
int total,len;
void init()
{
    fill(node[0].next,node[0].next+30,1);
    node[0].deep=-1;
    node[1].clear();
    end=1,size=2;
    total=len=1;
    memset(dlt,0,sizeof(dlt));
    ID[0]=1;
}
bool isDlt(int x)
{
    return x==0||dlt[node[x].s];
}
void addNode(int c,int s)
{
    int p=size++;node[p].clear();node[p].s=s,node[p].deep=node[end].deep+1;ID[len]=p;
    node[p].pos=len++;
    for(;isDlt(node[end].next[c]);end=node[end].fail)
        node[end].next[c]=p;
    int p1=node[end].next[c];
    if(node[p1].deep==node[end].deep+1)node[p].fail=p1;
    else
    {
        int p2=size++;node[p2]=node[p1];node[p1].fail=node[p].fail=p2;
        node[p2].deep=node[end].deep+1;
        for(;node[end].next[c]==p1;end=node[end].fail)
            node[end].next[c]=p2;
    }
    end=p;
    assert(size<Maxn+Maxn);
}
void addString(char str[])
{
    for(int i=0;str[i];++i)
        addNode(str[i]-'a'+1,total++);
}
void dltString(int k)
{
    for(int i=1;i<=k;++i)
    {
        dlt[node[ID[len-i]].s]=1;
    }
    end=ID[len-1-k];
    len-=k;
}
bool first;
int dfs(int x,int &l)
{
    if(l==0)return node[x].pos;
    for(int i=0;i<27;++i)
    {
        if(i==0&&first)
        {
            first=0;
            continue;
        }
        if(isDlt(node[x].next[i]))continue;
        l--;
        return dfs(node[x].next[i],l);
    }
    return node[x].pos;
}
int query(int l)
{
    first=1;
    addNode(0,total++);
    int tl=l;
    int id=dfs(1,tl);
    dltString(1);
    l-=tl;
    return id-l+1;
}
char str[Maxn];
int main()
{
    while(scanf("%s",str)!=EOF)
    {
        init();
        addString(str);
        int n;scanf("%d",&n);
        while(n--)
        {
            int x,l;scanf("%d",&x);
            switch(x)
            {
                case 1:scanf("%s",str);addString(str);break;
                case 2:scanf("%d",&l);printf("%d\n",query(l));break;
                case 3:scanf("%d",&l);dltString(l);break;
            }
        }
    }
    return 0;
}

E Find Black Hand (HDU 4271)
DP
http://www.acforfun.com/?p=84
http://www.cnblogs.com/swm8023/archive/2012/09/10/2679447.html

F LianLianKan (HDU 4272)
状态压缩DP,贪心
http://blog.csdn.net/troy_cornelius/article/details/7958735
http://blog.csdn.net/cgl1079743846/article/details/7959566
http://www.cnblogs.com/swm8023/archive/2012/09/10/2679455.html
http://www.cnblogs.com/kuangbin/archive/2012/09/11/2679708.html

G Rescue (HDU 4273)
计算几何模板题。三维凸包。
http://blog.himdd.com/?p=2713
https://github.com/ftiasch/mithril/blob/master/2012-09-08/G.cpp
http://www.cnblogs.com/kuangbin/archive/2012/09/12/2682534.html

H Spy’s Work (HDU 4274)
Tree dfs
http://blog.csdn.net/kksleric/article/details/7958600
http://blog.csdn.net/swrdlgc/article/details/7958615

I Color the Tree (HDU 4275)
思路见本日志下ftiasch所给评论
http://www.acforfun.com/?p=90
标程:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
using namespace std;
typedef long long ll;
const int Maxn=1e5+3;
const ll Mod=1000000007,P=10007;
struct Edge
{
    int to,next;
    Edge(){}
    Edge(int to,int next):to(to),next(next){}
}edge[Maxn<<1];
int box[Maxn],size;
void add(int from,int to)
{
    edge[size]=Edge(to,box[from]);
    box[from]=size++;
}
int n,m;
int degree[Maxn];
int que[Maxn];
int root1,root2;
ll po[Maxn];
void getPo()
{
    po[0]=1;
    for(int i=1;i<Maxn;++i)
        po[i]=po[i-1]*P;
}
void toposort()
{
    int in=0,out=0;
    for(int i=1;i<=n;++i)
        if(degree[i]<=1)que[in++]=i;
    while(out<n-2)
    {
        int tmp=in;
        while(out<in)
        {
            int x=que[out++];
            for(int i=box[x];i!=-1;i=edge[i].next)
            {
                int x1=edge[i].to;
                degree[x1]--;
                if(degree[x1]==1)que[tmp++]=x1;
            }
        }
        in=tmp;
    }
    assert(in==n);
    root1=que[in-1];
    if(out==in-2)root2=que[in-2];
    else root2=-1;
}
struct Node
{
    ll hash,cnt;
    int child;
    bool operator<(const Node &a)const
    {
        return hash<a.hash;
    }
    void clear()
    {
        child=1,cnt=1;hash=1;
    }
}node[Maxn];
ll exGcd(ll x,ll y,ll &a,ll &b)
{
    if(y==0)
    {
        a=1,b=0;return x;
    }
    ll gcd=exGcd(y,x%y,b,a);
    b-=x/y*a;
    return gcd;
}
ll getInverse(ll x,ll y)
{
    ll a,b;
    ll gcd=exGcd(x,y,a,b);
    assert(gcd==1);
    a%=y;
    if(a<0)a+=y;
    return a;
}
 
ll getC(ll x,ll y){
    ll ret=1;
    y=min(y,x-y);
    for(int i=1;i<=y;++i)
        ret=ret*(x-i+1)%Mod*getInverse(i,Mod)%Mod;
    return ret;
}
 
void dfs(int x,int l)
{
    assert(x>=1&&x<=n);
    vector<Node>vec;
    node[x].clear();
    node[x].cnt=m;
    for(int i=box[x];i!=-1;i=edge[i].next)
    {
        int x1=edge[i].to;
        if(x1==l)continue;
        dfs(x1,x);
        vec.push_back(node[x1]);
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<vec.size();)
    {
        int j;
        for(j=i;j<vec.size()&&vec[i].hash==vec[j].hash;++j)
        {
            assert(node[x].child<=n);
            assert(vec[i].child==vec[j].child);
            assert(vec[i].cnt==vec[j].cnt);
            node[x].hash+=po[node[x].child]*vec[j].hash;
            node[x].child+=vec[j].child;
        }
        node[x].cnt=node[x].cnt*getC(vec[i].cnt-1+j-i,vec[i].cnt-1)%Mod;
        i=j;
    }
    node[x].hash+=node[x].child;
}
int solve()
{
    dfs(root1,root2);
    if(root2==-1)return node[root1].cnt;
    dfs(root2,root1);
    if(node[root1].hash==node[root2].hash)
    {
        assert(node[root1].cnt==node[root2].cnt);
        return getC(node[root1].cnt-1+2,node[root1].cnt-1);
    }
 
    return node[root1].cnt*node[root2].cnt%Mod;
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    getPo();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(box,-1,(n+2)*sizeof(int));size=0;
        memset(degree,0,(n+2)*sizeof(int));
        for(int i=1;i<n;++i)
        {
            int x,y;scanf("%d%d",&x,&y);
            add(x,y),add(y,x);
            degree[x]++,degree[y]++;
        }
        toposort();
        printf("%d\n",solve());
    }
    return 0;
}

J The Ghost Blows Light (HDU 4276)
Tree DP
http://blog.csdn.net/wukonwukon/article/details/7958854
http://nightelf.sinaapp.com/2012/hdu-4276.html
http://www.acforfun.com/?p=88
http://www.cnblogs.com/yejinru/archive/2012/09/09/2677322.html
http://blog.csdn.net/cqlf__/article/details/7962130

K USACO ORZ (HDU 4277)
搜索
http://blog.csdn.net/kksleric/article/details/7958600
http://www.cnblogs.com/yejinru/archive/2012/09/08/2676899.html
http://blog.csdn.net/swrdlgc/article/details/7958615
http://blog.csdn.net/wukonwukon/article/details/7958854
http://blog.csdn.net/kk303/article/details/7958828
http://www.cnblogs.com/programCaiCai/archive/2012/09/08/HDU4277.html
http://blog.csdn.net/diannaok/article/details/7959456

You can follow any responses to this entry through the RSS 2.0 You can skip to the end and leave a response. Pinging is currently not allowed.

22 Responses



留言给 iloahz 取消留言

电子邮件地址不会被公开。 必填项已用*标注