whix

分类

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 数论(37) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

全部文章（共139篇）

Prime Time（素数预处理+精度误差的处理）

浮点数的精度误差，一般用1e-8和1e-6来处理。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int num[10005]; bool check(ll n) { if(n<2)...

2019-10-20

0 403

数论分块及应用

在一类要统计∑f(i) (1<=i<=n)的数学题中，由于f(i)是单调的，故存在x,y∈[i,j]使得f(x)=f(y)。于是只要找到这段区间就可以节省计算区间内每一个函数值的时间开销。时间复杂度大抵是O(sqrt(n))的。牛客——美味果冻：题解 #include <...

2019-10-14

0 417

The Football Season（拓展欧几里得思维题）

总的思路：贪心因为题目中说明了w>d，那么我们可以让y取得最小非负解，那么就可以使得x+y更小，这样就使z有解的可能性最大。第一种解法：暴力根据拓展欧几里得的x,y的通解。可知y的最小非负解的取值范围是0<=y<w，题中w=1e5。那么就可以直接暴力0~w的所有值，看是否满足...

2019-10-14

0 458

Pairs Forming LCM LightOJ - 1236（求n以内的最小公因数为n的数对的对数）

然后关键是如何讨论，主要是形成数学思维。假设a,b的最小公倍数为n,有：那么ak肯定是ek和dk中的最大值。即对于两个数a和b，其中必有一个数是包含了某个素因子的最高次幂，而另一个数包含该素因子的幂的范围是0~ak。然后对n的所有素因子依次进行如此的讨论，那么就一共有(2* a1+1) * (...

2019-10-11

0 444

数论模板整理！

一： 1.欧几里得求最大公约数 int _gcd(int x,int y) { return y?_gcd(y,x%y):x; } 2.最小公倍数 #include <bits/stdc++.h> using namespace std; int gcd(int x,in...

2019-10-10

0 400

Extended Euclid Algorithm Aizu - NTL_1_E（拓展欧几里得求同余方程）

要求求出的解满足|x|+|y|最小，第二条件是x<=y。直接求解即可，无需加特判。有点疑问？ #include <bits/stdc++.h> using namespace std; typedef long long ll; int _gcd(int x,int y) {...

2019-10-10

0 519

Paths on a Grid POJ - 1942（组合数学基础）

只能走上和右，且必有n个右，m个上，共n+m步。把路径写写出就可以发现如：样例1：上上上上右右右右右 … 只要从n+m个里面选出min(n,m)为上或右即可。利用求组合数的递推公式。 #include <cstdio> #include <cstring> #in...

2019-10-09

0 532

Number Sequence POJ - 1019

大概思路：用前缀和预处理出，当以某一个数为结尾数字时，前面的全部数字的总位数，只要处理到31268即可满足题目的要求。然后根据题目要求的位数，判断这个位置处于哪一段，然后遍历即可找到对应的数字。 #include <cstdio> #include <cstring> ...

2019-10-09

0 547

Harmonic Number (II) LightOJ - 1245（数论基础！）

***解！ #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; ll res; int main() { int t,cas=0; scanf("%d"...

2019-10-08

0 387

Round Numbers POJ - 3252组合数+分类

主要分3种情况： 1.长度比n的2进制表示的长度要小，形如：1xxxxx的格式（首位=1） 2.n能不能满足 3.长度=n的2进制表示，但从某一位开始比n小知识点：利用杨辉三角预处理组合数思想：分类考虑前缀和 #include <cstdio> #include <cs...

2019-10-05

0 426