6775 [NOI2020]制作菜品

zhqwq · 2020-08-23 22:01:24 · 个人记录

啊，，观察结论题杀我。。一分不得hhh。

好吧。。首先观察数据，发现它在明示你，m=n-1的是特殊的。m>=n-1的都是相对好做的？？又因为m>=n-2，所以可能只有m=n-2是极特殊的？？

好吧我们先品品m=n-1（然后我品了好久啥都没品出。

m==n-1

可能一个想法是，我拿最小的和最大的凑之类的。然后被我hack了。

喂！！明明这样就是m=n-1正解啊咋肥四啊！！！！&%@（%

佳衡给了个这样的证明：当m=1,n=2时，直接拼就行了。

当m>1时，你发现最小的d_i一定比k小。而最大的加最小的一定>k（否则结合\sum d=mk可以推出矛盾（大概？））。这样一次操作，一定会把最小的消掉，而大的不会被消完，m,n都-1，成了规模更小的问题。

m>n-1

可能一个想法是，如果有一个物品的d_i>=k，我先一直选它直到它<k。

然后我又把自己hack了。

结果它又是对的！！！啊我在想啥啊做这个题的时候/ll

大概是结合\sum d =mk,m>=n，你考虑最大的d一定大于等于k。于是最终我们一定可以让m变得等于n-1，然后就和上面一样了。

接下来就只剩下，，

m==n-2

然后要有一个观察：

直接贴一个洛谷题解的神仙证明Orzzzzz

好的现在我们的问题时，咋从这n个数中找x个，使的它们d的和为(x-1)k？

不太葱名的思路显然是设前i个选了j个d的和为s的方案数。直接去世。

葱名的想法是，把所有物品的体积当做d_i-k，那最后就是取任意多个使得体积和为-k了。

用柿子的话，就是求：\sum_{i=1}^xd_{r_i}=(x-1)k->\sum_{i=1}^x(d_{r_i}-k)=-k。（r是你选出来的物品的下标）。

然后你发现这个东西和Emiya家的饭很像。那个题是说你有n类物品。容斥后问题变成，要求某一类物品占总数超过一半。做法是把该类物品看做1，其他看做-1，最后变成和>=0、

也可以这么考虑：不妨把该类看成v=1，其他看成v=0，那就是要求\sum_{i=1}^x v_i>\frac{x}{2}->\sum_{i=1}^x 2v_i>x->\sum_{i=1}^x(2v_i-1)>0。那不就是该类看成1其他看成-1嘛！！

（虽然除二是向下取整，边界也没太看但是都是小问题。。）

然后我们就可以把“体积”当做d-k，设f[i][x]为前i个“题解”和为x是否有解。

然后感觉空间有点炸（虽然好像打暴力并不会炸。。），想把它滚掉，但构造方案就不太方便了。。然后想了个法子：

设g[x]为最小的i使得只用前i个数能凑出x。

然后你发现有这个东西就可以构造方案了：就找出能凑到-k的，然后最后一个取的就是g[-k]，然后把这个物品减掉，继续取g，继续减blabla就行了。

负数下标的处理一下就行了。

复杂度O(Tn*nk)（nk是值域，m==n-2时nm同阶）

考虑优化——\bitset/！

发现用上面的方法还挺好整的。

f直接左右移再或就能求。g的话，你这个和上个bitset异或一下，就知道哪些位置是在这一次从0变成1的。这些位置的g就是i了。

用_Find_first 和_Find_next就能找所有1了嘛w。剩下的都一样。。

有其他的方法，但仿佛就需要把每一位的bitset都记下来了？其实好像空间似乎也不会炸（？），但好虚啊。。

曹队的方法还是不太懂啊。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector> 
#include<queue>
#include<set> 
#include<bitset> 
using std::sort;
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::set;
using std::pair;
using std::make_pair;
using std::bitset;

int T;
int n,m,K; 

int read(){//int，不能读负数，longlong     
    int f=1;
    int h=0;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')h=(h<<1)+(h<<3)+c-'0',c=getchar();
    return h*f; 
}
const int MAXN=505;
const int MAXM=5050;
struct Node{
    int a,pos;
}d[505];
set<pair<int,int> >st;
set<pair<int,int> >::iterator it;

void work1(Node* d,int n,int m){
    st.clear();
    for(int i=1;i<=n;i++)st.insert(make_pair(d[i].a,d[i].pos));
    while(m>n-1){
        it=st.end();--it;
        int pos=(*it).second,d=(*it).first;
        printf("%d %d\n",pos,K);
        st.erase(it);
        if(d-K>0)st.insert(make_pair(d-K,pos));
        m--;
    }
    for(int i=1;i<=m;i++){
//      cout<<"???"<<i<<' '<<m<<endl;
        it=st.begin();
        int pos1=(*it).second,d1=(*it).first;
        if(d1==K){
            printf("%d %d\n",pos1,d1);
            st.erase(it);
        }
        else{
            int res=K-d1;
            printf("%d %d ",pos1,d1);
            st.erase(it);
            it=st.end();--it;
            int pos2=(*it).second,d2=(*it).first;
            printf("%d %d\n",pos2,res);
            st.erase(it);
            st.insert(make_pair(d2-res,pos2));
        }
    }
}

bitset<5000500>f[2],tmp;//滚动数组，记录是否可行。
int g[5500500];//记录第一次选出i，最后一个选的是啥。 
int Mn,Mx;//能凑出的最大/小值 
#define nm(x) (x-Mn)
Node d1[MAXN],d2[MAXN];int tot1,tot2;//分成的两部分 
bool in_d1[MAXN];

void work2(){//先全部-k，转化成求能否凑出-k 
    tot1=tot2=Mn=Mx=0;memset(g,0,sizeof(g));memset(in_d1,false,sizeof(in_d1));
    f[0].reset();f[1].reset();//reset全部置为0，set全部置为1 
    for(int i=1;i<=n;i++){
        if(d[i].a<K)Mn+=d[i].a-K;
        else Mx+=d[i].a-K; 
    } 
    int now=0,lst=1;
    f[now][nm(0)]=true; 
    for(int i=1;i<=n;i++){
        std::swap(now,lst);
        if(d[i].a-K>=0)f[now]=f[lst]|(f[lst]<<(d[i].a-K));//最低位下标是0 
        else f[now]=f[lst]|(f[lst]>>(-d[i].a+K)); 
        tmp=f[now]^f[lst];//找到在当前这一位变成有解的位置
        for(int v=tmp._Find_first();v!=tmp.size();v=tmp._Find_next(v)){
//          cout<<v<<' '<<i<<"GG"<<endl;
            g[v]=i;
        } 
        if(f[now][nm(-K)])break;
    }
//  for(int j=Mn;j<=Mx;j++){
//      if(f[now][nm(j)])cout<<j<<' '<<g[nm(j)]<<endl;
//  }
    if(!f[now][nm(-K)])return puts("-1"),void(); 
    int nw=-K;
    while(nw){
        int x=g[nm(nw)];
//      cout<<"X"<<x<<' '<<nw<<endl;
        d1[++tot1]=d[x];
        in_d1[x]=true;
        nw-=(d[x].a-K);
    }
    for(int i=1;i<=n;i++)if(!in_d1[i])d2[++tot2]=d[i];
//  cout<<"d1:";for(int i=1;i<=tot1;i++)cout<<d1[i].pos<<' ';puts("");
//  cout<<"d2:";for(int i=1;i<=tot2;i++)cout<<d2[i].pos<<' ';puts("");
    work1(d1,tot1,tot1-1);
    work1(d2,tot2,tot2-1);
}

int main(){
    T=read();
    while(T--){
        n=read(),m=read(),K=read();
        for(int i=1;i<=n;i++)d[i].a=read(),d[i].pos=i;
        if(m>=n-1){work1(d,n,m);continue;}
        else work2();
    }
}