题目链接：lightoj1317 这个题一开始还以为我读简单了，结果读了好多遍……确定了是个水题 题意：N个人，M个框，无数个球，每个人进球的概率一样均为p，每次每个人都投一次球称为一轮，问k轮后进了多少个球 很简单啊：题目假定了投向同一个篮筐的球不干扰，那么每轮每个人投了一个，总共投了k*N个球 每个球进球的概率都是p，那么根据加法原理有：答案为k*N*p 不知道题目在描述些啥……可能是刻意干扰吧 int t,n,m,k; double p; int main(){ //input; scanf("%d",&t); for(int C...

题目链接：lightoj 1321 题意：从0到n-1需要传输s个包，传输的时候每条边安全到达的概率为pi，每次传输的时间为2K，如果在传输时候没有安全到达，则要重新传送，求最小的传送时间 这个题，跟概率相关的地方在于推公式 首先，s个包和传输时间2K都是可以放在最后处理的，因为都是独立的，满足加法原理，最后乘进去答案里面就好了 那么，来分析每个边和点传输成功的概率 传输成功的期望时间=传输一次成功的概率*传输一次成功的时间+传输两次成功的概率*传输两次成功的时间+…… 即T=p*2K+p（1-p）*4K+p（1-p）（1-p）*6K…… 即T=2pK【1+2（1-p）+3（...

最近练习概率DP和计算的还是有用的啊，知道经典思路是什么了 题目链接：HDOJ5781 说说题意吧：有一本存折，忘记了有多少钱，只记得钱数不超过K 现在有M次猜测的机会，必须要确定存折中有多少钱！ 确定一个词，理解好了，这个题就好了。这样理解确定： 如果现在钱数不超过T，取一块钱都取不出来了，那么就确定存折里面没有钱了 如果现在钱数为1，取1块钱取出来了，那么就确定存折里面没有钱了（因为所有钱都已经取出来了） 确定一词，是用来确定边界情况的 所以，这个题的方法就是枚举：枚举所有的可能猜测的值（从1枚举到K），当然，有的取得出来，有的取不出来 日常概率的经典做法就是分类...

这波黑windows黑得很好我给满分，题目链接：HDOJ5802 看到两个数字的题，而且p，q都很大，不超过1e9，很明显数学题，先找规律，要么是公式，要么是打表，要么是贪心之类的算法 题意：p和q两个数，要求用最小步数从p走到q 如果选择减少，那么第一个单位时间减少1，如果前一个单位时间减少的是x，那么该单位时间减少2*x（相当于连击） 如果选择增加，那么每个单位时间增加1 如果选择休息，那么没有变化、 增加和休息对于减少来说都是打破连击 这样读完题，有一个很坑的边界条件，估计是比赛的时候很多队伍没有注意到的细节： 最大值无限，最小值不小于0 那么意味着什么呢？...

A题 水题防止爆零的，不解释了，比较大小的水题 B题 B题是一个数学容斥题，因为数据量比较大，需要用前缀和+容斥的思想来做 题意：n个点，1，2,3,4，……n初始化的时候成环形连边，也就是1-2,2-3,3-4……，n-1 然后，有k个重要城市，每个重要城市与其他所有城市都有一条边 任意两个城市之中，最多有一条边相连 每个点有自己的价值ci，每条边的价值是所连两个点i，j的价值乘积ci*cj 如何容斥？ 特殊情况：相邻的！记得特判 如何减小时间复杂度：利用前缀和：两个前缀和 第一个前缀和，是所有的ci之和，需要算进来，每当有一个重要城市的时候，先把重要城市的价值...

题目链接：HDOJ 5791 看上去就肯定是一个DP的，为什么？ 数据量啊，n和m都是1000，那么dp【i】【j】很好定：a串的前i个和b串的前j个的子串匹配值 那么dp【n】【m】为答案咯 接下来就稍微的吐槽一下题解：（水题）好吧 毕竟还是自己弱了，这个状态转移得考虑到容斥原理 dp【i】【j】肯定是与dp【i-1】【j-1】，dp【i】【j-1】和dp【i-1】【j】有关 当a【i】！=b【j】时， 那么匹配数值应该就是以前的，dp【i-1】【j】+dp【i】【j-1】 但是，这两个部分是有公共部分的，想想怎么来的，交集是dp【i-1】【j-1】 当a【i】==b...

题目链接：POJ1990 真的要下定决心来学习线段树和树状数组了，每次补题看到的题解都是基本题，水题，树状数组维护一下 不知道该吐槽自己弱，还是吐槽题解 题意：给n头牛的声调和位置，任意两头牛的交流花费值是距离*max（v【i】，v【j】） 求所有牛对的交流值之和 不可能暴力解的，那么需要高效的维护值，就得用数据结构来做 维护什么？维护位置，维护声调（不要觉得我废话） 方法1：按照v值升序排序（那么，不需要判断v【i】和v【j】的大小了，后插入的就是需要乘的值） 那么，需要快速求：对于牛i来说，x位置比i小的个数，以及这个牛前面的位置之和，这个牛后面的位置之和（输入...

给出一个序列求满足1<=a<b<=n，1<=c<d<=n，Aa<Ab，Ac>Ad的四元组个数 题目中强调了四元组哦，题目链接：HDOJ5792 先不说这个题，这个题的子问题：1<=c<d<=n，Ac>Ad是什么题？ 求逆序对，是吧，所以，这个题就是用树状数组来维护区间中比自己大，比自己小的数，对吧 还需要离散化对吧，因为数字太大了，我们只需要他们的相对大小就好了 逆序对的题目链接：POJ2299 题解在这：逆序对题解 所以呢，这个题：树状数组+离散化是基本思路 需要维护什么呢？四个值： 当前数的左...

每次做题就是太浮躁，注意不到各种细节！HDOJ1494 题意是中文的，所以读得太快，没有注意这么一句话： 加速卡的获得机制是：普通行驶的情况下，每通过1段赛道,可以获得20%的能量(N2O). 注意是普通行驶的情况下！所以，如果理解成普通行驶和加速行驶都会获得能量呢，就会导致一个地方的状态转移不对 20%可以理解成5次普通行驶之后会有1个加速器，转换成整数来计算 那么当普通行驶次数==14的时候 当理解对了题意的时候，是应该选择的，要么加速，要么普通行驶 但是，当我理解错了题意，任何行驶状态都是会获得能量了，那么一定得加速（不然就浪费一个加速器了对吧） 就是这个细节wa了一天 ...

2015年上海大都会的一个概率dp题，当时，不会，现在，开了专题，然后再来补题 有了不一样的感觉了，题海战术，还是有那么点感觉的。题目链接：HDOJ5236 概率dp，无非就是算期望或者递推求值，对吧 题意确实有点纠结，得读好久： 一篇文章n个字符，每次输入有一定的概率p输错（那么这个字符就是需要重新输入的），每到第i秒可以选择按下x个键存盘，那么之前的都不会丢失 求这篇文章完成的时间期望 很明显的递推公式，对吧（先不考虑保存的问题，先把文章打完） 设dp【i】为输入完前i个字符的时间期望 那么，由两部分组成： 第一部分：dp【i-1】为输入完前i-1个字符的时间期望...

题目链接：POJ2425 这个题典型的博弈题，每个节点给你提供了不同的状态转移，然后问你胜负关系 提供的是记忆化搜索的打表代码 #include<cstdio> #include<vector> #include<iostream> #include<cstdlib> #include<cstring> using namespace std; const int maxn=1e3+10; vector<int> a[maxn]; int n,m,sg[maxn],ans; int getsg(int x)...

题目链接：HDOJ 5795 就是因为这个题的题解（水题），逼着自己学SG函数，学打表，废话不多说 状态转移很简单，要么把一堆分成三堆，要么把一堆取任意个石子走（不能不取），所以可以提前打表找好规律 取任意个石子（不能不取），那么剩下的就是0，1，2……，x-1个 那么有sg【x】=mex（sg【0】，sg【1】……，sg【x-1】），这是第一部分 分成三堆，枚举i，j，k使得i+j+k==x 那么有sg【x】=mex（sg【i】^sg【j】^sg【k】），这是第二部分 然后，根据定义，就可以得到sg【x】的值 找到规律之后，异或就好了，代码如下： #include...

题目链接：HDOJ3032 跟HDOJ 5795没有本质区别吧，一个是两堆，一个是三堆，本质是一样的 HDOJ5795题解 代码如下： #include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; int t,n; int sg[maxn]; int ans,num; int g(int x){ int mex[maxn/100]; if (sg[x]!=-1) return sg[x]; memset(mex,0,sizeof(mex)); for(int i=0;i<...

题目链接：HDOJ1848 题目的状态转移给定是Fibonnacci的前几个数，需要提前打表计算 然后求SG（x），只需要去计算SG（x-1），SG（x-2）……SG（x-Fk），其中Fk是min【x，题中可能的最大Fibonacci】 代码如下： #include<bits/stdc++.h> using namespace std; const int N=1050; int sg[N]; int f[N]; int g(int x){ int mex[1010]; memset(mex,0,sizeof(mex)); if (sg[x]!=-1) ...