[置顶] 洛谷N句话题解QWQ

首先我会援引一些大佬的代码，如果大佬们看到自己的代码被挂了不开心，可以私信我，我会致谢或者删除$qwq$ ## $ps$：至于一些$zz$题……我就不整了$qwq$ 诶，这并不是一句话题解$qwq$,本蒟蒻太蒟了……所以会长一些qnq不过肯定会越来越短的啦！！ ___________ $P1002$过河卒[甩链接](https://www.luogu.org/problem/show?pid=P1002#sub) 诶这个题不是广搜？$emmmmm$好像方案数这个东西，搜起来很耗时，并且结果有可能会爆$int$…… 所以我们选择DP……这好像也不能算是DP……也就是个递推吧$qwq$, 即，每一格的状态总是可以通过上方、左方两个状态转移过来。 啊，显然方案总数也是可以这样乱搞的$qwq$ 但是据说好像可以滚去一维的空间……今天上午脑子昏沉，看不懂，以后再说吧$qwq$ ---------------------------------------- $p1004$ 方格取数[甩链接](https://www.luogu.org/problem/show?pid=P1004#sub) 诶这个题不就是传纸条吗$qwq$ 据说可以状压一下下，但本蒟蒻不会呀！ 既然是$DP$，那就考虑状态转移，只能从上下左右四个相邻的$classmates$传导过来$qwq$,那么就应该是二维$DP$，但由于有两个人，所以根据乘法原理，总共会有四维的状态总数，所以是四维$DP$. 哈，没那么简单，别忘了不能重复走这个问题$qwq$,其实只需要最后减去就好惹$QVQ$ $Such$ $as$ ```cpp f[i][j][k][l]=my_max(f[i][j-1][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1],f[i-1][j][k-1][l])+a[i][j]+a[k][l]; if(i==k&&j==l)f[i][j][k][l]-=a[i][j]; ``` ________________________ $p1006$传纸条[link](https://www.luogu.org/problem/show?pid=P1006) 其实吧，这和上一个几乎是一个题……但其实是可优化的！ 因为我们可以换一种方法来看待状态：我们可以将两个纸条看作同时传递，那么每一次移动的单位都是一定的，那么就可以有在上一个题中的$i+j=k+l=nowstep$, 所以我们可以通过枚举步数、分别枚举两个点的一个坐标，然后用$nowstep$推出另外一个坐标即可$qwq$. $Such$ $as$ ```cpp for (int k=1;k<=n+m-1;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ if (k-i<0 || k-j<0)continue; f[k][i][j] = my_max(f[k-1][i][j],f[k-1][i-1][j-1],f[k-1][i][j-1],f[k-1][i-1][j]) + a[i][k-i+1] + a[j][k-j+1]; } ``` ___________________________________ $p1010$ 幂次方[link](https://www.luogu.org/problem/show?pid=P1010#sub) 这个题一看就需要我们迭代操作……所以考虑递归。 那么递归到底的时候就只会有两种情况：出现$2(0)$或$2$,那我们就对于仍可以分解的每部分，中间以$"+"$号相连，每部分自身迭代下去就好。 嗯……递归算法是个好东西……但是需要理解透彻$qwq$ ```cpp void dfs(int n) { bool check=1; while(n) { if(!check)cout<<"+"; int w=(int)log2(n); if(w==1)cout<<"2"; else if(w==0)cout<<"2(0)"; else { cout<<"2(";dfs(w);cout<<")"; } n-=pow(2,w); check=0; } } ``` ___________________ $p1011$ 车站[link](https://www.luogu.org/problem/show?pid=P1011#sub) 乱搞一下就行……这是一道考察综合素质的水题……但是我做了好长时间$qwq$ 还有做题的时候一定要集中精力，读懂题再做……读三遍…… over. ____________________ $p1012$ 拼数[link](https://www.luogu.org/problem/show?pid=P1012#sub) 按照相邻的两个串相连接之后的字典序大小来写$sort$的$cmp$函数即可。 唔，还是要仔细想啊！水题也不能太过划水…… ______________________ $p1014$ Cantor表[link](https://www.luogu.org/problem/show?pid=P1014#sub) 啊，也是无脑的找规律，这个就只能看$OIer$的个人素养了$qwq$…… 对于这种题而言……还是不要抄题解的为好（逃 _______________________ $p1017$ 进制转换[link](https://www.luogu.org/problem/show?pid=P1017#sub) 这道题当时卡了我好久qwq……大约$45min$……因为我实在搞不清楚这个负进制是怎么个操作$qnq$…… 不过其实也挺简单的……就是要明白进制的定义： 对于一个数$k$,和一个数列$a_t…a_3a_2a_1a_0$,则对于一个$k$进制下的数，总可以表示成 ## $\Sigma_{i=0}^{n}(a_ik^i)$, $a_i\in[0,|k|)$ 这个式子看起来好像很富有亲和力$qwq$ $~~~~~$ ]反向逃。 也就是说每个进制位上的数只能是非负数啦！但是我们发现在短除法的时候有可能会出现负数，这个时候由于对于每个$a_i$都只会有$|a_i|<|k|$,所以我们只需要在这一位加上一个$|k|$即可，但是这样我们就需要向高位借一个$1$啦$qwq$ $Such$ $as$ ```cpp int divide(int n,int b,char *c) { int i=0,k; while(n!=0) { k=n%b; n/=b; if(k<0){k-=b;n+=1;} if(k>9)c[i]=char(k-10+'A'); else c[i]=char(k+'0'); i++; } return i-1; } ``` 这是从$DJblooky$大佬的题解里刨过来的$qwq$ ,在这里向这位大佬表示敬意！ ___________ $p1018$ 乘积最大 毒瘤啊$qwq$……居然要高精…… 先说不高精的，就是个$dp$，但是$dp$多种多样啊！在这里我选了一种很不错的$dp$方式，$by$ LOI_lxt大佬: 用$dp[k][i]$表示用了$k$个乘号,前$i$个数的乘积最大值,那么我们可以通过每次只枚举最后一个乘号来实现状态的推演，因为之前的$k-w(0<=w<k)$已经枚举过了$qwq$。 哦，高精我还不是很熟啊，需要练习一下$qwq$ ___________ $p1019$ 单词接龙[link](https://www.luogu.org/problem/show?pid=P1019) 这道题是真你萌毒瘤啊$qnq$,虽然就是很水的模拟而已 忽略上一句极富有素质的感慨$qwq$ 首先我们要知道一些坑点……不读题的伤你不懂…… $1.$一个单词可以用两遍…… $2.$在加长度的时候，减去的不是最大重复部分，而是最小重复部分 $3.$较为复杂的题往往需要良好的心态和码力，所以蒟蒻还需要练习哇！ 嗯，我还是太菜了。 最后付个辣鸡源码（主要的函数），顺便以期日后能够写得更简练。 ```cpp inline int add_haha(string a,string b) { int minus=0,tot=0; int la=a.size(),lb=b.size(); for(int i=0;i<=min(la,lb);i++) { bool flag=1; for(int j=la-i;j<=la-1;j++) { if(a[j]!=b[tot])flag=0; tot++; } if(flag&&!minus)minus=tot; tot=0; } return lb-minus; } inline bool check(string a,string b) { int tot=0; int la=a.size(),lb=b.size(),lla=la,llb=lb; for(register int i=0;i<min(la,lb);i++) { if(a[i]!=b[i]) break; else { lla--; llb--; } } int flag=0,ff=0,use=1; if((!lla&&llb)||(!llb&&lla))return 0; for(register int i=0;i<min(la,lb);i++) { for(register int j=la-i;j<=la-1;j++) { if(a[j]!=b[tot++])ff=1; use=0; } if(!ff&&!use)flag++; ff=0; tot=0; use=1; } if(!flag)return 0; return 1; } ``` _____________ $p1020$ 导弹拦截[link](https://www.luogu.org/problem/show?pid=P1020) 这个题不就是个最长上升子序列的裸题吗$qwq$,$nlogn$方法要好好打（背）。 求出一个子序列之后再乱搞贪心就好啊$qwq$ 贪心的时候就只需要对于每个导弹，我们都选择一个最小拦截高度的、但是可以拦截当前导弹的系统，如果没有可以拦截当前导弹的系统，系统个数就$++$。 ```cpp ………………………… x=0; for(k=1;k<=n;k++) if(h[k]>=a[i]) if(x==0)x=k; else if(h[k]<h[x])x=k; if(x==0)n++,x=n; h[x]=a[i]; i++; ………………………… ``` ______________ $p1021$ 邮票面值设计[link](https://www.luogu.org/problem/show?pid=P1021#sub) 这个题我当时不会做……嗯……留下了并没多好的印象$qnq$ 这个题我们首先可以考虑用深搜搜出来所用的几个数，而至于$MAX$，我们可以考虑$DP$，而需要注意以下这些$Tips$： $1.$虽然题目中说明了最多用$N$张邮票，也就是可以少放，但是多放的情况肯定大于少放的情况，所以直接对$n,k$进行$dfs$即可。 $2.$ $DFS$中的一个常见技巧——为了去重，可以将整个$ans$序列看作单调递增序列，比较好搞$qwq$ $3.$ 对于找$MAX$,我们可以以f[i]表示拼$i$所用的最小数的个数，那么在记录之后，我们就可以对$1$~$a[now]\times{n}$(因为当前最多取$a[now]\times{n}$，所以上界为$a[now]\times{n}$)，直到筛到个数$>n$为止。 嗯……辅助DP嵌套$DFS$还真是让本蒟蒻吃不消啊$qwq$ 嗯，贴关键部分（求$MAX$） ```cpp int up=a[now]*n; for(int i=1;i<=now;i++) for(int j=a[i];j<=up;j++) f[j]=min(f[j],f[j-a[i]]+1); for(int i=1;i<=up;i++) if(f[i]>n) return i-1; return up; ``` 我可是真菜$qnq$ _____________________________ $p1024$ 一元三次方程求解[link](https://www.luogu.org/problem/show?pid=P1024) 这个题的数据范围怎么给的这么暴力哇？？把数据范围再扩大个$100$倍暴力不也跑得过吗 以下这个好像是一个不知道对不对的二分……希望有大佬能指出问题来$qwq$ ```cpp for(double i=-100;i<=100;i++) { l=i,r=i+1; if(pks(i)<=0.01&&pks(i)>=-0.01)ans[++tot]=i,continue; while(r-l>=0.01) { double mid=(l+r)/2; if(pks(mid)>0.01)r=mid; else if(<pks(mid)<-0.01)l=mid; else ans[++tot]=mid; } } ``` _______________________________ $p1030$ 求先序排列[link](https://www.luogu.org/problem/show?pid=P1030#sub) 整理这个题的目的就是因为我老是忘记树的遍历是怎么回事…… 中：左->根->右 先：根->左->右 后：左->右->根 那么在我们知道后序遍历之后，最后一个元素就是根节点；然后再在中序遍历中查询根节点，得到左右子树，再到后序遍历中查找两个子树的根节点，然后继续迭代即可。 $emmmm$好像这题水的很，不过我还要为我没有打好树的基础而埋单啊$qnq$ ```cpp void build_pre(string pre,string aft) { if(pre.size()) { char root_now=aft[aft.size()-1]; cout<<root_now; int root=pre.find(root_now); build_pre(pre.substr(0,root),aft.substr(0,root)); build_pre(pre.substr(root+1),aft.substr(root,pre.size()-root-1)); } } ``` 感谢 sunyufei 大佬提供的一个很简洁的方法，此处鞠躬致敬$qwq$ _____________________ $P1037$ 产生数[link](https://www.luogu.org/problemnew/show/P1037#sub) 为什么是广搜$qwq$……只要用乘法原理把所有的字母的变换方式乘起来即可。 诶，是要高精的哇$qnq$（$unsigned$ $long$ $long$ $int$正面硬刚不过） 吼哇吼哇，就这么做完了。 ______________________ $p1042$ 乒乓球 不挂$link$了……这个水题就是考你怎么输入的…… __________________________________________________ $p1044$ 栈 就是个卡特兰数求第$n$项啊……在这里可以提供一种证明的思路：既然是跟入栈次序有关，就可以对于一个卡特兰数$Cut$（胡蒙的英文），可以如此求： ## $Cut(n)=\Sigma_{i=1}^{n-1}(Cut(i)+Cut(n-i)),Cut(1)=1$ 嗯……浅显易懂啊，我就不证了（逃 _________________________ $p1052$ 过河[link](https://www.luogu.org/problem/show?pid=P1052) 啊，这是道好题哇$qwq$. 首先很明确的是，青蛙每一步的状态总是由上一步的状态转移过来的，也就是说$DP$方程是没什么思维难度的： f[i]表示走到第$i$单位长度时踩到石头的最小数量，那么有： ### $f[i]=min$ { $f[i]-length+check[i]$},$s<=length<=t$ 然鹅并不可做，因为$l$实在是太大了,$O(n)$都会炸，所以考虑离散化。而离散化好像排序和取模都可以，在这里我选择了膜法$qwqqq$ ____________________________ $p1057$ 传球游戏[link](https://www.luogu.org/problemnew/show/P1057#sub) 这个题考虑$dp$,那么首先定义状态,用$f[i][j]$表示传回编号$i$，传了$j$次的最多不同方案数。那么状态之间的转移就是 有 ### $f[1][j]=f[n][j-1]+f[2][j-1]$ ### $f[i][j]=f[i+1][j+1]+f[i-1][j+1]$ 那么最终答案就存在$f[1][m]$里 而实质上，对于一道$DP$题目，我们要先去审清它是不是一道$DP$，就是通过找状态和状态之间是否可以转移得出结论的。那么之后就需要考虑如何转移，即相邻的两个状态该如何演变。$DP$的特点就是好理解，但是理解是被动，主动做的话就会十分的$embarrassing$ ~~嗯，其实就是因为我蒟.~~ ________ $p1063$ 能量项链[link](https://www.luogu.org/problemnew/show/P1063#sub) $emmmm$这应该可以算是一个很经典的区间$DP$,那由于我的某篇$zz$博客专门讲了，就挂个链吧。 [区间$DP$](https://www.luogu.org/blog/pks-LOVING/higher-level-dynamic-programming-jiao-gao-ji-di-dong-tai-gui-hua-ou-j) _______ $p1064$ 金明的预算方案[link](https://www.luogu.org/problemnew/show/P1064) 这个题疑似是有依赖的背包问题，那么其实对于普通的这种有依赖的背包问题（无嵌套），我们是都可以转化成有多种情况的普通背包。 比如在这个题目中，我们就可以简化成有五种情况的01背包。即： 对于一个主件而言 1、不买； 2、买自己，也买自己的左儿子； 3、买自己，也买自己的右儿子； 4、只买自己； 5、买自己，左儿子买，右儿子也买； 而附件是没有任何选择权的（只能被选择），所以不枚举附件。 ____________________ $p1075$ 质因数分解[link](https://www.luogu.org/problemnew/show/P1075#sub) 这道题其实没什么可整理的，就是个水题啊，但是让我至今也很记忆犹新的，是下面这份十分简练的$rqy$在初三上学期写出来的代码： ```cpp cin>>n; int i=2; while(n%i!=0)i++; cout<<n/i; ``` 我从来不肯承认有人真的比我强很多，所以我虽然很佩服$rqy$，但我也要把它当作一个争取超越的对象啊。 $"The$ $limit$ $of$ $your$ $mind$ $is$ $the$ $limit$ $of$ $your$ $world."$ ___________________ $p1080$ 国王游戏[link](https://www.luogu.org/problemnew/show/P1080#sub) 这个题本来不是很恶心，但是因为是个$NOIp$的题目，所以不加一个高精对不起这个题的毒瘤属性$qwq$,所以要加一个高精来毒瘤以下。 这个题的贪心方向应该很明显，就是按某种方式进行排序，然后使得最大的大臣收益最小。好的，那么$sort$需要一个$cmp$，那么现在的问题就是怎么写一个$cmp$。 很显然啊，排序的时候最好的方案应该是让在其他状态下收益高的大臣在前面，让受益小的大臣在后面。 而排序，在这里给出花姐姐自己的证明： 设正在进行$cmp$的两个大臣的左右手上写的为$l_1r_1,l_2r_2$在他俩之前总会有至少一个人，设其左右上的数字为$l_0r_0$。 那么对于两种不同的顺序，即1在2之前和2在1之前，有两种不同的收益： $1$在$2$前：$max(\frac{l_0l_1}{r_2},\frac{l_0}{r_1})$ $2$在$1$前：$max(\frac{l_0l_2}{r_1},\frac{l_0}{r_2})$ 那么对于这两个式子，我们设第一种情况的值要大于第二种情况，即让1在前面会更优，便可以得到： $max(\frac{l_0l_1}{r_2},\frac{l_0}{r_1})>max(\frac{l_0l_2}{r_1},\frac{l_0}{r_2})$ 因为都是正值，所以两边同乘r_2r_1可以有: $max(l_0l_1r_1,l_0r_2)>max(l_0r_1,l_0l_2r_2)$ 提取$l_0$可得: $max(l_1r_1,r_2)>max(r_1,l_2r_2)$ 而因为若式子左边有$r_2>l_1r_1$,那么就不可能有左边大于右边，因为显然$r_2<l_2r_2$,所以右边同理,可将原始式子化作： $l_1r_1>l_2r_2$ 这就是$cmp$ 至于高精乘，人家不会了啦$qwqqq$ ________________________ $p1087$ $FBI$树[link](https://www.luogu.org/problemnew/show/P1087#sub) 嗯，很棒啊，又是一道辣鸡橙题，然鹅当时我还是不会做$OTZ$ 他这个题很有良心的一点是让你后序遍历输出，那么很显然了哇，输出操作应该放在递归之后，也就是回溯的时候进行。那么在回溯的时候只需要在记录的左右区间内跑一遍就好。 好吧，当时不会的主要原因就是因为我对于树的遍历这部分掌握的太渣了$qnq$ __________________________ $p1088$ 火星人 [link](qhttps://www.luogu.org/problemnew/show/P1088#sub) 这道题就是一个$stl$的模板题……全排列直到$m--$变成0为止…… 那么在此，整理一下$next$_$permutation()$的用法，这个函数是一个$bool$型的，返回值的意义是是否还有下一个排列，与之相反的是$prev$_$permutation()$,那么对于这两个函数： $next$_$permutation()$ $bool$型 直接对原数组进行操作 所有排列的字典序是递增的 $prev$_$permutation()$ $bool$型 同上 $~~~~~~~~~~~~~~~~~~~~~~~~~$ 所有排列的字典序是递减的 $emmm$就这样吧 ___________________________ $p1115$ 最大子段和[link](https://www.luogu.org/problemnew/show/P1115) 这个地方给出一个$dp$做法。在求子段和的时候由于是由跨负数的,所以在我们的第一次循环之后，在第二次循环再进行一次反悔操作。当然同时也要保证最优性$QWQ$。那么就可以得到如下程序段： ```cpp for(int i=1;i<=n;i++) cin>>A[i]; dp[1]=A[1]; for(int i=2;i<=n;i++) dp[i]=max(dp[i-1]+A[i],A[i]); for(int i=2;i<=n;i++) dp[i]=max(dp[i-1],dp[i]); ``` 这就是如何求最大子段和的$DP$做法$qwq$