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-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-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-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-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-11-02 Xie Jingyi
真是巧妙的算法! 比起树上倍增,Tarjan算法实现起来更为简单,一个DFS加并查集即可。缺点便是:需要先把所有的查询都读进来,并且要储存结果。复杂度为O(n+q)。 Code var sets: array [1..100] of longint; visited: array [1..100] of Boolean; a: array [1..100, 1..100] of Boolean; questions: array [1..1000] of record x, y: longint; ans: longint; end; qn, n, 继续阅读 »
2014-11-02 Xie Jingyi
问题描述:已知数组a以及若干个查询(x, y),求a[x~y]之间的最小值。 分析 不难发现:若取t使得$2^t\leq y-x+1$且$2^{t+1}>y-x+1$,则有: $$[x, x+t]\bigcup[y-t+1,y]=[x,y]$$ 运用二进制的思想,我们只需预处理出$i~i+2^k-1$之间的最小值,即可快速完成查询。设dp[i][j]为$i~i+2^j-1$之间的最小值,则有: $$dp[i][j]=min(dp[i][j-1],dp[i+2^{j-1}][j-1])$$。 Code var a: array [1..100000] of longint; dp: array [1..1000 继续阅读 »
2014-09-27 Xie Jingyi
链接:Link 耗时:0.586s 昨晚做的太急了,没时间写总结,正好下午有空,补上。 这是一道典型的树形动态规划,不是很难,但十分坑语言。思路大致如下: 对于第i个节点,用d(i)表示其上诉所需的最小工人数。若i为叶节点,则d(i)=1;否则,遍历求出i的子节点所对应的d值,并由小到大排序,取出最小的几个相加,即为d(i)。 很容易想到用递归来实现。但对于“子节点的d值的排序”实现起来却十分困难:因为事先不知道有多少个数。当然啦,如果是C++组,用vector可以轻松搞定,可至于P党,实现起来却难上加难。思来想去,决定试试Pascal的动态数组。磕磕碰碰调了近1个小时,终于AC了。 Code: ```pascal // 继续阅读 »
2014-11-02 Xie Jingyi
var a: array [1..100, 1..100] of boolean; depth: array [1..100] of longint; father: array [1..100, 0..16] of longint; n, m, i, x, y: longint; root: longint; procedure dfs(x: longint); var i: longint; j: longint; begin depth[x] := depth[father[x][0]]+1; j := 1; while 1< 0 then 继续阅读 »