题意： 给你一个迷宫，求出从A到B最少需要多少次90度转弯。 思路： 这题和普通迷宫的区别在于：普通迷宫求的是最少走的步数，而这题要我们求的是最少的转弯数，这就导致了dfs的方式对于这题是优于bfs的，因为dfs的状态记录更加方便，而bfs还得专门开数组来记录方向和判重。 既然确定了解法，就可以开干了ヾ(•ω•`)o首先是读入，没啥好说的，顺带记录一下A和B就行了。这里我采用了雨巨教的一个数记录两个坐标的方法，还是挺方便的,省得用pair。 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { int ...

题目描述： 3元买一张彩票，买一张彩票得到1，2，3，4元的概率相等。问买n次，不亏的概率多少，输出最简分数形式。 思路： 由题意我们得，这一次买彩票新出现的情况是由上次买彩票的情况分别加上1，2，3，4元得到的。于是我们可以想到使用DP来解决这道题目，状态转移方程是： f[i][j]+=f[i-1][j-k];其中，i 代表当前是第 i 次买彩票，j代表这次买完之后的钱数，k代表这次得到的钱。于是，我们对彩票数由 1 ~ n 遍历，j由 0 ~ i*4 遍历，k由1到4遍历，然后把所有第n次得钱不亏的加起来，就组成了我们结果的分子。而分母很好求，就是4的n次方。 for(int i=1;i...

题目描述： 你是一个牧场主，你放牛吃草后，有出去砍树了。当你回来的时候，你发现你的牛在吃你心爱的小花，为了防止你的小花被吃，你只能把这些可恶的牛赶回他们的窝。。。但是你只有一个人，所以一次只能赶回一只牛，在你赶它们回去的时候，他们还在持续的吃草，而且根据牛个体的不同，赶回他们所需要的时间 t[i]*2 和它们在没有被赶的时候的吃草的速度也不同，所以你要想出一个赶牛的顺序，使得你的小花损失的最少。 题解： 我们可以发现，当我们更换赶回去的两头牛的顺序的时候，当他们本来就是一前一后被赶回去时，他们产生的效果不会影响别的牛，只会对总小花产生影响。 因此我们只要找出“先赶回去的牛”和“后赶回去的牛”满...

题目描述 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 题解： 题目没有给数据范围。。。实测1e5+10能过。 由于是 1~n 的一个排列，所以不用担心数字重复的问题。而且，由于是连续子序列，所以满足答案的序列必须是包含数字 b 的左右区间。 由于是求中位数，所以除了 b 以外的数的具体大小并不重要，重要的是该数比 b 大还是比 b 小。我们用 a[i] = -1 代表该数比 b 小，用 a[i] =1 代表该数比 b 大。 连续区间，很容易让人联想到前缀和。在这题中，我们使用前缀和来表示从当前数到 b 的区...

题目梗概： 搁你面前有十二道题，你们小队有 a[i] 的概率做出来第 i 题，如果做不出来，你分别还有 b[i] 和 c[i] 的概率从你旁边那俩讨论声音贼大的队伍口中听懂怎么做 （我怀疑他们是在装逼。。(╬▔皿▔)╯），最后要你输出从 一道都不会到全都会做的总共十三种情况的概率。 解题思路： 很明显，因为题目之间做不做的出来没有相互影响，所以每道题做出来的概率是独立的，我们设每道题做出来的概率是 p[i] ,而做不出来的概率是 up[i]，由于直接只算 p[i] 的情况较多，不便计算，所以我们先计算做不对的情况，就是 up[i]=(1-a[i])*(1-b[i])*(1-c[i])(很显...

题目简述： 在一个一维数组中，存放着'0'、'1'、'2'、'*'、'?'这几个字符，数字代表他左右两边存在'*'的个数，'*'的左右两边可以是数字或者'*'，而'?'代表这个地方的东西不确定是什么。题目问的是总共可能的情况有多少种，显而易见，不同的情况是由'?'所在的位置产生的。要我们输出所有的情况数，答案对1e9+7取模。 解决方案： 我们采用动态规划来解决这题。 首先是状态表示方程，我们用三维数组f[i][1/0][1/0]来表示方案数，第一个参数代表的是第i个格子，后面两个格子代表了当前格子和下一个格子的状态，一个f[i]有四种状态，代表了这个格子和下一个格子含有和不含有地雷的情况（...

题解： 首先，我们把问题拆分。假设这是一道不那么复杂，数据普通的子序列问题。 则对于一个数，结果中所有包含它的序列都是从前面的序列中继承过来的。那么到这个数为止，它能产生的新的序列就是1+它之前所有比较结果成立的序列数如果用 f[i] 来记录第i个数产生的新序列，那么转换方程就是1+sum{1,i-1}f[i]。 解决了状态转移方程的问题，接下来就是怎么把比较时的 a[i]^j 和 a[j]^i 实现的问题。 而对于这种指数问题，我们通常可以想到的方法就是取对数，于是我们将它们取以10为底的对数，化简就可以得到： j*log10(a[i]) 和 i*log10(a[j]) ,那为了不每次比...

华华给月月准备的礼物 题目：原题链接 题解： 这是一道纯血的二分搜索题。题目中要求切出k根等长木棍，输出可能的最大长度。于是我们可以使用二分遍历所有可能的木棍长度，判断当前长度是否满足来缩减范围。由于最大的可能长度为1e9，所以时间复杂度并不是很高，加上遍历判断的过程，复杂度只有O(nlogn).其余的介绍在代码中以注释的形式给出。 拓展 附上两种常用滴二分模板： int search(int l,int r){ while(l<r){ int mid=l+r>>1; if(check(mid)) l=...

2020/6/30 以后这边就是我写日记的地方了。我认识到了数学好对计算机学习的重要性。容易获得的兴奋是虚无的，通过自己努力获得的成功是宝贵的。

#include<iostream> using namespace std; typedef long long LL; LL Pow(LL a,LL b,LL p){     a%=p;     LL res=1;     while(b){         if(b&1){             res=(res*a)%p;             res%=p;         }             a=(a*a)%p;         b>>=1;     }     return res; } int main(){     LL a,b,p...