NOIP 2018 普及组初赛试题阅读程序解析

第 18 题

阅读程序写结果：

#include<stdio.h>
char st[100];

int main() {
  scanf("%s", st);//输入一个字符串
  for (int i = 0; st[i]; ++i) {
      if (‘A’ <= st[i] && st[i] <= ‘Z’)//如果是大写字母，执行指令
      st[i] += 1;//往后退一位（如A变成B，B变成C）
  }//是小写字母就照常输出
  printf("%s/n", st);//输出结果
  return 0;
}

输入：QuanGuoLianSai

解析：这个程序其实并不难。就是输入一个字符串，大写字母就往后退一位，小写字母照常输出就可以了。具体见代码注释。

答案：RuanHuoMianTai

第 19 题

阅读程序写结果:

#include <stdio.h>
int main() {
   int x;
   scanf("%d", &x);
   int res = 0;//res是result的缩写
   for (int i = 0; i < x; ++i) {//循环x-1次
      if (i * i % x == 1) {
          ++res;//如果符合条件，结果++
      }
   }
   printf("%d", res);//输出结果
   return 0;
}

输入：15

解析：这个程序也不是很难。输入一个数字，枚举0到x-1有没有取余这个数字等于1，有的话就输出答案。枚举可得1、4、11、14满足条件，有四个答案。具体见代码注释。

答案：4

第 20 题

阅读程序写结果:

#include <iostream>
using namespace std;
int n, m;

int findans(int n, int m) {
   if (n == 0) return m;
   if (m == 0) return n % 3;
   return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);//递归函数
}

int main(){
   cin >> n >> m;
   cout << findans(n, m) << endl;
   return 0;
}

解析：这个很简单，画一个图表。通过枚举可得n=5，m=6时，答案为8。

答案：8

第 21 题

阅读程序写结果:

#include <stdio.h>
int n, d[100];
bool v[100];

int main() {
   scanf("%d", &n);
   for (int i = 0; i < n; ++i) {
      scanf("%d", d + i);//d是个数组，+0就是d[0]，+1就是d[1]
      v[i] = false;
   }
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (!v[i]) {//如果v[i]是false
         for (int j = i; !v[j]; j = d[j]) {
            v[j] = true;
         }
         ++cnt;
      }
   }
   printf("%d/n", cnt);
return 0;
}

解析：可以模拟一下这个题。如果输入了十个数，0到9,。0的变化就是0>-7>-8>-9，1的变化就是1>-1（1是个自环），2的变化就是2>-4>-2（2、4循环），3的变化就是3>-3（3是个自环），4对应的是2（找过了），5的变化就是5>-5（5是个自环），6的变化就是6>-9>-6（6、9循环），7、8、9都提过了。程序想找的就是有几个环。

答案：6

第 22 题
完善程序

（最大公约数之和）下列程序想要求解整数 nn 的所有约数两两之间最大公约数的和对10007求余后的值，试补全程序。（第一空2分，其余3分）

举例来说，4的所有约数是1，2，4。1和2的最大公约数为1；2和4的最大公约数为2；1和4的最大公约数为1于是答案为1+2+1=4。

要求 getDivisor 函数的复杂度为O(sqrt(n))，gcd函数的复杂度为O(log max(a,b))。

#include <iostream>
using namespace std;

const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;

void getDivisor() {//得到n的所有因数，并存入a数组
   len = 0;//len代表有几个因数
   for (int i = 1; ① <= n; ++i)
      if (n % i == 0) {
         a[++len] = i;//如果len=1，就代表a[1]=1
         if ( ② != i) a[++len] = n / i;//有一个漏洞，当找到i后，有一种情况是n/i=i
      }
   }

int gcd(int a, int b) {
   if (b == 0) {
      ③ ;
   }
   return gcd(b, ④ );//按函数描述，gcd(a,b)需变成gcd(a,a%b)
}

int main() {
   cin >> n;
   getDivisor();
   ans = 0;
   for (int i = 1; i <= len; ++i) {//循环a数组中的所有因数，所以i对应的是a[i]
      for (int j = i + 1; j <= len; ++j) {//j从i+1出发，保证了不会重复
         ans = ( ⑤ ) % P;
      }
   }
   cout << ans << endl;
   return 0;
}

答案：1.i*i

2.n/i

3.return a

4.a%b

5.ans+gcd(a[i],a[j])

第 23 题
对于一个1到n的排列P（即1到n中每一个数在P中出现了恰好一次），令q[i]为第i个位置之后第一个比 P[i] 值更大的位置，如果不存在这样的位置，则 q[i]=n+1。举例来说，如果n=5 且 P 为 1 5 4 2 3 ，则q为 2 6 6 5 6。

下列程序读入了排列 PP ，使用双向链表求解了答案。试补全程序。

答案：

答案：1.a[x]=i
2.i+1
3.R[a[i]]
4.a[i]
5.R[i]

#include <iostream>
using namespace std;

const int N = 100010;
int n;
int L[N], R[N], a[N];

int main() {
   cin >> n;
   for (int i = 1; i <= n; ++i) {
      int x;
      cin >> x;
      ① ;//a[i]=x是通过下标来找值，但我们希望通过值来找下标，就是a[x]=i
   }

   for (int i = 1; i <= n; ++i) {
      R[i] = ② ;//右边是i+1
      L[i] = i – 1;//左边是i-1
   }

   for (int i = 1; i <= n; ++i) {
      L[ ③ ] = L[a[i]];//中间是a[i]，右边是R[a[i]]，左边是L[a[i]]
      R[L[a[i]]] = R[ ④ ];//让L[a[i]]的左边指向R[a[i]]，让R[a[i]]的右边指向L[a[i]]
   }

   for (int i = 1; i <= n; ++i) {
      cout << ⑤ << ” “;
   }

   cout << endl;
   return 0;
}