博主有幸参加了NOI2020,考场上的经历和心得请见这篇文章。这里就不唠叨了。
本题题解
本题的突破口在于(m)和(n)的关系。也就是数据范围表里这些奇怪的限制:(m=n-1),(mgeq n-1),(mgeq n-2)。我们一个一个来看。
走出第一步:(m=n-1)时
显然,(n)种原材料,除了在输出答案时,其他时候它们的原始顺序对我们解题没有任何影响。所以可以先将它们排序。现在假设(d_1leq d_2leq dots leq d_n)。
考虑一种贪心:先用最大的原材料和最小的原材料一起做成第一道菜。然后把它们剩余的部分,当做一种新的材料,插入回(d)序列中,转化为一个(m-1)道菜的子问题。
这种贪心在(m=n-1)时是正确的,而且一定有解。以下是证明:
引理1.1:(d_1<k)。
证明1.1:
反证法,假设(d_1geq k),则((sum_{i=1}^{n}d_i)geq d_1 imes ngeq k imes n)。又因为((sum_{i=1}^{n}d_i)=m imes k),所以(m imes kgeq n imes k),(mgeq n)。与(m=n-1)矛盾。故可以证明:(d_1<k)。
引理1.2:(d_1+d_ngeq k)。
证明1.2:
反正法,假设(d_1+d_n<k),则((sum_{i=1}^{n}d_i)=(d_1+d_n)+(sum_{i=2}^{n-1}d_i)<(n-1) imes k)。这与((sum_{i=1}^{n}d_i)=m imes k=(n-1) imes k)矛盾。故可以证明:(d_1+d_ngeq k)。
结合引理1.1和引理1.2,我们在贪心时,每次操作,一定会把最小的原材料和最大的原材料都用上,一定能用它们拼成一道菜,并且能把多余的(d_1+d_n-k)作为一种“新的”原材料放回序列中。那么,每次操作后,(n)和(m)各减小(1),仍然满足(m=n-1)。我们如此归纳下去,直到(m=1,n=2)时,直接拼成一道菜即可。
注意,在证明时,我们认为可以允许存在一道菜(d_i=0)(否则,(n)每次就不一定减少(1),而有可能减少(2):也就是(d_1+d_n=k)的情况)。这样假设不会影响该做法的正确性,但在输出答案时要注意判断。
朴素地实现这一贪心,每次操作后将序列重新排序。时间复杂度(O(mnlog n))。可以用( exttt{std::set})优化到(O(mlog n))不过没有必要。
继续努力:(mgeq n)时
(mgeq n)时,考虑向(m=n-1)转化。
引理2.1:(d_ngeq k)。
证明2.1:
反证法,假设(d_n<k),则((sum_{i=1}^{n}d_i)<n imes k)。又因为((sum_{i=1}^{n}d_i)=m imes k),所以(m imes k<n imes k),(m<n)。与(mgeq n)矛盾。故可以证明:(d_ngeq k)。
于是我们每次使用(d_n)做一道菜,这样(m)会减少(1),(n)不变。若干次后,一定能转化为(m=n-1)的情况。然后按上一段所述的方法贪心构造即可。
走向正解:(m=n-2)时
考虑把手上的原材料,分成两部分,分别满足(m=n-1)。具体来说,我们要证明:
引理3.1:(m=n-2)时,有解当且仅当,存在一个集合(Ssubsetneq {1,dots ,n}),使得((sum_{iin S}d_i)=(|S|-1) imes k)。
证明3.1:
充分性:可以对(S)和(T={1,dots ,n}setminus S)这两个集合分别构造方案。根据定义,显然这两个集合都满足:“(m=n-1)”。所以一定是有解的。
必要性:考虑建一张(n)个点的图。如果在最终方案下,第(i)种原材料和第(j)种原材料,曾经共同拼成过一道菜,则在点(i)和点(j)之间连一条边。因为总共只有(m)道菜,所以最多会连出(m=n-2)条边。因此这张图一定不连通。此时必然至少有一个连通块满足“(m=n-1)”(也就是至少有一个连通块是树。不可能每个连通块都有环,否则边数不够用了),它就是集合(S)。也就是说,有解时,必然存在一个这样的集合(S)。
如何划分出这样的集合(S)呢?(2^n)枚举肯定不行。考虑DP。
可以设计出这样一个朴素的状态:(dp[i][j][w]),表示考虑了前(i)种原材料,选出了(j)种原材料,它们的质量之和为(w),是否存在一种这样的方案。转移就考虑下一种原材料选或不选,分别转移到(dp[i+1][j+1][w+d_{i+1}])和(dp[i+1][j][w])。最终,如果存在一个(j)使得(dp[n][j][(j-1) imes k]=1),则有解,我们顺着转移的过程,反推回去就能得到集合(S)。
时间复杂度(O(n^2sum d_i)=O(n^3k))。
继续优化,发现我们并不关心(j)是多少,只关心(j)和(w)的关系:也就是(w-j imes k=-k)。于是我们可以令每样物品的权值为(v_i=d_i-k)。设计一个新的状态:(dp[i][j]),表示考虑了前(i)种物品,权值和为(j),是否存在这样的方案。考虑下一种原材料选或不选,可以转移到(dp[i+1][j+v_{i+1}])和(dp[i+1][j])。最终只要看(dp[n][-k])是否为(1)即可。另外,这种DP状态下,第二维可能是负数(最小为(-nk))。所以在实现时,我们把数值统一加上(nk)即可。
在新的状态下,DP的状态数减小至(n imes(nk+mk+1))个(第一维大小为(n),第二维在([-nk,mk]))。转移是(O(1))的。时间复杂度(O(n^2k)),还是不足以通过全部数据。
因为DP数组里只存(01)两种值,所以考虑用( exttt{bitset})优化DP。具体来说,把DP的第二维,看做一个大小为(nk+mk+1)的( exttt{bitset}),则DP的转移就相当于将上一阶段的( exttt{bitset}),或上它左移(v_i)位。即:(dp[i]=dp[i-1]operatorname{or}(dp[i-1]ll v_i))。特别地,如果(v_i)为负数,要写成右移(|v_i|)位。
时间复杂度(O(frac{n^2k}{w})),其中(w=64)。可以通过本题。
还有一个小问题。做完这个DP后,只是知道了是否有解。但我们还需要构造出(S)集合。不过这也不难,通过现有的DP数组就能构造出来。考虑定义一个( exttt{getS(i,x)})函数,用递归实现。保证传入的(i,x)满足(dp[i][x]=1)。显然,当(i>0)时,(dp[i-1][x])和(dp[i-1][x-v_i])必有至少一个为(1)。任选一个为(1)的递归下去即可。如果递归了((i-1,x-v_i)),相当于把原材料(i)加入集合(S),否则相当于加入另一个集合。初始时,传入(i=n,x=-k)。递归的边界是(i=0)时直接返回。这样显然可以构造出满足我们要求的两个集合(分别满足(m=n-1))。
总时间复杂度(O(frac{n^2k}{w}+mnlog n))。
参考代码:
//problem:LOJ3342
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
const int MAXN=500,MAXM=5000,MAXK=5000;
int n,m,K;
pii a[MAXN+5];
pair<pii,pii> ans[MAXM+5];
void work(pii a[],int n,int m,pair<pii,pii> ans[]){
sort(a+1,a+n+1);
for(int i=1;i<=m;++i){
assert(n>0);
int curm=m-i+1;
if(n<=curm){
assert(a[n].fi>=K);
ans[i]=mk(mk(a[n].se,K),mk(0,0));
a[n].fi-=K;
sort(a+1,a+n+1);
}
else{
assert(n==curm+1);
assert(a[1].fi<K);
assert(a[1].fi+a[n].fi>=K);
ans[i]=mk(mk(a[1].se,a[1].fi),mk(a[n].se,K-a[1].fi));
a[1].fi=a[1].fi+a[n].fi-K;
a[1].se=a[n].se;
--n;
sort(a+1,a+n+1);
}
}
for(int i=1;i<=m;++i){
if(ans[i].se.se>ans[i].fi.se) swap(ans[i].fi,ans[i].se);
if(ans[i].se.se)
cout<<ans[i].fi.fi<<" "<<ans[i].fi.se<<" "<<ans[i].se.fi<<" "<<ans[i].se.se<<endl;
else
cout<<ans[i].fi.fi<<" "<<ans[i].fi.se<<endl;
}
}
pii a1[MAXN+5],a2[MAXN+5];
pair<pii,pii> ans1[MAXN+5],ans2[MAXN+5];
bitset<MAXN*MAXK+(MAXN-2)*MAXK+5> dp[MAXN+5];
int bas,n1,n2;
void getset(int i,int x){
if(i==0) return;
if(dp[i-1][x+bas]){
getset(i-1,x);
a2[++n2]=a[i];
}
else{
int v=a[i].fi-K;
assert(dp[i-1][x-v+bas]==1);
getset(i-1,x-v);
a1[++n1]=a[i];
}
}
void solve_case(){
cin>>n>>m>>K;
for(int i=1;i<=n;++i){
cin>>a[i].fi;
a[i].se=i;
}
if(n<=m+1){
work(a,n,m,ans);
return;
}
assert(n==m+2);
bas=n*K;// DP数组为了保证下标不为负而产生的的偏移量
//dp[-x] -> dp[-x+bas]
dp[0].reset();
dp[0][0+bas]=1;
bool flag=0;
for(int i=1;i<=n;++i){
int v=a[i].fi-K;
if(v>0)
dp[i]=(dp[i-1]|(dp[i-1]<<v));
else if(v<0)
dp[i]=(dp[i-1]|(dp[i-1]>>(-v)));
else
dp[i].reset();
if(dp[i][-K+bas]==1){
n1=n2=0;
getset(i,-K);
for(int j=i+1;j<=n;++j){
a2[++n2]=a[j];
}
flag=1;
break;
}
}
if(!flag){
cout<<-1<<endl;
return;
}
// for(int i=1;i<=n1;++i) cerr<<a1[i].fi<<" "; cerr<<endl;
// for(int i=1;i<=n2;++i) cerr<<a2[i].fi<<" "; cerr<<endl;
int sum1=0,sum2=0;
for(int i=1;i<=n1;++i) sum1+=a1[i].fi; assert(sum1==(n1-1)*K);
for(int i=1;i<=n2;++i) sum2+=a2[i].fi; assert(sum2==(n2-1)*K);
assert(n1>=1);
assert(n2>=1);
work(a1,n1,n1-1,ans1);
work(a2,n2,n2-1,ans2);
}
int main() {
// freopen("dish.in","r",stdin);
// freopen("dish.out","w",stdout);
int T;cin>>T;while(T--){
solve_case();
}
return 0;
}