华师一附中OI组

标题: NOIP2015试题讨论贴 [打印本页]
作者: hr567    时间: 2015-11-7 21:16
标题: NOIP2015试题讨论贴
欢迎大家来此讨论2015年NOIP试题，提高组普及组皆可。
作者: hr567    时间: 2015-11-7 21:17
本帖最后由 hr567 于 2015-11-7 21:35 编辑

提高组我的第一题
  1. #include <iostream>
  2. using namespace std;
  3. int n, i, j, k, x, y;
  4. int a[29][29];
  5. int main()
  6. {
  7.     cin >> n;
  8.     y = 0;
  9.     x = (n-1)/2;
  10.     do
  11.     {
  12.         a[y][x] = ++k;
  13.         x = (x+1)%n;
  14.         y = (y-1+n)%n;
  15.         if (a[y][x] != 0)
  16.         {
  17.             x = (x-1+n)%n;
  18.             y = (y+2)%n;
  19.         }
  20.     }
  21.     while (k != n*n);
  22.     for (i = 0; i < n; ++i)
  23.     {
  24.         for (j = 0; j < n; ++j)
  25.             cout << a[i][j] << ' ';
  26.         cout << endl;
  27.     }
  28. }
复制代码

应该没什么问题吧。
作者: hr567    时间: 2015-11-7 21:33
我的第二题
  1. #include <iostream>
  2. using namespace std;
  3. int n, i, j, c, ans;
  4. int a[200000];
  5. bool b[200000];
  6. int main()
  7. {
  8.     cin >> n;
  9.     for (i = 0; i < n; ++i)
  10.     {
  11.         cin >> a[i];
  12.         --a[i];
  13.     }
  14.     for (i = 0; i < n; ++i)
  15.     {
  16.         for (j = 0; j < n; ++j)
  17.             b[j] = false;
  18.         j = i;
  19.         c = 0;
  20.         do
  21.         {
  22.             ++c;
  23.             b[j] = true;
  24.             j = a[j];
  25.         }
  26.         while (!b[j] && j != i);
  27.         if (c < ans || ans == 0)
  28.             ans = c;
  29.     }
  30.     cout << ans;
  31.     return 0;
  32. }
复制代码

请问数据有二十万个数字的话该怎么优化呀？
作者: diggersun    时间: 2015-11-8 13:54
你的第一题每行的末尾多输出了一个空格
作者: diggersun    时间: 2015-11-8 13:54
你的第一题每行的末尾多输出了一个空格
作者: smileandyxu    时间: 2015-11-8 14:10
diggersun 发表于 2015-11-8 13:54
你的第一题每行的末尾多输出了一个空格

那个空格不会忽略吗（尽管我没打）？
作者: diggersun    时间: 2015-11-8 14:11
最后一行的空格肯定会被忽略  不是最后一行的，没有定义，不过我想第一题，CCF不会如此无聊卡空格吧？
作者: hr567    时间: 2015-11-8 15:16
本帖最后由 hr567 于 2015-11-8 15:18 编辑
diggersun 发表于 2015-11-8 13:54
你的第一题每行的末尾多输出了一个空格

我在考试的时候写的代码注意到空格的问题了，把数组的第一个数单独输出了，回家重新写的时候就没有注意，输入输出考试的时候写的是<fstream>。
作者: hr567    时间: 2015-11-8 15:20
本帖最后由 hr567 于 2015-11-10 10:50 编辑

我考试时写的代码原样：
  1. #include <fstream>
  2. using namespace std;
  3. ifstream cin("magic.in");
  4. ofstream cout("magic.out");
  5. int n, i, j, k, x, y;
  6. int a[29][29];
  7. int main()
  8. {
  9.     cin >> n;
  10.     y = 0;
  11.     x = (n-1)/2;
  12.     do
  13.     {
  14.         a[y][x] = ++k;
  15.         x = (x+1)%n;
  16.         y = (y-1+n)%n;
  17.         if (a[y][x] != 0)
  18.         {
  19.             x = (x-1+n)%n;
  20.             y = (y+2)%n;
  21.         }
  22.     }
  23.     while (k != n*n);
  24.     for (i = 0; i < n; ++i)
  25.     {
  26.         cout << a[i][0];
  27.         for (j = 1; j < n; ++j)
  28.             cout << ' ' << a[i][j];
  29.         cout << '\n';
  30.     }
  31.     return 0;
  32. }
复制代码
作者: diggersun    时间: 2015-11-8 19:22
本帖最后由 diggersun 于 2015-11-8 19:27 编辑

那么你100分到手了，避免了爆零的尴尬。
作者: hr567    时间: 2015-11-10 10:28
想想去年，第一题一群三十分……
作者: smileandyxu    时间: 2015-11-20 12:54
http://www.tyvj.cn/Contest/449
tyvj比赛
作者: smileandyxu    时间: 2015-11-20 12:55
另外，跳石头那一题究竟要怎么选择向左合并还是向右合并距离？



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2