2009/10/13 22:42
AekdyCoin req RP
ym
topsky
mcfn
haozi
superlong
liuzhe
dsh
foreverlin
sevn
winnie
lccycc
wzc
daxia
vge
javaboy
xiaobo
cd
yayamao
z_y
梦幻boy
Phoenix
wekooo
SHH
BHH
小丽姐
whb
drogon_hdu
zero
guying
chijing
Qinz
lost
xwx
whereisherofrom
.
.
.
.
.
RP+++
Bless 宁波
|
2009/09/29 16:38 接触数论已接近半年,回想昔日在HDU老菜鸟杯上出的那2道数论题，从那时开始到现在几乎都在啃数论,现在或许应该是停止啃的时候了,毕竟ACM比赛不仅仅是只有数论.走过了这半年，下面稍微做一个小结吧！
这里的小结只涉及到算法，并未设计到具体的代码实现,有兴趣的朋友可以在我的空间找到大部分代码.
作为数论，实际上正如某位大牛称的"素论",大部分是围绕素数来展开，当时学长教我的素数筛选法,第一次认识到了数字的美妙.
1.素数的筛选
1-1.关于简单素数筛选的问题，我推荐下面这道:
|
2009/09/21 12:50 PS.PKu上面已经有现成公式了.
题目意思不再累述
Q=1的时候,表示询问T内门会坏几次的期望
Q=2的时候表示询问T时间内***会被惩罚几次的期望(如果某次门被打开坏了，那么以后每开一次门,都会诶惩罚一次,坏的那次不算,即如只开了2次门，第1次开门被搞坏了，第2次开被惩罚了，所以这种情况下是被惩罚1次)
p表示开一次门门会坏的概率,q=1.0-p,Q=1.0/q,c(i,j)表示从i个中选j个数的方案(组合数)
Q=1
P(n,i)表示T时间内一共开了n次门，坏了i次.
P(n,i)=(nanda * T)^n / n! * c(n,i) |
2009/09/19 9:05 传送门
题目大意:
假设直角三角形的一个边长为K，那么3个边都是整数的构成方案假设有N种.比如K=3,显然这种情况下只有1个方案，即(3,4,5).现在题目反过来，告诉你N，叫你求最小的K
N<5000
先来看看，假设它的另外一个直角边是a,斜边是d
那么显然有
k^2 +a^2 = d^2
k^2 = (d-a)(d+a)
记
|
2009/09/18 8:50 我是沙茶吗？
|
2009/09/15 18:07 cpg的题题，即传说中的****过程，自然由于精度要求不高，完全可以暴力暴力解决.今天秃然想用解线性方程组的方法做一下，结果却开始了一个下午的悲剧.
原因在最后会给出.
dp[i]表示cpg在有i个apple的情况下win的概率
然后假设题目给的是p
令q=1.0 - p;
dp[i]=p*dp[i-C] + q*dp[i+D]//因为这些概率可以认为是常数！这点很重要
注意
if(x<0) d |
2009/08/29 10:06 这个暑假,第一次组队,第一次体验比赛的紧张气氛,同时也看到了许多不足,特别感谢我的队友在暑假训练的过程中对我这个新人的照顾~闲话到此为止,下面进入正题(由于比赛过多,下面只是部分总结):
*比赛中的所有题目都可以在各OJ找到(TJU,HDU,FOJ等)
Multi-School Training Contest - TOJ Site #1 (Private)(17)
暑假开场第1次比赛,在这次比赛中我只AC了一个简单数学题.看来自己还是太弱 |
2009/08/24 13:36 所有的题目都是比赛以后做的,姑且称为一次"比赛".
Problem A
显然一看就可以知道是裸的DLX,其实这题规模很小,直接暴搜可以过.我是使用了位压缩来做的.把一列看成10个int型.然后判断某一行能否继续加入解集的判断就完全成了位运算的天下.(利用"与"运算可以方便快速的知道当前行时候可能加入当前解集,因为这一行的所有'1'必须在上面没出现过,所以与完必须是0)
而加入解集以后只需要把 |
2009/08/19 12:19 题目地址
不知道是SPOJ数据超强还是什么原因,在UVA 跑0.1s结果到了SPOJ跑了3S+
G=0;
for(k=1;k< N;k++)
for(j=i+1;j<=N;j++)
{
G+=gcd(k,j);
}
显然如果O(n^2*gcd复杂度) ,一组数据就 |
2009/08/18 10:06 题目地址
题目大意:给你2个字符串A，B，希望你在其中插入若干个空格，使新得到的A，B串长度一样，并"距离最小"
所谓的"距离"为:
1.如果A[i],B[i]中全为字母,那么"距离"为他们的ASCII码差的绝对值
2.如果A[i],B[i]中全为空格,"距离"为0.
3.如果A[i],B[i]中有且只有一个空格，那么"距离"k由题目给出
问 |
2009/08/18 0:09 首先不得不承认我已经很久没写这种WS的题目了，诚然这题相当恶心，我足足想了N个小时以后才得到解.
题目给你一个超级长数字串,希望你输出比它大的Palindrome,而所谓的Palindrome我想应该是无人不知了.(必须输出第一个满足条件的数)
由于题目给的数字超级大(10^1000000),所以暴力模拟显然会严重超时.于是考虑从数的特点来求解
首先假设一个n位10进制数字可以表示为 A[0]A[1]A[2]...A[N-1]
那么
1.我们希望从中间开始修改数字，使数增加的尽量少
|
2009/08/16 14:53 以下涉及到定理的证明的部分全部略过.
开题自然少不了介绍,以上的公式就是Pell方程的一般形态.
显然如果告诉你a,b,c,一开始想到的只可能是暴力,可是接下来介绍的纯数学的方法可以很快速的求解几乎大部分解.
1.首先构造一个系数矩阵,显然为了构造这个矩阵，我们需要先得到
下面方程的一个最小特解(x,y>0)
|
2009/08/15 20:50 题目地址
题目的意思是给了K种颜色的小珠子,每种的个数都是已知的,现在把这些小珠子全部构成一个环形的项链，由于项链可以旋转，所以旋转得到的被认为是同构的.(本质相同)
很显然这是一个同构计数问题,由于模型比较土，所以可以直接套用BurnSide引理..
对于旋转0度，很显然是一个经典的排列组合的问题，即有可重复元素出现的排列问题.
然后旋转i格，每个等价类中有n/gcd(n,i)个元素N (n表示小珠子总个数 |
2009/08/13 10:30 二分时间求解
题目地址
题目的意思是给你一群衣服,每个衣服都有一个ai表示它所含有的水的值,而每一个单位时间它们的含水的值减1(直到0,dry..)
题目还额外给了一个烘干机,每单位时间可以减少k个单位的水.
二分时间,判断可行性,然后求解即可.
注意判断可行性的过程:
1.先把所有衣服的含水量减去T
2.对于剩余水量>=(k-1)的,拿去烘干, |
2009/08/13 9:47 PS.b a i d u 的吞空格太恶心了
/*
这道可以说是解Pell方程的入门题目,首先我们必须得到这个"方程"
假设房子的编号为n,最后一个房子的编号为m
于是
1+2+..+n-1 = (n+1) + (n+2) + .. + m
即
n(n-1) = (m-n)(m+n+1)
所以
n^2 - n = m^2 - n^2 + m - n
整理得:
2*n^2=m^2 + m
2边同时乘4,得到
8*n^2 = 4*m^2 + m
2边同时加1
8n^2 + 1 = (2m+1)^2
令
x=2m+1
y=n
所以上面可以写成:
x^2 - 8y^2 = 1
由于8非完全平 |
| | |
