神奇的暴力——CF1271F Divide The Students

Sweetlemon · 2019-12-18 09:59:23 · 题解

CF1271F Divide The Students

我一开始根据初中数学套路列了不等式，然后要判断七元不等式组是否有整数解？我想还是算了。

那么怎么办呢？是不是可以动态规划？好像又没有什么思路……

打开 tutorial 一看，真是太神奇了……

下面简述思路。

首先，你可能经历了和我上面一样的心路历程。发现没办法做了？

接着，如果这是 OI 赛制的含部分分题目，那么你应该会在“数据范围”一栏看到一些“特殊性质”。现在没有“特殊性质”，就让我们来自己脑补！

如果所有学生都翘课，那么直接输出 7 个 0 就好了～生活好轻松……
如果所有的学生都只上一门课，那么这个问题很容易解决，只要 a_{i,1}+a_{i,2}\ge d_{i,4},b_{i,1}+b_{i,2}\ge d_{i,6},c_{i,1}+c_{i,2}\ge d_{i,7} 即有解，分配时也可以随意地把学生分组，每个小组数学、编程和体育的承载力分别为 a_{i,j},b_{i,j},c_{i,j}。
如果所有的学生都只上两门课。那么似乎不知道怎么解决？这档部分分先跳过。
如果所有学生都上完三门课，那么只要 \min(a_{i,1},b_{i,1},c_{i,1})+\min(a_{i,2},b_{i,2},c_{i,2})\ge d_{i,1} 即有解，分配时同样可以把学生分组，每个小组的承载力为 \min(a_{i,j},b_{i,j},c_{i,j})。

这是一些比较容易想到的部分分。由于第 2 种和第 4 种情况我们都很容易解决，因此还可以造出这样的部分分：

如果所有的学生要么只上一门课，要么上完三门课，那么只要先分配上完三门课的学生，再分配只上一门课的学生即可。

上面这些部分分都很好做，O(1) 就做完了。

可是一旦加上了“上两门课的学生”，问题就困难了不少！怎么办呢？

OI 赛制下如果想不到解决办法怎么办？暴力啊。

这里也有一种暴力：先枚举只上两门课的学生的分组情况，这样就转变为了第 5 种部分分的情况，可以再花 O(1) 时间解决。由于只上两门课的学生有三种，要分别枚举这三种学生的分组情况，因此需要三重循环，总复杂度 O(n^3) 级别。

什么？你告诉我已经做完了？我怎么不相信！难道 n^3 能过 3000？

事实上，这题似乎真能过。由于学生总人数不超过 3000，因此选两门课的三类学生人数（分别记作 x,y,z）满足 x+y+z\le 3000。总计算量至多是 xyz，根据均值不等式，xyz\le (\frac{x+y+z}{3})^3=10^9。由于这题有 8\mathrm{s} 时限，因此平均到每一秒的计算量大约是 1.25\times 10^8，对一个不是很复杂的算法来说勉强可过。何况由于可以随手写一些剪枝，这个计算量也很难达到。

综上，复杂度 O(n^3)= O(\text{能过})！事实上，（据出题人所说）不加剪枝的程序在最慢的点只跑了 1.8\mathrm{s}，我的加了简单剪枝的程序（见下）在最慢的点只跑了 46\mathrm{ms}。

这题的主要启示就是，要善于把问题特殊化（想部分分），并能从部分分中得到原问题的解。事实上，这种思维方法在 NOIP 中也有多次出现。另外，还要适当估算时间复杂度，敢于写 O(\text{玄学})。

#include <cstdio>
#include <cctype>
#define MAXIOLG 25
#define FILENAME(x)\
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout);
#define LOWBIT(x) ((x)&(-(x)))
using namespace std;

typedef long double ld;
typedef long long ll;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读，实现略去
void ayano(io_t x,char spliter='\n'); //快写，实现略去

int a1,b1,c1,a2,b2,c2;
int dabc,da,db,dc,dab,dac,dbc;

int check(void);
int min(int a,int b);
int min(int a,int b,int c);

int main(void){
    int testdatas=seto();
    while (testdatas--){
        a1=seto(),b1=seto(),c1=seto();
        a2=seto(),b2=seto(),c2=seto();
        dabc=seto(),dab=seto(),dac=seto(),
        da=seto(),dbc=seto(),db=seto(),
        dc=seto();
        for (int tab=0,uab=min(dab,min(a1,b1));tab<=uab;tab++){
            if (dab-tab>min(a2,b2))
                continue;
            a1-=tab,b1-=tab,a2-=(dab-tab),b2-=(dab-tab);
            for (int tac=0,uac=min(dac,min(a1,c1));tac<=uac;tac++){
                if (dac-tac>min(a2,c2))
                    continue;
                a1-=tac,c1-=tac,a2-=(dac-tac),c2-=(dac-tac);
                for (int tbc=0,ubc=min(dbc,min(b1,c1));tbc<=ubc;tbc++){
                    if (dbc-tbc>min(b2,c2))
                        continue;
                    b1-=tbc,c1-=tbc,b2-=(dbc-tbc),c2-=(dbc-tbc);
                    if (check()){
                        int fabc=min(min(a1,b1,c1),dabc);
                        a1-=fabc,b1-=fabc,c1-=fabc;
                        int fa=min(a1,da);
                        int fb=min(b1,db);
                        int fc=min(c1,dc);
                        ayano(fabc,' '),ayano(tab,' '),ayano(tac,' '),
                        ayano(fa,' '),ayano(tbc,' '),ayano(fb,' '),
                        ayano(fc);
                        goto nowok; //偷懒用 goto，勿喷
                    }
                    b1+=tbc,c1+=tbc,b2+=(dbc-tbc),c2+=(dbc-tbc);
                }
                a1+=tac,c1+=tac,a2+=(dac-tac),c2+=(dac-tac);
            }
            a1+=tab,b1+=tab,a2+=(dab-tab),b2+=(dab-tab);
        }
        ayano(-1);
        nowok: ;
    }

    return 0;
}

inline int min(int a,int b){
    return (a<b)?(a):(b);
}
inline int min(int a,int b,int c){
    return min(min(a,b),c);
}

int check(void){
    int tmn1=min(a1,b1,c1);
    int tmn2=min(a2,b2,c2);
    if (tmn1+tmn2<dabc)
        return 0;
    if (a1+a2-dabc>=da && b1+b2-dabc>=db && c1+c2-dabc>=dc)
        return 1;
    return 0;
}

//以下略去读入输出优化的实现