针对2012 ACM/ICPC 金华赛区10月28日现场赛,本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
A Physical Examination (HDU 4442)
http://blog.csdn.net/shuimu12345678/article/details/8123577
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
http://www.cnblogs.com/pony1993/archive/2012/10/29/2745454.html
http://www.cnblogs.com/moonbay/archive/2012/10/30/2745929.html
http://blog.sina.com.cn/s/blog_9d987af5010177xe.html
B Lost (HDU 4443)
http://hi.baidu.com/caiych/item/9dda9743d84e25ea1e19bc19
http://blog.csdn.net/zz_1215/article/details/8136840
C Walk (HDU 4444)
http://blog.csdn.net/asdfgh0308/article/details/8125832
http://blog.csdn.net/zz_1215/article/details/8125930
http://hi.baidu.com/_suxing11/item/d6269b29c4cd92c4a5275a38
http://winguse.com/blog/2012/10/30/hdu-4444-walk-2012%E4%BA%9A%E6%B4%B2%E5%8C%BA%E9%87%91%E5%8D%8E%E7%AB%99c%E9%A2%98/
http://iseasoul.com/jinhua-onsite-easy-sol
注:除最后一条外,其余可能都有错误,但因数据弱所以也通过了。
D Crazy Tank (HDU 4445)
http://blog.renren.com/blog/284250792/878678994
http://bu540402.diandian.com/post/2012-10-29/40042959509
http://winguse.com/blog/2012/11/01/4445-crazy-tank-2012%e4%ba%9a%e6%b4%b2%e5%8c%ba%e9%87%91%e5%8d%8e%e7%ab%99d%e9%a2%98/
http://www.cnblogs.com/jffifa/archive/2012/11/04/2754065.html
E IT Companies (HDU 4446)
http://hi.baidu.com/isaacpei/item/1c5c7fc1d9bddfd9ee183bc4
F Yuanfang, What Do You Think? (HDU 4447)
论文 https://docs.google.com/open?id=0B207bvwVi4QrSG5MclJkdmxkZE0
论文 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.3592&rep=rep1&type=pdf
http://hi.baidu.com/isaacpei/item/4f7807327e54c681b611db63
http://blog.csdn.net/cyberzhg/article/details/8139869
sixujie提供的源代码:https://skydrive.live.com/?cid=CA782D9BC2210D14&id=CA782D9BC2210D14%21117
如果打不开,也可以展开下面的代码直接看
#include <cstdio> #include <vector> #include <algorithm> #include <string> using namespace std; //#define DEBUG const int N = 1200; int gcd(int,int); struct Node{ Node(int _p, int _a):pow(_p), a(_a){} int pow; int a; void output(bool positiveSign=false) { if(positiveSign && a>0) putchar('+'); if(pow==0){ printf("%d",a); return; } if(a==-1){ putchar('-'); } else if(a!=1){ printf("%d",a); } putchar('x'); if(pow>1) printf("^%d",pow); } //bool operator < (const Node& nd)const{ // return pow > nd.pow; //} bool operator == (const Node& nd)const{ return pow==nd.pow && a == nd.a; } }; struct Expression{ vector<Node> expression; // trivial case 1: order = p, where p is a prime void tr1(int order) { expression.clear(); for(int i=1;i<order;++i){ expression.push_back( Node(order-i,1) ); } expression.push_back( Node(0,1) ); } // trivial case 2: order = p^k, where p is a prime void tr2(int k, const Expression& xp) { expression.clear(); for(int i=0; i< xp.expression.size();++i){ expression.push_back( Node( k*xp.expression[i].pow, xp.expression[i].a) ); } //expression.push_back( Node(0,1) ); } void norm() { if(expression.size()<1)return; int c=abs(expression[0].a); for(int i=0;i<expression.size();++i){ c= gcd(c, abs( expression[i].a ) ); if(c==1)break; } if(c==1)return; for(int i=0;i<expression.size();++i) expression[i].a/=c; } void output() { putchar('('); for(int i=0;i<expression.size();++i){ expression[i].output(i!=0); } putchar(')'); } void positive() { //if( expression.size() <=0 )return; if(expression[0].a > 0)return; for(int i=0;i<expression.size();++i){ expression[i].a = - expression[i].a; } } void timesK(int k) { if(k>1) //Expression res; for(int i=0;i<expression.size();++i) expression[i].a *= k; //res.push_back( Node( expression[i].pow,k*expression[i].a ) ); //return res; } void timesX(int k) { if(k>0) for(int i=0;i<expression.size();++i) expression[i].pow += k; } void minus(const Expression& exp){ Expression res; int i=0,j=0; int sz1 = expression.size(); int sz2 = exp.expression.size(); while(i<sz1 && j<sz2){ const Node& np = expression[i]; const Node& nq = exp.expression[j]; if(np.pow < nq.pow){ res.expression.push_back( Node(nq.pow, -nq.a) ); j++; } else if(np.pow == nq.pow){ i++;j++; if(np.a==nq.a)continue; res.expression.push_back( Node(np.pow, np.a-nq.a) ); // i++; j++// continue_bug } else{ res.expression.push_back( Node(np.pow, np.a) ); i++; } } while(i<sz1){ res.expression.push_back( Node( expression[i].pow, expression[i].a) ); i++; } while(j<sz2){ res.expression.push_back( Node(exp.expression[j].pow, - exp.expression[j].a) ); j++; } expression = res.expression; //return res; } bool operator < (const Expression& exp) const{ int sz1 = expression.size(); int sz2 = exp.expression.size(); for(int i=0;i<sz1 && i<sz2; ++i){ if(expression[i] == exp.expression[i])continue; const Node& np = expression[i]; const Node& nq = exp.expression[i]; if( np.pow < nq.pow ){ return true; } else if (np.pow==nq.pow){ if( abs(np.a) != abs(nq.a) ) return abs(np.a) < abs(nq.a); return np.a < nq.a; } else{ return false; } } return sz1 < sz2; } bool constant() { if(expression.size()<1)return true; if(expression.size()==1 && expression[0].pow==0) return true; return false; } }; int gcd(int a, int b){ return b==0 ? a : gcd(b,a%b);} Expression gcd(Expression& a, Expression& b) { a.positive(); b.positive(); #ifdef DEBUG puts("now:"); puts("a="); a.output();puts(""); puts("b="); b.output();puts(""); #endif if(b.constant()){ return a; } Expression cpb = b; while(b.expression[0].pow <= a.expression[0].pow){ #ifdef DEBUG puts("next: a="); printf("a:pow=%d co=%d\n", a.expression[0].pow,a.expression[0].a); #endif a.positive(); b.positive(); int ca = a.expression[0].a; int cb = b.expression[0].a; int c = (long long)ca*cb/gcd(ca,cb); #ifdef DEBUG printf("c=%d\n",c); printf("a:pow=%d co=%d\n", a.expression[0].pow,a.expression[0].a); printf("b:pow=%d co=%d\n", b.expression[0].pow,b.expression[0].a); #endif a.timesK(c/ca); b.timesK(c/cb); #ifdef DEBUG puts("after timesK"); printf("a:pow=%d co=%d\n", a.expression[0].pow,a.expression[0].a); printf("b:pow=%d co=%d\n", b.expression[0].pow,b.expression[0].a); #endif b.timesX( a.expression[0].pow - b.expression[0].pow ); a.minus(b); if(a.constant())break; b = cpb; } a.norm(); b.norm(); return gcd(cpb,a); } Expression ans[1200]; void deal(int k) { int p,q; p=1; q=k; int i=1; while(i*i<k)i++; if(k>2) for(;i>=2;--i){ if(k%i)continue; if(gcd(i,k/i)!=1)continue; p = i; q = k/i; break; } if (p==1){ int b=2; while(b<k && k%b)b++; //trivial case 1 if(b==k) ans[k].tr1(k); else //trivial case 2 ans[k].tr2(k/b, ans[b] ); } else{ Expression ea; ea.tr2(k/p,ans[p]); Expression eb; eb.tr2(k/q,ans[q]); ans[k] = gcd(ea, eb); } } void verify() { Expression t1,t2; Expression f2; Expression f3; f2.tr1(2); puts("f2="); f2.output(); puts(""); f3.tr1(3); puts("f3="); f3.output(); puts(""); t1.tr2(3, f2); t2.tr2(2, f3); Expression f6 = gcd(t1,t2); puts("f6="); f6.output(); puts(""); Expression f5; f5.tr1(5); Expression f7; f7.tr1(7); t1.tr2(5,f3); t2.tr2(3,f5); Expression f15 = gcd(t1,t2); puts("f15="); f15.output(); puts(""); t1.tr2(15,f2); t2.tr2(2,f15); Expression f30 = gcd(t1,t2); puts("f30="); f30.output(); puts(""); t1.tr2(15,f7); t2.tr2(7,f15); Expression f105 = gcd(t1,t2); puts("f105="); f105.output(); puts(""); t1.tr2(3,f7); t2.tr2(7,f3); Expression f21 = gcd(t1,t2); puts("f21="); f21.output(); puts(""); t1.tr2(5,f7); t2.tr2(7,f5); Expression f35 = gcd(t1,t2); puts("f35"); f35.output(); puts(""); Expression f4; f4.tr2(2,f2); puts("f4="); f4.output(); puts(""); t1.tr2(4,f5); t2.tr2(5,f4); Expression f20 = gcd(t1,t2); puts("f20="); f20.output(); puts(""); t1.tr2(7,f20); t2.tr2(20,f7); Expression f140 = gcd(t1,t2); puts("f140="); f140.output(); puts(""); Expression f11; f11.tr1(11); puts("f11=="); f11.output(); puts(""); t1.tr2(11,f35); t2.tr2(35,f11); Expression f385 = gcd(t1,t2); puts("f385="); f385.output(); } int main() { int n; //verify(); //return 0; ans[1].expression.push_back( Node(1,1) ); ans[1].expression.push_back( Node(0,-1) ); for(int i=2;i<=1100;++i){ deal(i); } while(scanf("%d",&n),n){ if(n==1){ puts("x-1"); continue; } vector<Expression> ansv; for(int i=1;i<=n;++i){ if(n%i==0) ansv.push_back( ans[i] ); } sort(ansv.begin(),ansv.end()); for(int i=0;i<ansv.size();++i){ ansv[i].output(); } puts(""); } return 0; }
G Spade 7 (HDU 4448)
H Building Design (HDU 4449)
http://blog.csdn.net/d891320478/article/details/8127374
I Draw Something (HDU 4450)
http://blog.csdn.net/shuimu12345678/article/details/8124566
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
http://nstxacm.blog.163.com/blog/static/2114423512012929920971/
http://blog.sina.com.cn/s/blog_71fda4350101a60o.html
http://blog.sina.com.cn/s/blog_9d987af5010177xh.html
J Dressing (HDU 4451)
http://blog.csdn.net/xinge008/article/details/8124544
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
http://blog.csdn.net/youngyangyang04/article/details/8126594
http://blog.sina.com.cn/s/blog_71fda4350101a6g8.html
http://blog.sina.com.cn/s/blog_9d987af5010177xj.html
K Running Rabbits (HDU 4452)
http://blog.csdn.net/zzxyyx_1/article/details/8125433
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
http://blog.sina.com.cn/s/blog_71fda4350101a6g0.html
http://www.cnblogs.com/moonbay/archive/2012/10/29/2745493.html
http://blog.sina.com.cn/s/blog_9d987af5010177xm.html
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.
F题论文:
https://docs.google.com/open?id=0B207bvwVi4QrSG5MclJkdmxkZE0
或
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.3592&rep=rep1&type=pdf
J 水一发http://blog.csdn.net/xinge008/article/details/8124544
水K http://blog.csdn.net/zzxyyx_1/article/details/8125433
现场被血虐的弱菜C题题解http://blog.csdn.net/asdfgh0308/article/details/8125832
水题A,I,J,K
http://www.cnblogs.com/kuangbin/archive/2012/10/29/2745368.html
C题:http://blog.csdn.net/zz_1215/article/details/8125930
水体将军第i题http://nstxacm.blog.163.com/blog/static/2114423512012929920971/
这么简单没有做出来,银牌到铁牌的失落!
D题http://blog.renren.com/blog/284250792/878678994
这么简单没有做出来,银牌到铁牌的失落!
D题 水 http://bu540402.diandian.com/post/2012-10-29/40042959509
http://blog.sina.com.cn/s/blog_71fda4350101a6g0.html
k题
C题,水一个。
http://hi.baidu.com/_suxing11/item/d6269b29c4cd92c4a5275a38
H题
http://blog.csdn.net/d891320478/article/details/8127374
http://hi.baidu.com/caiych/item/9dda9743d84e25ea1e19bc19
B题
http://www.51nod.com/question/index.html#!questionId=694
G题,憋七。
D题都没有读的弱渣,跑去搞B 和F,给跪了。处女场就悲剧打铜。。。。
F题:http://hi.baidu.com/isaacpei/item/4f7807327e54c681b611db63
F题已AC代码,基本思路就实现一元多项式的欧几里得算法(对两个一元多项式求GCD)
https://skydrive.live.com/?cid=CA782D9BC2210D14&id=CA782D9BC2210D14%21117
B题:http://blog.csdn.net/zz_1215/article/details/8136840
http://iseasoul.com/jinhua-onsite-easy-sol
C题,这里面所有解题报告都是错的 – – 现在都过不了了。
没精力验证……等比赛全完了可能往晒代码里面批量导入一下验证看看。
我来组成一个正经的D。