针对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.
http://blog.csdn.net/kksleric/article/details/7958600
已有AHK三题,晚上把比赛时队友做的和子集wa的题A掉后继续更新
http://acmicpc.info/archives/823 最后一题..
弱菜贡献两题吧
B题http://blog.csdn.net/troy_cornelius/article/details/7958821
F题http://blog.csdn.net/troy_cornelius/article/details/7958735
BTW..
理解出题不容易,不过数据确实微水啊
http://blog.csdn.net/swrdlgc/article/details/7958615
求把F题删掉,我贪心水过的。。。
已删除。但个人认为,即使水过也可以为大家提供思路。
嗯,赛后我仔细考虑了下,我的那种贪心策略好像有点问题。
第十题,两种DP一起乱搞。。
http://nightelf.sinaapp.com/2012/hdu-4276.html
http://www.acforfun.com/?p=84
发个水题1005,新blog欢迎多访问。
1001 http://www.cnblogs.com/programCaiCai/archive/2012/09/08/HDU4267.html
1002 http://www.cnblogs.com/programCaiCai/archive/2012/09/08/HDU4268.html
1011 http://www.cnblogs.com/programCaiCai/archive/2012/09/08/HDU4277.html
发现Color the Tree这个题,标程序getc(n,m)的复杂度太高了,居然可以过….n=10^9,m=10^9,p=10^9+7啊。。。
因为C(n, k)中k的和不超过节点数。
我错了,m = 10^5
C题: http://zhyu.me/acm/hdu-4269.html
来两个短代码的
1010:http://www.acforfun.com/?p=88
1001:http://www.acforfun.com/?p=86
欢迎多访问acforfun.com
http://hi.baidu.com/buaa_babt/item/a42588e604155b1f570f1db4
C题
Problem I
对于任意自同构,质心是不动点(质心:直径的中点,如果直径长度是奇数,则质心在边上)。
不失一般性,假设直径长度是偶数。取质心为根,设$f(T)$表示树$T$本质不同的染色数。取树$T$的根$r$,设点$r$的儿子中,共有$k$个同构等价类,分别是$T_1, T_2, \ldots, T_k$,数量是$c_1, c_2, \ldots, c_k$。对于任意等价类,递归计算$f(T_i)$,问题等价于用$f(T_i)$种颜色给$c_i$个物品染色的方案数(不计顺序),这又等价于方程$x_1 + x_2 + \cdots + x_{f(T_i)} = c_i$的解数。
1009思路已有,若不嫌弃这里有份代码。
http://www.acforfun.com/?p=90
写的不咋样但是长度还是不错的
自荐~
http://lujunda.tk/2012/09/09/hdu4269%E6%A8%A1%E6%8B%9F-defend-jian-ge/
http://www.acforfun.com/?p=98
1004,貌似还是第一个哈
1004标程做法有错。
询问字典最小的字串时候加一个新字符是要遍历fail数组的,这个遍历和后缀自动机构建时候的遍历是不一样的。
构建时候总遍历复杂度是O(2*n*CH),因为每个点只可能加CH个边,加满了就不能再加了。而现在每次询问都加一个新的,是O(n)的,总复杂度是询问次数*N。
TLE的数据很容易构造,长串为全a,长为100000.
询问100000,都是 2 2