题目描述

多组测试数据(<=5e3)
给你一个n(<=1e5),m;n是序列的长度,m是背包容量(<=1e6).每个序列都是2的幂的形式且不超过m!
求需要几个m容量的背包

样例

2
5 16
1 2 8 4 8
6 10
2 8 8 2 2 8

2
3

算法1

(multiset) $O(nlogn)$

multiset是一个非常好用的容器,是排序好的集合（元素已经进行了排序），并且允许有相同的元素。
这样方便我们在容器中进行lower_bound操作!!!,插入查询删除的时间复杂度都是$O(logn)$.
这题需要的就是multiset!!!
算法流程
1.先将这个序列从大到小排序
2.枚举每一个数
a:找到multiset容器中比当前数d小于或等于的最大数(it)
b:if容器中有这样的数 (it),修改 (it)的值!!!先删除 (it),然后插入 (it)-d
c:if容器中没有这样的数*it,重新开一个背包,插入w-d!!!
注意
每次插入的额是背包的剩余容量

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, w;
        cin >> n >> w;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.rbegin(), a.rend());
        //排序后变成从大到小
        multiset<int> s;
        //s存的是每一层还有多少容量可以放,multiset具有自动排序的功能
        int rv = 0;
        for (int d : a) {
            auto it = s.lower_bound(d);//在s容器中找到比d小或等的最大的数

            if (it == s.end()) {
                rv++;//s中没有空间可以放*it,重新开一层
                s.insert(w - d);//插入剩余可以放的w-d容量
            } else {
                int cur = *it;//s中有空间可以放*it
                s.erase(it);//*it需要在s中修改,先清除s再插入cur-d;
                s.insert(cur - d);
            }
        }

        cout << rv << "\n";
    }
}

题目描述

多组测试数据
给你一个n(序列长度)以及序列中的n个元素,将按顺序分组,使得每一个的任意两个数的乘积都不是
一个平方数,要求组数最小

分析

首先这个a[]里面的数会很大,一旦里面多个数乘积爆ll就很难受了!!!
考虑到一个数x可以分解质因数,每个质因子的指数不同,有的大于1,有的等于1,
把所有大于1的指数mod2,这样可以简化数的大小而且不影响分组!!!
例如[18,6,2,4,1]简化后变成[2,6,2,1,1]则可[18,6],(2 * 6不是平方数),[2,4] (2 * 4不是平方数),[1]
然后简化后的数按照原来的序列放进set里,如果当前的简化后的元素不在set中出现过
就放进去,否则就组数加1,清空set,重新插入新元素
算法流程
1.筛质数
2.简化序列元素
3.用set维护组数

代码

#include<bits/stdc++.h>
using namespace std;
#define rd(x) scanf("%d",&x)
const int N =2e5+10,M=1e7+10;
int primes[M],pcnt;
int t,n,cnt=1,k;
int a[N];
bool st[M];
int opt(int x)//简化元素
{
    int res=x;
    for(int j=0;primes[j]<=x/primes[j];j++)
    {
        int i=primes[j];
        while(res%(i*i)==0) res/=(i*i);
    }
    return res;
}
void init()
{
    for(int i=2;i<=M;i++)
    {
        if(!st[i])  primes[pcnt++]=i;
        for(int j=0;primes[j]*i<=M;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)  break;
        }
    }
}
set<int>arr;//定义arr
int main()
{
  init();
  int t;
  rd(t);
  while(t--)
  {
    arr.clear();//先清空
    cnt=1;
    rd(n),rd(k);
    for(int i=1;i<=n;i++)
    {
        rd(a[i]);
        int s=opt(a[i]);
        a[i]=s;
    }

    for(int i=1;i<=n;i++)
    {
        if(arr.count(a[i]))//出现过清空cnt++
        {
            cnt++;
            arr.clear();
        }
        arr.insert(a[i]);//没出现加入
    }
    cout<<cnt<<endl;
  }
}