[THUPC 2024 初赛] 分治乘法
题目描述
小艾想要挑战分治乘法。TA 将策略抽象成了如下问题：
现在给定一个目标集合 \(T\)，该集合是 \(\{1,\dots,n\}\) 的一个子集（\(1\leq n\leq 5\times 10^5\)）。你需要通过一系列操作构造一些集合最后得到 \(T\)，具体来说有以下三种操作：
- 创造一个大小为一的集合 \(|S|=1\)。
- 将已经被构造出的两个不交集合 \(A, B\) 并起来，得到 \(A\cup B\)。
- 将已经被构造出的一个集合 \(A\) 进行平移，也即 \(A+x = \{ a+x : a\in A \}\)。
一个已经被构造出的集合可以在之后被使用多次。同时你需要保证操作过程中出现的所有集合都是 \(\{1,\dots,n\}\) 的子集。
你的代价是构造出的所有集合的大小之和，你不需要最小化代价，只需要让代价控制不超过 \(5\times 10^6\) 即可。你用的操作数量也不应超过 \(10^6\)。
输入格式
第一行输入一个正整数 \(n\)。
接下来一行输入一个 01 串，长度为 \(n\)，第 \(x\) 位为 1 表示 \(x\in T\)，否则 \(x\notin T\)，保证 \(T\) 非空。
输出格式
第一行输出一个正整数 \(m\) 表示你使用的操作数量。
接下来 \(m\) 行，每行描述一个操作，设第 \(i\) 次操作得到的集合为 \(T_i\)：
1 x表示创造一个大小为一的集合 \(\{x\}\)。2 x y表示将不交集合 \(T_x, T_y\) 并起来。3 x y表示将已经被构造出的一个集合进行平移，也即 \(T_x+y\)。
你需要保证所有操作满足题目要求，并且最后一次操作产生的集合是 \(T\)。
赛时被蔡神秒了，%%%
首先考虑分治，代价是 \(O(nlog n)\) 的，大概多了一倍。而且没用操作3.
平移想到什么？分块！
考虑 B 个为一块，那么每一块总共有 \(2^B\) 种形态。设第 \(i\) 种形态出现位置序列为 \(f_i\)，那么 \(\sum|f_i|=\frac nB\)，用分治做法得到所有的 \(f_i\)，代价为 \(O(\frac nB\log n)\)，然后再平移得到所有的位置。
然后再用合并果子合并上去。集合大小的和是 \(n\)，总共 \(B2^B\) 个集合，复杂度是 \(O(nlog(B2^b))=O(nB)\) 的。
代价复杂度可以平衡到 \(O(n\sqrt {\log n})\)
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,B=5,M=5e6+5;
int n,p[M],sz[M],r,idx,op[M],aa[M],bb[M];
char s[N];
vector<int>g[N];
int haffman()
{
if(!r)
return 0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
for(int i=1;i<=r;i++)
q.push(make_pair(sz[p[i]],p[i]));
while(q.size()>1)
{
pair<int,int>u=q.top(),v;
q.pop();
v=q.top();
q.pop();
op[++idx]=2,aa[idx]=u.second,bb[idx]=v.second;
q.push(make_pair(u.first+v.first,idx));
}
return q.top().second;
}
int slv(vector<int>&g,int l,int r)
{
if(l==r)
{
op[++idx]=1,aa[idx]=g[l]+1;
sz[idx]=1;
return idx;
}
int md=l+r>>1;
int u=slv(g,l,md);
int v=slv(g,md+1,r);
sz[++idx]=sz[u]+sz[v];
op[idx]=2,aa[idx]=u,bb[idx]=v;
return idx;
}
int main()
{
scanf("%d%s",&n,s);
for(int i=0;i<n;i+=B)
{
int t=0;
for(int j=0;j<B&&i+j<n;j++)
t|=s[i+j]-48<<j;
g[t].push_back(i);
}
// puts("NO!!!");
for(int i=0;i<(1<<B);i++)
{
if(g[i].empty())
continue;
int x=slv(g[i],0,g[i].size()-1);
if(i&1)
p[++r]=x;
for(int j=1;j<B;j++)
if(i>>j&1)
p[++r]=++idx,op[idx]=3,aa[idx]=x,bb[idx]=j,sz[idx]=sz[x];
}
int k=haffman();
printf("%d\n",idx);
for(int i=1;i<=idx;i++)
{
printf("%d %d ",op[i],aa[i]);
if(op[i]^1)
printf("%d",bb[i]);
puts("");
}
}