这是本系列的第一篇文章，旨在记录我学习C++历程中所有的感想和感悟。

1.1 士兵列队训练问题

题目信息

题目描述：

某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

输入

本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。

输出

共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。

样例输入

2
20
40

样例输出

1 7 19
1 19 37

数据范围

N<5000

题目分析

方法一：数组标记

这是一个较为简单的方法，运用桶的思想，数组下角标为士兵现有序号，开局桶内均为“空”的（即原本序号a[i]=i）；报数后出列的人的桶内装满水（序号变为无限大，a[i]=5010），通过排序将其甩到队尾，剩下的“空”桶们重复这一步骤。除此以外，我们需要记住每一轮出列了多少人，剩下的空桶数即可已确定。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a[5010];
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>m;
        for(int i=1;i<=m;i++)
        {
           a[i]=i;  
        }
        while(m>3)
        {
            for(int i=1;i<=m;i++)
            {
                if(i%2==0) a[i]=5010;   
            }
            sort(a+1,a+1+m);
            m=m-m/2;
            if(m<=3) break;
            for(int i=1;i<=m;i++) 
            {
                if(i%3==0) a[i]=5010;
            }
            sort(a+1,a+1+m);
            m=m-m/3;
        }
        for(int i=1;i<=m;i++)
          cout<<a[i]<<" ";
        }
        return 0;   
}

时间596ms，内存2176KB

方法二：线性链表

完全基于指针模拟士兵站队以及出列。初始时，士兵1,2,3,4,5站在一起。当报完1和2后，2,4出列，1的下一个不再指向2，而直接指向3；3不再指向4，直接指向5：

改变前      1--->2--->3--->4--->5-- ······
                    进|
                    行|
                    报|
                    数v
改变后      1-------->3-------->5-- ······

               ->2-      ->4-

最后，线性表里只会剩下满足要求的人，直接输出就行。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef struct line
{
    int a;
    int pos;
    line *next=NULL;
} line;//线性表指针
int operate2(line *p_head)//12报数线性表操作
{
     int j = 0;
    line *pl = p_head;
    do
    {
        j++;
        if ((pl->pos) % 2 == 1)
        {
            pl->next==NULL? pl->next=NULL : pl->next = ((pl->next)->next);//防止第i个指向的第i+2个指针为空指针而崩溃
        }
        pl->pos = j;
        pl=pl->next;
    } while (pl!=NULL);
    return j;
}
int operate3(line *p_head)//123报数线性表操作
{
    int j = 0;
    line *pl = p_head;
    do
    {
        j++;
        if ((pl->pos) % 3 == 2)
        {
             pl->next==NULL? pl->next=NULL : pl->next = ((pl->next)->next);
        }
        pl->pos = j;
        pl=pl->next;
    } while (pl!=NULL);
    return j;
}
void print(line *p_head)
{
    line *pli=p_head;
    for(;pli!=NULL;pli=pli->next)
    cout<<pli->a<<" ";
    cout<<endl;
}
void operate(line *p_head)//打印线性表
{
    while(1)
    {
        if(operate2(p_head)<=3)break;
        if(operate3(p_head)<=3)break;
    }
    print(p_head);
    return;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int ns;
        cin >> ns;
        line *p = new line[ns + 1];
        for (int j = 1; j <= ns; j++)
        {
            p[j].a = p[j].pos = j;
            if (j < ns)
                p[j].next = &(p[j + 1]);
        }
        line *p_head = &p[1];
        if(ns<=3)//一开始忘了三个人及以下不需要进行报数，WA50%（qaq）
        {
            print(p_head);
        }
        else 
        operate(p_head);
        delete[] p;//释放内存，速度加快的代价是内存飙到131620kb，释放后为2328kb
    }
    system("pause");
    return 0;
}

时间223ms，内存2328KB

速度加快是省去了排序的时间。（再二分sort也不可能0ms过吧）

1.2 斐波那契数列

题目信息

题目描述：

斐波那契数列中 求出斐波那契数列的第n项。

输入

第一行输入一个整数T表示样例个数,对于每个样例,输入一个整数n表示需要求出第n项斐波那契数字。

输出

对于每个样例,输出一个数字num表示第n项斐波那契数字。

样例输入

3
1
2
3

样例输出

1
1
2

数据范围 n <= 60

题目分析

方法一：小数据递归

n比60小真的没啥威胁度，暴力倒推都能搞出来。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,m,a[1001];
    a[0]=0,a[1]=1;
    cin>>n;
    for(int i=1;i<=n;i++)
    {  
      cin>>m;
       if (m>=2)
       {
        for(int i=2;i<=m;i++)
        {
            a[i]=a[i-1]+a[i-2];
           }
       }
       cout<<a[m]<<endl;
    }
    return 0;
}

时间4ms，内存2176KB

方法2：矩阵快速幂

其实这个题这么玩就算是玩坏了，就回到了寒假快乐十道题中的H。这个题如果再苟一点，n直接小于1e8，就相当于超级加辈了：unsigned long long装不下，要用mod100000007，暴力递归1s内绝对超时，这个时候就是矩阵快速幂的天下了。

矩阵快速幂是怎么回事？还得先说斐波那契的表达式

表达式的数列形式是：

$ a_{n+1} = a_n +

而写成矩阵形式就是：（线代不会qaq）

这就引发了一个好玩的东西：我们把加法变成了乘法。而乘法可以通过快速幂加速运算。

因此，斐波那契的矩阵幂公式为：

剩下的，就是二分实现矩阵快速幂的事情了。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct matrix
{
    int m;
    int n;
    ll a[3][3] = {(0, 0, 0), (0, 0, 0), (0, 0, 0)};
};
matrix matrixmul(matrix A, matrix B)
{
    matrix C;
    C.m = A.m;
    C.n = A.n;
    for (int i = 1; i <= A.m; i++)
        for (int j = 1; j <= B.n; j++)
        {
            for (int s = 1; s <= A.n; s++)
            {
                C.a[i][j] += (A.a[i][s] * B.a[s][j]);//第一次错在这里，矩阵乘法公式都记错了，3月3号就考试了，哎，回炉得了qaq
            }
        }
    return C;
}
matrix matrixquickpow(matrix A, int n)
{
    matrix E;
    E.m = E.n = 2;
    E.a[1][1] = E.a[2][2] = 1;
    while (n)
    {
        if (n & 1)
            E = matrixmul(E, A);
        A = matrixmul(A, A);
        n >>= 1;
    }
    return E;
}
int main()
{
    int ns;
    cin >> ns;
    for (int i = 1; i <= ns; i++)
    {
        int n;
        cin >> n;
        if (n == 1 || n == 2)
        {
            cout << "1" << endl;
            continue;
        }
        matrix p;
        p.m = 2;
        p.n = 1;
        p.a[2][1] = 1;
        p.a[1][1] = 1;
        matrix Ez;
        Ez.m = Ez.n = 2;
        Ez.a[1][1] = Ez.a[1][2] = Ez.a[2][1] = 1;

        matrix ans;
        ans = matrixmul(matrixquickpow(Ez, n - 2), p);
        cout << ans.a[1][1] << endl;
    }
    system("pause");
    return 0;
}

时间5ms（nnd还慢了1ms），内存2220KB。

1.3 高精度加法（A+B）

题目信息

（这还用说？？？！）

题目分析

常规的竖式计算模拟，string类记录数字，打包成函数就可以了。注意。每一列相加的计算都要加上上一次的进位并减掉下一次的进位，最后判断是否需要加位数。毕竟99+1=100，你不能写个00吧（bushi

代码：

#include<bits/stdc++.h>
using namespace std;
string proplus(string a,string b)
{
    string c;
    int len;
    int len1=a.length(),len2=b.length();//统计长度
    //补齐空位
    if(len1>len2)
    {
        len=len1;
        for(int i=1;i<=len1-len2;i++)
        b="0"+b;
    }
    else
    {
        len=len2;
        for(int i=1;i<=len2-len1;i++)
        a="0"+a;
    }
    竖式进位计算模拟
    int cf=0,temp=0;
    for(int i=len-1;i>=0;i--)
    {
        temp=a[i]-'0'+b[i]-'0'+cf;
        cf=temp/10;
        temp%=10;
        c=char(temp+'0')+c;
    }
    if(cf!=0)
    c=char(cf+'0')+c;//字符串叠加运算
    return c;
}
int main()
{
    string a,b;
    cin>>a>>b;
    cout<<proplus(a,b)<<endl;
    system("pause");
    return 0;
}

内存2224KB，时间3ms

1.4 三角形个数

题目信息

题目描述：

小有一个仅包含非负整数的数组，她想知道有多少个三元组，满足且可能作为某个三角形的三条边的边长。

输入

第一行输入一个正整数，表示数组中元素个数；

第二行个非负整数，表示中元素，以空格隔开；

输出

输出一个数，表示满足题意的三元组个数

样例输入

4
2 2 3 4

样例输出

3

数据范围

，中任意元素满足。

题目分析

挑选类问题（排列组合类）直接套用深度优先搜索（DFS）模板。 终点状态明确：目标个数为3. 递归搜索状态：搜索完了第个，要继续搜索第个到.

void dfs(int m,int next)
{
    if(m==3)
    {
        if() ans++; //检查是否满足条件
        return;
    }
    for(int i=mext;i<=n;i++)
    {
        rem[m+1]=a[i];//搜索记忆
        dfs(m+1,i+1);//下一步搜索
    }
    return;
}

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int ans=0;
int n;
int s[4];
void dfs(int num,int next)
{
    
    if(num==3)
    {
        if(s[1]+s[2]>s[3]&&abs(s[1]-s[2])<s[3])ans++;//三角形判定
        return;
    }
    for(int i=next;i<=n;i++)
    {
        s[num+1]=a[i];//不能是s[m+1]=a[next]，必须是a[i]才能实现变化写入。
        dfs(num+1,i+1);
    }
    
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    dfs(0,1);
    cout<<ans<<endl;
    system("pause");
    return 0;
}

内存2224 KB，时间455 ms

1.5 找零

题目信息

题目描述：

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？如果无法支付K元，输出-1.

输入

输入第一行为一个整数T，表示样例个数。 对于每个样例，第一行输入一个整数N表示需要找零的钱数，第二行输入7个整数表示每个纸币拥有的数量，分别表示1,2,5,10,20,50,100纸币的个数。

输出

对于每个样例，输出一个数字表示最少找零个数，输出-1表示无法找开。

样例输入

2
107
1 1 1 1 1 1 1 
200
1 1 1 1 1 0 0

样例输出

3
-1

数据范围

对于100%的数据，保证贪心可解。

题目分析

一开始以为是一个动规，后来发现没那个必要，毕竟生活里面我们自己都是先花最大的。 对于每一款纸币，先讨论剩余的未付价格是不是高于这款纸币，如果不高于直接下一款；高于则在比较未付价格是否高于这款纸币总价值之和，高于则直接全部算上；不高于的话先计算需要的张数,然后计算付完后的剩余未付价格。顺序一定不能错，否则就寄了，而且相当难以发现错误。（害的作者都去要了个代码对着找） 最后的最后，如果剩余未付价值不为0，则不满足要求。 代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int ans = 0;
        int k;

        int c1, c2, c5, c10, c20, c50, c100;//纸币张数
        cin >> k;
        cin >> c1 >> c2 >> c5 >> c10 >> c20 >> c50 >> c100;
        if (k / 100 >= c100)//开始贪心
        {
            k -= c100 * 100;
            ans += c100;
        }
        else
        {
            ans += (k / 100);
            k %= 100;
        }
        if (k / 50 >= c50)
        {
            k -= c50 * 50;
            ans += c50;
        }
        else
        {
            ans += (k / 50);
            k %= 50;
        }
        if (k / 20 >= c20)
        {
            k -= c20 * 20;
            ans += c20;
        }
        else
        {
            ans += (k / 20);
            k %= 20;
        }
        if (k / 10 >= c10)
        {
            k -= c10 * 10;
            ans += c10;
        }
        else
        {
            ans += (k / 10);
            k %=10;
        }
        if (k / 5 >= c5)
        {
            k -= c5 * 5;
            ans += c5;
        }
        else
        {
            ans += (k / 5);
            k %= 5;
        }
        if (k / 2 >= c2)
        {
            ans += c2;
            k -= c2 * 2;
        }
        else
        {
            ans += (k / 2);
            k %=2;
        }
        if (k / 1 >= c1)
        {
            k -= c1 * 1;
            ans += c1;
        }
        else
        {
            ans += (k);
            k -= k;
        }
        if (k == 0)//判定
            cout << ans << endl;
        else
            cout << "-1" << endl;
    }

    system("pause");
    return 0;
}

内存2220KB，时间6ms

1.6 汉诺塔

题目信息

题目描述

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

输入

第一行包含一个整数T表示样例数。 对于每个样例,输入一个n表示汉诺塔的级数。

输出

对于每个样例,输出一个整数表示最少需要移动的次数。

样例输入

3
1
2
3

样例输出

1
3
7

题目分析：

假设有n个，先要把上面的n-1个挪走，把最后一个挪到位，再把n-1个挪回来，即递推数列

化简即得数学公式

代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull quickpow(ull a,int n)//原理同矩阵快速幂，快速计算2的n方
{
    ull E=1;
    while(n)
    {
        if(n&1)E=a*E;
        a=a*a;
        n>>=1;
    }
    return E;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        cout<<(quickpow(2,a)-1)<<endl;
    }
    system("pause");
    return 0;
}

内存2220KB，时间4ms

1.7 绝对值排序

题目信息

题目描述

输入个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。

输入

输入数据有多组，每组占一行，每行的第一个数字为,接着是个整数，表示输入数据的结束，不做处理。

输出

对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。

样例输入

3 3 -4 2
4 0 1 2 -3
0

样例输出

-4 3 2
-3 2 1 0

数据范围

题目分析

STL函数

template<class _RAIter> inline void std::sort(_RAIter __first, _RAIter __last,_Compare __comp)

代码：

#include <bits/stdc++.h>
using namespace std;
bool compare(int a, int b)
{
    return abs(a) > abs(b);
}//排序法则更改
int main()
{

    int num;
    while (cin >> num && num != 0)
    {
        int *a = new int[num];
        for (int i = 0; i < num; i++)
            cin >> a[i];
        sort(a, a + num, compare);//排序
        for (int i = 0; i < num; i++)
            cout << a[i] << " ";
        cout << endl;
        delete[] a;
    }

    system("pause");
    return 0;
}