A code a day, keeps the girls away!
C++博客
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
随笔:46 文章:0 评论:16 引用:0
2011年8月13日
hdu 3918 Beiju
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3918一个如上图所示的杯子,一开始为空,且杯子的重量不计,沿着杯壁往里面慢慢地倒水,直到杯子倒了为止,最高能往里面倒多少水,求最后水的高度。做法:将杯身分割成梯形,每个梯形中,重心是在x轴的分量,是往一个方向偏移,也就是有单调性。求出从下往上枚举每个梯形,求出第一个使得杯子倒掉的梯形,然后在这个梯形内部二分,求出...
阅读全文
posted @
2011-08-13 16:25
AmazingCaddy 阅读(329) |
评论 (0)
|
编辑
收藏
hdu 3869 Color the Simple Cycle
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3869polya计数 题里给的环,可以从某个顶点开始,按照逆时针顺序,依次将经过的边权和点权构成一个序列,那么这个序列唯一确定这个环。并且,一切旋转,都相当于对形成的序列进行循环移位。因此可以用扩展KMP算法,将两个原序列拼接作为匹配串,将原序列作为模式串,就可以在O(N)内知道所有能和原串重合的移位方法。对于...
阅读全文
posted @
2011-08-13 16:15
AmazingCaddy 阅读(311) |
评论 (0)
|
编辑
收藏
hdu 3911 Black And White
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3911久违的线段树啊,亲好久没写线段树了,都不会写了。。。在队友的指导下,艰难地写完了。。。 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  ...
阅读全文
posted @
2011-08-13 16:11
AmazingCaddy 阅读(310) |
评论 (0)
|
编辑
收藏
hdu 3930 Broot
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3930题目意思很简单 对于方程 x^k = b mod p,给出k,b,p,求所有的x ( 0<= x < p ),题目的数据范围很恶心,其实没有那么大,只有10^12那么大,可以打素数表了亲,再大的话,只能rho来分解了。。。 1) 先暴力求p的原根g 2) ...
阅读全文
posted @
2011-08-13 16:07
AmazingCaddy 阅读(733) |
评论 (0)
|
编辑
收藏
2011年5月10日
pku 3659 Cell Phone Network
摘要: http://poj.org/problem?id=3659题意: 给出一棵树(无向图),让你在上面选点放塔, 塔覆盖范围为当前点和相邻的点,用最小的塔覆盖所有点解法1:树型DP dp[ i ][ 0 ], 表示该点不放塔, 且被祖先结点覆盖 dp[ i ][ 1 ], 表示该点不放塔, 不被祖先覆盖 dp[ i ][ 2 ], 放塔 u为i 的子结点d...
阅读全文
posted @
2011-05-10 16:32
AmazingCaddy 阅读(297) |
评论 (0)
|
编辑
收藏
2011年2月27日
hdu 2865 Birthday Toy
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2865题意:AekdyCoin大神对一个特殊的玩具进行染色,跟pku2888(http://www.cppblog.com/AmazingCaddy/archive/2011/02/27/140750.html)差不多。玩具如题中所示,中间一个圆,外面圆周上排列了N个小圆,形成一个大圈,一共N+1个圆,每个小圆都...
阅读全文
posted @
2011-02-27 18:59
AmazingCaddy 阅读(333) |
评论 (0)
|
编辑
收藏
pku 2888 Magic Bracelet
摘要: http://poj.org/problem?id=2888题意:Harry Potter 要用m种颜色的珠子做一个长度为n的手镯,手镯首尾相接。其中某些颜色的珠子不兼容,不能放在一起。求Harry Potter能够早多少种不同的手镯(每种颜色的珠子都有无限多颗,旋转之后能够吻合的算同一种)。解法:polya计数,sum = sigma ( Euler( n / i )*Gettr( i ) ) ...
阅读全文
posted @
2011-02-27 18:43
AmazingCaddy 阅读(517) |
评论 (0)
|
编辑
收藏
2011年2月26日
pku 2154 Color
摘要: http://poj.org/problem?id=2154楼爷的题目,题目大意就是一个长度为n的项链,首尾相接,用n种颜色去染色,求有多少种染色方案(经过旋转之后一样的,算同一种方案),最后只要输出总方案 mod P。解法:polya定理 由于n很大,所以对n进行分解之后,再DFS求出所有的因数。 1/**//* 2*&nb...
阅读全文
posted @
2011-02-26 21:08
AmazingCaddy 阅读(432) |
评论 (0)
|
编辑
收藏
2011年2月8日
pku 3696 The Luckiest number
摘要: http://poj.org/problem?id=36968*10^0+8*10^1+8*10^2+8*10^3+8*10^4+.....+8*10^(n-1) = 8*(10^n-1)/9由题意有 8 * ( 10^n - 1 ) / 9 = 0 ( mod L ) 求最小的 n-------> 8 * ( 10^n - 1 ) = 0 ( mod 9 * L )-------> ...
阅读全文
posted @
2011-02-08 19:19
AmazingCaddy 阅读(278) |
评论 (0)
|
编辑
收藏
2011年1月30日
tzc 2352 Factovisors
http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2352
好久没有做数论题了,弱死了,这题弄了N久,因为没有考虑0这个特殊的家伙不能作为除数。
题意相当简单,就是判断m能否整除n!。
解法:对m进行素因数分解,m = p1^t1 * p2^t2 * ... * ps^ts。那么对于pi,判断n!是否含有x个因数,使得x >= ti。
tzc_2352
1
#include
<
cstdio
>
2
#include
<
iostream
>
3
#include
<
cmath
>
4
#include
<
algorithm
>
5
#include
<
cstring
>
6
#include
<
string
>
7
#include
<
complex
>
8
#include
<
queue
>
9
using
namespace
std;
10
typedef __int64 ll;
11
12
const
int
maxn
=
66000
;
13
bool
vis[ maxn ];
14
ll p[ maxn ];
15
int
plen, flen;
16
int
a[
65
], b[
65
];
17
18
void
prime( )
19
{
20
ll i, j, k;
21
plen
=
0
;
22
memset( vis,
false
,
sizeof
( vis ) );
23
for
( i
=
2
, k
=
4
; i
<
maxn;
++
i, k
+=
i
+
i
-
1
)
24
{
25
if
(
!
vis[i] )
26
{
27
p[ plen
++
]
=
i;
28
if
( k
<
maxn )
for
( j
=
k; j
<
maxn; j
+=
i ) vis[ j ]
=
true
;
29
}
30
}
31
}
32
33
void
num_factor( ll n )
//
在有素数表的前提下的素因数分解
34
{
35
int
i;
36
flen
=
0
;
37
for
( i
=
0
; p[ i ]
*
p[ i ]
<=
n; i
++
)
38
{
39
if
( n
%
p[ i ]
==
0
)
40
{
41
for
( b[ flen ]
=
0
; n
%
p[ i ]
==
0
;
++
b[ flen ], n
/=
p[ i ] );
42
a[ flen
++
]
=
p[ i ];
43
}
44
}
45
if
( n
>
1
) b[ flen ]
=
1
, a[ flen
++
]
=
n;
46
}
47
48
int
factor( ll n, ll p )
49
{
50
int
sum
=
0
;
51
while
( n )
52
{
53
n
/=
p;
54
sum
+=
n;
55
}
56
return
sum;
57
}
58
59
int
main(
int
argc,
char
*
argv[])
60
{
61
ll n, m;
62
prime( );
63
while
( scanf(
"
%I64d %I64d
"
,
&
n,
&
m)
!=
EOF )
64
{
65
if
( m
==
0
)
66
{
67
printf(
"
0 does not divide %I64d!\n
"
,n);
68
continue
;
69
}
70
num_factor( m );
71
int
flag
=
0
;
72
for
(
int
i
=
0
; i
<
flen; i
++
)
73
{
74
int
tmp
=
factor( n, a[ i ] );
75
if
( tmp
<
b[ i ] )
{ flag
=
1
;
break
; }
76
}
77
if
( flag ) printf(
"
%I64d does not divide %I64d!\n
"
,m,n);
78
else
printf(
"
%I64d divides %I64d!\n
"
,m,n);
79
}
80
return
0
;
81
}
82
posted @
2011-01-30 23:22
AmazingCaddy 阅读(257) |
评论 (0)
|
编辑
收藏
2010年10月21日
fzu 1971 A math problem
摘要: http://acm.fzu.edu.cn/problem.php?pid=19712010年福州网赛A题,AC出的身体,看了AC的解题报告写的,死活不会那个证明,然后就用了第二种方法。题解详见:http://hi.baidu.com/aekdycoin/blog/item/e87f5f9653423c6255fb969b.html Orz AekdyCoin PS: 题目有个...
阅读全文
posted @
2010-10-21 20:54
AmazingCaddy 阅读(326) |
评论 (0)
|
编辑
收藏
2010年10月6日
sgu 433 Japhshan and Ramshut
摘要: http://acm.sgu.ru/problem.php?contest=0&problem=433题目大意:要求使用一个长为L,宽为1的矩形,刚好填充一个大的矩形。解法:比较裸的DLX,knuth的论文中有更加复杂的图案。建图:行代表 以一个格子为起点,使用第i个小矩形,横着或者竖着填充大矩形。 &nbs...
阅读全文
posted @
2010-10-06 22:08
AmazingCaddy 阅读(401) |
评论 (0)
|
编辑
收藏
2010年10月5日
sgu 435 UFO Circles
摘要: http://acm.sgu.ru/problem.php?contest=0&problem=435题目大意,每个UFO会使长草的地面变成荒地,使荒地长出草来,作用范围是一个圆,求最后荒地和草地面积各为多少。圆的离散化,比赛的时候没有想仔细,没有做出来,赛后经haozi一点拨,发现可以做,就拿以前写的一个圆离散化的代码改了改,结果精度不够。重新写了一个,结果打错了一个变量,一直没有发现,...
阅读全文
posted @
2010-10-05 02:08
AmazingCaddy 阅读(522) |
评论 (3)
|
编辑
收藏
2010年9月29日
eoj 2830 Hamster 2
摘要: http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=2830题目大意:空中有很多竖直的门,一个点以V0的初速度抛出,忽略空气阻力,重力加速度为10m/s2,求此点最多能穿过几个门。解法:对于每个门,根据斜抛运动,解出初速度与x轴的夹角范围,然后求出重叠次数最大的区域,输出该次数。 eoj 2830Code highlighting produc...
阅读全文
posted @
2010-09-29 00:27
AmazingCaddy 阅读(252) |
评论 (0)
|
编辑
收藏
2010年9月7日
hdu 2966 In case of failure
摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2966题目的意思是:平面上有n个点(n<100000),求每个点的最近点到该点的平方距离。KD_Tree可以解决此题。详细资料可以参看此链接 http://en.wikipedia.org/wiki/Kd-tree,上面给出了算法。PS: 这道题时限开了恐怖的30秒。 hdu_2966Code high...
阅读全文
posted @
2010-09-07 11:26
AmazingCaddy 阅读(577) |
评论 (1)
|
编辑
收藏
仅列出标题
下一页
<
2024年10月
>
日
一
二
三
四
五
六
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
DP(1)
(rss)
MST(1)
(rss)
计算几何(15)
(rss)
数据结构(3)
(rss)
数论(12)
(rss)
数学题(6)
(rss)
线段树(6)
(rss)
杂(6)
(rss)
随笔档案
2011年8月 (4)
2011年5月 (1)
2011年2月 (4)
2011年1月 (1)
2010年10月 (3)
2010年9月 (2)
2010年8月 (4)
2010年7月 (9)
2010年6月 (3)
2010年5月 (8)
2010年4月 (3)
2010年3月 (4)
传送门
AekdyCoin
edwardmj
Felicia
forverlin
haozi
lccycc
matrix67
Puzzle
sha 崽
topsky
ZJ@coreBug
搜索
最新评论
1. re: zoj 3324 Machine[未登录]
请问大神,这组数据为啥是这样?
1
6 2
p 0 5
r 3 4
Case #1:
0
0
--小红
2. re: hdu 2966 In case of failure[未登录]
thnx
--a
3. re: hdu 3571 N-dimensional Sphere
评论内容较长,点击标题查看
--AmazingCaddy
4. re: hdu 3571 N-dimensional Sphere
为什么要加上一个极大值使负数都变正?
取模过程中正负都无影响的吧?但是不这样做就会WA。
好纠结。。。
--嘟嘟洒水车
5. re: hdu 3571 N-dimensional Sphere
@_Yuan
这个高斯消元我是从浙大模板上改过来的
--AmazingCaddy
阅读排行榜
1. spoj 5971 LCM SUM(1106)
2. poj 1151(974)
3. hdu 3571 N-dimensional Sphere(772)
4. hdu 3930 Broot(733)
5. poj 1177(679)
评论排行榜
1. hdu 3465 Life is a Line(4)
2. hdu 3571 N-dimensional Sphere(4)
3. sgu 435 UFO Circles(3)
4. hdu 3411 Snail Alice(3)
5. zoj 3324 Machine(1)