hdu 1204糖果大战

题意：A有n个糖果，B有m个糖果，他们玩24点游戏，A能解答出来的概率是p，B能解答出来的概率是q，如果都解答出来或都没解答出来就平局，否则如果A解答出来了，B给A一颗糖，否则A给B一颗糖，某一方糖全部给光结束。求A赢的概率。 下面记pa = p(1-q)为A赢的概率，pb = q(1-p)为B赢的 ...
2019-11-06

poj 2096概率dp

大意：每个bug有两种属性N和S。N有n种可能取值，S有s种可能取值。bug的属性的分布是等概率的。一个人一天找一个bug，问他找到的bug中有所有属性的期望天数（不需要取遍所有组合，有就行了）。 由于每种属性是等价的，因此状态可以定义为两个属性各自取到的数量。 设dp[i][j]为遇到了i种N属性 ...
2019-11-06

luogu 2371墨墨的等式

数论转图论神仙题。 题意可以理解为，有n个物品，第i个物品价值为a[i]，每个物品能使用任意次，求在区间[B_min, B_max]中能凑出多少中价值。其中n <= 12, 0 <= a[i] <= 5e5, 1 <= B_min <= B_max <= 1e12 ...
2019-11-06

bzoj 2705 Longge的问题

求 其中0<N<=2^32 看起来是莫比乌斯反演，其实不是。。。。。。 化一波式子先 然后别化了（手动喷血 后面那个求和号不就是欧拉函数的定义么（手动喷血 然后变成了求 什么？枚举因子个数和求欧拉函数都是的，所以总的是O(N)？ 注意到这里要求的都是N的因子的欧拉函数的值，因此可以对 ...
2019-11-05

bzoj1257 数论分块

求 其中1 <= n <= 1e9, 1 <= k <= 1e9 把取模拆开 注意到总共有O(sqrt(k))种取值，可以数论分块。 代码： #include <iostream> using namespace std; typedef long long ...
2019-11-05

bzoj 2813 奇妙的Fibonacci

题意：设f为fibonacci数列，询问使得f[j]能整除f[i]的j的个数以及j^2的和。3e6个询问，1 <= i <= 1e7 由定义，f[1] = f[2] = 1，f[i] = f[i-1] + f[i-2] 下面用数学归纳法证明gcd(f[i], f[i-1]) == 1 ( ...
2019-11-05

2019 CCPC 哈尔滨站 B题

链接：https://codeforces.com/gym/102394/problem/B 首先要发现一个性质： 如果i >= j >= k，那么f(i, k) <= f(j, k) 感性理解一下，就是在同一方向，离自己越近的与自己的公共前缀越长。因为离自己更远的数，最高的与自己 ...
2019-11-05

bzoj 1053 反素数

题目大意：定义，当任意小于x的数的约数的个数都小于x的约数的个数时，称x为反素数。 给定n <= 2e9，求小于等于n的最大的反素数。 感觉以前刷数学刷偏了。这么简单的题都不会。。。 显然，当两个小于等于n的数的因子数相同时，较小的那个数才是反素数（之前就是这里没发现）。而因子数等于这个数的质 ...
2019-11-04

bzoj 1502月下柠檬树 Simpson积分

关键点是，水平的圆投影到水平面之后仍然是与原先全等的圆。 然后圆与圆之间通过曲面无缝连接，所以投影下来之后圆与圆之间通过公切线连接。 直接求有点难。把投影区域的上边界当成一个函数，然后套Simpson积分就简单了。 我的实现用了指针从左往右扫，其实没必要，暴力好像还会快一点。 代码(darkbzoj ...
2019-11-03

poj 2826

vjudge链接：https://vjudge.net/problem/POJ-2826 题意很简单，天上下雨，用两根线段接水，问能接住多少面积的水。 看起来很简单，然后WA了5发。。。 首先判断两根线段是否相交，若不相交则显然不能接到水。 然后求交点p。分别求出两条线段的端点中较上面的端点p1, ...
2019-11-02