NOIP2014提高组第一试题解

NOIP2014提高组第一试题解

【第一题】石头剪刀布rps 【题目大意】

a和b石头剪刀布游戏，每个人一共有五种方式，相互之间的胜负关系给出，a和b出拳的方式是循环的，赢者得一份，其余不得分。 问n轮以后a和b的得分。

纯粹的模拟题，把胜负关系打表或者case出来即可。

1. #include 2. #include 3. #include 4.

5. using namespace std; 6. const int win[5][5] = { 7. 0,0,1,1,0, 8. 1,0,0,1,0, 9. 0,1,0,0,1, 10. 0,0,1,0,1, 11. 1,1,0,0,0 12. };

13. int a[205], b[205]; 14. int main() 15. {

16. freopen(\,\,stdin); 17. freopen(\,\,stdout); 18. int n, na, nb; 19. cin>>n>>na>>nb;

20. for (int i = 0; i < na; ++i) cin>> a[i]; 21. for (int i = 0; i < nb; ++i) cin>> b[i]; 22. int i = 0, j = 0;

23. int ascore = 0, bscore = 0; 24. while (n) {

25. ascore += win[a[i]][b[j]]; 26. bscore += win[b[j]][a[i]]; 27. i = (i + 1) % na; 28. j = (j + 1) % nb;

29. n --; 30. }

31. cout << ascore << \<< bscore<

【第二题】联合权值link

给出n个点，n-1条件的图，每个点均有点权值w[i]，如果i和j距离为2，那么他们会产生w[i] * w[j]的值，求问产生值中的最大值和产生值得总和。

分析：如果两两求，那么我们构造一个星形的图，这样的点对就接近n^2对，那么复杂度太高。

那么利用点i，周围的点a,b,c ,如果a，b，c在i的周围那么a，b，c相互之间的距离一定是2。那么他们会产生的值有ab+ac+ba+bc+ca+cb=(a+b+c)^2-a^2-b^2-c^2

故我们可以利用这种方法求出两两之间的和，至于最大值，直接选取a，b，c中的最大值和次大值来产生最大值。

1. #include 2. #include 3. #include 4. #include 5. #define maxn 600010 6. using namespace std; 7. struct Edge { 8. int v,next; 9. }e[maxn];

10. long long p[maxn],w[maxn], en = 0; 11. int f[maxn];

12. void add(int u, int v) { 13. en ++; 14. e[en].v = v; 15. e[en].next = f[u]; 16. f[u] = en; 17. }

18. int main() 19. {

20. freopen(\,\,stdin); 21. freopen(\,\,stdout); 22. int n,u,v; 23. cin >> n;

24. for (int i = 1; i <= n; ++i) f[i] = -1; 25. for (int i = 1; i < n; ++i) { 26. scanf(\, &u, &v); 27. add(u,v); 28. add(v,u); 29. }

30. long long total = 0, max = 0;

31. for (int i = 1; i <= n; ++i) scanf(\, &w[i]); 32. for (int i = 1; i <= n; ++i) { 33. int cnt = 0; 34. long long sum1= 0; 35. int max1 = 0, max2 = 0;

36. for (int j = f[i]; j != -1; j = e[j].next) { 37. p[++cnt] = w[e[j].v];

38. sum1 = (sum1 + p[cnt]) % 10007;

39. total = (total - p[cnt] * p[cnt] + 10007) % 10007; 40. if (p[cnt] > max1) max2 = max1, max1 = p[cnt]; 41. else

42. if (p[cnt] > max2) 43. max2 = p[cnt]; 44. }

45. if (cnt > 0) {

46. total = (total + sum1 * sum1) % 10007; 47. }

48. if (total < 0) total += 10007;

49. if (max1 * max2 > max) max = max1 * max2; 50. }

51. cout <

【第三题】飞扬的小鸟 bird 【题目大意】游戏规则：

1. 游戏界面是一个长为n，高为m的二维平面，其中有 k个管道（忽略管道的宽度）。

2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

3. 小鸟每个单位时间沿横坐标方向右移的距离为1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度Y。小鸟位于横坐标方向不同位置时，上升的高度X和下降的高度Y可能互不相同。

4. 小鸟高度等于0或者小鸟碰到管道时，游戏失败。小鸟高度为m时，无法再上升。 现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

分析：本体类似于经典的完全背包问题，每个阶段解决向上或者向下，而且次数不限，类似于物品个数没有限制。所以f[i][j]的状态可以从f[i-1][*]和f[i][*]中转移过来。 保证时间复杂度是O（nm）即可

1. #include 2. #include 3. #include 4. #include 5. #define maxn 10010 6. using namespace std; 7. const int inf = 0x7ffffff; 8. int n,m,k,p,l,h;

9. int x[maxn],y[maxn],down[maxn], up[maxn]; 10. int f[maxn][1001]; 11. int main() {

12. freopen(\,\,stdin); 13. freopen(\,\,stdout); 14. scanf(\,&n,&m,&k); 15. for (int i = 0; i < n; ++i) 16. scanf(\, &x[i], &y[i]); 17. for (int i = 1; i <=n; ++i) { 18. down[i] = 0; 19. up[i] = m + 1; 20. }

21. for(int i = 1; i <= k; ++i) { 22. cin >> p >> l >> h; 23. down[p] = l;