tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

NOIP2014提高组第一试题解


NOIP2014 提高组第一试题解
【第一题】石头剪刀布 rps 【题目大意】 a 和 b 石头剪刀布游戏,每个人一共有五种方式,相互之间的胜负关系给出,a 和 b 出拳的 方式是循环的,赢者得一份,其余不得分。 问 n 轮以后 a 和 b 的得分。 纯粹的模拟题,把胜负关系打表或者 case 出来即可。
1. #include <iostream>

; 2. #include <cstdio> 3. #include <cstdlib> 4. 5. using namespace std; 6. const int win[5][5] = { 7. 8. 9. 10. 11. 12. 0,0,1,1,0, 1,0,0,1,0, 0,1,0,0,1, 0,0,1,0,1, 1,1,0,0,0 };

13. int a[205], b[205]; 14. int main() 15. { 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. freopen("rps.in","r",stdin); freopen("rps.out","w",stdout); int n, na, nb; cin>>n>>na>>nb; for (int i = 0; i < na; ++i) cin>> a[i]; for (int i = 0; i < nb; ++i) cin>> b[i]; int i = 0, j = 0; int ascore = 0, bscore = 0; while (n) { ascore += win[a[i]][b[j]]; bscore += win[b[j]][a[i]]; i = (i + 1) % na; j = (j + 1) % nb;

29. 30. 31. 32. 33. } }

n --; cout << ascore << " "<< bscore<<endl; return 0;

【第二题】联合权值 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 <iostream> 2. #include <cstdio> 3. #include <cstdlib> 4. #include <vector> 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. 14. 15. 16. 17. } 18. int main() 19. { en ++; e[en].v = v; e[en].next = f[u]; f[u] = en;

20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. }

freopen("link.in","r",stdin); freopen("link.out","w",stdout); int n,u,v; cin >> n; for (int i = 1; i <= n; ++i) f[i] = -1; for (int i = 1; i < n; ++i) { scanf("%d %d", &u, &v); add(u,v); add(v,u); } long long total = 0, max = 0; for (int i = 1; i <= n; ++i) scanf("%d", &w[i]); for (int i = 1; i <= n; ++i) { int cnt = 0; long long sum1= 0; int max1 = 0, max2 = 0; for (int j = f[i]; j != -1; j = e[j].next) { p[++cnt] = w[e[j].v]; sum1 = (sum1 + p[cnt]) % 10007; total = (total - p[cnt] * p[cnt] + 10007) % 10007; if (p[cnt] > max1) max2 = max1, max1 = p[cnt]; else if (p[cnt] > max2) max2 = p[cnt]; } if (cnt > 0) { total = (total + sum1 * sum1) % 10007; } if (total < 0) total += 10007; if (max1 * max2 > max) max = max1 * max2; } cout <<max<<" "<<total<<endl; return 0;

【第三题】飞扬的小鸟 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 <iostream> 2. #include <cstdio> 3. #include <cstdlib> 4. #include <cstring> 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. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. } for(int i = 1; i <= k; ++i) { cin >> p >> l >> h; down[p] = l; freopen("bird.in","r",stdin); freopen("bird.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for (int i = 0; i < n; ++i) scanf("%d %d", &x[i], &y[i]); for (int i = 1; i <=n; ++i) { down[i] = 0; up[i] = m + 1;

24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. } } } }

up[p] = h; for (int i = 1; i <= n; ++i) for (int j = 0; j <= m; ++j) f[i][j] = inf; f[0][0] = inf; int arrive = k; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if(j >= x[i-1]){ f[i][j] = min(f[i][j], f[i-1][j-x[i-1]] + 1); f[i][j] = min(f[i][j], f[i][j-x[i-1]] + 1); } if(j == m) { for(int k=j-x[i-1];k<=m;k++) { f[i][j] = min(f[i][j], f[i-1][k] + 1); f[i][j] = min(f[i][j], f[i][k] + 1); } } } for (int j = down[i]+1; j <= up[i]-1; ++j) if( j + y[i-1] <= m) f[i][j] = min(f[i][j], f[i-1][j+y[i-1]]); for (int j = 1; j <= down[i]; ++j) f[i][j] = inf; for (int j = up[i]; j <= m; ++j) f[i][j] = inf; int cnt = k, ans = inf; for (int i = n; i >= 1; i--) { for (int j = down[i]+1; j <= up[i]-1; ++j) if (f[i][j] < inf) ans = min(ans, f[i][j]); if (ans != inf) break; if (up[i] <= m) cnt --; if(cnt==k) printf("1\n%d\n", ans); else printf("0\n%d\n", cnt); return 0;


推荐相关:

NOIP2014提高组第一试题解

NOIP2014 提高组第一试题解【第一题】石头剪刀布 rps 【题目大意】 a 和 b 石头剪刀布游戏,每个人一共有五种方式,相互之间的胜负关系给出,a 和 b 出拳的...


NOIP2014提高组第二试题解

NOIP2014提高组第试题解_IT认证_资格考试/认证_教育专区。NOIP2014提高组第试题解 1.无线网络发射器选址只需在读入数据时对每个场所将其能接触到 WIFI 信号...


NOIP2014提高组复赛试题day1+day2

NOIP2014提高组复赛试题day1+day2_从业资格考试_资格考试/认证_教育专区。CCF ...保证存在一组最优解使得同一单位时间 最多点击屏幕 3 次; 对于 50%的数据:...


NOIP2009提高组复赛题解

NOIP2009提高组复赛题解_IT/计算机_专业资料。NOIP2009提高组复赛题解 NOIP2009 提高组复赛题解(1) 2010-02-21 19:38 1. 潜伏者 (spy.pas/c/cpp) 【问题...


NOIP2014提高组复赛试题

NOIP2014提高组复赛试题_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克...保证存在一组最优解使得同一单位时间最多点击屏幕 3 次; 对于 50%的数据:5...


noip2012 开车旅行 题解

noip2012开车旅行 题解题目大意:给出 n 个排成一...2014年驾照交规 2014年1月1日起“驾照新规”出炉 ...noip 2012 提高组 解题报... 19页 免费 NOIP 2012...


noip2010提高组解题报告

0​1​0​提​高​组​解​题​报...全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 ...2014年笑话大全之让你笑个够 儿童笑话大全爆笑 爆笑...


NOIP2005提高组解题报告

NOIP2005提高组解题报告_初一理化生_理化生_初中教育...第一题:谁拿了最多的奖学 第一题:谁拿了最多的...上一个巧妙的剪枝就可以在很短的时间内出解.可以...


Noip2014初赛提高组C试题及答案(完整版)

Noip2014初赛提高组C试题及答案(完整版)_IT认证_资格考试/认证_教育专区。Noip2014 初赛提高组试题及答案(完整版) 提高组 C 语言试题 一、单项选择题(每题 1.5...


NOIP2004 提高组试题

NOIP2004 提高组试题_其它考试_资格考试/认证_教育专区...输入数据保证有且仅有一组解, 【输入文件】 输入...2014年笑话大全之让你笑个够 儿童笑话大全爆笑 爆笑...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com