暴力“暴力”是指不用任何策略就能够解决问题。比如问1 2 ⋯ 100 12\dots10012⋯100的值for(int i1;i100;i)就是暴力。但当我们需要解决更复杂的问题时暴力往往会超时就需要使用其他的算法了。今天就来讲讲 CSP-J 考纲中的几种基本算法方括号内的是难度【3】贪心法【3】递推法【4】递归法【4】二分法【4】倍增法今天讲简单的先不讲倍增下次一起讲分治。贪心“贪心”是一种基本的算法。它的核心是在每一步选择中都采取当前状态下的最优解。但是贪心能造成局部最优不一定造成全局最优。一般情况下贪心的局部最优解可以导致全局最优解。什么时候要使用贪心关键当前选择不依赖后续选择也不会被之前选择影响。最优子结构问题的最优解包含其子问题的最优解可以通过一系列局部最优选择构建局部最优解。无后效性作出选择后不会回头重新考虑之前的决策过去的决策只影响当前装袋不影响未来选择。例题P13158 [GCJ 2017 Qualification] Oversized Pancake Flipper题目描述去年Infinite House of Pancakes 推出了一种新型煎饼。这种煎饼的一面“开心面”上有用巧克力豆做成的笑脸另一面“空白面”则什么都没有。你是当班的主厨。煎饼被排成一排在加热面上烹饪。为了进一步提升效率餐厅最近给你配备了一个超大号煎饼翻转器每次可以同时翻转恰好K KK个连续的煎饼。也就是说在这K KK个煎饼的范围内每个开心面朝上的煎饼会变为空白面朝上反之亦然煎饼的左右顺序不会改变。你不能用翻转器翻转少于K KK个煎饼即使是在煎饼排的两端因为加热面两侧有凸起的边界。例如你可以翻转最左边的K KK个煎饼但不能只翻转最左边的K − 1 K-1K−1个煎饼。你的学徒厨师还在学习工作他刚刚用老式的单煎饼翻转器翻转了一些单独的煎饼然后带着翻转器跑去洗手间了正好在顾客即将参观厨房之前。现在你只剩下超大号煎饼翻转器你需要尽快使用它使所有正在烹饪的煎饼都开心面朝上这样顾客才能满意地离开。给定当前煎饼的状态计算至少需要使用多少次超大号煎饼翻转器才能让所有煎饼都开心面朝上或者说明无法做到这一点。输入格式输入的第一行包含测试用例的数量T TT。接下来有T TT组测试用例。每组测试用例包含一行包括一个字符串S SS和一个整数K KK。S SS表示煎饼的排列每个字符为 表示该煎饼初始为开心面朝上或 -表示该煎饼初始为空白面朝上。输出格式对于每组测试用例输出一行格式为Case #x: y其中x xx是测试用例编号从 1 开始y yy是所需使用超大号煎饼翻转器的最小次数或者如果无法做到则输出IMPOSSIBLE。输入 #13 ----- 3 4 --- 4输出 #1Case #1: 3 Case #2: 0 Case #3: IMPOSSIBLE说明/提示数据范围1 ≤ T ≤ 100 1 \leq T \leq 1001≤T≤100。S SS中每个字符均为 或 -。2 ≤ K ≤ S 2 \leq K \leq S2≤K≤S的长度。例题解析很明显这是一道贪心。为什么呢对于从左到右的每个煎饼一旦我们决定是否翻转它所在的位置这个决定就是最终的。翻转第i ii个煎饼也不会影响已经处理过的左边部分让当前煎饼变成开心面能导致局部最优。思路从左到右遍历每遇到一个反面就将他反转。反转时记录步数。最后扫一遍如果还有反面的煎饼说明不可能实现输出IMPOSSIBLE。代码#includeiostream#includestring#includevectorusingnamespacestd;intmain(){intT;cinT;for(intt1;tT;t){string s;intK;cinsK;intns.length(),cnt0;vectorchararr(s.begin(),s.end());boolpostrue;for(inti0;in;i){if(arr[i]-){if(iKn){posfalse;break;}cnt;for(intji;jiK;j)arr[j]?arr[j]-:arr[j];//反转}}if(posfalse)coutCase #t: IMPOSSIBLE\n;else{boolalltrue;for(charc:arr)if(c-){allfalse;break;}if(all)coutCase #t: cntendl;elsecoutCase #t: IMPOSSIBLE\n;}}return0;}//elseif123递归在学习递归之前我常听到很多人都因为递归学不会而放弃了递归确实很重要那我们详细讲一讲。其实不要把递归想得太复杂、太难这是一个比较有趣的算法。在学习递归前你需要先学会函数。递归是指函数不断调用自己以解决复杂的问题。递归需要的两个部分递归出口什么时候跳出递归递归式如何递归。先看入门例题。例题B2153 求阶乘的和题目描述给定正整数n nn求不大于n nn的正整数的阶乘的和即求1 ! 2 ! 3 ! ⋯ n ! 1!2!3!\dotsn!1!2!3!⋯n!输出阶乘的和。阶乘定义为n ! n × ( n − 1 ) × ( n − 2 ) × ⋯ × 1 n!n\times (n-1)\times (n-2)\times \cdots \times 1n!n×(n−1)×(n−2)×⋯×1。例如5 ! 5 × 4 × 3 × 2 × 1 120 5! 5 \times 4 \times 3 \times 2 \times 11205!5×4×3×2×1120。输入格式输入一行包含一个正整数n ( 1 n 12 ) n(1 n 12)n(1n12)。输出格式输出一行表示阶乘的和。输入 #15输出 #1153例题解析思路先看看怎么计算阶乘。阶乘是每一个教练都要讲的入门题。观察5 55的阶乘5 × 4 × 3 × 2 × 1 5\times 4\times 3 \times 2\times 15×4×3×2×1。怎么拆分它使得我们能够运用递归的思路经过观察我们也发现5 55的阶乘为5 × 4 ! 5\times 4!5×4!。就是单拎出来第一个数后面的数就是( n − 1 ) (n-1)(n−1)的阶乘。这就是递归式了。那么这个递归的出口是什么当计算到1 11的时候递归的出口就是返回1 11因为1 ! 1 1!11!1。递归代码intjc(intx){//计算 x 的阶乘if(x1)return1;//递归出口elsereturnx*jc(x-1);//递归式}最后再暴力地for(int i1;in;i)将结果相加即可。注意对于这道题更推荐暴力。因为递归会调用栈空间效率反而不如暴力。代码递归代码#includeiostream//本人不推荐使用万能头usingnamespacestd;intjc(intx){if(x1)return1;returnx*jc(x-1);}intmain(){intn,ans0;cinn;for(inti1;in;i)ansjc(i);coutans;return0;}暴力代码AC记录#includeiostreamusingnamespacestd;intn,ans0;intmain(){cinn;for(inti1;in;i){intjc1;for(intji;j1;j--)jc*j;ansjc;}coutans;return0;}此外斐波那契数列也是入门好题这里不再赘述。深入地“递归”上文讲到的递归只是皮毛来看看递归实际的用处。在上面的例子中我们知道递归的本质是将问题拆分成个体和一个整体再将整体逐个拆为个体如果你是入门者可能还没有感觉那么请看下文。二叉树的中序遍历左子树 - 根 - 右子树。来通过递归实现中序遍历。// 递归中序遍历voidf(TreeNode*root,vectorintresult){if(rootnullptr)return;f(root-left,result);// 左result.push_back(root-val);// 中f(root-right,result);// 右}前序、后序同理只需调换顺序即可。推荐问题汉诺塔问题(hanoi)请读者自行查阅。递推递推和递归差不多唯一的区别在于递归往后推递推往前推考试也不会问“这是递归还是递推”递归的应用也更多。所以这里不再赘述递推感兴趣的读者可以自己查阅资料。二分什么是二分二分二分查找/二分法是一种在有序数据集合中快速查找目标元素的算法。其核心思想为每次将搜索区间减半通过比较中间元素与目标值排除一半不可能的区域。二分模板while(lr){intmidl(r-l1)/2;// 找最大可行解if(check(mid))lmid;// 可行尝试更大的elsermid-1;// 不可行减小}coutlendl;请务必记熟。感觉 CSP-J 挺看重二分的。例题P1873 [COCI 2011/2012 #5] EKO / 砍树题目描述伐木工人 Mirko 需要砍M MM米长的木材。对 Mirko 来说这是很简单的工作因为他有一个漂亮的新伐木机可以如野火一般砍伐森林。不过Mirko 只被允许砍伐一排树。Mirko 的伐木机工作流程如下Mirko 设置一个高度参数H HH米伐木机升起一个巨大的锯片到高度H HH并锯掉所有树比H HH高的部分当然树木不高于H HH米的部分保持不变。Mirko 就得到树木被锯下的部分。例如如果一排树的高度分别为20 , 15 , 10 20,15,1020,15,10和17 1717Mirko 把锯片升到15 1515米的高度切割后树木剩下的高度将是15 , 15 , 10 15,15,1015,15,10和15 1515而 Mirko 将从第1 11棵树得到5 55米从第4 44棵树得到2 22米共得到7 77米木材。Mirko 非常关注生态保护所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度H HH使得他能得到的木材至少为M MM米。换句话说如果再升高1 11米他将得不到M MM米木材。输入格式第1 11行2 22个整数N NN和M MMN NN表示树木的数量M MM表示需要的木材总长度。第2 22行N NN个整数表示每棵树的高度。输出格式1 11个整数表示锯片的最高高度。输入输出样例 #1输入 #14 7 20 15 10 17输出 #115输入输出样例 #2输入 #25 20 4 42 40 26 46输出 #236说明/提示对于100 % 100\%100%的测试数据1 ≤ N ≤ 10 6 1\le N\le10^61≤N≤1061 ≤ M ≤ 2 × 10 9 1\le M\le2\times10^91≤M≤2×109树的高度≤ 4 × 10 5 \le 4\times 10^5≤4×105所有树的高度总和 M MM。例题解析这是一个典型的二分答案问题因为答案具有单调性锯片高度 H 越高得到的木材越少可验证性对于给定的 H可以快速计算能得到的木材总量答案范围确定H 在 [0, max(tree_heights)] 之间二分搜索策略左边界left 0锯片高度为 0 时得到所有木材右边界right max_height锯片高度等于最高树时得到 0 木材对于每个mid计算f(mid)如果f(mid) M说明高度可以更高在右半部分搜索如果f(mid) M说明高度太高了在左半部分搜索计算木材总量对于每棵树高度tree[i]如果tree[i] H则得到tree[i] - H米木材如果tree[i] H则得到 0 米木材代码#includeiostream#includevectorusingnamespacestd;intn,m,maxx;intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnm;vectorlonglongq(n);for(inti0;in;i){intval;cinval;q[i]val,maxxmax(maxx,val);}intl0,rmaxx,mid;while(lr){midl(r-l1)/2;longlongtot0;for(inti0;in;i)tot(q[i]-mid0?q[i]-mid:0);if(totm)lmid;elsermid-1;}coutlendl;return0;}例题2P1020 [NOIP 1999 提高组] 导弹拦截题目描述某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。输入格式一行若干个整数中间由空格隔开。输出格式两行每行一个整数第一个数字表示这套系统最多能拦截多少导弹第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。输入输出样例 #1输入 #1389 207 155 300 299 170 158 65输出 #16 2说明/提示对于前50 % 50\%50%数据满足导弹的个数不超过10 4 10^4104个。该部分数据总分共100 100100分。可使用O ( n 2 ) \mathcal O(n^2)O(n2)做法通过。对于后50 % 50\%50%的数据满足导弹的个数不超过10 5 10^5105个。该部分数据总分也为100 100100分。请使用O ( n log ⁡ n ) \mathcal O(n\log n)O(nlogn)做法通过。对于全部数据满足导弹的高度为正整数且不超过5 × 10 4 5\times 10^45×104。此外本题开启 spj每点两问按问给分。NOIP1999 提高组 第一题例题 2 代码#includeiostream#includealgorithm#includecstringusingnamespacestd;constintMAXN100005;intmissiles[MAXN];inttails1[MAXN];// 用于最长不上升inttails2[MAXN];// 用于最长上升intmain(){intn0;while(cinmissiles[n]){n;}if(n0){cout0\n0\n;return0;}// 第一问最长不上升子序列intlen10;for(inti0;in;i){inthmissiles[i];// 二分查找第一个小于 h 的位置intleft0,rightlen1;while(leftright){intmidleft(right-left)/2;if(tails1[mid]h){rightmid;}else{leftmid1;}}// 插入或替换tails1[left]h;if(leftlen1){len1;}}// 第二问最长上升子序列intlen20;for(inti0;in;i){inthmissiles[i];// 二分查找第一个大于等于 h 的位置intleft0,rightlen2;while(leftright){intmidleft(right-left)/2;if(tails2[mid]h){rightmid;}else{leftmid1;}}// 插入或替换tails2[left]h;if(leftlen2){len2;}}coutlen1\nlen2\n;return0;}