_pks 'w blog

_pks 'w blog

除了勇气,我什么都不缺。

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

posted on 2018-04-02 11:27:56 | under 陶冶情操 |

首先我会援引一些大佬的代码,如果大佬们看到自己的代码被挂了不开心,可以私信我,我会致谢或者删除 $qwq$

$ps$ :至于一些 $zz$ 题……我就不整了 $qwq$

诶,这并不是一句话题解 $qwq$ ,本蒟蒻太蒟了……所以会长一些qnq不过肯定会越来越短的啦!!


$P1002$ 过河卒甩链接

诶这个题不是广搜? $emmmmm$ 好像方案数这个东西,搜起来很耗时,并且结果有可能会爆 $int$ ……

所以我们选择DP……这好像也不能算是DP……也就是个递推吧 $qwq$ , 即,每一格的状态总是可以通过上方、左方两个状态转移过来。

啊,显然方案总数也是可以这样乱搞的 $qwq$

但是据说好像可以滚去一维的空间……今天上午脑子昏沉,看不懂,以后再说吧 $qwq$


$p1004$ 方格取数甩链接

诶这个题不就是传纸条吗 $qwq$

据说可以状压一下下,但本蒟蒻不会呀!

既然是 $DP$ ,那就考虑状态转移,只能从上下左右四个相邻的 $classmates$ 传导过来 $qwq$ ,那么就应该是二维 $DP$ ,但由于有两个人,所以根据乘法原理,总共会有四维的状态总数,所以是四维 $DP$ .

哈,没那么简单,别忘了不能重复走这个问题 $qwq$ ,其实只需要最后减去就好惹 $QVQ$

$Such$ $as$

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

其实吧,这和上一个几乎是一个题……但其实是可优化的!

因为我们可以换一种方法来看待状态:我们可以将两个纸条看作同时传递,那么每一次移动的单位都是一定的,那么就可以有在上一个题中的 $i+j=k+l=nowstep$ , 所以我们可以通过枚举步数、分别枚举两个点的一个坐标,然后用 $nowstep$ 推出另外一个坐标即可 $qwq$ .

$Such$ $as$


 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

这个题一看就需要我们迭代操作……所以考虑递归。

那么递归到底的时候就只会有两种情况:出现 $2(0)$ 或 $2$ ,那我们就对于仍可以分解的每部分,中间以 $"+"$ 号相连,每部分自身迭代下去就好。

嗯……递归算法是个好东西……但是需要理解透彻 $qwq$


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

乱搞一下就行……这是一道考察综合素质的水题……但是我做了好长时间 $qwq$

还有做题的时候一定要集中精力,读懂题再做……读三遍……

over.


$p1012$ 拼数link

按照相邻的两个串相连接之后的字典序大小来写 $sort$ 的 $cmp$ 函数即可。

唔,还是要仔细想啊!水题也不能太过划水……


$p1014$ Cantor表link

啊,也是无脑的找规律,这个就只能看 $OIer$ 的个人素养了 $qwq$ ……

对于这种题而言……还是不要抄题解的为好(逃


$p1017$ 进制转换link

这道题当时卡了我好久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$

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

这道题是真你萌毒瘤啊 $qnq$ ,虽然就是很水的模拟而已

忽略上一句极富有素质的感慨 $qwq$

首先我们要知道一些坑点……不读题的伤你不懂……

$1.$ 一个单词可以用两遍……

$2.$ 在加长度的时候,减去的不是最大重复部分,而是最小重复部分

$3.$ 较为复杂的题往往需要良好的心态和码力,所以蒟蒻还需要练习哇!

嗯,我还是太菜了。

最后付个辣鸡源码(主要的函数),顺便以期日后能够写得更简练。

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

这个题不就是个最长上升子序列的裸题吗 $qwq$ , $nlogn$ 方法要好好打(背)。

求出一个子序列之后再乱搞贪心就好啊 $qwq$

贪心的时候就只需要对于每个导弹,我们都选择一个最小拦截高度的、但是可以拦截当前导弹的系统,如果没有可以拦截当前导弹的系统,系统个数就 $++$ 。

        …………………………                    
        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

这个题我当时不会做……嗯……留下了并没多好的印象 $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$ )

    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

这个题的数据范围怎么给的这么暴力哇??把数据范围再扩大个 $100$ 倍暴力不也跑得过吗 以下这个好像是一个不知道对不对的二分……希望有大佬能指出问题来 $qwq$

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

整理这个题的目的就是因为我老是忘记树的遍历是怎么回事……

中:左->根->右 先:根->左->右 后:左->右->根

那么在我们知道后序遍历之后,最后一个元素就是根节点;然后再在中序遍历中查询根节点,得到左右子树,再到后序遍历中查找两个子树的根节点,然后继续迭代即可。

$emmmm$ 好像这题水的很,不过我还要为我没有打好树的基础而埋单啊 $qnq$

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

为什么是广搜 $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

啊,这是道好题哇 $qwq$ . 首先很明确的是,青蛙每一步的状态总是由上一步的状态转移过来的,也就是说 $DP$ 方程是没什么思维难度的:

f[i]表示走到第 $i$ 单位长度时踩到石头的最小数量,那么有:

$f[i]=min$ { $f[i]-length+check[i]$ }, $s<=length<=t$

然鹅并不可做,因为 $l$ 实在是太大了, $O(n)$ 都会炸,所以考虑离散化。而离散化好像排序和取模都可以,在这里我选择了膜法 $qwqqq$


$p1057$ 传球游戏link

这个题考虑 $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

$emmmm$ 这应该可以算是一个很经典的区间 $DP$ ,那由于我的某篇 $zz$ 博客专门讲了,就挂个链吧。 区间 $DP$


$p1064$ 金明的预算方案link

这个题疑似是有依赖的背包问题,那么其实对于普通的这种有依赖的背包问题(无嵌套),我们是都可以转化成有多种情况的普通背包。 比如在这个题目中,我们就可以简化成有五种情况的01背包。即:

对于一个主件而言

1、不买;

2、买自己,也买自己的左儿子;

3、买自己,也买自己的右儿子;

4、只买自己;

5、买自己,左儿子买,右儿子也买;

而附件是没有任何选择权的(只能被选择),所以不枚举附件。


$p1075$ 质因数分解link

这道题其实没什么可整理的,就是个水题啊,但是让我至今也很记忆犹新的,是下面这份十分简练的 $rqy$ 在初三上学期写出来的代码:

   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

这个题本来不是很恶心,但是因为是个 $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

嗯,很棒啊,又是一道辣鸡橙题,然鹅当时我还是不会做 $OTZ$

他这个题很有良心的一点是让你后序遍历输出,那么很显然了哇,输出操作应该放在递归之后,也就是回溯的时候进行。那么在回溯的时候只需要在记录的左右区间内跑一遍就好。

好吧,当时不会的主要原因就是因为我对于树的遍历这部分掌握的太渣了 $qnq$


$p1088$ 火星人 link

这道题就是一个 $stl$ 的模板题……全排列直到 $m--$ 变成0为止……

那么在此,整理一下 $next$ $permutation()$ 的用法,这个函数是一个 $bool$ 型的,返回值的意义是是否还有下一个排列,与之相反的是 $prev$ $permutation()$ ,那么对于这两个函数:

$next$ _ $permutation()$ $bool$ 型 直接对原数组进行操作 所有排列的字典序是递增的

$prev$ _ $permutation()$ $bool$ 型 同上 $~~~~~~~~~~~~~~~~~~~~~~~~~$ 所有排列的字典序是递减的

$emmm$ 就这样吧


$p1115$ 最大子段和link

这个地方给出一个 $dp$ 做法。在求子段和的时候由于是由跨负数的,所以在我们的第一次循环之后,在第二次循环再进行一次反悔操作。当然同时也要保证最优性 $QWQ$ 。那么就可以得到如下程序段:

    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$