AT934+AT1071_牛客博客

AT934：
此题思路：把 $N$ （那个数）的因子全部都找出来，之后判断所有因子的和是否等于本身，是否大于本身，是否小于本身。找的方法只要采用暴力即可，枚举到 $sqrt(N)$ 。原因是一个数第 $N/2$ 个因子，最大是 $sqrt(N)$ 。

科普一下完全数：

在公元前六世纪，毕达哥拉斯学派就已经认识到完全数的存在，最开始发现的完全数是6和28 。随着科技的发展找到的完全数也越来越多，截止到2013年2月，人们已经找到了48个完全数。

注意事项：

1.不含数本身，但含1。

2.要判断是否为平方数，如 25所有因数和为 6，而不是11。

3.要换行

#include <bits/stdc++.h>
//万能头文件 
using namespace std;
long long cd(long long x)//函数（使思路更清晰 
{
    long long sum=1;//赋初值 
    for(int i=2;i<=sqrt(x)/*可节省时间*//*sqrt为cmath中的平方根函数（现成的）*/;i++)
    {
        if(x%i==0)//判断因数 
        {
            sum+=i;//加上因子 
            sum+=x/i;//加上它的另一个因子 
        } 
        if(i==sqrt(x)&&x%i==0)//判断是否为平方数 
        sum-=i;//减去另一个因子 
    }
    return sum;//返回 
}
int main()
{
    long long n;
    cin>>n;
    if(n==1)//特判 
    {
        cout<<"Deficient"<<endl;
        return 0;
    }
    if(cd(n)==n)//判断是否等于它本身 
    {
        cout<<"Perfect"<<endl;
        return 0;
    }
    if(cd(n)>n)//判断是否大于它本身
    {
        cout<<"Abundant"<<endl;
        return 0;
    }
    if(cd(n)<n)//判断是否小于它本身
    {
        cout<<"Deficient"<<endl;
        return 0;
    }
    return 0;//结束 
}

AT1071：
这道题就是一个基本的背包，可是好多人上来就以为是模拟（包括我）
这是我最开始WA的很惨的模拟代码（惨不忍睹）我就不过多解释了。

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    int min1=1e9+7;设计最小值
    cin>>n>>m;
    int a[n+5];
    for(int i=1;i<=n;i++)
    cin>>a[i];//输入
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            min1=min(min1,a[i]+a[j]-m);//每次取最小的（和min1自己比较）
        }
    }
    if(min1<0)
    cout<<"-1"<<endl;//判断（不行是-1）
    else
    cout<<min1+m<<endl;//正常输出
    return 0;//结束
 }

后来研究了好久才发现只要用一个01背包就行了（a[i]既是所耗费的数，也是所得到的数）自从公式找到后就容易多了 f[j]=max(f[j],f[j-a[i]]+a[i]);之后再把这个公式放到程序里就好了（也没有绿题的难度）。不过还是有几个点要注意的

1，里层循环不要写反（否则就变成完全背包了）

2，注意输出是换行。

3，一定要先把F数组清为零（否则会出现很奇怪的结果）（我最开始就怎么错了）

 #include <iostream>
#include <cstring> //memset的头文件
#define H 1000005//装装逼
using namespace std;
int main()
{
    int n,m,sum=0;//sum一定要清零
    cin>>n>>m;//输入N和M
    int a[H],f[H];//一个用来输入和计算，一个用来储存答案
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];//输入数字
        sum+=a[i];//加一下
     } 
    int sum1=sum;
    sum1-=m;//定义一个新变量
    memset(f,0,sizeof(f));//清空数组
    if(sum1<0)//判断能否计算
    {
        cout<<"-1"<<endl;//不能输出-1
        return 0;//直接结束
    }
    for(int i=1;i<=n;i++)//外层枚举从1到N
    {
        for(int j=sum1;j>=a[i];j--)//01背包不要写成完全背包
        {
            f[j]=max(f[j],f[j-a[i]]+a[i]);//前面计算出来的公式，不要忘了。而且一定要取最大值
        }
    }
    cout<<sum-f[sum1]<<endl;//输出，一定记住是sum-f[sum1]，而不是f[sum1]，和P1049
    return 0;//结束（没啥说的????）
}

珍惜生命，远离抄袭

做完此题可尝试

P1048,P1049,P1616等。

不见不散！