ACM

http://codeforces.com/contest/625/problem/D 题意：问能否找到一个s，满足s+s的反转=k 思路：如果是回文数。。。那么显然满足。除以2就可以得到答案。 代码实现 1 如果不是回文数。。那么考虑进位的情况。 2 要么从后一位进1，要么从前一位退10回来。 3 需要特殊考虑1开头的。 4 5 6 7/* *********************************************** 8Author :111qqz 9Created Time :2016年02月07日 星期日 18时28分39秒 10File Name :code/cf/#342/D.cpp 11************************************************ */ 12 13#include <cstdio> 14#include <cstring> 15#include <iostream> 16#include <algorithm> 17#include <vector> 18#include <queue> 19#include <set> 20#include <map> 21#include <string> 22#include <cmath> 23#include <cstdlib> 24#include <ctime> 25#include <sstream> 26#define fst first 27#define sec second 28#define lson l,m,rt<<1 29#define rson m+1,r,rt<<1|1 30#define ms(a,x) memset(a,x,sizeof(a)) 31typedef long long LL; 32#define pi pair < int ,int > 33#define MP make_pair 34 35using namespace std; 36const double eps = 1E-8; 37const int dx4[4]={1,0,0,-1}; 38const int dy4[4]={0,-1,1,0}; 39const int inf = 0x3f3f3f3f; 40const int N=1E5+7; 41bool vis[N]; 42 43void pre() 44{ 45 ms(vis,false); 46 for ( int i = 10 ; i <12000 ; i++) 47 { 48 int vala = i ; 49 stringstream ss; 50 ss<<vala; 51 string tmp = ss.str(); 52 53 reverse(tmp.begin(),tmp.end()); 54 55 int valb; 56 sscanf(tmp.c_str(),"%d",&valb); 57// cout<<i<<" "<<vala+valb<<endl; 58 if (vala+valb<N) vis[vala+valb] = true; 59 60 } 61 62 for ( int i = 1 ; i < N ; i++) 63 { 64 if (vis[i]) cout<<i<<endl; 65 } 66} 67char ans[N],s[N]; 68int n; 69int sum[N]; 70 71bool ok() 72{ 73 // cout<<"n:"<<n<<endl; 74 for ( int i = 0 ; i < n/2 ;) 75 { 76 int l = i ; 77 int r = n-1-i; 78 if (sum[l]==sum[r]) i++; 79 else if (sum[l]==sum[r]+1||sum[l]==sum[r]+11) 80 { 81 sum[l]--; 82 sum[l+1]+=10; 83 } 84 else if (sum[l]==sum[r]+10) 85 { 86 sum[r-1]--; 87 sum[r]+=10; 88 89 } 90 else return false; 91 } 92 93 if (n%2==1) 94 { 95 if (sum[n/2]%2==1) return false; 96 if (sum[n/2]>18||sum[n/2]<0) return false; 97 ans[n/2] = char(sum[n/2]/2 +'0'); 98// cout<<"ASDHJKASD"<<endl; 99 } 100 for ( int i = 0 ; i < n/2 ; i++) 101 { 102 if (sum[i]<0||sum[i]>18) return false; 103 ans[i] =(sum[i]+1)/2+'0'; 104 ans[n-1-i] =sum[i]/2+'0'; 105 } 106 return ans[0]>'0'; 107} 108int main() 109{ 110 #ifndef ONLINE_JUDGE 111 freopen("code/in.txt","r",stdin); 112 #endif 113 114 //pre(); 115 // 116 117 scanf("%s",s); 118 n = strlen(s); 119 for ( int i = 0 ; i < n ; i++) sum[i] = s[i] - '0'; 120 if (ok()) 121 { 122 cout<<ans<<endl; 123// cout<<"aaa"<<endl; 124 return 0; 125 } 126 127 if (s[0]=='1'&&n>1) 128 { 129 for ( int i = 0 ; i < n ; i++) 130 sum[i] = s[i+1]-'0'; 131 sum[0]+=10; 132 n--; 133 if (ok()) 134 { 135 cout<<ans<<endl; 136 return 0; 137 } 138 else 139 puts("0"); 140 } 141 else puts("0"); 142 143 144 #ifndef ONLINE_JUDGE 145 fclose(stdin); 146 #endif 147 return 0; 148}

http://codeforces.com/problemset/problem/621/E # 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。 思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。

http://codeforces.com/contest/621/problem/D # 题意：给出12个式子，问哪个最大。 思路：主要记住两个。一个是比较指数形式的数一个常用办法是取对数，同时要考虑是否能取对数，分情况讨论对于不能取对数的情况经过变换去取对数。第二个是取了两次对数后比较时候的最大值可能是小于0的。所以初始时置于0不够小。官方题解说得很清楚。

http://codeforces.com/contest/625/problem/C 题意：构造一个矩阵。。满足三个条件。。。 思路：简单构造。。。看代码把。。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月07日 星期日 17时49分15秒 4File Name :code/cf/#342/C.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=5E2+7; 34 35int n; 36int k; 37int ans[N][N]; 38int main() 39{ 40 #ifndef ONLINE_JUDGE 41 freopen("code/in.txt","r",stdin); 42 #endif 43 44 cin>>n>>k; 45 int cnt = 0; 46 ms(ans,0); 47 for ( int i = 1 ; i <= n ; i++) 48 for ( int j = 1 ; j <= k-1 ; j++) 49 { 50 cnt++; 51 ans[i][j] = cnt; 52 } 53 for ( int i = 1 ; i <= n ;i++) 54 for ( int j = k ; j <=n ;j++) 55 { 56 cnt++; 57 ans[i][j]=cnt; 58 } 59 int sum = 0 ; 60// cout<<"k:"<<k<<endl; 61 for ( int i = 1 ; i <= n ; i++) 62 { 63 sum +=ans[i][k]; 64 65 // cout<<"sum:"<<sum<<endl; 66 } 67 68 cout<<sum<<endl; 69 for ( int i = 1 ; i <= n ; i++) 70 { 71 for ( int j = 1 ; j <= n-1 ; j++) 72 { 73 printf("%d ",ans[i][j]); 74 } 75 printf("%d\n",ans[i][n]); 76 } 77 78 #ifndef ONLINE_JUDGE 79 fclose(stdin); 80 #endif 81 return 0; 82}

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放进去。 观察答案，可以这样理解（我是用样例推出公式后理解。。。数学差的人心好累）：如果i为最大值，那么n次每次必须投掷出1..i的点数，概率为 (i/m)^n，但是要至少有一个投掷成i，也就是要减去所有的数都是1..i-1中的情况（概率 为((i-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. Note, that if Wet Shark uses no integers from the n integers, the sum is an even integer 0.

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. Wet Shark thinks that two bishops attack each other if they share the same diagonal. Note, that this is the only criteria, so two bishops may attack each other (according to Wet Shark) even if there is another bishop located between them. Now Wet Shark wants to count the number of pairs of bishops that attack each other.

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. Each shark will grow some number of flowers s__i. For i-th shark value s__i is random integer equiprobably chosen in range from _l__i_to r__i. Wet Shark has it’s favourite prime number p, and he really likes it! If for any pair of neighbouring sharks i and j the product s__i·s__j is divisible by p, then Wet Shark becomes happy and gives 1000 dollars to each of these sharks.

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 ************************************************ */ #include #include #include #include #include #include #include #include #include #include #include #include #define fst first #define sec second #define lson l,m,rt«1 #define rson m+1,r,rt«1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair

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…