题目大意:
有一个集合A={1,2....n},从A中选出一个子集,在这个子集中 初始权值为图片说明 ,对于任意的i>=2,j>=2,如果有图片说明 ,那么这个子集的权值就要减去图片说明
题目思路

嗯..刚开始思路是对的..

  • 第一步:可以确定我们可以按幂去分组,因为2的幂与3的幂集合之间没有任何的交集,也就是说,如果已经把2选入到子集中,那么3选进去与3不选进去是没有影响的。能产生的影响的只有 底数相同的幂。

  • 第二步:我们按幂分组之后,组内的数就被确定,之后我们就需要枚举组内的数可以产生的组合,然后分别去修改这些组合,使得这些组合满足题目中的条件。最后计算当前这种组合的权值,作为这个子集这时的权值,枚举所有组合的权值之后取一个最大值,即为幂分组后该组对答案的贡献。

  • 第三步:如何计算出当前这个组合的权值呢?题目中说只要出现一对(i,j)满足那么bj就要减去一次,所以我们首先令当前组合的ai全部加入,第一层for循环枚举x,第二层for循环枚举y是不是x的幂。如果是的话就减去一次:

    ll judge(ll x,ll y)
    {
      for(ll k=x;k<=n;k*=x)
          if(k==y) return 1;
      return 0;
    }
    //以上为judge函数,判断y是否为x的幂。
          for(ll k=1;k<=x;k++)
          {
    
              if(i>>(k-1)&1)//第k位是否为1
                  c[++cot]=save[k];
          }
          for(ll k=1;k<=cot;k++) sum+=a[c[k]];
          for(ll k=1;k<=cot;k++)
          {
              for(ll j=1;j<=cot;j++)
              {
                  if(c[j]<c[k]&&judge(c[j],c[k]))
                      sum-=b[c[k]];
              }
          }
  • 第四步: 计算一下时间复杂度,因为二进制枚举的时间复杂度为:图片说明 ,指数级别的复杂度是很令人害怕的,开始我也没敢写,不过计算一下这个复杂度:按幂分组之后,组中元素个数最多为图片说明 ,也就是最坏的二进制枚举为图片说明 ,然后外层套一个sqrt(N),因为sqrt(N)之后的,要么已经被幂分组分进去了,要么没有被幂分组分进去,此时这个数可以直接加入到这个子集里。所以总体的时间复杂度为:图片说明 ,由于n是100000大概是个1e7~5e7的复杂度,但是绝对比这个复杂度要小很多,因为计算的最坏情况!



    所以剩下的内容就看你的二进制枚举学的怎么样了,其实感觉挺简单的,开始M题意读错了,唉.. 放一下代码啦
    hhaha 牛哥会在阿楚姐的帮助下送我抱枕嘛?
ll n,m,p;
ll a[maxn],b[maxn],c[maxn];
ll vis[maxn];
ll save[maxn];
ll judge(ll x,ll y)
{
    for(ll k=x;k<=n;k*=x)
        if(k==y) return 1;
    return 0;
}
ll work(ll x)
{
    ll maxl=0;
    for(ll i=0;i<(1<<x);i++)
    {
        ll cot=0;
        ll sum=0;
        for(ll k=1;k<=x;k++)
        {

            if(i>>(k-1)&1)//第k位是否为1
                c[++cot]=save[k];
        }
        for(ll k=1;k<=cot;k++) sum+=a[c[k]];
        for(ll k=1;k<=cot;k++)
        {
            for(ll j=1;j<=cot;j++)
            {
                if(c[j]<c[k]&&judge(c[j],c[k]))
                    sum-=b[c[k]];
            }
        }
        maxl=max(sum,maxl);
    }
    return maxl;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++) scanf("%lld",&b[i]);
    ll res=a[1];
    for(ll i=2;i*i<=n;i++)
        if(!vis[i])
        {
            for(ll k=i*i;k<=n;k*=i)
                vis[k]=1;
        }
    for(ll i=2;i<=n;i++)
    {
        ll cnt=0;
        if(i*i<=n&&!vis[i])
        {
            for(ll k=i;k<=n;k*=i) save[++cnt]=k;
            res+=work(cnt);
        }
        else if(i*i>n&&!vis[i]) res+=a[i];
    }
    printf("%lld\n",res);
    return 0;
}