神奇的暴力——CF1271F Divide The Students

Sweetlemon

2019-12-18 09:59:23

Solution

### CF1271F Divide The Students 我一开始根据初中数学套路列了不等式,然后要判断七元不等式组是否有整数解?我想还是算了。 那么怎么办呢?是不是可以动态规划?好像又没有什么思路…… 打开 [tutorial](https://codeforces.com/blog/entry/72247) 一看,真是太神奇了…… 下面简述思路。 首先,你可能经历了和我上面一样的心路历程。发现没办法做了? 接着,如果这是 OI 赛制的含部分分题目,那么你应该会在“数据范围”一栏看到一些“特殊性质”。现在没有“特殊性质”,就让我们来自己脑补! 1. 如果所有学生都翘课,那么直接输出 $7$ 个 $0$ 就好了~生活好轻松…… 2. 如果所有的学生都只上一门课,那么这个问题很容易解决,只要 $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}$。 3. 如果所有的学生都只上两门课。那么似乎不知道怎么解决?这档部分分先跳过。 4. 如果所有学生都上完三门课,那么只要 $\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 种情况我们都很容易解决,因此还可以造出这样的部分分: 5. 如果所有的学生要么只上一门课,要么上完三门课,那么只要先分配上完三门课的学生,再分配只上一门课的学生即可。 上面这些部分分都很好做,$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{玄学})$。 ```cpp #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; } //以下略去读入输出优化的实现 ```