一些小知识点

关于输入和输出

  1. scanf 和cin
    知识点：
    scanf 在读入的时候，不会自动过滤掉空格，制表符
    cin则自动过滤掉了
  2. fgets 
    1
    2
    3
    4
      fgets（buf，n，stdin）;
    //buf:这是指向一个字符数组的指针，该数组存储了要读取的字符串
    //n:这是要读取的最大字符数（包括最后的空字符）。通常是使用以 str 传递的数组长度
    //stdin

关于循环

  1. 循环n次的一个简单方法

    1
    while(n--){...}

  2. 简单斐波那契

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    #include <iostream>
    using namespace std;
       int main()
     {
      int n;
      cin >> n;
      int a = 0, b = 1;

      for (int i = 0; i < n; i ++ )
       {
         cout << a << ' ';
         int c = a + b;
         a = b;
         b = c;
       }
      cout << endl;
      return 0;
     }

  3. 循环在时间复杂度方面的一个优化

    例题：
    一个整数，除了本身以外的其他所有约数的和如果等于该数，那么我们就称这个整数为完全数。

    例如，6 就是一个完全数，因为它的除了本身以外的其他约数的和为 1+2+3=6。

    现在，给定你 N 个整数，请你依次判断这些数是否是完全数。

    输入格式
    第一行包含整数 N，表示共有 N 个测试用例。

    接下来 N 行，每行包含一个需要你进行判断的整数 X。

    输出格式
    每个测试用例输出一个结果，每个结果占一行。

    如果测试数据是完全数，则输出 X is perfect，其中 X 是测试数据。

    如果测试数据不是完全数，则输出 X is not perfect，其中 X 是测试数据。

    数据范围
    1≤N≤100,
    1≤X≤108

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include<cmath>
using namespace std;
int main()
{
  int N;
  cin>>N;
  while(N--)
  {
      int m ,sum=0;
      cin>>m;
      if(m==1) printf("%d is not perfect\n",m);
      else 
      {
          sum+=1;
          for(int i=2;i<=sqrt(m);i++) if(m%i==0) 
       {
          int n=m/i;//做除后的另一个约数
          if(n==i) sum+=i;//判断是否是开根
          else sum+=(i+n);
       }
           if(sum==m) printf("%d is perfect\n",m);
           else printf("%d is not perfect\n",m);
      }
  }
  return 0;
}
  • x本身除以一个约数往往可以得到另外一个约数，如果在这里思考下手并优化，极有可能减少至少开根号的循环量
  • 使用数学函数，sqrt 作为限制循环次数的条件，而另外一个约数则由输入数x除以当前的循环的约数，即可求得另一约数
    注：此处需要考虑等于的情况，比如16， 开根号是4， 4也是约数， 优化过后，复杂度为O(10^6) 100万 完全hold住
  • 以后遇到此类题，诸如质数、完全数 等定义中带有约数、需要整除，优化方面皆可朝开平方处思考

关于数组

首先是要理解数组，是一种储存数据的强而有力的手段

1.