发表于 | 阅读次数:
字数统计: 405 字

今天的命题人好像和昨天的是一个人， 所以命题风格也很像。 Day1会有很多水题可以拿分主要还是有很多暴力分。

分数0 + 100 + 20 = 120

做题回顾

其实今天的T1爆零是很不应该发生的一件事情。因为在对拍的时候把T2误粘到了T1而且没有检查， 导致我的T1直接爆零， 而这道题如果打暴力都可以拿到35 ~ 60之间的分数 。所以一定要注意检查啊 . . . 不然真的会死的很惨。连自己怎么凉的都不知道。

T2应该是题目的问题， 出题人想要卡一下nlogn的算法，但是由于数据的问题。 std没有开快读和快写，导致std就被卡到了20秒左右的极限时间。 导致这个时间好像很多不正确的算法加上快读就可以卡过20秒。所以就很侥幸的A了。

T3只会写20分的暴力， 大概就是一个dfs枚举每一个元素在那一个集合中。时间复杂度为O(2的n次方)的级别。

失误和总结

  1. 一定要在考试结束的前15分钟左右在把自己的程序检查一遍， 眼查 + 编译 + 过样例 都要进行。不能少任何的步骤， 不然到时候真的会出现这种很难受的情况。并且写完一道题之后就直接备份一下， 不管如何都不要动备份的程序， 不要进行修改。
  2. 学一下fread吧。 这个很快的。

发表于 | 阅读次数:
字数统计: 332 字

今天是昨天的Day2。以为今天还会延续昨天比较友好的风格，会有很多的暴力分数可以拿一下。

分数： 15 + 0 + 0 = 15

考试开始

等待今天的考试开始之后直接拿题，看了下T1发现40分很好拿， 于是就根据题面意思打了40分的暴力出来， 显然对于n大于1e5的数据，这个暴力是过不了的。于是开始向正解，10分钟左右感觉好像自己是想出来了一个好像是整洁的东西， 5分钟打完。 样例发现可以过， 顿时感觉好像很稳。找出刚才写的暴力，写了一份对拍，但是发现第一组就没过去， 于是开始从新调， 最后还是用暴力打了一份表找到了规律。

T2可以2的n次方的算法， 但是可惜的是题并没有十分理解。导致今天的后两题没有很好地解决。

考试之后

发现好像自己T1只剩下15分了。应该是一堆位运算的锅，改成bitset直接一遍过。

总结与过失

  1. 二进制相关可以使用bitset来防止复杂的位运算。
  2. 学习到了dfs模拟二进制选与不选的情况。枚举全排列

发表于 | 阅读次数:
字数统计: 830 字

今天的题比较友好，出题人给了很多暴力分可以拿。

总分80 + 20 +40 = 140分

比赛开始

今天其实感觉状态并不是十分的好， 有一种说不出来的困。想想觉得还是要好好对待， 看完T1之后并没有太好的思路， 没有那种直接秒题的快感，思路还错了几回。看了一眼n的范围，只有4000左右，这样的话n²就可以A掉， 又整理一遍思路。 发现可以从每一个点开始向两边开始跑， 时间复杂度就是n²。30分钟左右打完调好。 由于没有大样例也没有暴力来对拍， 所以感觉心里并不是很稳。预计分数：100分。

然后开始看T2，感觉好像这个题面很简洁啊， 不是那种需要花很长时间来理解出题人意图的语文阅读题。 给好评！然而看完之后，又看了眼数据范围感觉有点蒙，好像50分不能n²写。那么n²就只剩下20分可以写了， 这道题又只给了32MB的内存， 这是在强行搞事情啊。10分钟打完20分直接弃掉这道题开始看T3。T2预计分数：20分。

T3看起来好像很咋呼人，当维度超过3维之后就没法直接抽象的想象了。看了下数据， 好像点分的很细。发现好像d≤3的情况写满了就有40+的分数可以拿， 然后没有坏点的情况就是求一个裸的组合数。那么这道题很可以写一下啊， 差不多到11点30左右d≤2的情况都写好了。 这时候就只剩下30分钟了， 这时候我没有选择继续莽T3剩下的20分左右的部分分， 而是掉过头来开始检查T1和T2， 差不多5分钟左右检查完T1和T2两道题，确保没有问题。才开始转头莽T3的组合数， 10分钟左右打好， 发现对不上之前的暴力. . .只能弃掉了，注释掉写的组合数， 双手离开键盘。等待GG。

全天预计得分：100 + 20 + 50 = 170

成绩出来之后

等到成绩出来之后发现好像不算很糟，但是T1不知道怎么回事挂掉了20分。T2稳定发挥20分到手。T3的10分好像出了一些小锅。

还有一件很难受的事情，因为我好像在T1的输出里面多打了一个空格， 导致我的输出文件在linux系统下无法打开。 但是在win系统下竟然还跑了80分。 一定得加强检查输出文件这种东西！！！

失误总结

  1. 这个比赛策略感觉还挺好用的， 有的放矢。能抓住的就一定要抓住， 知道自己肯定拿不了的就不要浪费时间。
  2. 注意不要打挂题，其他的都好说
  3. 注意能拿到的暴力分一定要想办法拿全，蚊子在再少也是肉啊。5分10分有可能就可以差出一个人的距离
  4. 注意在写读入和输出的时候输入输出文件名字中不要出现多余的符号或者空格等等。

发表于 | 阅读次数:
字数统计: 267 字

今天是昨天的Day2， 这个出题人真的不良心。 基本上没办法做啊， 基本上没有啥可以拿分数的点。 总分20 + 0 + 0 = 20

比赛开始

今天的T1分数划得有点问题， 其实就是两档分数，20 Or 100 分。时间复杂度一个是O(n²)一个是O(nlogn)。正解是用了树状数组来优化前缀和。于是就只拿到了O(n²)的20分，（其实好像是因为今天的数据是有梯度的，所以可以优化一下常数然后多拿10分）。总之就是没法写啊 . . .

T2是一个平衡树， 好像是要自己手写一棵平衡树， 于是就GG。 T2就没有继续看下去，然后没有挣扎。

T3是一个概率期望，好像比之前看到的概率和期望还不很一样， 是在图上做概率期望DP。打扰了. . .

失误总结

  1. 像这种数据是有梯度的可以把自己写的卡卡时， 争取过更多的数据。 
                           ---End---

发表于 | 阅读次数:
字数统计: 837 字

今天是又一套题， 感觉好像难度偏难一些 . . . （可能我还是比较弱吧）自我感觉好像打的还可以。

分数：70 + 0 + 10 = 80分

考试开始：

今天考试开始之后，先看了下T1。第一眼好像是差分， 第二眼感觉不对啊，好像并不是区间修改， 也不是变成一样的数字， 是都变成0。 所以好像不是差分。再看一眼之后发现好像每一个数都是独立的， 与前后的无关， 所以这个数所消耗的 a 和 b 的个数就只由这个数所决定。于是就列了一个方程， 发现这不就是裸的Exgcd吗，然后很兴奋的开始打了一个Exgcd出来。但是又发现这个解就是在限制ax+by=c中|x|+|y|最小。想起来拓展欧几里得的一个性质， 这个解出来的一组解可以保证|x|+|y|最小。 但是好像如果c不是gcd(a, b)的情况下，使用裴蜀定理 可以发现当且仅当c|gcd(a, b)的时候，这个不定方程有解。于是我们知道了输出-1的情况，所以我们现在只需要找出满足ax+by=c的一组解，使得|x|+|y|最小。然后问题就来了，我们可以用一组特解来推出满足这个不定方程的一组通解， 但是我们还需要保证|x|+|y|最小。 搞了差不多20分钟左右才把这个调好， 然后开始看后面题。 发现好像T2不可做， T3可以打15分的暴力。 于是剩下的时间草草打完暴力就结束了上午的比赛。预计得分：100+15 = 115分。

考试结束：

等到考试结束后， 看了下成绩发现好像T1没有A掉的， 在场最高80分，我拿了70分左右。 T3少了5分， 好像是因为p==n的数据出了一些问题。导致5分的送分又挂了. . . 总体感觉还好吧， 明天的比赛加油！

失误总结

  1. 之后比赛有一个时间分配，规定如果是比较重要的比赛的话， 尽量1道正解，1道高分暴力， 1道小暴力分。大概这样打题的话如果不打挂题的话， 差不多两天300+是没有太大问题的。

题解

有一道考验性质的题， 贴一下：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h> 
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
ll a, b, c;
void Exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
	if (!b) {
		x = 1;
		y = 0;
		d = a;
		return;
	}
	ll tx, ty;
	Exgcd(b, a % b, d, tx, ty);
	x = ty;
	y = tx - (a / b) * ty;
}
inline ll abs(ll a) {return a < 0 ? -a : a;}
int main() {
	while(cin>>a>>b>>c,a|b|c) {
		bool flag = 0;
		ll min_x, min_y;
		if (a < b) swap(a, b), flag = 1;
		ll d, x0, y0;
		Exgcd(a, b, d, x0, y0);
		x0 *= c/d;
		y0 *= c/d;
		ll t = y0 / (a / d); ll minn = INF;
		for (int i=t-5;i<=t+5;++i)	{
			ll x = x0 + b/d * i;
			ll y = y0 - a/d * i;
			if (abs(x) + abs(y) < minn) {
				minn = abs(x) + abs(y);
				min_x = abs(x);
				min_y = abs(y);
			}
		}
		if (flag) printf("%lld %lld\n", min_y, min_x);
		else printf("%lld %lld\n", min_x, min_y);
	}
	return 0;
}

发表于 | 阅读次数:
字数统计: 837 字

今天打了昨天的Day2，总分100 + 0 + 0 = 100分

其实感觉今天打得比昨天要好一点。 虽然分数一样， 但是状态根本就不同。 今天的题写的感觉好像更有把握， 虽然还是因为一些非智力因素丢了一些不应该丢掉的分数。 （比如说T2送的20分）

考试开始后

发现今天的T1是一道很水的题， 开场10分钟O(Tnm)的算法就写出来了，（其实能感觉出这个写法不很优秀， 能有更好的算法） 50分的暴力，看起来好像不少。这时候我就算了一波复杂度，当时我算的是好像可以过掉100%的数据， 因为这道题给了2秒，（不知道当时是怎么算的）。于是就放在了那里。开始看T2， 然而看起来好像并不是很可以写。大概好像是可以O(n²)的算法， 但是好像并不是很好实现。这时候我想起来我可以去把T1拍一下， 反正数据也很好生成， 去看一下实际跑的时间。结果花了10分钟写好对拍， 跑起来好像每个点能跑4~7秒钟， 蛤？这肯定是要爆炸的啊。于是开始从新来想一下正解， 推了5分钟左右， 正解的思路大概是有了。由于这道题是真的很水， 于是就没有怎么理思路就开始了， 写的貌似也过了样例， 于是我就开始改对拍，想和之前写的暴力拍一下。差不多花了10分钟左右写好了对拍，这时候却发现好像和之前的暴力并拍不上。又开始调， 花了15分钟+ 最后发现是对拍写错了。 它的输出好像不是很对。在10点整的时候，写的正解终于和暴力拍了上去。T1应该是A了，我当时这么想。

然后就开始看T2， 发现是一道类似计算几何之类的东西。 看完题之后看了一眼数据范围，我的天， 好像有20分是送的啊， 于是很高兴。感觉好像今天起码100 + 20 = 120+了， 但是看了半天发现好像题中点投影的位置问题好像不是很好解决。 头铁又莽了30分钟左右发现如果用斜率来表示的话， 会出现一些比较奇怪的bug， 比如说会出现除零或者排序的规则不好定义之类的小bug，感觉好像代码量有点大。于是就放掉了。

T3一看是概率与期望， 看了一下题面， T3难度的概率与期望打扰了. . . 看了一眼表11点30，于是就开始等待考试结束 . . .

成绩出来之后

T2的20丢掉是让我很难受的， 这20分就是两行的代码的事。 但是还是因为自己的疏忽导致GG. 最后好像还是编译错误， 十分难受。 不知道为什么当时不在本地调好再交啊. . .

经验与教训

  1. 立一个flag ： 之后写题如果交完再不检查的话我SB
  2. 一定要注意检查自己的代码
  3. 坚持每道题都要打完， 即使不会正解

发表于 | 阅读次数:
字数统计: 1,039 字

今天是10月23号

分数: 100+0+0 = 100

今天的考试还算可以接受, 和NOIP的形式十分相似. 难度也很相近, 应该算是一个高质量的题, 但是并没有打出很高的分数.

今天的T1是一道比较典型的NOIP类型的题, 暴力好拿分, 不会打挂掉, 但是想要A掉还是有一定的难度. 益智小学奥数题, 暴力是50分的, 这部分分很好拿, 大概开场10分钟左右就打好了. 但是感觉从50跳到100的差距好像有点大. 类似的, 这种题还是要打表找一下规律. 于是用5分钟左右写好了打表程序, 把n, m小于100的情况打了一下表, 然后开始找规律, 令人遗憾的是, 这道题并可以直接从表里找出什么显然的规律.感觉并没有什么思路,于是感觉要放一下. 期望分50;

开始看T2, 其实看完之后发现好像是一道DP或者贪心这个样子. 好像可以直接贪心, 但是并没有什么很优的策略. 感觉好像这道题不能直接贪心了,于是打了一下二分加上贪心判定, 复杂度O(nlogn).可以卡85的数据, 感觉好像还行.但是开始打贪心判定的时候发现还是贪心策略会出一点小问题, 调了大概有30分钟+,心态有点小炸,于是又去看下T3,感觉好像是图论相关, 2-SAT之类的东西. 感觉好像不是很可做, 于是想再看看T1, 来继续找一下规律.

因为之前打有一个T1的表, 发现并没有什么显然的规律之后就放弃从表中找东西了, 开始看T1题面中给的那个式子, 发现好像这个下取整好像有什么性质可以挖掘一下, 于是我就写了一下如果没有下取整的式子, 感觉好像是可以直接公式求解, 时间复杂度可以直接降到O(1). 于是乎我就开始考虑下取整对答案的影响, 发现不考虑下取整的答案好像会偏大, 还发现如果两数互质的话, 可以直接就减去gcd(a,b) \* (1 + (a - 1)) \* a / 2,即可得到答案, 下一步就是把这个性质推及所有的情况, 所以我就考虑将两个数同时除以gcd(a,b), 这样两数就都变成了质数, 对于除以gcd(a,b)这个剩余系中的所有数都需要再乘以b, 然后剩余系中的和可以直接带等差数列的公式.于是答案就出来了,即为(p + 1) * q - p + gcd（p, q）

推出T1,这是已经到了11点左右, 想起来我好像T1之前好像还写有一个暴力, 就对了下拍, 打有差不多15分钟, 发现数据好像都拍上了, 于是感觉T1应该稳了.这时已经到了11点30, 又补了一下T2, 发现好像好像还差点什么, 感觉是补不完了, 就放弃挣扎了. (其实看下题解发现T2离正解已经很近, 只要在整理下思路就行了). T3也就没写

今天的大锅应该是时间分配, 其实如果好好写的话应该后两道题暴力也能写点分的, 大概60 +　30 左右的分数, 这就十分可观了.

这两天出现的问题:

  1. 写题好像没了斗志, 竟然会出现懒得打爆力这个念头. 要端正态度, 不然总是想着到NOIP了再打暴力,到那时很可能就真的翻车了

  2. 会花费大量的时间去莽正解, 昨天就是因为这个策略的失误导致T1翻车, 后两题连暴力也没来得及打. 直接爆零, 要注意比赛的策略. 先打暴力, 再想正解, 不要花费大量的时间来莽一道题

加油吧!

发表于 | 阅读次数:
字数统计: 4,494 字

代码模板。

巨长的代码模板。

图论

图

连通块的划分（图的染色）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int x) {
    color[x] = cnt;
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (color[y]) continue;
        dfs(y);
    }
}
for (int i=1;i<=n;++i) {
    if (!color[i]) {
        cnt++;
        dfs(i);
    }
}

BFS遍历一个树/图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bfs() {
    queue<int> q;
    memset(d, 0, sizeof(d));//如果搜索的是一棵树的话， 那么d数组指的是节点x在树中的深度。如果是一张图的话， d数组指的是x的层次， （从起点1走到x所要经历的最少点数）。
    q.push(1); d[1] = 1;
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i];
            if (d[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
}//bfs有两个重要的性质， 1.在访问过所有的第i层节点之后，才会开始访问i+1层节点2.任意时刻，队列里只会出现i层的节点和i+1层的节点，并且所有的第i层节点都在第i+1层节点之前。（简单来说就是满足“两端性”和“单调性”）
//并且dfs的时间复杂度和bfs的时间复杂度是相同的， 都为O(n+e)的时间复杂度，只不过限制两个算法的一个是堆栈大小， 一个是队列的大小

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Dijkstra(int x) {
    priority_queue<pair<ll ll> > q;
    for (int i=1;i<=n;++i)	dis[i] = INF, vis[i] = false;
    dis[x] = 0;
    q.push(make_pair(0, x));
    while(q.size()) {
        int x = q.top().second;	q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i], w = edge[i];
            if (dis[y] > dis[x] + w) {//由于是拿出现在堆中最小的那个点来更新其他的点， 所以写的顺序需要注意
                dis[y] = dis[x] + w;
                q.push(make_pair(-dis[y], y));
            }
        }
    }
}//适用于有向图和无向图中，只适用于边长不为负的图。时间复杂度为O(n+m)log(n));

Floyed

1
2
3
4
5
6
void Floyed() {
    for (int k=1;k<=n;++k) 
        for (int i=1;i<=n;++i) 
            for (int j=1;j<=n;++j) 
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}//多源最短路，可以有负权边。适用于大部分的情况。但是时间复杂度高达O(n³)。

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Kruskal() {
	for (int i=1;i<=n;++i)	f[i] = i;
    sort(e+1, e+1+m);
    for (int i=1;i<=m;++i) {
        int a = getf(e[i].x), b = getf(e[i].y);
        if (a == b)	continue;
        else {
            ans += e[i].v;
            f[b] = a;
            ++cnt;
        }
        if (cnt == n - 1)	break;
    }
}//这个是求出最小生成树的所有边的权值和， 其实可以可以在计算所有边的权值和的同时从新建一棵最小生成树

并查集

1
2
3
4
5
6
7
8
9
10
11
void init() {
    for (int i=1;i<=n;++i) f[i] = i;
}//使用并查集的初始化
int getf(int x) {
    return (f[x] == x) ? x : f[x] = getf(f[x]);
}//进行路径压缩的并查集
void un(int x, int y) {
    int a = getf(x), b = getf(y);
    if (a == b) return;
    else f[b] = a;
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Topsort() {
    queue<int> q;
    for (int i=1;i<=n;++i) {
        if (du[i] == 0) {
            q.push(i);
        }
    }//找到入度为0的点， 入队
    while(q.size()) {
        int x = q.front(); q.pop();
        a[++tot] = x;
        for (int i=head[x]; i; i=Next[i]) {
            if (--du[ver[i]] == 0) {
                a[++tot] = ver[i];
                q.push(ver[i]);
            }
        }
    }
}//有向图中使用，记清楚！必须是有向图。显然的是，在进行完成拓扑排序之后，图中还留下来的东西就是一些环。即tot != n;
//算法的应用：1.有向图找环（无向图是不能使用拓扑排序的）

二分图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool find(int x) {
    for (int i=1;i<=m;++i) {  
        if (Link[x][i] && !used[i]) {
            used[i] = true;
            if (girl[i] == 0 || find(girl[i])) {
                girl[i] = x;
             	return true;   
            }
        }
    }
    return false;
}//其实就是在寻找增广路的过程
int Maxmatch() {
    int ans = 0;
    for (int i=1;i<=n;++i) {
        memset(used, 0, sizeof(used));
        if (find(i)) ++ans;
    }
    return ans;
}//匈牙利算法如果使用邻接矩阵的话可以在O(n³)的时间内找到一个二分图的最大匹配数。空间复杂度是一个邻接矩阵(n²)。

Tarjan求强联通分量

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
void Tarjan(int x) {
    dfn[x] = low[x] = ++tim;
    Stack[++top] = x;
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (!dfn[ver[i]]) {
            Tarjan(ver[i]);
            low[x] = min(low[x], low[ver[i]]);
        }else if (vis[ver[i]]) {
            low[x] = min(low[x], dfn[ver[i]]);
        }
    }
    if (dfn[x] == low[x]) {
		int temp = 0;
		++cnt;//一个新的强联通块
		do{
			temp = Stack[--top];
			color[temp] = cnt;//color里存的是第i个点属于第几个联通块
			vis[temp] = false;
		}while(x != temp);
	}
}
int main() {
    for (int i=1;i<=n;++i) {
        if (!vis[i])
            tarjan(i);//因为这张图可能不连通
    }
}

缩点

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
void Tarjan() {
    dfn[x] = low[x] = ++tim;
    Stack[++top] = x;
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (!dfn[ver[i]]) {
            Tarjan(ver[i]);
            low[x] = min(low[x], low[ver[i]]);
        }else if (vis[ver[i]]) {
            low[x] = min(low[x], dfn[ver[i]]);
        }
    }
    if (low[x] == dfn[x]) {
        int temp;
        ++cnt;
        do {
            temp = Stack[top--];
            color[temp] = cnt;
            vis[y] = false;
        }while(x != temp)
    }
}
/*现在说一说缩点，其实就是拿着邻接表，和强连通分量们来建一张新的图，在新的图中，点就是原来的强连通分量，边的具体操作有点复杂，现在具体说一说，大致意思就是：既然点都变成了强连通分量，那么边就应该在他们当中去连接不是吗?那什么和什么连？似乎可以看到，连接同一个强连通分量里的点是没有任何意义的，所以就好办了，跑一遍原邻接表，如果一条边（u，v,w）的u和v不在同一个强连通分量中，那么就在新图中连这条边，就这样点就缩好了。听起来也许有些玄幻，但是它就真真切切的完成了？！*/
for (int i=1;i<=m;++i) {//一共m条边
    if (color[a[i]] != color[b[i]]) {//如果两条边的两个端点不在一个强连通分量里面， 那么我们在这两个点之间连一条边
        adde(color[a[i]], color[b[i]], z[i]);
    }
}
//等于用剩下的信息建了一张新图

树

LCA

树上倍增
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
void bfs() {
    t = log(n)/log(2);
    queue<int> q;
    d[s] = 1;
    q.push(s);
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i];
            if (d[y]) continue;
            d[y] = d[x]　＋ 1;
            f[y][0] = x;
            for (int j=1;j<=t;++j) {
                f[y][j] = f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}
int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i=t;i>=0;--i) {
        if (d[f[y][i]] >= d[x])	y = f[y][i];
    }
    if (x == y) return x;
    for (int i=t;i>=0;--i) {
        if (f[y][i] != f[x][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}
Tarjan算法离线求LCA
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
void init() {
    int a, b;
    for (int i=1;i<n;++i) {
        a = Read(); b = Read();
        adde(a, b); 
        adde(b, a);
    }//一棵树n-1条边
    for (int i=1;i<=k;++i) {
        a = Read(); b = Read();
        qadde(a, b);
        qadde(b, a);
    }//k个询问
    for (int i=1;i<=n;++i) f[i] = i;
}
void Tarjan(int x) {
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (vis[ver[i]])  continue;
        tarjan(ver[i]);
        f[ver[i]] = x;
    }
    for (int i=qhead[x]; i; i=Next[i]) {
        if (vis[qver[i]]) 
            ans[edge[i]] = getf(qver[i]);
    }
}

树的直径

1
2
3
4
5
6
7
8
9
10
11
12
void dp(int x) {
    vis[x] = true;
    for(int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);//d数组的含义是从x节点出发走向x的子树， 所能到达的最远距离。
        //那么树上最长链的距离即为从x到x的子节点yi的距离加上x到x的子节点yj的距离加上d[yi]再加上d[yj]即可
        //d[x]中存的是从x走向他的前i个子节点最长的路径， 再加上当前的点到它子节点最长的路径即可得到x所在链的长度， 取一下max即为最长链的长度， 即为树的直径
    }
}

树的重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int x) {//树的重心的定义就是将该点删去之后所形成的最大的子树最小的那个点
    vis[x] = true;
    size[x] = 1;//子树x的大小
    int max_part = 0;//删掉子树x后分成的最大子树的大小
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y])	continue;
        dfs(y);
        size[x] += size[y];//从子节点向上更新
        max_part = max(maxn_part, size[y]);//x的子节点中最大的那个节点的size
    }
    	max_part = max(maxn_part, n - size[x]);//现在max_part中储存的是该节点删去之后形成的若干个子树最大的那个的大小 
    //n - max_part里存的是x向上连接他的父亲节点的那一棵子树的大小。
    if (max_part < ans) {
        ans = max_part;
        pos = x;
    }
}

树的各点子树的大小

1
2
3
4
5
6
7
8
9
10
void dfs(int x) {
    vis[x] = true;
    size[x] = 1;
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dfs(y);
        size[x] += size[y];
    }
}

树的各点的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int x) {
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i) {
        int y = ver[i];
        if (vis[y])	continue;
        d[y] = d[x] + 1;
        dfs(y);
    }
}
void bfs(int x) {
    memset(d, 0, sizeof(d));
	queue<int> q;
    d[x] = 1; q.push(x);
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x];i;i=Next[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
}

数论

Gcd 和 Lcm

1
2
3
4
5
6
int gcd(int a, int b) {
    return b? gcd(b, a%b) : a;
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

线性筛求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll prime[maxn]， size = 0;
bool vis[maxn]; 
inline void init() {
    memset(vis, true, sizeof(vis));
    memset(prime, 0, sizeof(vis));
    vis[1] = false;
    for (int i=2;i<=n;++i) {
        if (vis[i]) prime[++size] = i;
        for (int j=1;j<=size&&i*prime[j]<=n;++j) {
            vis[i*prime[j]] = false;
            if (i % prime[j] == 0)	break;
        }
    }
}//时间复杂度O(n)

EXGCD

1
2
3
4
5
6
7
8
9
10
11
12
void Exgcd(int a, int b, int& d, int& x, int& y) {
    if (!b) {
        x = 1;
        y = 0;
        d = a;
        return;
    }
    int x1, y1;
    Exgcd(b, a%b, d, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;  
}

求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//如果p是素数那么可以使用小费马定理
int inv(int a, int p) {
	return = power(a, p - 2, p);    
}
//如果p不是素数那么可以使用EXgcd
int inv(int a, int p) {
	int x, y, d;
    exgcd(a, p, d, x, y);
    return d == 1 ? (a + p)% p : -1;
}//如果返回-1则这个数没有逆元
//如果要求出n以内所有在膜p情况下的的逆元,可以线性递推
void inv(int n, int p) {
    inv[1] = 1;
    for (int i=2;i<=n;++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
}

快速幂

1
2
3
4
5
6
7
8
int power(int a, int b, int p) {
    int res = 1 % p;
    for(; b; b >>= 1) {
        if (b & 1) res = (long long)res * a % p;
        a =(long long)a * a % p;
    }
    return res;
}

龟速乘

1
2
3
4
5
6
7
8
ll Mul(ll a, ll b, ll p) {
    ll res = 0;
    for(; b; b >>= 1) {
        if (b & 1) res = (res % p + a % p) % p;
        a = (a << 1) % p;
    }
    return res;
}//可以防止两数相乘过大炸掉long long

组合数学

1
2
3
4
5
6
7
8
9
10
void init() {
    memset(c, 0, sizeof(c));
    c[1][0] = c[1][1] = 1;
    for (int i=2;i<=maxn;++i) {
        c[i][0] = c[i][i] = 1;
        for (int j=1;j<i;++j) {
            c[i][j] =(c[i-1][j] % mod + c[i-1][j-1] % mod)% mod;
        }
    }
}

矩阵乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Mat {
    a[maxn][maxn];
}A, e;
Mat Mul(Mat x, Mat y) {
    Mat c;
    for (int i=1;i<=n;++i)
    for (int j=1;j<=n;++j)
        c.a[i][j] = 0;
   	for (int k=1;k<=n;++k)
	for (int i=1;i<=n;++i)	
	for (int j=1;j<=n;++j)
        c.a[i][j] = c.a[i][j] % mod + (x.a[i][k] * y.a[k][j] % mod) % mod;
    return c;
}
Mat power(Mat x, int p) {
    Mat ans = e;
    for (; b; b>>=1) {
        if (b & 1) ans = Mul(ans, a);
        a = Mul(a, a);
    }
    return ans;
}

数据结构

链表

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
32
33
34
inline void init() {
    a[1].pre = 0;
    a[1].next = -1;
    a[0].next = 1;
    a[0].pre = -1;
}
inline void insert(int x, int k, int p) {
    if (p == 1) {
        a[x].pre = k;
        a[x].next = a[k].next;
        a[a[k].next].pre = x;
        a[k].pre = x;
    }else {
        k = a[k].pre;
        a[x].pre = k;
        a[x].next = a[k].next;
        a[a[k].next].pre = x;
        a[k].next = x;
    }
    return;
}//在k的前或者后面插入一个值为x的点
//p == 1 时表示在k的后面插入了x
//p == 0 时表示在k的前面插入了x
inline void del(int x) {
    if (a[x].pre != -1) {
        a[a[x].pre].next = a[x].next;
        a[a[x].next].pre = a[x].pre;
        a[x].pre = -1;
    }
}
//一个数的pre为-1表示这个点已经被删除
for (int i=a[0].next;i!=-1;i=a[i].next) {
    //一个链表的遍历
}

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//STL
queue<int> q;

q.push(x);
q.pop();
int x = q.front();
int size = q.size();
bool is_empty = q.empty();

//手写一个队列
inline void init(){
    head = 0; tail = 0;
	memset(q, 0, sizeof(q));
}
inline void push(int x) {q[++tail] = x;}
inline void pop()		{head++;}
inline int  front()		{return q[tail];}
inline bool empty()		{return head >= tail;}
inline int 	size()		{return tail - head;}

优先队列

1
2
3
4
5
6
7
8
9
10
//STL
priority_queue<int> q;
priority_queue<int, vector<int>, greater<int> > q;

q.push(x);
q.pop();
int x = q.top();
int size = q.size();
bool is_empty = q.empty();
//不会手写

栈

1
2
3
4
5
stack<int> s;
s.push(x);
s.pop();
int x = s.top();
bool is_empty = s.empty();

单调队列

1
2


单调栈

1
2


Hash表

1
2
3
4
5
6
7
unsigned long long h(char s[]) {
    int len = strlen(s);
    unsigned long long ans = 0;
    for (int i=0;i<len;++i) 
		ans += ans * 131 + (unsigned long long)(s[i] - 'a' + 1);
	return ans;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void prekmp() {
    m = strlen(b + 1);
    Next[1] = 0;
    for (int i=2,j=0;i<=m;++i) {
        while(j && b[i] != b[j + 1])j = Next[j];
        if (b[i] == b[j + 1]) ++j;
        Next[i] = j;
    }
}
void kmp() {
    n = strlen(a + 1);
    for (int i=1,j=0;i<=n;++i) {
        while(j && a[i] != b[j + 1])j = Next[j];
        if (a[i] == b[j + 1]) ++j;
        if (j == m) {
            ++ans;
            printf("%d\n", i - m + 1);
            j = Next[j];
        }
    }
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void add(int x, int v) {
    for (; x <= n; x += x & (-x))	c[x] += v;
}
inline int ask(int x) {
    int res = 0;
    for (; x; x -= x & (-x))	res += c[x];
    return x;
}
inline void init() {
    for (int i=1;i<=n;++i)	add(i, a[i]);
}
inline int sum(int x, int y) {
    return ask(y) - ask(x - 1);
}
add(x, v);//单点修改x加上v
int sum = sum(a, b)//区间求和， 从a到b的区间
//区间修改，区间求和
inline void change(int l, int r, ll d) {
	    
}

线段树

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct Segment {
    int l, r;
    ll dat, add;
    #define l(x)	tree[x].l
    #define r(x)	tree[x].r
    #define dat(x)	tree[x].dat
    #define add(x)	tree[x].add
}tree[maxn << 2];
int a[maxn];

inline void update(int p) {
    dat(p) = dat(p<<1) + dat(p<<1|1);
}
void build(int p, int l, int r) {
    l(p) = l; r(p) = r;
    if (l == r) {dat(p) = a[i];return;}
    int mid = (l + r) >> 1;
    build(p<<1,	l, mid);
    build(p<<1|1,mid+1, r);
    update(p);
}
void spread(int p) {
    if (add(p)) {
        dat(p<<1) += add(p) * (r(p<<1) - l(p<<1) + 1);
        dat(p<<1|1) += add(p) * (r(p<<1|1) - l(p<<1|1) + 1);
        add(p<<1) += add(p);
        add(p<<1|1) += add(p);
        add(p) = 0;
    }
}
void change(int p, int l, int r, int d) {
    if (l <= l(p) && r >= r(p)) {
        dat(p) += (long long)d * (r(p) - l(p) + 1);
        add(p) += d;
        return;
    }
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    if (l <= mid)	change(p<<1, l, r, d);
    if (r > mid)	change(p<<1|1, l, r, d);
    update(p);
}
long long ask(int p, int l, int r) {
    if (l <= l(p) && r >= r(p))	return dat(p);
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    long long res = 0;
    if (l <= mid)	res += ask(p<<1, l, r);
    if (r > mid)	res += ask(p<<1|1, l, r);
    return res;
}

分块

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
32
33
34
void build() {
    block = sqrt(n);
    num = n / block;  if (n % block) num++;
    for (int i=1;i<=num;++i)
        l[i] = (i - 1) * block + 1, r[i] = i * block;
    r[num] = n;
    for (int i=1;i<=n;++i) {
        a[i] = Read();
        belong[i] = (i - 1) / block + 1;
        sum[belong[i]] += a[i];
    }
}
void add(int x, int y, int d) {
    for (int i=x;i<=min(x, r[belong[x]]);++i) 
        a[i] += d, sum[belong[i]] += d;
    if (belong[x] != belong[y]) {
        for (int i=l[belong[y]];i<=y;++i)
            a[i] += d, sum[belong[i]] += d;
    }
    for (int i=belong[x]+1;i<=belong[y]-1;++i)
        sum[i] += block * d, tag[i] +=d;
}
int ask(int x, int y) {
    ll ans = 0;
    for (int i=x;i<=min(x, r[belong[x]]);++i) 
        ans += tag[belong[i]] + a[i];
    if (belong[x] != belong[y]) {
        for (int i=l[belong[y]];i<=y;++i)
            ans += tag[belong[i]] + a[i];
    }
    for (int i=belong[x]+1;i<=belong[y]-1;++i)
        ans += sum[i];
    return ans;
}

搜索

Dfs

1
2
3
4
5
6
7
8
void dfs(int x) {
    if (x > n) {
        ...
        return;
    }
    ...
	dfs(x + 1);
}

Bfs

1
2
3
4
5
6
7
8
9
void bfs(int x) {
    queue<int> q;
    q.push(x);
    while(q.size()) {
        int x = q.front();
        ...
        q.push(...);
    }
}

迭代加深

1
2


其他

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//求小于等于x最大的那一个
inline bool check(int x) {
    if (...) return true;
    else return false;
}
int work() {
    int l = 0; r = max_n;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid))	l = mid;
        else r = mid - 1;
    }
    return l;
}
//求大于等于x的最小的那一个
int work() {
    int l = 0; r = max_n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

发表于 | 阅读次数:
字数统计: 515 字

OJ3539

这是一道同余类bfs。 思路就是构造a个点，为什么只要a个呢？是因为如果能到达某个0~a-1的点x，那么x+a，x+2a ….等都可以到达。然后我们考虑从x出发，可以到达x+b与x+c，所以我们将x与x+b，x+c分别相连，权值分别为b,c，然后跑一次最短路，得到的dis[x]一定是最早能到达的点，然后dis[x]+a,dis[x]+2 a也都一定可以到达，并且也用上了b，c所能做的共献。（在a的同余类中的点只要加上k倍的a，就可以遍历整个整数集）

Code:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <queue>
#define up(i, j, k) for (int i=j;i<=k;++i)
#define down(i, j, k) for (int i=j;i>=1;--i)
#define Anto(i, x) for (int i=head[x];i;i=Next[i])
using namespace std;
typedef long long ll;
const ll maxn = 100010;
const ll INF = 1000000007;
ll n, a, b, c;
ll dis[100010];
ll head[maxn<<1], ver[maxn<<1], edge[maxn<<1], Next[maxn<<1], tot;
bool vis[maxn<<1];
inline void adde(ll x, ll y, ll z) { 
	Next[++tot] = head[x]; head[x] = tot;
	ver[tot] = y; edge[tot] = z;
}
ll Read() {
	ll x=0,f=1;char ch=getchar(); 
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void bfs() {
	memset(dis, 0x3f, sizeof(dis));
	queue<ll> q;	q.push(1);
	dis[1%a] = 1; vis[1%a] = true;
	while(!q.empty()) {
		ll x = q.front(); 	q.pop();
		vis[x] = false;
		Anto(i, x) {
			ll y = ver[i]; 
			if (dis[y] > dis[x] + edge[i]) {
				dis[y] = dis[x] + edge[i];
				if(!vis[y]) q.push(y), vis[y] = true;
			}
		}
	}
}
int main() {
	n = Read(); a = Read(); b = Read(); c = Read();
	if(a > b) swap(a, b); if(a > c) swap(a, c);
	for (ll i=0;i<a;++i) {
		adde(i, (i+b)%a, b);
		adde(i, (i+c)%a, c);
	}
	bfs();
	ll ans = 0;
	for (ll i=0;i<a;++i) {
		if (dis[i] <= n)ans += (long long)(n - dis[i])/a + 1;
	}
	printf("%lld", ans);
	return 0;
}

发表于 | 阅读次数:
字数统计: 2,295 字

正好有空来整理一下关于组合数学相关的知识点

加法原理

加法法则其实就像字面意思一样， 我们对于按照顺序选择的一些事件， 方案数可以直接相加。百度的官方解释是：

设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。其中，事件A和事件B是互斥的。

这个还是很好理解的。
如果我们设A集合的元素个数为|A|，B的元素个数为|B|，那么加法原理的公式表示就是这个样子的：

需要注意的是，加法原理的使用必须满足两个集合中没有重复元素的情况下使用。如果存在重复的元素， 那么必须减去重复计算的元素才能得到正确的数量。

阅读全文 »