NOIP2015试题讨论贴

hr567

欢迎大家来此讨论2015年NOIP试题，提高组普及组皆可。

hr567

提高组我的第一题

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

我的第二题

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

你的第一题每行的末尾多输出了一个空格

diggersun

你的第一题每行的末尾多输出了一个空格

smileandyxu

diggersun 发表于 2015-11-8 13:54
你的第一题每行的末尾多输出了一个空格

那个空格不会忽略吗（尽管我没打）？

diggersun

最后一行的空格肯定会被忽略  不是最后一行的，没有定义，不过我想第一题，CCF不会如此无聊卡空格吧？

hr567

diggersun 发表于 2015-11-8 13:54
你的第一题每行的末尾多输出了一个空格

我在考试的时候写的代码注意到空格的问题了，把数组的第一个数单独输出了，回家重新写的时候就没有注意，输入输出考试的时候写的是<fstream>。

hr567

我考试时写的代码原样：

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

那么你100分到手了，避免了爆零的尴尬。