1 5 3 1 1 2 1 3 1 4 1 5 1 1 2 3 4
1 3 2 2 2 11
思路来源于：cxlove博客
题意：
每个数，有4个评估
1、是素数 2、约数个数是素数 3、约数的和是素数 4、约数的乘积是完全平方数
从n个中选出k个，使得分数最高，如果选的k个中没有一个满足某个条件，则有另外的分值。
思路：
sqrt枚举n的约数，打一个大点的素数表能判断1、2、3；至于4的话考虑到n有约数i时同时也有n/i，而i*n/i=n，故可以边乘边处理，注意n自身是平方数的情况i和n/i只取一个，预处理完了之后就是判断怎样得出最佳答案了。
数只有可能有2^4种状态，而每种状态的得分又是确定的，可以统一处理，暴力枚举每种数是否出现，然后根据每一种出现的状态，先将出现的数全部取一个（使取得数满足这种状态），然后从得分高的往得分低的取（贪心），如果能恰好取k个，加上附加值，更新答案就够了。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 10005
#define MAXN 200005
#define OO (1<<31)-1
#define mod 100000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int n,m,ans,cnt,tot,flag;
int a,b,state,sc;
int s[5],score[16];
bool vis[4000005];
struct Node
{
int s,num;
}xx[20];
void sieve(int nn) // 筛选素数
{
int i,j;
memset(vis,0,sizeof(vis));
vis[1]=1;
for(i=2; i<=nn; i++)
{
if(nn/i<i) break ;
if(!vis[i])
{
for(j=i*i; j<=nn; j+=i)
{
vis[j]=1;
}
}
}
}
bool cmp(Node x,Node y)
{
return x.num>y.num;
}
void init()
{
int i,j,t,num;
sieve(4000000);
for(i=0;i<16;i++) // 得到状态和每种状态的得分
{
xx[i].s=i;
t=i; num=0;
while(t>0)
{
if(t&1) num++;
t>>=1;
}
xx[i].num=num;
}
sort(xx,xx+16,cmp); // 按照得分排序
}
bool issquare(ll pro) // 判断是否是平方数
{
ll d=sqrt(pro*1.0);
if((d-1)*(d-1)==pro||d*d==pro||(d+1)*(d+1)==pro) return true ;
return false ;
}
void solve()
{
int i,j,t,flg,num,sum;
ll pro=1;
num=sum=0;
for(i=1; i*i<=a; i++) // sqrt(a)枚举约数
{
if(a%i==0)
{
pro*=i;
if(i*i!=a)
{
num+=2; sum+=i+a/i; pro*=a/i;
}
else
{
num++; sum+=i;
}
if(pro==ll(a)*ll(a)) pro=1; // 注意这里的强制转换！
}
}
if(!vis[a]) flg=1;
else flg=0;
state=sc=0;
if(flg) sc++,state|=1;
if(!vis[num]) sc++,state|=(1<<1);
if(!vis[sum]) sc++,state|=(1<<2);
if(issquare(pro)) sc++,state|=(1<<3);
score[state]+=b;
}
int main()
{
int i,j,t;
init();
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(score,0,sizeof(score));
vector<int>v;
for(i=1; i<=n; i++)
{
scanf("%d%d",&a,&b);
solve();
v.push_back(sc);
}
for(i=0; i<4; i++)
{
scanf("%d",&s[i]);
}
tot=1<<16;
ans=-INF;
int res,k,ns;
for(i=1;i<tot;i++) // 每一种数出现的状态
{
res=ns=0; k=m;
for(j=0;j<16;j++) // 每一种状态的数 先全部取一个
{
if(!(i&(1<<j))) continue ;
ns|=xx[j].s;
res+=xx[j].num;
k--;
if(score[xx[j].s]<1) k=-INF; // 该状态没有值
}
if(k<0) continue ; // 取的超出k个
for(j=0;j<16;j++) // 然后贪心 从分高的往低的取
{
if(!(i&(1<<j))) continue ;
if(k>score[xx[j].s]-1)
{
k-=score[xx[j].s]-1;
res+=(score[xx[j].s]-1)*xx[j].num;
}
else
{
res+=k*xx[j].num;
k=0;
break ;
}
}
if(k==0) // 如果能够取k个
{
for(j=0;j<4;j++)
{
if(!(ns&(1<<j))) res+=s[j];
}
ans=max(ans,res);
}
}
for(i=0;i<n;i++)
{
if(i!=0) printf(" ");
printf("%d",v[i]);
}
printf("\n%d\n",ans);
}
return 0;
}
Linux - 操作文件与目录(manipulating files and directories),布布扣,bubuko.com
Linux - 操作文件与目录(manipulating files and directories)
原文：http://blog.csdn.net/caroline_wendy/article/details/21555775