| 峰's profile流 浪 的 枫 之 羽PhotosBlogLists |  Tools  Help |
|
|
HDOJ1527问题： 碰到这道题时我的思路： 设集合A, B分别为先手能赢和后手能赢的二元无序对(x,y)的集合 先从最基础的开始考虑，(n,0) (n,n) 属于A，因为这样的情况先手肯定能赢（n为正整数，下同） 如果存在(a,b)，对于一切n，(a-n,b-n)均属于A，则(a,b)属于B 接下来从先手的角度分析，如果他能在移动石子后留给对手(2,1)个石子，那么他就能赢，于是 找出一个不属于A的最小对，(5,3)， 这个元素肯定属于B集合，因为从中任意取出元素后的结果肯定属于A集合 这时发现，B集合相对A集合元素少很多，只要找出B集合中元素的特征，就能解决这个问题。 一旦B中包含(x,y)对，A中就会相应的包含(x, y+n), (x+n, y), (x+n,y+n) 公式可以见这个博客 HDOJ2136Problem Description
Everybody knows any number can be combined by the prime number.Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.Specially, LPF(1) = 0. Input
Each line will contain one integer n(0 < n < 1000000).
Output
Output the LPF(n).
Sample Input
1 2 3 4 5 Sample Output 0 1 2 1 3 http://acm.hdu.edu.cn/showproblem.php?pid=2136 算法思想：采用素数筛选法改进以符合这道题目！ memset(prime, -1, sizeof(prime)); 一道排列组合题目！今天在群里师兄发了一道公务员试题：4个球放入8个编号不同的盒子，每个盒子可放0－4个，则有几种放法？
我们可以进行推广，就是m个球放入n个编号不同的盒子，每个盒子可放0－m个，则有几种放法？
解题思路1：
用递归：
1个盒子,m个球:1种方法
2个盒子,m个球:分别有(0,m) (1,m-1) (2,m-2)...(4,0) 共m+1种方法 设n个盒子,m个球有f(n,m)种放置方法，现取第1个盒子的球数分别为0,1,2,.,i,..m ,对于这m+1种情况中的第i种情况，有f(n-1,m-i)个含n-1个元素的字符串数组
全部拼起来即可 解题思路2：
/*这其实是一个n进制数的问题
假定存在一个m位的n进制数，他的k位上的数字表示第k个球所在盒子的编号，可以证明这个m位的n进制数和盒子的排列是一一对应的 我们知道，对于这种题目，可能的组合数为n^m，那么你只要把0- >n^m-1的数转换成n进制数，再检查对应的每位数既可知道每个球所在的盒子 所以唯一的难点就是整数转换成n进制数的问题，这个好像不是难题哦，学过计组的都应该知道除余法 也就是对于整数x, x%n表示n进制数个位上的数字，要求更高位的数字，要用x= x/n迭代*/ 递归的程序实现：
#include <cstdlib>
#include <iostream> using namespace std; int *a; int n; int cnt =0; void f( int len, int sum ){ int i; if( sum==0 ){ for( i=0; i<len; ++i ) cout<<a[i]<<" "; for( ; i<n; ++i ) cout<<0<<" "; cout<<endl; cnt++; return; } if( len==n-1 ) { a[len]=sum; for( i=0; i<=len; ++i ) cout<<a[i]<<" "; cout<<endl; cnt++; return; } for( i=0; i<=sum; ++i ){ a[len]=i; f( len+1, sum-i ); } } int main( )
{ int m; while(cin>>m>>n) { cnt = 0; a=new int[n]; f( 0, m ); cout<<cnt<<endl; delete a; } return 0;
} 第32届ACM亚洲预赛蓉城赛区传来捷报 我校学生摘取金牌 11月18日，在第32届国际大学生程序设计竞赛亚洲预赛成都赛区决赛中，我校计算机学院学生林乐、徐海东与理学院学生赖力组成的参赛队发挥出色，最终以高校排名第4位的优异成绩获得金牌，参赛成绩位列浙江省高校之首。 本届竞赛，共有经过预选赛后产生的89支代表队的267名学生进军成都赛区，可谓强队聚首，高手相逢，高校排名前3位的分别是北京大学、复旦大学、清华大学、中山大学，其中复旦和清华并列第二。 本届竞赛，我校参赛队在指导教师总教练刘春英的带领下，此前已多有斩获，分别获得长春赛区银牌1枚、北京赛区银牌与铜牌各1枚、南京赛区铜牌1枚。我校在本届ACM竞赛中刷新记录，实现摘取金牌的零的突破，令竞赛组办部门、高校界以及计算机界刮目相看。 我校自2003年9月开始组织学生参加大学生程序设计竞赛，并从2004年起在全校范围内挑选优秀学生组成ACM集训队，由专业指导教师实施备战训练。此外，计算机学院还于2005年针对该项赛事设计了每年举行6次月赛（其中含2次校级比赛）的竞赛制度，在学生中广泛普及ACM知识，训练学生利用计算机分析问题、解决问题的能力，全面提高学生程序设计水平，同时也为ACM集训队输送源源不竭的优秀选手。据统计，每年参加该项赛事的学生近2000人次。（教务处、计算机学院） 网上找到几张06年省赛的相片！全家福：
DOOMIII
颁奖典礼
New contest is comingDear feng5166, We would like to invite you to participate in our forthcoming online programming contest: Ural SU contest. Petrozavodsk training camp, January 2006. Date: Saturday, August 12, 2006 at 13:00 UTC+6 Duration: 5 hours Link: http://acm.timus.ru/contest.aspx?id=51 Problemset was used during Petrozavodsk training camp, Winter 2006. Problems are prepared by team Ural SU T34 (Dmitry Ivankov, Alexander Ipatov and Artem Melentyev) with help of Alexander Toropov and Vladimir Yakovlev. All problems are equally solvable with any of language C/C++, Pascal, Java. For more details about contest schedule see http://acm.timus.ru/schedule.aspx Timus Online Judge http://acm.timus.ru 难以忘怀在ACM训练队地日子时光荏苒，转眼一年的时间我就要离开ACM训练队了。然而曾经的出征的经历还历历在目，彼时的训练也都清晰可见。忘不了给与我们无限关注和照顾、对我们寄以殷切希望的老师和教练，忘不了一同奋斗一同征战的杭电的ACMer，而自己在ACM队的所思所感所得所获更是难以忘怀。 一年前，我幸运地加入了杭电ACM集训队。学长们的风采让我心潮澎湃，他们拼搏的精神也让我敬佩不已。作为新加入的集训队成员，我明白自己身上所担负的责任。 训练的日子是辛苦的，然而也是充实的。上午讲座，下午做题，晚上讨论、总结、完善和改进。不知不觉，走过了酷暑和金秋。经过半年的磨合，我们整个集训队有了相当的默契；在教练的帮助下，每个人的实力也大有长进；我们经历风雨，走过坎坷，创造了佳绩，看到了美丽的彩虹。在05年11月的成都和北京两场ACM国际大学生程序设计比赛亚洲区比赛分区赛上，我们获得一铜一银的好成绩，也改写了杭电在这一竞赛历史上零的突破，这些奖项的获得，不仅是对我们努力拼搏的肯定，同时也激励着我们向着更高目标前进，更是对教练刘春英老师敬业精神的一种回报！ “老师、教练、学校，对我们这么重视，提供了这么好的训练条件，我们应该做的是好好珍惜和把握，持之以恒，努力不息，争取赛出最好的成绩”，这是我们整个训练队员每个人心中暗自许下的心愿！ 经过一年在ACM程序设计竞赛中的锻炼，我个人也收获很多，实力水平和心理素质上都有很大提高，更加体会到团队协作的力量。我相信，杭电ACM队所特有的学习氛围和竞赛精神——将每次的练习当成真正的比赛，而将真正的比赛当成平常的练习，以良好的心态训练和比赛——再加上我们每位队员不懈的努力和拼搏，目标就一定可以实现！ 又是一年省赛，而它的到来更要求我们去刻苦的训练。经过我们长时间艰苦的训练，功夫不负有心人，杭电整个ACM集训队在新的一年又有很大进步，做题速度快了，1次通过率也提高了。我们如愿以偿地在浙江省第三届程序设计竞赛中拿到2金2银和2铜。那一刻，开心的喜悦流过心田，所有集训队成员与教练紧紧相拥在一起…… 回望走过来的路，我也曾有失误，有过挫折。在紧张激烈的5小时赛场上，即使是一个闪过脑海的放弃的念头、一个微不足道的松懈的行为，都直接影响着队友的情绪，影响着比赛的结果。而ACM的经历，教会了我什么是沉着冷静，什么是着眼全局，我也从来没有如此清楚地看到自己的弱点：过于浮躁，过于主观。而我在今后的学习生活中，会一步一个脚印，稳步向前，不只用眼睛，更会用心去体会周围的人和事。 喜欢ACM，喜欢这种拼搏，喜欢这样学习的乐趣！喜欢ACM集训队，喜欢这份团结，喜欢在这里思考、讨论、交流的纯净！然而“一代新人换旧人”，看见学弟们那种选择ACM的迫切心情和义无反顾的决心，我欣然选择了退役，虽然心有不舍，但我为杭电ACM队的青春活力和美好明天而激动和兴奋。我因你而自豪！一年前如此，现在如此，今后也将如此！ 参加竞赛，确实要付出很多；但只要你用心、投入，就可以从中得到更多。就像在苦酿美酒之后，就能尽享甘醇。
圆满完成任务！退役了，再也见不到我在ACM赛场上奋斗了，值得怀念的一年，只得珍惜的与队友一起走过的一年！ 省赛比好最后一场，光荣退休！这是我最后一次机会了！ 省赛了1魔鬼特训一星期，所有人都不要找我！相信我们，为了我们三个人的最后一次真正的合作而努力，我们是永远的DOOM III，没有什么原因，下星期浙大省赛时再见！ 欧拉回路模版/*之所以从n-1搜到0应该是为了最后在path中保持字典序,但是对于不是回路的情况, path最后一个元素不是起点元素,也就没有字典序了.好像应该是如果从0搜到n-1, 最后输出的时候逆向输出,就可以了,刚才瞄到一个题,的确要这么改改才能过. 本来是这样的..*/ #include<stdio.h> #define MAXN 50 void find_path_u(int n,int mat[][MAXN],int now,int& step,int* path){ int i; for (i=n-1;i>=0;i--) while (mat[now][i]) { mat[now][i]--,mat[i][now]--; find_path_u(n,mat,i,step,path); } path[step++]=now; } 筛素数！void prim() { int i,j; for(i=2;i<=N/2;i++) if(prime[i]==0) for(j=i*2;j<=N;j+=i) prime[j]=1; } 并查集模板！#include<stdio.h> #define MAXN 30005 int Parent[MAXN], Rank[MAXN]; int vist[MAXN]; void make_set(int x) { Parent[x] = x; vist[x]=1; Rank[x] = 0; } // 合并x,y所在的集合，并返回交集 // 返回到元素i所属的集合的代表元素, 同时进行路径压缩 int FindSet(int i) { if( ( i == -1 ) || ( i >= MAXN ) ) { // -1表示空集 return -1; } else { if(( Parent[i] != -1 ) && ( Parent[i] != i ) ) // Parent[i] = FindSet( Parent[i] ); // 这句话进行路径压缩*/ return Parent[i]; } } int Union(int x, int y) { x = FindSet( x ); // 找到x所在的树的根 y = FindSet( y ); // 找到y所在的树的根 if( x == y ) return x; // -1表示空集 if( x == -1 ) return y; if( y == -1 ) return x; if( Rank[x] > Rank[y] ) { // 将较低的树合并到较高的树上 Parent[y] = x; vist[x]=vist[x]+vist[y]; return x; } else { Parent[x] = y; vist[y]=vist[x]+vist[y]; if( Rank[x] == Rank[y] ) Rank[y]++; // 改变树的高度 return y; } } 来自URAL的邀请Dear feng5166, We would like to invite you to participate in our forthcoming online programming contest: Timus Top Coders: Second Challenge Date: Saturday, April 22, 2006 at 13:00 UTC+6 Duration: 5 hours Link: http://acm.timus.ru/contest.aspx?id=48 Timus Top Coders: Second Challenge is the second open online programming contest, which is organized by the leaders of Timus Online Judge rating. The problems for this contest are created by well-known programmers Nikita Rybak, Ilya Grebnov and Dmitry Kovalioff from Top 10 of Timus Online Judge. The problemset is quite balanced and contains both relatively easy problems and rather difficult ones - even for top programmers. All problems are specially created for this contest, based on new ideas and thoroughly tested. All problem statements will be available both in English and Russian. If you are at Timus Online Judge for the first time, please, register to participate in the contest and look through FAQ. If you are already registered, no additional registration is needed. For more details about contest schedule see http://acm.timus.ru/schedule.aspx Timus Online Judge http://acm.timus.ru hdoj1072搜索!#include<cstdio>
#include<queue> using namespace std; bool vist[8][8][7];//标志某一能量是否走过 int map[8][8]; typedef struct p { int x; int y; int z;//能量 int depth;//步数 }p; p p1,p2,p3; queue<p>que; int dir[4][2]={1,0,0,-1,0,1,-1,0}; int main() { int i,j,k; int cas; int w,h; int x,y,z; int Si,Sj,Ti,Tj; while(scanf("%d%d",&w,&h)&&w>0)
{ for(i=0;i<w;i++) { for(j=0;j<h;j++) { scanf("%d",&map[i][j]); if(map[i][j]==2) { Si=i; Sj=j; } else if(map[i][j]==3) { Ti=i; Tj=j; } } } for(i=0;i<w;i++) for(j=0;j<h;j++) for(k=1;k<=6;k++) vist[i][j][k]=false; p1.x=Si; p1.y=Sj; p1.depth =0; p1.z=6; que.push(p1); int flag=0; while(!que.empty()) { if(flag) break; p2=que.front(); que.pop(); for(i=0;i<4;i++) { x=p2.x+dir[i][0]; y=p2.y+dir[i][1]; z=p2.z-1; if(z>0&&map[x][y]!=0&&!vist[x][y][z]&&(x>=0&&y>=0&&x<w&&y<h)) { if(Ti==x&&Tj==y) { flag=true; break; } p3.x=x; p3.y=y; p3.depth=p2.depth +1; vist[x][y][z]=true; if(map[x][y]==4) { p3.z=6; } else p3.z=z; que.push(p3); } if(flag) break; }
}
if(flag) { printf("%d\n",p3.depth); } else { printf("-1\n"); } while(!que.empty()) que.pop(); } return 0; } 周六的比赛我出题!HDU 2005 ACM Weekly Exercise 1
绝对是做过ACM的可以秒杀的题,不过也没办法,学校的整体水平差的可以,所以这种题估计做完的也不会多的,一共6道,HOHO! 赋值问题在很多程序设计语言中，忘记给变量赋初值的错误常令人头疼。请编程求出含N(0≤N≤100)行的程序段运行以后有哪些变量中有确定的值。在下面的问题中，最开始仅有变量a中有确定的值。变量为单个小写字母，每行恰好有三个字符，中间一个是赋值运算符'='。 输入 输入有多组数据，每组数据的第一行有一个整数N，表示程序段的行数。以下N行，每行3个字符，为一条语句。最后一组数据N=-1表示输入结束，不需要处理。 输出 对每一组数据输出一行结果，按字母表顺序给出所有有确定值的变量名。如果没有变量有确定的值，输出none。 输入样例 4 b=a c=d d=b e=f -1 输出样例 a b d
#include <stdio.h> } 成都拿了块铜牌!在川大拿了块铜牌,北大,浙大的比赛,杭电ACMer继续加油啊! 北京赛区也出现!北京赛区总算出现了，不过留给集训队的是一块很大的心理阴影,从四川到杭州再到北京,三场预选赛虽说都出现了,但结果呢.......,没有胜利的掌声,没有喝彩,剩下的只有去从容面对现实,我们的实力太差,HDOJ也在这三场预选赛的过程中完工了,服务器也拿到了,域名也批了acm.hziee.edu.cn,但我们的水平呢,到了现场还是被别的强校蹂躏,这个就是不睁的事实.不知道,最后的结果怎么样,蹂躏就蹂躏,至少杭电的acmer不会放弃暂存的希望之火,11月5日,成都,我们来了,四川大学将见证我们的到来,加油吧,队友们 【合集】2005北京赛区预选赛解题报告 By jinji2005北京赛区预选赛解题报告 By jinji
开始后，我采用的方针是先尽量多的看题，先不着急做。对每个题大概是什么样的有了感觉后才能选得最好。
A和I题是简单题。
A题就是在连续的一段，再去除几段，最后数算上面的点数，一段一段减即可，刘晨虎完成。
I题因为规则比较简单，当动物接近（即下一单元时间可接触主人公）前，可以连续工作；而当动物接近后，休息一单元从而让动物远离，再工作一单元，即半时间工作即可。刘晨虎调试AC。
F和H看是模拟题，用不着太在乎名次，得到长进才重要，于是我就把目光放在了B题，D题，G题。
D题较为单纯，是第一项都向上取整的调和数列求和。此题的卖点在于数据规模大：20亿。那么不能直接算，而是考虑数列的后半部有大量向上取整后值相同的项，只要计算这每一段的开始与结束位置，用值与长度相乘代替一个一个加即可。如果一段的开始的下标为n1，此段d=ceil(G/n1)，那么ceil(G/(d-1))即是下一段开始的下标。
B题是数学题，关键在于数学运算出最终的式子。浪费了我们不少时间，这是一个重要的失误。此题还有一个难处，即是结果做出来后，自己比较难以检验是否完全正确。因为题目给的例子数据中，一个是比较小的数，再加上结果一取整，造成当式子有一点差错时，无法从例子数据中判断是否有问题。另一个例子数据则是只代表结果>10000，更没有数字让我们来详细检验。这样就没法知道自己的算出的结果是否正确。开始我是用线速度来算的，把矩形上的一些结论搬到题目中的扇形上，造成了一些误差。因为此题没法自己设计测试用例，只能再更详细的推，这下消耗了不少时间。后来用角速度的方式来算，如果用Integrate代表积分，则alpha=Integrate(sqrt(3)*u/(d+u*t),对t积)|0~T，积分得alpha=sqrt(3)*ln(d+u*t)|0~T。解之得T=(exp(alpha/sqrt(3)+ln(d))-d)/u。注意，这里的alpha是孤度制(为了与孤长的换算方便)，而题目给的是角度制。
G是动态规划。可惜时间已经不多，当时没有做完，事后补了一小时做完，直接AC。此题比较容易想到是动态规划，但是关键是在于把具体的递推关系找出并用式子表示。因为jimmy送东西时，不可能路过而不送，那么可以将原问题设计这样的子问题f[j][k][dir]。它代表剩下j~k区域里的没有送达时的要完成余下的这些任务需要的最少代价。dir为0时代表从i端为起点，dir为1代表从j端为起点。那么题目原问题即为f[0][N-1][0]的值。递推关系是：f[j][k][0]等于t[j][j+1]*remain[j+1][k]+f[j+1][k][0]和t[j][k]*remain[j+1][k]+f[j+1][k][1]，两个中较小的一个。其中，remain[x][y]表示从x到y区域内未送的东西的总数，而t[x][y]代表x点到y点的最短距离（无非是顺时针和逆时针两种距离）。类似的有f[j][k][1]等于c[k-1]*remain[j][k-1]+f[j][k-1][1]和t[j][k]*remain[j][k-1]+f[j][k-1][0]中最小的那一个。
这次的优点是还算比较忍耐得住，没有过分得陷入时海看到题就立即编。能够把大部分时间于在分析和推理题目上。这点在一个队只有一台机子时将更为重要。并且，分析推理得越清楚，编码时也会更得心应手，本次我就没有因为编码WA过，不过因方法问题WA了一次。不过缺点也是很明显的，就是速度还不够。明明会的题没有得到及时的解决，这是最让人遗憾的事情。 |
|
|
