Posts

http://codeforces.com/contest/625/problem/C 题意：构造一个矩阵。。满足三个条件。。。 思路：简单构造。。。看代码把。。。。

http://codeforces.com/contest/625/problem/B 题意：给出两个字符串，问要替换掉多少个字符才能使得前者中不包含后者。 思路：直接搞…找到一个把收尾替换成‘#’，然后下次从该位置继续开始找，直到找不到。

http://codeforces.com/contest/625/problem/A 题意：有n块钱，塑料瓶饮料a元一瓶，玻璃瓶饮料b元一瓶，退还玻璃瓶可以得到c元。问最多能买多少瓶饮料。 思路：贪心。如果塑料瓶比玻璃瓶的实际价格便宜，那么一定买塑料瓶的，否则先买玻璃瓶，再用塑料瓶填。注意一些边界的判断。。

http://codeforces.com/problemset/problem/148/D # 题意：盒子里有w只白老鼠，b只黑老鼠，公主和魔王轮流取（公主先），先取到白老鼠的人获胜。魔王每次取完以后，盒子中的老鼠会因为吓尿了跑掉一只，跑掉的老鼠不算任何人取的。问公主获胜的概率。

http://codeforces.com/problemset/problem/107/B 题意：有m个部门，每个部分s[i]个人，HW在第h部门，现在要从这m个部门中挑选包括HW在内的n个人去参加比赛，问被挑选的人中有HW的队友（同部门的人）的概率是多少。如果m个部分的人数不够组成n人的球队，输出-1. # 思路：考虑一般情况。至少有一个队友的情况较多，应该从反面考虑，即没有一个队友的情况。选完HW以后面临的状态是：事件总数为从total(m个部门的人员之和)-1个人中选n-1个的方案数，包含的事件数目为从a(a=total-s[h])中选n-1个人包含的方案数。 可以看出分母相同，可以约掉。 # 然后对于边界情况，首先判断total是否比n小。然后，如果a<n-1，表示除去HW所在的h部分之外的人不可能组成n-1个人，也就是一定要选择HW的队友，概率为1.

http://codeforces.com/problemset/problem/518/D 题意：有n个人排队上一个电梯。。。在某一秒内，队首的人有p的概率上电梯，1-p的概率不动。每个人只有在队首的位置才可以上电梯（也就是每一秒内，最多只有一个人可以上电梯）。电梯无线长（也就是上了电梯就不会离开了），问在第t秒的时候，电梯上的人的个数的数学期望是多少。 # 思路：一开始推公式的我还是图样。这题是dp.其实也不难想。dp[i][j]表示第i秒时电梯上有j个人的概率。 当j==n的时候，也就是所以人都上了电梯以后。dp[i+1][j]+=dp[i][j]，对于其他时刻 dp[i+1][j+1]+=dp[i][j]p,dp[i+1][j]+=dp[i][j](1-p). 初始化dp[0][0]=1，即0时刻电梯上有0个人的概率为1. # 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月02日 星期二 15时57分06秒 4File Name :code/cf/518D.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E3+7; 34int n,t; 35double p; 36double dp[N][N]; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 ms(dp,0); 43 dp[0][0] = 1; 44 cin>>n>>p>>t; 45 for ( int i = 0 ; i <= t ; i++) 46 { 47 for ( int j = 0 ; j <= n ; j++) 48 { 49 if (j==n) 50 { 51 dp[i+1][j]+=dp[i][j]; 52 } 53 else 54 { 55 dp[i+1][j+1]+=dp[i][j]*p; 56 dp[i+1][j]+=dp[i][j]*(1-p); 57 } 58 } 59 } 60 double ans = 0 ; 61 for ( int j = 1 ; j <= n ; j++) 62 ans +=j*dp[t][j]; 63 64 printf("%.12f\n",ans); 65 66 #ifndef ONLINE_JUDGE 67 fclose(stdin); 68 #endif 69 return 0; 70}

http://codeforces.com/problemset/problem/312/B # 题意：两个人比赛射箭，先射的人射中的概率是a/b，后射的人射中的概率是c/d，问先射的人赢的概率。 思路：应该叫条件概率。。。？ 不过我们可以用古典概型的思维想。每射一次看成一个点，射中的点用白色表示，没有射中的用黑色表示。如果两个人第i次都没有射中，那么就要继续第i+1 轮，而第i+1轮和之前的每一轮是独立的。等于重复这个过程。所以古典概型的样本总量应该减去宝石两个人都没有射中的点的个数，为bd-(b-a)(d-c)，整理为bc+ad-a*c，设为n.要想第一个人赢，那么对于某一次，只要不是第一个人没射中，第二个人射中这种情况，就都是第一个人赢。而第一个人没射中的事件数为b-a，第二个人射中的事件数为c，总数为（b-a）*c，所以答案为(n-(b-a)*c)/n

http://codeforces.com/problemset/problem/453/A 题意：m面骰子，每面点数出现的概率相同，连续投掷n次，问出现的最大值的数学期望。 思路：手写样例。。。发现答案为 。。。记得把（1/m）^n放进去。

http://codeforces.com/problemset/problem/476/B 题意：给出两个长度相等-且不超过10的字符串，串1只包含‘-’,’+‘。按照‘+’为1，‘-’为-1累加可以得到一个值。串2还包含若干‘？’，代表该处的值不确定，且为’+‘和’-‘的概率相等，都是0.5.问串2的值和串1相等的概率。 思路：我们可以扫一遍得到‘？’的个数和两个式子的差值。设问号个数为a，差值为b，那么在a个问号中需要有(a-b)/2个为‘+’（容易知道，a,b一定奇偶性相同，所以a-b一定能被2整除），根据超几何分布，概率为 c[a][(a-b)/2]*(1/2)^a; 写的时候可以先打个组合数的表。1A，开心。

http://codeforces.com/contest/621/problem/A A. Wet Shark and Odd and Even time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Today, Wet Shark is given n integers. Using any of these integers no more than once, Wet Shark wants to get maximum possible even (divisible by 2) sum. Please, calculate this value for Wet Shark.

http://codeforces.com/contest/621/problem/B B. Wet Shark and Bishops time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Today, Wet Shark is given n bishops on a 1000 by 1000 grid. Both rows and columns of the grid are numbered from 1 to 1000. Rows are numbered from top to bottom, while columns are numbered from left to right.

http://codeforces.com/contest/621/problem/C C. Wet Shark and Flowers time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output There are n sharks who grow flowers for Wet Shark. They are all sitting around the table, such that sharks i and i + 1 are neighbours for all i from 1 to n - 1. Sharks n and 1 are neighbours too.

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1857 题意：计算最大的n，满足n!/* *********************************************** Author :111qqz Created Time :2016年01月29日 星期五 19时49分25秒 File Name :code/uva/10916.cpp ************************************************ */

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=43 题意：其实就是给了两个式子。。。(N+1)^h=a,N^h=b,a,b已知，然后求关于N的两个式子.。。 思路：数学上这个方程貌似不可解。。？ 所以只能枚举一下==。。。注意精度问题把。。。

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=787 题意：从x增加到y，第一步和最后一步步长只能是1，其他步一定可以是上一步减一，和上一步相等，或者上一步步长加一，三种情况，且步长恒为正。问从x到y最少需要的步数。

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=966 题意：?1?2?3?4…?n=k，把每个？替换成+或者-，找到最小的n使得式子成立。 题意：这道题最关键的一点是。如果s1=1+2+3+.,x+..+n>=k (所有数取正数），那么一定有s2=1+2+3+..-x+..+n=k

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=49 题意：求p开n次方。保证结果为整数。 思路：p最大10的101次方。。。double最大10的308次方。。因为肯定是整数。。不存在精度问题。。所以可以用double水过QAQ…

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1726 题意：给出26个大写字母的权值，要求构造一个长度为n（n不超过210）的字符串。并且满足奇数位置只能放元音字母，偶数位置只能放辅音字母，且每个元音字母最多放21次，每个辅音字母最多放5次，要求构造的字符串的权值之和最小，在权值最小的前提下字典序最小。

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1135 题意：给出球队的名字和比赛的信息，得出standing 思路：字符串处理。需要注意的是多组数据记得初始化多次，以及比较字典序的时候team name是大小写不敏感的。

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=92 题意：给出一段文字，包含若干个单词，以’#‘结束。按照字典序输出所有的ananagrams。所谓ananagram，是指经过任意的重排后，不能得到这段文字中的另一个单词（不区分大小写） 思路：首先是字符串的读入…可以整行读入然后用空格分隔单词。由于补区分大小写，所以要都转化成小写…但是输出的时候要输出原始，所以还记得保留一份。而且要能够通过新的找到原始的（我用了一个toori的map<string,string>来实现） 然后最关键的部分是如何判断两个单词经过重排是否能一样…