whix

分类

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

/ 注册

全部文章（共139篇）

Nice Trick

利用好S3的公式，枚举第4项，每次都计算S3公式中所需要的三个和，然后当i>3时每次输入a[i]时都算一遍S3，并计算a[i]*S3的值，最后加起来即可。边加边模，防止溢出。知识点：快速幂取模费马小定理 #include <bits/stdc++.h> using namespac...

2019-10-05

0 594

二项式系数奇偶性判定准则

给出n,k，求C(n,k)的奇偶性：如果k&(n-k)==1,那么为偶数；否则为奇数。 Binomial Coefficients POJ - 3219 #include <cstdio> using namespace std; int main() { int ...

2019-10-04

0 554

Strange Optimization

题目意思是要求在t固定的情况下，i，j任意取值，求得f(t)的所有最小值中的最大值。对于i/n-j/m而言，根据拓展欧几里得的有解的条件，那么它可以表示gcd(n,m)/(nm)的任意倍数，那么当t是固定的时，t到和它最近的两个gcd(n,m)/(nm)的倍数之间的距离中的最小值必然小于等于gcd...

2019-10-04

0 497

求一个大数的前3位和后3位

求后3位，快速幂取模求前3位：对于n^k这个数，可以用10 ^p表示（p为浮点数），即10^p=n ^k, 那么p=k*log10(n) 用整型数x表示p的整数部分，用浮点数y表示p的小数部分，0<=y<1。那么10^p=10 ^(x+y)=(10 ^y) * (10 ^x)。即...

2019-10-04

0 338

Sigma Function LightOJ - 1336

求1~n中多少个数的因子和为偶数。推荐一篇博客主要思路是：直接求有多少个数的因子和为偶数不太好求，那么我们可以转换思路，求出有多少书读的因子和为奇数，如何一减即可。 1.首先我们要知道：偶数*偶数=偶数奇数 *奇数=奇数偶数 *奇数=偶数 2.对于题目中给定的求因子和的公式，如果其中的每一...

2019-10-03

0 487

Prime Independence LightOJ - 1356

HK+质因子分解 HK是二分图匹配中匈牙利算法的优化，时间复杂度O(sqrt(n)*m) 先通过bfs寻找多条增广路，记下每个点到源点的距离（类似于网络流dinic算法），然后用类似于匈牙利算法中dfs的方法，进行匹配。要求图是二分的，并且根据增广路的特性模板： #include<bit...

2019-10-02

0 489

大数__int128

include <bits/stdc++.h> using namespace std;typedef long long ll;const ll M=1e18;int n,k;__int128 res;int main(){ while(scanf("%d%d",&n,&...

2019-10-01

1 514

二分专题

Cable master POJ - 1064 【浮点数二分】一般题目会要求输出相应的精度，而这类题目就容易错在这里。可以通过人为的控制循环来达到所要求的精度，或者设立相应的终止条件。 #include <cstdio> #include <algorithm> #inc...

2019-09-28

0 483

Gone Fishing POJ - 1042

大概思路：贪心+枚举如果直接求解，最难算的就是从一个湖到另一个湖的过程，到底要不要走，要不要在这个湖钓鱼，这就比较难考虑。那么我们可以换一种思维方式。因为人最终肯定是要停止在某一个湖的，那么我们就可以枚举最终停止的湖泊，这样从第一个湖到停止的湖的耗时就确定了。那么，我们就可以认为人可以在湖之间瞬...

2019-09-27

0 619

Lifting the Stone HDU - 1115

计算几何，已知多边形的各个顶点的坐标，求多边形的重心坐标。先贴一篇详解一开始以为直接用坐标相加然后除以n即可。看了题解才知道和面积有关。首先要在已知三角形三个顶点的情况下，求三角形的面积，有公式。原理是向量的叉乘求三角形面积。 s=(x1y2-x2y1+x2y3-x3y2+x3y1-x1y3...

2019-09-26

0 425