NOIP 2018普及组复赛C/C++参考答案

网友投稿 2019-05-18 17:54

第1题 标题统计

  1. #include

  2. #include

  3. using namespace std;

  4. int main()

  5. {

  6. freopen("title.in", "r", stdin);

  7. freopen("title.out", "w", stdout);

  8. string title;

  9. getline(cin, title);

  10. int len = title.size();

  11. for(int i = 0; i < (int)title.size(); i++)

  12. {

  13. if(' ' == title[i])

  14. {

  15. len--;

  16. }

  17. }

  18. cout << len;

  19. return 0;

  20. }

评测结果

https://cdn.china-scratch.com/timg/190520/1K4314432-0.jpg

第2题 龙虎斗

  1. #include

  2. #include

  3. #include

  4. using namespace std;

  5. #define LL long long

  6. int main()

  7. {

  8. freopen("fight.in","r",stdin);

  9. freopen("fight.out","w",stdout);

  10. int n, i, m, p1, p2;

  11. cin >> n;

  12. LL c[n + 1], s1, s2;

  13. for(i = 1; i <= n; i++)

  14. {

  15. cin >> c[i];

  16. }

  17. cin >> m >> p1 >> s1 >> s2;

  18. c[p1] += s1;

  19. LL lPower = 0; // 龙势力

  20. for(i = 1; i < m; i++)

  21. {

  22. lPower += c[i] * (m - i);

  23. }

  24. LL rPower = 0;

  25. for(i = m + 1; i <= n; i++)

  26. {

  27. rPower += c[i] * (i - m);

  28. }

  29. //cout << lPower << ' ' << rPower << endl;

  30. LL gap = abs(lPower - rPower); // 双方的气势差

  31. p2 = m; //默认放在m位置

  32. for(i = 1; i <= n; i++)

  33. {

  34. if(i < m) // 神兵加到左侧龙势力

  35. {

  36. if(abs(lPower + s2 * (m - i) - rPower) < gap)

  37. {

  38. gap = abs(lPower + s2 * (m - i) - rPower);

  39. p2 = i;

  40. }

  41. }

  42. else if(i > m) // 神兵加到右侧虎势力

  43. {

  44. if(abs(rPower + (i - m) * s2 - lPower) < gap)

  45. {

  46. gap = abs(rPower + (i - m) * s2 - lPower);

  47. p2 = i;

  48. }

  49. }

  50. }

  51. cout << p2 << endl;

  52. return 0;

  53. }

评测结果：

https://cdn.china-scratch.com/timg/190520/1K431F54-1.jpg

第3题 摆渡车

  1. #include

  2. #include

  3. #include

  4. using namespace std;

  5. int n,m;

  6. int data[1024];

  7. int sum[1024];

  8. int dp[1024][128];

  9. int main()

  10. {

  11. // freopen("bus.in", "r", stdin);

  12. // freopen("bus.out", "w", stdout);

  13. scanf("%d%d", &n, &m);

  14. for(int i=1; i<=n; ++i)

  15. {

  16. scanf("%d", data + i);

  17. }

  18. sort(data+1, data+n+1);

  19. for(int i=1; i<=n; ++i)

  20. {

  21. sum[i] = sum[i-1] + data[i];

  22. }

  23. // i代表第i个人（可能不止一个）

  24. for(int i = 1; i <= n; ++i)

  25. {

  26. // j表示当前这个人可能的候车时间，取值[0,m-1)

  27. for(int j = 0; j < m; ++j)

  28. {

  29. int curBusTime=data[i] + j;

  30. if(j)

  31. {

  32. dp[i][j] = dp[i][j - 1];

  33. }

  34. else

  35. {

  36. dp[i][j] = curBusTime*i - sum[i];

  37. }

  38. // 最近的一趟车可能出发的时间

  39. for(int lastBusTime = max(curBusTime - 2 * m + 1, 0); lastBusTime <= curBusTime - m; ++lastBusTime)

  40. {

  41. // lastCarry表示被上一辆车接走的学生人数

  42. int lastCarry = lower_bound(data + 1, data + n + 1, lastBusTime + 1)- (data + 1);

  43. // lastWait表示上一个人的候车时间

  44. int lastWait = min(lastBusTime - data[lastCarry], m - 1);

  45. // 动态转移方程

  46. int tmp = dp[lastCarry][lastWait] + (i - lastCarry) * curBusTime - (sum[i] - sum[lastCarry]);

  47. if(tmp< p="">

  48. {

  49. dp[i][j]=tmp;

  50. }

  51. }

  52. }

  53. }

  54. printf("%dn",dp[n][m-1]);

  55. return 0;

  56. }

评测结果

https://cdn.china-scratch.com/timg/190520/1K4323a2-2.jpg

第4题 对称二叉树

  1. #include

  2. inline int max(int x, int y)

  3. {

  4. return x > y ? x : y;

  5. }

  6. const int MAXN = 1000000;

  7. int cnt[MAXN + 5], lef[MAXN + 5], rig[MAXN + 5], ans;

  8. int v[MAXN + 5]; // 节点的权值

  9. // 检查左右子树是否对称

  10. bool checkSym(int leftId, int rightId)

  11. {

  12. if(leftId == -1 && rightId == -1)

  13. {

  14. // 若左右子节点都不存在，则认为是对称

  15. return true;

  16. }

  17. if(v[leftId] != v[rightId])

  18. {

  19. // 左子节点值 不等于 右子节点值，说明不对称

  20. return false;

  21. }

  22. else

  23. {

  24. // 左子节点值等于右子节点值，则左左=右右且右左=左右，说明对称；否则不对称。注意要递归下去

  25. return checkSym(lef[leftId], rig[rightId]) && checkSym(rig[leftId], lef[rightId]);

  26. }

  27. }

  28. // 求第nodeId个节点为根节点的二叉树，所包含的节点总数

  29. int nodeCnt(int nodeId)

  30. {

  31. // 当前节点不存在

  32. if(-1 == nodeId)

  33. {

  34. return 0;

  35. }

  36. else

  37. {

  38. // 左子树节点数 + 右子树节点树 + root本身的节点数1

  39. return cnt[nodeId] = nodeCnt(lef[nodeId]) + nodeCnt(rig[nodeId]) + 1;

  40. }

  41. }

  42. void dfs(int nodeId)

  43. {

  44. // 空节点为递归终止的条件

  45. if(-1 == nodeId)

  46. {

  47. return;

  48. }

  49. // 左子树节点总数 等于 右子树节点总数，这是对称的前提

  50. if(cnt[lef[nodeId]] == cnt[rig[nodeId]])

  51. {

  52. if(checkSym(lef[nodeId], rig[nodeId]))

  53. {

  54. // 若对称，获取总的节点数，并与原先的ans比较

  55. ans = max(ans, cnt[nodeId]);

  56. }

  57. }

  58. // 左子树下是否包含对称二叉树

  59. dfs(lef[nodeId]);

  60. // 右路子树是否包含对称二叉树

  61. dfs(rig[nodeId]);

  62. }

  63. int main()

  64. {

  65. freopen("tree.in", "r", stdin);

  66. freopen("tree.out", "w", stdout);

  67. int n;

  68. scanf("%d", &n);

  69. for(int i=1; i<=n; i++)

  70. {

  71. scanf("%d", &v[i]);

  72. }

  73. for(int i=1; i<=n; i++)

  74. {

  75. scanf("%d%d", &lef[i], &rig[i]);

  76. }

  77. nodeCnt(1);

  78. dfs(1);

  79. printf("%dn", ans);

  80. return 0;

  81. }

https://cdn.china-scratch.com/timg/190520/1K4322D5-3.jpg

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com