问题 E：取数排列

这个问题好像很多同学被绊了一下，这里看无非1~9回溯一波就可以了啊

注意回溯的标记数组问题

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int v[20];
int ans[20];
int tot;
int n, m;
int ok = 1;
void dfs(int k)
{
    if (k > n)
    {
        tot++;
        if (tot == m)
            for (int i = 1; i <= n; i++)
            {
                cout << ans[i];
                ok = 0;
            }
        return;
    }
    for (int i = 1; i <= n; i++)
        if (!v[i])
        {
            ans[k] = i;
            v[i] = 1;
            dfs(k + 1);
            if (!ok)
                return;
            v[i] = 0;
        }
}
int main()
{
    cin >> n >> m;
    dfs(1);
    return 0;
}

问题 H：自然数无序拆分

这个应该就是很多人离AK的分水岭，赛时的我也没想出正解的DP，就算想出，一时半会也实现不出来

看一眼数据 N<=100 （虚...我又发现新大陆啦，天生爱打表..理理思路迅速码完代码，打表搜答案，O(1)复杂度解决问题....没想到罚时有些许的优势拿了Rank 1 （不能骄傲，继续加油）

这个题我分阶段解决，然后把答案合并，分阶段的意思是，一个数分成若干数相加，有几种情况？答案是N中，最少是 1 个数，最多是 N个数。

下边贴上我的搜索代码：

#include <cstdio>
#include <iostream>
using namespace std;
int n, k, tot;
void dfs(int now, int sum, int cur)
{
    if (cur == k)
    {
        if (sum == n)
            tot++;
        return;
    }
    for (int i = now; sum + i * (k - cur) <= n; i++)  //想一想，这里其实没必要往下搜了，相当于剪枝了
        dfs(i, sum + i, cur + 1);
}

int main()
{
    //freopen("std.in","w",stdout);
    for (int i = 1; i <= 100; i++)   //这里枚举1到100所有数
    {
        n = i;
        tot = 0;
        for (int j = 1; j <= n; j++)  //这里枚举他分成几部分
        {
            k = j;
            dfs(1, 0, 0);
        }
        cout << tot << endl;
    }
}

下面贴上我提交的代码：

#include<iostream>
using namespace std;
int k[200]={1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,8349,10143,12310,14883,17977,21637,26015,31185,37338,44583,53174,63261,75175,89134,105558,124754,147273,173525,204226,239943,281589,329931,386155,451276,526823,614154,715220,831820,966467,1121505,1300156,1505499,1741630,2012558,2323520,2679689,3087735,3554345,4087968,4697205,5392783,6185689,7089500,8118264,9289091,10619863,12132164,13848650,15796476,18004327,20506255,23338469,26543660,30167357,34262962,38887673,44108109,49995925,56634173,64112359,72533807,82010177,92669720,104651419,118114304,133230930,150198136,169229875,190569292};
int main()
{
    int n;
    cin>>n;            //输入
    cout<<k[n-1];    //输出
    return 0;
}

赛后问朋哥这题正解：朋哥：DP！

一个小时后...

两个小时后...

朋哥：再等我10分钟

半小时后....

第二天，代码出来了....（这里不是说朋哥敲的慢，朋哥心里还惦记着他的电路呢，明天下午考试啊！为朋哥祈祷，别挂科，哈哈）传送门DP解法

问题 K：最少移动次数

每堆糖果必定变成总糖果的平均数

怎么说呢，我没法证明我是对的，但是找不出反例来，就是数的传递呗，1给2，2给3，3给4..

如果某堆糖果小于平均数，他就跟下一堆要，传递次数+1，如果恰好是平均数，传递次数不变，如果大于平均数，那么传递给下一堆，传递次数+1

Lrj蓝书有一道跟这个相似的题，不过那个题要难些，求的是最少传递的糖果数，有兴趣同学可以去翻一下 Page 4

细节见代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
long long c[500];
long long tot, k, x;
long long ans;
long long num[500];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
        tot += num[i];
    }
    k = tot / n;
    tot = 0;
    if (num[1] < k)
    {
        tot++;
        num[2] -= (k - num[1]);
        num[1] = k;
    }
    else if (num[1] > k)
    {
        tot++;
        num[2] += (num[1] - k);
        num[1] = k;
    }
    for (int i = 2; i < n; i++)
    {
        if (num[i] == k)
            continue;
        if (num[i] < k)
        {
            tot++;
            num[i + 1] -= (k - num[i]);
            num[i] = k;
        }
        else if (num[i] > k)
        {
            tot++;
            num[i + 1] += (num[i] - k);
            num[i] = k;
        }
    }
    cout << tot;
    return 0;
}