2014-10-25 Xie Jingyi
题目大意 输入a, b, k, n, m,计算$a^n\times b^m\times C_k^n$模10007的余数。 分析 对于幂数的计算并不难,关键在于对组合数$C_n^k$的计算。 通常来说,组合数的计算一般是这样的:$$C_n^k=\frac{n}{k}\times\frac{n-1}{k-1}\times\ldots\times\frac{n-k+1}{1}$$ 这对于单精度的计算来说是十分快捷的,但如果要对结果取模的话就不起作用了——取模运算对于除法不成立。因此只能另辟蹊径了。 注意到加减乘法对于取模都是成立的,从而想到:能否将组合数转化成加法? 自然而然,想到了组合恒等式:$$C_n^k=C_{n-1}^{k} 继续阅读 »
2014-11-17 Xie Jingyi
现在算起来,至少有220分是不应该丢的——已经接近我的得分了,都是由各种脑残的错误引起的。总之,经历了这一切,我都早已习惯了。过去的事只能让它过去了,重要的是:经历了这一切,我总要明白一些什么。 生活大爆炸版剪刀石头布 题目链接:Link 得分:100 这题是真正的大水题,当然也是我唯一一道满分的题(欲哭无泪)。不说了,模拟就是了。 联合权值 题目链接:Link 得分:40 这题不难,关键是要将无根树转化成为有根树,做一次DFS。事实上,两个距离为2的节点,要么一个是另一个的祖父节点,要么两个节点是兄弟关系。一方面,我们在DFS时先求当前节点与祖父节点产生的联合权值(如果有的话);另一方面,遍历当前节点的子节点。对于一个 继续阅读 »
2014-10-08 Xie Jingyi
从今天起至10月11日,持续连载。 关于计算机 ENIAC 出现于1946年。 是最早的计算机。 是电子管计算机。 其他 阶码,即浮点数的指数部分。 IPv6是128位的。 求补码:二进制下:各位取反再加1 或 把原码减1再取反。 关于算法 各种排序的时间复杂度 快速排序:$O(nlogn)$,最坏为$O(n^2)$。 冒泡排序:$O(n^2)$。 归并排序:$O(nlogn)$。 计数排序:$O(n)$。 插入排序:$O(n^2)$。 关于树 完全二叉树 vs 满二叉树:完全二叉树最后一层不一定满。 前序遍历:中左右;中序遍历:左中右;后序遍历:左右中。 节点数 继续阅读 »
2014-10-26 Xie Jingyi
题目 涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:$\sum_{i=1}^{n}{(a_i-b_i)^2}$ ,其中 ai表示第一列火柴中第 i 个火柴的高度,bi表示第二列火柴中第 i 个火柴的高度。 每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。 分析 这真是一道好题——断断续续想了几天才完全AC。 事实上,由排序不等式可知: 当$a_i, b_i$从小到大排序时,距离 继续阅读 »
2014-09-22 Xie Jingyi
记得11年的时候,觉得这道题爆难,根本无从下手。三年后再次回顾,终于AC了,就当是对表达式求值和动态规划的复习吧。 题目:Link ```cpp // Accepted. include <iostream> define Mod 10007; using namespace std; typedef struct { long long v0; //当前值为0的个数 long long v1; //当前值为1的个数 char ch; //当前字符 } vertex; vertex f[100000]; void merge_sum(int p) { int w0 = f[p-1 继续阅读 »
2014-10-01 Xie Jingyi
今天开始学习数论方面的算法。这部分在NOIP中并不常出现,即使出现了也不会像高联这么难(。。。)。 什么是扩展欧几里得算法 所谓欧几里得算法,实际上就是辗转相除法——求两个数最大公约数的一种高效算法。而扩展欧几里得算法则是来源于于一类方程的解决: $$ax+by=gcd(a,b)$$ 这有点像是裴蜀定理的一般形式。和裴蜀定理类似,这类方程也有无数多个整数解。如何高效率地求得它的一组特解呢? 代码 pascal procedure gcd_ex(a, b: longint; var d: longint; var x, y: longint); begin if b = 0 then begin 继续阅读 »
2014-10-15 Xie Jingyi
链接:Link 耗时:0.699s 思路 dfs(t, x, y, d, s)表示当前走了t步,在(x,y),上一个方向为d,s为一个求和用的辅助变量。 当前位置无法走完剩下的路时直接回溯。可节省接近2s的时间。 ps: 这道题虽然没有明说每个城市只走一次,但它的确那样判了,这一点坑了我好久。 Code //Accepted. const dx: array [1..4] of integer = (1, 0, 0, -1); dy: array [1..4] of integer = (0, 1, -1, 0); dir: array [1..4] of char = ('e', 'n', 's', 继续阅读 »
2014-10-06 Xie Jingyi
链接:Link 耗时: 0.012s 前言 真是疯玩了几天,脑袋都残了,一道弱智题做了近一个小时。 Code var pre, mid, s: string; tree: array [1..50] of record l, r: integer; ch: char; end; cur: integer; function init: integer; var m: integer; begin readln(s); m := length(s) >> 1 + 1; pre := Copy(s, 1, m-1); mid 继续阅读 »
2014-10-01 Xie Jingyi
链接:Link 耗时:1.825s 这道题做的可真够久的:前前后后加起来将近有两个小时,因此当AC的那一刻,自己心中还是挺自豪的。 事实上,这是一道复杂一点的区间型动态规划,之所以说“复杂”,是因为它的状态转移是二维的:切蛋糕既可以横切,也可以纵切。由此我想到了分治算法: 假设一个矩形它所需要切的刀数是f,则f可以由组成该矩形的小矩形的f值决定。 因此,这个问题具有最优子结构。由于每个状态为一个矩形,因此需要4个维度来记录状态(及左上、右下两个顶点)。下面是横切时的状态转移方程,纵切时同理可得: f(up, down, left, right) = min{f(up, i, left, right) + f(i, dow 继续阅读 »
2014-10-24 Xie Jingyi
链接:Link 耗时:0.679s 分析 本质上,这是一道求数列通项的题目。我们列出前几个字符串: $$01,$$ $$1001,$$ $$01101001,$$ $$1001011001101001,$$ $$\ldots$$ 如果用$S_i$表示第i个字符串中“00”的个数,则有: $$S_1=0,\ S_2=1,\ S_3=1,\ S_4=3,\ S_5=5,\ S_6=11,\ldots$$ 经过观察可以发现有如下规律: $$S_n=2\times S_{n-1}+{(-1)}^n$$ 求通项就简单了,换个元即可: $$S_n=\frac{1}{3}[{(-1)}^n+2^{n-1}]$$ 程序采用高精度实现。 Cod 继续阅读 »