https://blog.csdn.net/qq_40907279/article/details/81265253 eps是浮点误差. 可以做什么？ 对于数字5，如果计算机存储的数据为5.000000000000001，显然对这种情况不需要用到eps进行补偿，而对于有缺省的类似于4.9999999999999998的数据，eps可以进行对它的缺省值进行一定的补偿，使其在计算机中的存储值变成5.00000000000000或者5.000000000000001，这样在后续的计算中就会解决因为存储的误差造成的不必要后果。 #define eps 1e-8  在某些卡精度的题中(四舍五入类,保留小...

题意：对一个给定的n，从1到n，他们的σ[n]中有几个是偶数。pi 是n的素数因子，ei 是对应素因子的个数。 分析：对所有的素数，如果p为2，则那一项一定为奇数，对于不是2的素数，可以发现当ei+1为奇数的时候(因式分解你就懂了)，即pi这个素因子出现偶数次时，那一项项也为奇数。 若使得那一整个式子为奇数，那么对于每一项只有两种方式，要么为2，要么p的为偶数次，再进一步思考，这完全可以通过n^2 和 2*n^2来得到所有满足的数。 #include<stdio.h> #include<math.h> #include<string.h> #include&...

题意： 给你两个数a，b，让你求出来a是否能够被b整除。 题解：大数取余 当一个数很大时，大到long long int类型都存放不了的时候，我们该怎么办呢？首先我们举个简单的例子来了解该算法的思想： 假设有一个数443，我们要求443%3，不妨拿起笔和纸和我一起演算一下。  #include <bits/stdc++.h> using namespace std; typedef long long ll; char a[30000]; ll b,s; int main() {  int t,cnt=0; scanf("%d", &t); while(...

拓展gcd详解传送门 思路：设时间为t，则两个青蛙的位置分别为(x+mt)mod L、(y+nt) mod L，相遇即是(x+mt)%L=(y+nt)%L，即(m-n)t+kL=y-x。 OK，现在已经符合ax+by=c的方程了，设a=m-n，b=L，c=y-x，然后套用模板求出特解t的值，注意t>0，所以要用通解公式得出最小正整数 解释<1> gcd 只对非负整数有意义，所以如果a<0等式两边要同时取负，a,c都要变成相反数；b本来就是正数，不用变也不能变。 解释<2> 利用exgcd，我们可以求解ax+by=g的一个解，然后 等式两边同乘c/g，得a* ...

每一组没告诉你读多少个，用stringstream。 然后对每一组gcd就行，没什么好说的。 #include<cstdio> #include<iostream> #include<sstream> #include<string> using namespace std; int num[100], n; string s; int gcd(int a, int b) {  return b ? gcd(b, a % b) : a; } int cal() {  int i, j, maxn = 0; for (i = 0; i < n...

1.注意怎么处理输入的数据 2.利用两个栈来实现运算 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3e6+7; const int mod = 1e9+7; char a[maxn]; stack <char> mystacka; stack <int> mystackb; int main() {  int n,cnt=2; scanf("%d", &n); getchar(); gets(a); int...

题目大意： 给你一个数x = b^p,求p的最大值 分析：x=p1^a1 * p2^a2 . . .pn^an x只有一个因子的p次幂构成 所以，本题所求实质上就是求 :a1,a2,a3,a4…an的最大公约数 本题有一个坑，就是x可能为负数，如果x为负数的话，x = b^q, q必须使奇数，所以将x转化为正数求得的解如果是偶数的话必须将其一直除2转化为奇数 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10; int pri[N]; bool vis[N]...

https://vjudge.net/contest/356798#problem/W 水题，但值得注意的点： 1.本题多组输入，多组输入可以通过打表、前缀和来节省查询时间。 2.memset()不可以初始化数组为非0值 3.int cnt[N]={1}只能使得 cnt[0]=1; #include <bits/stdc++.h> using namespace std; const int N = 1e4+10; int cnt[N]={ 1}; //这里仅仅是把cnt[0]设为1了  void init() {  for(int i=1; i<N; i++) {  int...

tag:通过设概率为未知数解题。 对 期望=概率*结果 更深理解 题意 n扇门，如两扇门每个分别为 +x +x，则可用 x+x 的时间出去，如为 −x−x，则可用 x+x 的时间回到原点。每次随机选一个，问出去的期望时间。 题解  由式子可以看出，当n负==n的时候，永远无法离开迷宫。 #include <bits/stdc++.h> using namespace std; int gcd(int a, int b) {  return b ? gcd(b,a%b) : a; } int main() {  int t,cnt=0; scanf("%d", &...

参考博客：https://www.cnblogs.com/daydayupacm/p/5788115.html 题意 现在有n个格子，每个格子上都有一定的黄金值；还有一个色子（1-6）。起始位置站在格子1上面，若每次投掷色子得到数x,x+i<=n（i表示现处位置的格子编号），则可以到达（x+i）格子上；反之，再进行一次投掷。问：到达标号为n的格子上面，得到黄金的期望值是多少？ 期望 一件不确定的事件有确定的所有结果，把第一种的结果值记为s1，它发生的概率记为p1，第二种结果值记为s2，它发生的概率为p2，… 第n种结果值记为sn，它发生的概率记为pn … 那么期望值 Ei= s1p1 +...

题目传送门 题目分析传送门 看完题目分析后，参考代码注解 #include <bits/stdc++.h> #define eps 1e-10 using namespace std; const int N=1e5+7; double dp[N]; void init() {  for(int i=2; i<N; i++) {  double num, ans; num=-1; ans=0; int nu=(int)sqrt(i); for(int j=1; j<=nu; j++) //从1开始的全部除数 {  if(i%j == 0) {  num++; ans+=...

题目解法新颖，值得拓展思维。 优化:将被捕概率转换为安全概率，即将被捕概率小于P的限制条件转换为安全概率大于等于1-P 题解：dp[i]的值是抢了i价值的安全概率，从V(全部都抢的价值总和)开始从大到小地去dp。以最大地安全概率来更新dp[i],最后从V开始从大到小查询dp[v]从而得到满足要求的最大的v。 dp中的贪心思维体现在了最大的安全概率以及最后的查询顺序。 #include <bits/stdc++.h> using namespace std; const int N = 1e5+7; double dp[N]; struct node {  int w; double...

思考引例： 2000年前后小浣熊干脆面风靡各大校园，每一包干脆面随机附赠一款水浒英雄卡，集齐108张卡即可换钱，请尝试使用数学工具解决集卡这个问题。    参考视频：https://www.bilibili.com/video/av59313918?from=search&seid=13802179280028317433

题目传送门：https://vjudge.net/contest/361424#problem/G 题意：给出一个n面色子，现在扔色子，知道所有面都出现一次，问掷色子次数的期望值。 题目解析：假设现在已经掷出了k个不同的面，再掷下一次的过程是一次伯努利实验，即X（首次掷出新面需要的投掷次数）服从参数p( 掷出新面的概率是(n-k) / n )的几何分布，因此E(X)=1/p。 k从0到n，把对应的期望累加起来就好了。 #include <bits/stdc++.h> #define eps 1e-10 using namespace std; const int N = 1e5+7...