whix
whix
全部文章
分类
acm(1)
codeforces(13)
dp(1)
java(1)
区域赛真题(2)
图论(20)
字符串(3)
数据结构(4)
数论(37)
未归档(32)
牛客(8)
组合数学(7)
计算几何(1)
题解(9)
归档
标签
去牛客网
登录
/
注册
whix的博客
全部文章
(共139篇)
Prime Distance POJ - 2689
大区间素数查找。 因为给出的数据范围太大,无法开到那么大的数组,所以不可以一开始预处理出所有的素数。 又因为l和u之间的差值最大1e6,所以也不可能一个一个地去判断。 正确的方法时,先预处理出 sqrt(N)范围内的全部素数,那么就可以通过这些素数来判断1~N内的所有数是素数还是合数。 对于给定的区...
2019-08-24
0
339
Killer Names HDU - 6143
容斥定理的思想。 当长度为n时,对于姓所用的字符个数从1~m-1讨论。 f[i]表示长度为n的姓用i个字符时,姓的可能数量。 那么f[i] = in-c[i][i-1]*(i-1)n-c[i][i-2]*(i-2)^n… 因为要保证不重复,当用i个字符时,如果只用了i-1个,那么这种情况在只用i-1...
2019-08-24
0
335
Evacuation POJ - 3057
题目大意,在一房间里,有多个’.'每个代表一个人,房间的的边界由’X’和’D’组成,分别代表墙和门,而且房间内部保证没有门。现在问题问所有人逃离房间(到达’D’处即表示逃离成功),而且每一扇门一个时间只能允许一个人通过,每个人只能向上下左右移动,每次移动花费一秒。逃离过程中,一个点可以容纳多个人,即...
2019-08-23
0
432
Ilya And The Tree
一开始看题目,完全没有思路,想到用dfs,但一直不知道处理。看了别人的思路,最后写了很久,才AC。 大概思路: 对于根节点,要么为0,那么不为0,而且根节点一定处于任意一条路中,利用这个性质,我们可以对根节点的状态进行枚举。 当根节点为0时,那么每条路上的把一个数变成0的机会已经用掉了。那么只有对此...
2019-08-21
0
326
The Balance POJ - 2142
拓展欧几里得的通解的应用; 已知两个特解x0,y0, 通解 :x=x0+k*(b/gcd) y=y0-k*(a/gcd) 然后根据条件对一定范围内的解进行依次求解 #include <cstdio> #include <cstring> #include <cmath...
2019-08-19
0
364
确定比赛名次 HDU - 1285
一开始题目意思理解错了,以为要求求出所有选手的排名关系,看了题解后,才知道只要满足题目给的次序即可,没有给的信息,可以不用管。 因此,问题就变成了拓扑排序的模板题。所谓的拓扑排序是相对于有向无圈图的顶点的一种排序,如果出现了从u到v的路径,那么排序后,v一定在u的后面。 基本操作就是,每次先找到入度...
2019-08-19
0
427
C Looooops POJ - 2115
#include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; ll a,b,c,k; ll _gcd(ll a,ll b,ll &a...
2019-08-18
0
379
数论基础
1.最大公因数( g c d gcd gcd...
2019-08-18
0
266
GCD XOR UVA - 12716
题目一开始看,完全没有思路。 看了书上的分析才会,而且枚举过程一开始也写错了。 本题主要是利用性质,如果gcd(a,b)==a^b=c,那么b=a-c。(书上有证明,打表可以看出),然后主要枚举a ,c即可。枚举的方法借鉴与素数筛法,减小时间复杂度。(一开始不会),同时利用递推的关系先预处理出每个n...
2019-08-18
0
321
Minimum Sum LCM UVA - 10791
数论题, 唯一分解定理的应用 把每个n分解成素数的幂的表示形式,把相同的素因子放在一起时,有最小和。 特殊情况: n=1时, 只有一个素因子时, 列素数时,只需列一部分即可,如果最后无法分解,表示最后剩下的数即为素数。 pow有精度损失,自己手写。 #include <cstdio> ...
2019-08-18
0
321
首页
上一页
5
6
7
8
9
10
11
12
13
14
下一页
末页