记录刷题过程中有意义的题...........

题单戳这

Part 1 入门阶段

P1012 [NOIP1998 提高组] 拼数
题解

#include<iostream>
#include<string>
#include<algorithm>//提供sort 

using namespace std;

string s[25];//不多说 
int n;//限制数字个数 

bool cmp(string a,string b) {
    return a+b>b+a;//自定义排序函数，这一步非常巧妙，假设a=321，b=32；a+b=32132，b+a=32321这样下面sort排下来就是32>321避免出现32132>32321的情况 
}
/*如果这样写：
bool cmp（string a，string b）{
    return a>b;
    会发生321>32的情况，具体原因是字符串自己的关系运算是这样设定的 
}*/

int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>s[i];
    sort(s+1,s+n+1,cmp);//神来之笔 
    for(int i=1; i<=n; i++) cout<<s[i];//完美收场（yo）！ 
    return 0;
}

P1025 [NOIP2001 提高组] 数的划分

dp做法-1 分成有1和无1两种情况

这道题我们可以用dp:

f[i][x] 表示 i 分成 x 个非空的数的方案数。

显然 i<x 时 f[i][x]=0 , i=x 时 f[i][x]=1;

其余的状态，我们分情况讨论：

①有1的 ②没有1的

第一种情况，方案数为 f[i-1][x-1]

第二种情况，方案数为 f[i-x][x] (此时 i 必须大于 x)

所以，状态转移方程为： f[i][x]=f[i-1][x-1]+f[i-x][x]


先写出状态转移方程：dp[i][j]=dp[i-j][j]+dp[i-1][j-1];

i表示整数为i，j表示分成j份。那么对于把i这个数分成j份的分发，有两种情况。

要么就是已经将i-1分成了j-1份，只要再分多一个1就可以了。即dp[i-1][j-1]

要么就是在把i-j已经分成了j份，只要每一份都+1，就成了把i分成j份的情况了。即dp[i-j][j]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;

int n, k, f[201][7];  //f[k][x] k 分成 x 份 ={f[k-1][x-1],f[k-x][x]}

int main(){
    cin >> n >> k;
    for (int i=1;i<=n;i++) 
    {
        f[i][1] = f[i][0] = 1;
    }
    for (int x=2;x<=k;x++) 
    {
        f[1][x] = f[0][x] = 0;
    }  // 边界，为了防止炸，我把有0的也处理了

    // f[i][j]的集合含义, 将整数i分成j份的不同的方案数
    for (int i = 2; i <= n; i ++)
        for (int x = 2; x <= k; x ++)
        {
            f[i][x] = f[i - 1][x - 1];
            if (i > x) f[i][x] += f[i - x][x];
        }
    cout<< f[n][k] << endl;
    return 0;
}

dp-2 背包

#include<iostream>
using namespace std;

int f[207][10];

int main(){
    int n,k;
    cin>>n>>k;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
      for(int j=i;j<=n;j++)
         for(int z=1;z<=k;z++)
           f[j][z]+=f[j-i][z-1];

           cout<<f[n][k];
        return 0;
}

dfs剪枝

 #include<cstdio>

int n,k,cnt;

void dfs(int last,int sum,int cur)
{
    if(cur==k)
    {
        if(sum==n) cnt++;
        return;
    }
    for(int i=last;sum+i*(k-cur)<=n;i++)//剪枝，只用枚举到sum+i*(k-cur)<=n为止
        dfs(i,sum+i,cur+1);
}

int main()
{
    scanf("%d%d",&n,&k);
    dfs(1,0,0);
    printf("%d",cnt);
}