正式竞赛笔记

strcmp：C++自带函数---字典序

strcpy:交换顺序

getline:

• 本质上有两种getline函数，一种在头文件中，是istream类的成员函数。一种在头文件中，是普通函数。
  
  • 在中的getline函数有两种重载形式：
    istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );
    作用是从istream中读取至多n个字符保存在s对应的数组中。即使还没读够n个字符，如果遇到换行符'\n'（第一 种形式）或delim（第二种形式），则读取终止，'\n'或delim都不会被保存进s对应的数组中。
  • 在中的getline函数有四种重载形式：
    istream& getline (istream& is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);
istream& getline (istream& is, string& str);
istream& getline (istream&& is, string& str);
    用法和上一种类似，不过要读取的istream是作为参数is传进函数的。读取的字符串保存在string类型的str中。
    
• getline不是C库函数，而是gcc的扩展定义或者C++库函数。它会生成一个包含一串从输入流读入的字符的字符串，直到以下情况发生会导致生成的此字符串结束。
  
  • 到文件结束；
  • 遇到函数的定界符；
  • 输入达到最大限度。
• 比较抽象，那么。。。和cin对比一下
  
  • 举个例子，比如 cin >> namel;
    然后写一段代码，像这样

#include <iostream>
#include <string> 
using namespace std;
int main()
{
    string name;
    string city;    
    cout << "Please enter your name: ";
    cin >> name;
    cout << "Enter the city you live in: ";
    cin >> city;
    cout << "Hello, " << name << endl;
    cout << "You live in " << city << endl;
    return 0;
}

而结果呢，是这样的

Please enter your name： John Doe
Enter the city you live in: Hello, John
You live in Doe

所以说虽然可以使用 cin 和 >> 运算符来输入字符串，但它可能会导致一些需要注意的问题：当 cin 读取数据时，它会传递并忽略任何前导白色空格字符（空格、制表符或换行符）。一旦它接触到第一个非空格字符即开始阅读，当它读取到下一个空白字符时，它将停止读取

而在这个示例中，用户根本没有机会输入 city 城市名。因为在第一个输入语句中，当 cin 读取到 John 和 Doe 之间的空格时，它就会停止阅读，只存储John作为name的值。在第二个输入语句中，cin使用键盘缓冲区中找到的剩余字符，并存储 Doe 作为 city 的值。

• 
  
  • 为了解决这个问题，可以使用一个叫做getline的C++函数。此函数可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。
    举个栗子getline(cin, inputLine);

#include <iostream>
#include <string> 
using namespace std;
int main()
{
    string name;
    string city;
    cout << "Please enter your name: ";
    getline(cin, name);
    cout << "Enter the city you live in: ";
    getline(cin, city);
    cout << "Hello, " << name << endl;
    cout << "You live in " << city << endl;
    return 0;
}

输出结果

Please enter your name: John Doe
Enter the city you live in: Chicago
Hello, John Doe
You live in Chicago

刘子闻（神！）讲的高精度【太强了】\

1.6 10:大整数加法

总时间限制: 1000ms 内存限制: 65536kB

描述

求两个不超过200位的非负整数的和。

输入

有两行，每行是一个不超过200位的非负整数，可能有多余的前导0。

输出

一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。

样例输入

22222222222222222222
33333333333333333333

样例输出

55555555555555555555

#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    char a[205]={0},b[205]={0};
    int d[205]={0},f[205]={0},e[205]={0},c,l=0;
    int l1,l2;
    gets(a);
    gets(b);
    l1=strlen(a);
    l2=strlen(b);
    for(c=0;c<l1;c++)
    {
        d[205-l1+c]=a[c]-'0';
    } 
    for(c=0;c<l2;c++)
    {
        f[205-l2+c]=b[c]-'0';
    }
    c=205;
    while(c--)
    {
        e[c]+=d[c]+f[c];
        if(e[c]>=10)
        {
            e[c-1]++;
            e[c]=e[c]%10;
        }
    }
    for(c=0;c<205;c++)
    {
        if(e[c]!=0) 
        break;
    }
    for( c;c<205;c++)
    l+=printf("%d",e[c]);
    if(l==0) 
    printf("0");
    return 0;
}

• 看好了哈，主程序第一行和第二行那些数组，如果你在开的小一点，你就会得到（等会儿，我试一下）额。。。九分的好成绩！！！

1.6 11:大整数减法

总时间限制: 1000ms 内存限制: 65536kB

描述

求两个大的正整数相减的差。

输入

共2行，第1行是被减数a，第2行是减数b(a > b)。每个大整数不超过200位，不会有多余的前导零。

输出

一行，即所求的差。

样例输入

9999999999999999999999999999999999999
9999999999999

样例输出

9999999999999999999999990000000000000

#include<cstdio>
#include<cstring>
#define m 220
int x[m],y[m];
char b[m],c[m];
int i,s,r,t,z; 
int main() 
{
    scanf("%s%s",b,c);
    s=strlen(b);
    r=strlen(c);
    if(s>r) t=s;
    else t=r;
    for(int i=0;i<s;i++) x[i]=b[s-i-1]-'0';
    for(int i=0;i<r;i++) y[i]=c[r-i-1]-'0';
    for(int i=0;i<t;i++)
    {
        x[i]-=y[i];
        if(x[i]<0)
        {
            x[i+1]--;
            x[i]+=10;
        }
    }
    int z=t;
    while(x[z]==0&&z!=0)
    {
        z--;
    }
    for(int i=z;i>=0;i--)
    {
        printf("%d",x[i]);
    }
    return 0;
}

• 这次我好像注意数组了，然鹅。。。逻辑上有些失误，运算过程中出现了一点差错。嗯。没了（听取WA声一片）

1.13 09:大整数乘法

总时间限制: 1000ms 内存限制: 65536kB

描述

求两个不超过200位的非负整数的积。

输入

有两行，每行是一个不超过200位的非负整数，没有多余的前导0。

输出

一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。

样例输入

12345678900
98765432100

样例输出

1219326311126352690000

#include<cstdio>
#include<cstring>
#include<cmath>
#define m 500
using namespace std;
int x[m],y[m], z[m];
char b[m],c[m];
int main() 
{
    int len1, len2, len3;
    scanf("%s%s", b, c);
    len1=strlen(b); 
    len2=strlen(c);
    for(int i=0; i<len1; i++)
        x[i] = b[len1-1-i]-'0';
    for(int i=0; i<len2; i++)
        y[i] = c[len2-1-i]-'0';
    for(int i=0; i<len1; i++)
    {
        for(int j=0; j<len2; j++)
        z[i+j]+=x[i]*y[j];
        len3 = len1+len2;
    }   
    for(int i=0; i<=len3; i++)
    {
        if(z[i]>=10)
        {
            z[i+1]+=z[i]/10;
            z[i]%=10;
        }
    }
    while(z[len3-1]==0 && len3>1) len3--;
    for(int i=len3-1; i>=0; i--)
    {
        printf("%d", z[i]);
    }
    return 0;
}

洛谷 P1480 A/B Problem（高精除以低精）

题目描述

输入两个整数a,b，输出它们的商(a<=10^5000,b<=10^9)

输入格式

两行，第一行是被除数，第二行是除数。

输出格式

一行，商的整数部分

输入样例

10
2

输出样例

5

#include<cstdio>
#include <cstring>
using namespace std;
int a[10000];
int y; 
int l=0; 
int yushu; 
int shang;
int f=0; 
int main()
{
    char c=getchar();
    while (c>='0' && c<='9')
    {
        l++;
        a[l]=(c-'0');
        c=getchar();    
    }
    //scanf("%s",a);
    //l=strlen(a);
    scanf("%d",&y); 
    for (int i=1;i<=l;i++) 
    {
        yushu=a[i]%y;//第i位的余数 
        shang=a[i]/y;//第i位的商 
        a[i]=shang;
        a[i+1]+=yushu*10;//把余数弄到下一位
    }
    for (int i=1;i<=l;i++)
    {
        if (f==0 && a[i]>0) f=1;
        if (f==1) printf("%d",a[i]);
    }
    return 0; 
}

• 看看代码中的注释吧。。。
• 高精除以高精在洛谷上评测的是一道黑题（注意！是黑题！！！），所以。。。我不会

洛谷 P1706 全排列问题

题目描述

输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

n(1≤n≤9)

输出格式

由1～n组成的所有不重复的数字序列，每行一个序列。每个数字保留5个场宽。

输入输出样例

输入

3

输出

1    2    3
1    3    2
2    1    3
2    3    1
3    1    2
3    2    1

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m=0;
int a[10];
bool vis[25];
void q()
{
    if(m==n)
    {
        for(int i=0; i<n; i++) printf("%5d", a[i]);
        printf("\n");
    }
    for(int i=1; i<=n; i++)
    {
        if(vis[i]==0)
        {
            vis[i]=1;
            a[m++]=i;
            q();
            m--;
            vis[i]=0;
        }
    }
}
int main()
{
    scanf("%d", &n);
    q();
    return 0;
}

• 这里的话就先定义一个函数，用来排列搜索所有情况（从头扫一遍）。
• 然后，你也看到了，主程序就那么一丢丢/手动滑稽/

时间复杂度

先来一段有趣的对话

看到时间复杂度的重要性了吧

那什么是时间复杂度呢

一天过后，小灰和大黄各自交付了代码，两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒，内存占用5MB。小灰的代码运行一次要花100秒，内存占用500MB。于是......

由此可见，衡量代码的好坏，包括两个非常重要的指标：

• 运行时间；
• 占用空间。

我们先看一下标准的定义

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

• “大O记法”：在这种描述中使用的基本参数是n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

• 常见的时间复杂度

  • 按数量级递增排列，常见的时间复杂度有：
    $$常数阶O(1)<对数阶O(logn)<线性阶O(n)<线性对数阶O(nlogn)<平方阶O(n^2)<立方阶O(n^3)<...<k次方阶O(n^k)<指数阶O(2^n)$$ （$log2n= logn$）
    其中，
    $$O(n)，O(n^2)， 立方阶O(n^3),...， k次方阶O(n^k)$$ 为多项式阶时间复杂度，分别称为一阶时间复杂度，二阶时间复杂度。。。
    $$O(2^n)$$ 指数阶时间复杂度，该种不常见
    $$对数阶O(logn),线性对数阶O(nlogn)$$ 除了常数阶以外，该种效率最高

如何计算时间复杂度

• 通常情况下，我们看循环次数来计算时间复杂度
  
  • 举个栗子
    $$\sum_{i=1}^n\frac{1}{2}(n-i+1)(n-i+2)$$
    那这里，它的时间复杂度就是$O(n^3)$
    原式$\Rightarrow \sum_{i'=1}^n\frac{1}{2}i(i+1)$
    $\Rightarrow \frac{1}{2}\sum_{i'=1}^ni^2+\frac{1}{2}\sum_{i'=1}^ni$前一个$O(n^3)$后一个$O(n^2)$
  • 如果这个比较抽象，那随便来段代码

for(i=0;i<n;i++)
    {  
       for(j=0;j<i;j++)  
       {
          for(k=0;k<j;k++)
             x=x+2;  
       }
    }

那我们可以看到，代码中出现了三层循环，那么我们可以认为它的时间复杂度为$O(n^3)$

当i=m,j=k的时候,内层循环的次数为k

当i=m时,j可以取 $0,1,…,m−1$

所以这里最内循环共进行了$0+1+…+m−1=\frac{(m−1)m}{2}$次

所以,i从0取到n, 则循环共进行了:$0+\frac{(1−1)×1}{2}+…+\frac{(n−1)n}{2}=\frac{n(n+1)(n−1)}{6}$

所以时间复杂度为$O(n^3)$

• 平时听到某些大佬口中的$O(1)$是什么呢？
  temp=i;i=j;j=temp; 遇到这样的语句，我们可能会听到“使用$O(1)$查询。。。”之类的话语。实际上与n无关，只是在执行语句。

• 当然，在一些场合，你可能会听到频度这个词。那频度又是什么？（很明显我前面忘说了）

  • 还是来看一下标准定义

    一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为$T(n)$。

  • 其实我也没太看懂

  • 所以还是举个栗子吧
    假设$T(n)=2n^2+n+1$，那么我们就可以忽略n的最高次项的系数，以及其他项（包括常数项），认为$T(n)=O(n^2)$
    当然，你也可以类比一下。
    物理老师上课讲过当$m<<M$的时候，表达式$a=\frac{M}{M+m}g$忽略m的取值，即m微小到不对结果起到作用/手动@yyp/
  • 样例代码呢。。。

for (i=1;i<n;i++) {
    y=y+1;         ①   
    for(j=0;j<=(2*n);j++)   { 
    x++; }       ②      
}

像这样，代码中语句①的频度是$n−1$

语句②的频度是$(n−1)∗(2n+1)=2n^2−n−1$

$f(n)=2n^2−n−1+(n−1)=2n^2−2$（f(n)上面提到了）

该程序的时间复杂度$T(n)=O(n^2)$

i=1;       ①
while (i<=n)
    i=i*2; ②

语句①的频度是1

到这里，又卡住了，语句②是什么鬼。。。（我也不知道）

那我们可以设语句②的频度是$f(n)$, 则：$2^{f(n)}≤n$；$f(n)≤logn$

取最大值$f(n)=logn$，$T(n)=O(logn)$

• 总结一下（来源于网络）

一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数$f(n)$，因此，算法的时间复杂度记做：$T(n)=O(f(n))$。随着模块n的增大，算法执行的时间的增长率和$f(n)$的增长率成正比，所以$f(n)$越小，算法的时间复杂度越低，算法的效率越高。

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出$T(n)$的同数量级（它的同数量级有以下：$logn, n, nlogn, n^2, n^3, 2^n,n!$)，找出后，$f(n)=该数量级$，若$\frac{T(n)}{f(n)}$求极限可得到一常数c，则时间复杂度$T(n)=O(f(n))$。

• 看到上面那个求极限了？就是
  $$\lim_{n \rightarrow+\infty}\frac{T(n)}{f(n)}$$

C++ cmath库中的函数

今天模拟，想调用<cmath>中的函数，然鹅。。。突然忘了，所以还是总结一下吧