首页 > 其他分享 >洛谷355BAJ-Bytecomputer8

洛谷355BAJ-Bytecomputer8

时间:2023-10-07 17:44:27浏览次数:48  
标签:洛谷 数列 证明 Bytecomputer8 操作 355BAJ

这一道题如果直接做是没有什么思路的,所以我们合理猜测应该是有什么结论

看这个数列最开始就只有三个值,所以我们猜测最后也只有这三个值

下面是证明

首先第一个数最小是-1,所以所有数的下界是-1

其次如果存在某一个数大于1,我们找到这个数列最前面的这个数,那他前面的数肯定是1,然后对相同的操作我们把这个数只加到1是只优不劣的,不然后面的数都得大于1,显然加多了(好吧这里的证明很模糊,我觉得一点也不显然,谁能严谨地证明?)

然后证明完了

然后证明操作一定是从前往后的(这样才符合DP的无后效性)

某一个数操作了多次,分情况讨论即可

标签:洛谷,数列,证明,Bytecomputer8,操作,355BAJ
From: https://www.cnblogs.com/dingxingdi/p/17747057.html

相关文章

  • holiday 假期题解(洛谷搬家)
    P5892holiday假期题解前言:如果您想要过这一道题,需要的前置条件:知道什么是决策单调性。知道可持久化线段树怎么找前$k$大。有耐心看很多文字。对于第二点,如果您不会的话,可以参考我的学习笔记(专门为过这道题做的)。链接:https://i.cnblogs.com/posts/edit;postId=1769732......
  • 【洛谷 P1739】表达式括号匹配 题解(栈)
    表达式括号匹配题目描述假设一个表达式有英文字母(小写)、运算符(+、-、*、/)和左右小(圆)括号构成,以@作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则输出YES;否则输出NO。表达式长度小于,左圆括号少于个。输入格式一行:表达式。输出格式一行:YES或NO......
  • 【题解】洛谷#P7073 [CSP-J2020] 表达式
    【题解】洛谷#P7073[CSP-J2020]表达式Description给定一个逻辑表达式和其中每一个操作数的初始取值后,再取反某一个操作数的值时,求出原表达式的值。表达式将采用后缀表达式的方式输入。Solution根据题目可得,当取反一个操作数的值时,整个表达式大体只有变与不变两种情况,而往下......
  • 关于洛谷题解审核
    我想问一下,大家觉得题解的重点是什么?很显然是思路,代码的正确性,次要的才是格式。但是,洛谷对于题解格式的审核是不是有点过于严格了呢?比如说这段话:如果\(n\)为\(0\),那么便是无解。大家能一眼看出,后面多了空格吗?这种题解其实没什么大问题,别人看题解时根本不会在意这些......
  • 洛谷 P7830 [CCO2021] Through Another Maze Darkly
    洛谷传送门被联考创出shit了。考虑一种极限情况:每个点指向父亲。那么这种情况我们会顺着欧拉序完整地把整棵树都走一遍。但是初始的时候不一定每个点都指向父亲。发现我们走过\(O(n^2)\)步就能到达上面的极限情况。比较显然,因为每次扩展至少使一个点从不指向父亲变成指向父......
  • 洛谷5324 删数
    首先给出结论:对于一个数列,某一个数字\(i\)的个数有\(cnt[i]\)个,那么此数字可以覆盖一个区间\([i-cnt[i]+1,i]\),遍历每一个数字并记录每个区间,最后答案就是没有被覆盖到的数字的个数证明:任意修改一个数字,会使一个\(cnt\)减一(这至多会产生一个没有被覆盖的数),另一个\(cnt\)加一(这至......
  • 洛谷 Power Tree 题解
    题目链接PowerTree分析将叶子节点按dfs序重标号后,每次控制操作可以转化为将子树内叶子节点所在区间加(或减)一个数不难可以想到将叶子区间进行差分每次对\(l\)到\(r\)的操作可以转化为将\(l\)上的数转移到\(r+1\)上每次操作后差分数组的和不变将所有点权变为\(0\)......
  • 洛谷P5303
    这一道题跟NOIP集训模拟赛1的D题非常像,当然D题的递推方程更复杂(磁盘里面有题解pdf)对于这一道题,我们设f[i][0]表示铺了i列而且全部用的完整的砖的方案数f[i][1]表示铺了i列,但是第i列缺了一个而且第i列的唯一的那一块砖头就是1X1其中一个f[i][2]表示铺了i列,但是第i列缺了一个而且......
  • 【题解】洛谷 P1003 [NOIP2011 提高组] 铺地毯
    原题链接解题思路如果直接按照题意开一个二维数组来模拟每个点最上面的地毯编号,会发现所占空间最坏情况下约为(2*105)2*4B=4*1010*4B=1.6*1011B≈149GB,程序完全无法运行。但实际上没有必要将每一个点的信息记录下来,只需要记录每一块地毯能覆盖哪些点,再依次判断哪那些地毯可以......
  • 洛谷5343总结
    这题我们很容易想出一个状态,设f[i][j]表示前i个长度划分长度为j的块的总方案然后我们自信的写出\(f[i][j]=f[i-1][j]+f[i][j-a[i]]\)但这其实是错的!这跟背包很想,+f[i][j-a[i]]这一项的本质是说这个长度为j的块的最后一段的长度是a[i],但其实最后一段的长度是不定的,所以我们可以写......