水蓝(蒟蒻ACMer) 的博客

Thinking will not overcome fear but action will.

关于约瑟夫环递推式的一些思考

题目大意： N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。（其实这是一段非常悲惨的历史故事的改编，愿世界永无战争，虽然这是个幻想）具体思路：暴力的方法就不讨论了，我想从递推这个角度考虑（万物皆可递推）假设我们知道x个人，每次报数k个...

Posted by 水蓝(蒟蒻ACMer) 的博客 on January 16, 2021

HDU6351 BeautifulNow

计算当前序列从有序序列经多少了次交换

题目大意：给你一个数，你可以交换这个数任意两位，可以交换k次。但是不能出现前导0。求经过k次操作可以形成的最大值和最小值。这个数小于20位。解题思路: 首先，需要先解决这样一个问题：给定一个原序列，再给出它经过几次变换的序列，能不能求出，原序列最少经过了几次交换，成为了新的序列。不妨假设原序列的为 1，2，3….n。(如果是其他情况，完全可以建一个下标数组b，让它记录这一位现在是原来...

Posted by BY 水蓝 on January 15, 2021

Paths on a Grid

一种求单个组合数的方法

题目大意给你一个n*m的矩阵，最开始在左上角，只能向下或者向右，求，从左上走到右下的所有路线的方案数。点击进入原题地址不难发现，需要走n+m步，然后从n+m中挑出n个走下，即答案就是但是！本题的询问较多，且差距较大，是无法通过递推得到的。所以就要利用一种求单个组合数的方法。思路的本质是所以我们把它当成k个分数乘起来就好了。（分子分母分别乘可能会爆longlong）...

Posted by BY 水蓝 on January 15, 2020

【洛谷】P1156 垃圾陷阱解题报告

【洛谷】P1156 垃圾陷阱解题报告题目描述卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D(2 \le D \le 100)D(2≤D≤100)英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放，并且堆放垃圾不用...

Posted by BY 水蓝 on September 4, 2019