2023牛寒2--Tokitsukaze and K-Sequence

Tokitsukaze 有一个长度为 n 的序列 a她想把这个序列划分成 k 个非空子序列。定义序列的值为这个序列中只出现一次的数字的个数。
对于 k=1…nTokitsukaze 想知道把序列 a 划分成 k 个非空子序列后所有子序列的值的和最大是多少。
请注意子序列不一定是连续的。

输入描述
第一行包含一个正整数 T (1≤T≤10)表示测试数据的组数。
对于每组测试数据
第一行包含一个整数 n (1≤n≤10^5)。
第二行包含 n 个整数 a1,a2,…,an​ (1≤ai≤10^5)。

输出描述
对于每组数据输出 n 个整数第 i (1≤i≤n) 个整数表示 k=i 时的答案。

输入

1
3
2 2 1

输出

1
3
3

样例说明
当 k=1 时a 只能划分成 [a1,a2,a3]即 [2,2,1]。其中只有 1 个数字只出现了一次所以答案是 1。
当 k=2 时a 可以划分成 [a1,a3], [a2]即 [2,1] 和 [2]。[2,1] 中有 2 个数字只出现了一次[2] 中有 1 个数字只出现了一次所以答案是 2+1=3。
当 k=3 时a 只能划分成 [a1], [a2], [a3]即 [2], [2], [1]。所以答案是 1+1+1=3。

解析单独算贡献就是说每个数字排完之后对后面的数字排列得分无关因此想清楚一种数字怎么放置其他数字都是相同的记录某个数字有cnt个分析得出如果cnt<=k那么得分就是cnt否则最优方案就是前k-1集合各放一个剩下的都放在第k集合中得分为k-1但是问题要求输出1~n情况每个答案因此暴力就不行了得优化😥

标程解法将每个数字出现次数记录然后存入multiset然后如果判断到某个次数>k那么肯定对答案贡献都是k-1。

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int N=1e5+5;
multiset<int> st;
int cnt[N];
void solve()
{
	int n,x;
	memset(cnt,0,sizeof cnt);//多组初始化
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&x),cnt[x]++;//记录每个数出现次数
	for(int i=1;i<=1e5;i++) st.insert(cnt[i]);
	int sum=0,ge=st.size();//sum记录答案ge记录有多少个>k
	for(int i=1;i<=n;i++)
	{
		while(!st.empty()&&*st.begin()<=i)
		{
			//*st.begin()<=i表示出现次数<=k得分就是*st.begin()
			sum+=*st.begin();
			st.erase(st.begin());
			ge--;//该情况产生了一个<=k的次数那么>k的个数-1
		}
		printf("%d\n",sum+ge*(i-1));
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--) solve();
	return 0;
}

非标程解法有点难理解😥最初出现1次的次数肯定就是k=1的时候的答案我们用cs[ ]记录出现了 i 次的次数那么我们求和cs[2~n]为sumk=1肯定没有贡献k=2时候贡献是cs[ k ]+sum(多于2的放一个在集合1其他都放在第2个集合)因为我们将得出了cs[2]的贡献那么就得将cs[2]从sum中分离出来sum减去cs[2]后面以此类推。

#include <cstdio>
#include <cstring>
const int N=1e5+5;
int cnt[N],cs[N];//cs记录出现了i次的次数
void solve()
{
    memset(cnt,0,sizeof cnt);//多组初始化
    memset(cs,0,sizeof cs);
    int n,x,ans=0,sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&x),cnt[x]++;
    for(int i=1;i<=1e5;i++)
    {
        if(cnt[i]==1) ans++;//只出现1次就是k=1的放置
        else if(cnt[i]>1) cs[cnt[i]]++;
    }
    for(int i=2;i<=1e5;i++) sum+=cs[i];
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",ans);
        ans+=sum+cs[i+1];
        sum-=cs[i+1];
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}