分类 ACM/ICPC 中的文章

ACM – UVa10006 – 快速幂

水题一发。无奈自己没有好好审清题意,另外快速幂居然写错了- = 快速幂在过程中修改a的值,但是我却计算成了在偶数时相乘,调试半天。看来还是咩有好好理解啊。……

阅读全文

ACM – UVa138 – 数学基础

这道题目其实就是推个公式,主要还是考验编程技巧。。 首先double的精度范围是15-16位,浮点数运算还是最快的,依据最后一个答案(总共10组),平方为16位刚好够用。 如果想要最精确的结果,当然还是使用long double或者long long来来保证精度问题。不过计算速度就会有所损失,采取二分的方法加速比较好。 利用double的代码: 利用long long的代码: 不过有一点就是无论怎么个快法,不使用打表肯定是会超时的,所以算出来直接上交即可。= =。这在大赛中应该也是允许的吧。……

阅读全文

山东省第五届省赛 Circle

首先一点什么是高斯消元? 高斯消元其实就是一种求行列式的值的方法。 例如 |a[0][0]_x1 + a[0][1]_x2+ … a[0][n-1]_xn = a[0][n]| |a[1][0]_x1 + a[1][1]_x2+ … a[1][n-1]_xn = a[1][n]| |a[2][0]_x1 + a[2][1]_x2+ … a[2][n-1]_xn = a[2][n]| |a[3][0]_x1 + a[3][1]_x2+ … a[3][n-1]_xn = a[3][n]| … |a[n-1][0]_x1 + a[n-1][1]_x2+ … a[n-1][n-1]*xn = a[n-1][n]| 已知a[x][y],求x1, x2 .. xn的值。这个时候就可以使用高斯消元。 本题目就是高斯消元求解的一道题目。 依据题意,可以列出方程: $$E[x] = 0.5_(E[x-1]+1) + 0.5_(E[x+1]+1)$$ 其中E代表期望,利用高斯消元我们可以得到x1-xn的值,输出我们需要的E[x]即可。 高斯消元其实就是我们所说的消元,但是针对于大型的矩阵。 倒是很简单的题目。……

阅读全文

山东省第五届省赛 Hearthstone II

斯特林数stirling 第一类 stirling数 s(n, k) n个人分成k组,组内再按特定顺序围圈 也就是分成了k组,组内就像是项链颜色一样, ( {A, B}, {C, D} ) ( {B, A}, {C, D} ) 属于一组 ({A}, {B, C, D}) ({A}, {B, D, C}) 不属于一组 给定 $s(n,0)=0,s(1,1)=1$,有递归关系$s(n,k)=s(n-1,k-1) + (n-1) s(n-1,k)$ 第二类 stirling数 S(n, k) 是把p元素集合划分到k个不可区分的盒子里且没有空盒的划分个数。 公式: $$ S(n, n) = 1 (n >= 0) $$ $$ S(n, 0) = 0 (n >= 1) $$ $$ S(n,k)=k*S(n-1,k)+S(n-1,k-1),\text (1<=k<=n-1) $$……

阅读全文

bestcoder#2-1

一开始直接使用结构体搞结果wrong了,随后查看了某牛的代码发现应该直接在区间上累加 — 得出结论不要直接使用复杂的结构体,转变成简单的数据形式未尝不是一个好方法 原题: http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=526&pid=1001……

阅读全文

蓝桥杯基础练习

数列排序 十六进制转八进制 转换的时候,先转换成二进制,再转换成十六进制。 这道题目还是比较有意思的,使用string只需要78ms,使用char*则超时。可能strcat每次都需要从头遍历数组,但是string则不需要。 当然,如果是数字没有这么大,完全可以这样处理 是不是很精髓= = 十六进制转十进制 十进制转十六进制 由此也可以想到,如果是二进制的相关转换(数值范围允许的情况),我们可以写一个简单二进制转十六进制,然后利用sscanf来做进一步转换。 当然,正规的做法还是除二取余,逆序排列。 特殊回文数 回文数 特殊的数字 只要读题不出问题就没有问题了。。。不刷了……

阅读全文