月度归档：2017年11月

OI退役

有一大堆话想说，但又不知道从何下笔，于是就随便写写吧，说到哪里就算哪里。

2017年11月11日和12日，是我整个中学阶段参加的第二次NOIP，也是我最后一次参加NOIP。这次复赛，我考得比较糟糕，Day1的T1考了一道小学奥数题，这道题把我的思路全部打乱，本来想用扩展欧拉定理（前一天刚刚抱佛脚学的），结果死活也出不来，整场考试有相当一部分时间在想这个，结果导致T3虽然有暴力分，也根本没时间敲。T2是道大模拟，本来应该比较轻松的AC的，但恰好因为T2出题人卡了输入，而我没有准确的而灵活的掌握scanf的输入字符串用法；以及没有准确的掌握结构体赋值运算符重载，而且当时考试时的由于T1的没做出来而紧张，思路错误，本来应该用栈实现，结果搞了个DFS，结果也肯定过不去，所以导致Day1整个崩掉。还好，在考试结束前半个小时突然来了个灵感，找到了答案的表达式，和暴力做法对拍了一下，发现结果是正确的，然后就交了T1，应该是可以AC的，所以预计Day1总分100。T2被卡输入的人也许也不在少数，但是也有不少人AC，所以总体来说，Day1的暴力分数应该达到220分左右。而Day2，我只能说自己发挥勉强正常；T1本来是冲着AC去的，结果考试出来有人说算空间距离必须用double/unsigned long long，而我用的是long long，有可能被卡掉20分，这个会不会卡掉要看数据/命题人是否善良了。而T2本来想写满分的，结果搜索的回溯写出问题了，最后不得已用了个贪心+并查集求个最小生成树，预计得分只能是20分；这道题大部分人的得分应该是70或者100，可惜我写挂了，并不知道这个该怎么写，后来有人说函数传个vector，我是不敢在函数里传vector的，也根本没想到这条路。T3是个树状数组，然而虽然会裸的树状数组维护，然而并没看出来，而且匆匆忙忙打完T2，时间也不够了。所以T3只能匆匆忙忙打个暴力，目测30分，还不知道这30分的数据会不会被卡掉。所以Day2预计得分130。Day2暴力分应该是200。所以总体上加起来两天暴力分数400，而我就打了230左右。这个和理想的分数400还差的很远。估计今年省一的分数线还要涨，而且保不定230哪里写挂了就要扣分……所以目测省一是没希望了……现在再拜佛烧香也来不及了，只能听天由命了……

说起我第一次编程序还要追溯到小学高年级，而第一次知道OI竞赛则是在初中，初中那时在搞网络/服务器/网站一类的东西，于是就入了这个计算机的中学生网络圈子，正好里面有南方的学生在搞这个，于是我听到这个还很羡慕啊，也想参加这个竞赛……后来在上高一之前的那个暑假开学之前几天想要报名NOIP，结果找到北京OI官网时，发现报名已经截止了……，于是就错失了高一参加比赛的报名机会。后来在2016年2月28日，又给北京市的CCF特派员邮箱发了一个邮件，询问报名NOIP的相关事宜。然而当时的我并不知道，这个时候恰恰是NOIP2015结束好长一段时间之后，而且离NOIP2016还有几个月，根本没人看工作邮箱，这个事情就被搁置下来。当时我个人发邮件特派员根本没人搭理，所以我还以为必须集体报名，后来进了圈子以后发现其实是可以自己报名的，但是你必须挑准合适的时间报名咨询。在这里给北京的同学指条明路，不要在绕弯子了（北京OI奥赛官网http://oi.student.gov.cn/，直接把地址复制到浏览器里，里面有北京信息学奥赛报名的各项信息）。我比较幸运的一点是，有了北京市翱翔计划的支持，通过翱翔计划联系到了负责八十中奥赛的贾老师，贾老师同意为我报名NOIP，于是我就在高二的周末抽出课余的时间看MOOC，如果你想学习信息学奥赛的话，个人推荐MOOC（也是我自己看的）：（按照难度顺序递增）中国大学MOOC(icourse163)北京大学郭炜：程序设计与算法（一）C语言程序设计、程序设计与算法（二）算法基础。（程序设计与算法（三）C++面向对象程序设计不要看，竞赛用不上面向对象）；浙江大学陈越数据结构。学堂在线：清华大学邓俊辉（数据结构）上、下。这三个MOOC。这三个MOOC都有配套的C++程序练习题，一定要跟着做完。OI考试最重要考察的就是你的编码能力。然后呢，如果想考验一下自己的编程能力可以去参加浙江大学陈越主办的PAT考试（Program Ability Test），北京有北工大考点，分为三个级别（顶级、甲级、乙级），PAT比赛都有比较好的集成开发环境（IDE），支持Visual Studio，调试起来非常方便，赛制是IOI赛制，支持实时评测（标准输入输出）并查看分数，但是OI赛制（NOIP）可不是这样的，只能最后提交，全国统一评测（文件输入输出）。这个比赛能够稍稍贴近NOIP的考试环境，可以让你适应考试，同时也可以测试你的数据结构/算法功底。当你能够达到乙级满分时，说明你有了基本的编程思想。当你能够达到甲级满分时，恭喜你，你最少应该能够达到NOIP省三的水平了，但是也不要急着参加NOIP，水平还是达不到的。（说实话，这个PAT是大学毕业后找工作用的……可见普通程序员对算法/数据结构的要求之低，因为普通程序员只要做应用就行了，不需要算法的思想）（PAT的往期题库可以在及PAT考试官网patest.cn找到）然而这些都不够，所有的三门MOOC中没有一门讲授动态规划的思想……所以到现在仅凭自学，我基本上不会任何DP。。当然仅凭这三个MOOC对于数据结构/算法介绍，来对付NOIP也是不够的，你还需要自学树状数组/线段树等。当然，这三个MOOC中，也有一些数据结构是在国家级比赛(NOI)甚至世界级比赛(IOI)根本用不到的，比如红黑树，编写起来太难了。而有的则需要在省选时用到，比如Splay，当然，如果你能仅凭自己走到省选那一步，那实在是非常厉害。不过我觉得你要是能省选，应该是有教练的，这样的话，你就没必要看这篇文章了，你的教练肯定要比我经验丰富的多。除了PAT考试之外，还有CCF举办的CSP测试，和PAT是同一性质，在此不加详述，有兴趣的自学同学可以在网上搜索打听一下。于是在经历了这一系列课余的学习与考了几场PAT测试与CSP测试之后，我就独自来到了NOIP2016的舞台，先是有惊无险的以倒数的名次过了NOIP2016的初赛，然后就参加NOIP2016的复赛。当时我连搜索都不怎么会，因为去年的NOIP2016比较简单，然后我就拿到了209的分数，得了2=。今年是高三了，我想最后拼搏一把，就报名了NOIP2017，在复赛考试之前一个月开始请假周六周日参加模拟赛，再在考前一周请整周的假期练习。结果今年的题出成这样，然后我就挂的貌似差不多了。。希望CCF给我开开恩啊……对于想要参加NOIP的选手来说，在这些都做完之后，一定要在各大OJ刷题，我个人帮洛谷OJ打个广告，非常好的一个OJ，管理员人比较好，而且肯下功夫维护。并且除了练习基础题之外，一定要抽时间写一些NOIP真题！NOIP真题是非常重要的！

我的OI一路走来这么长的时间，所有东西都是我抽时间在课余学习的，而且是贯穿了整个高中时光的休息时间，这么紧张的时候，我也没有教练培训，能坚持下来是为什么呢？要是纯是为了功利，我自己肯定早就放弃了。其实大部分OIer能够坚持下来，或者说大部分竞赛生能坚持下来，都是因为自己的志趣在此（用个文雅的词语）。。或者说是兴趣。。其实我也不知道我的兴趣是怎么来的……也许可能就是小时候一件不经意的计算机小事激发了我的斗志，然后完成了它，带给了我一种成就感。然后就一发不可收拾，走上了这条道路。当然这其中也不乏功利的成分，要是竞赛奖项没用的话我可能就不参加高三的NOIP了……但是更更主要的是个人的成就感推动着你走上这条路，形成一个良性循环。所以说，一个人为什么喜欢做一件事，享受做一件事？因为这能够给他带来满足感、快乐感、成就感。要想让人干一件什么事，总是得有点快乐才行的。。

从此以后，我就真正的算作OI退役选手了。在去年参加NOIP之前，我还在想，我能否真正的算作一个OI选手呢？也没有教练，什么都没有，还是自己看的MOOC，什么都没怎么学，甚至连一次课都没有停过，就随随便便的得了2=。这样怎么能算真正的OI选手呢？但是今年NOIP2017参加过之后，我相信自己已经真正的成为了一名OI退役选手了，或者说曾经当过OI选手，哪怕我今年NOIP爆零我都是一名真正的OI选手，因为我真正的为我所钟爱的梦想的NOIP2017信息学奥赛而奋斗、努力过。有高一周末时天天看MOOC学习数据结构算法，也有我贯穿整个高中的刷题与调试程序、更有我高二复赛前请假准备、最有高三复赛前一个月周末请假，复赛前一周周末刷题的疯狂。尽管我今年的暴力可能打爆了，也可能得不到一等奖，或者是什么奖都拿不到，我也是一名真正的OI选手。结果固然重要，得一等奖固然重要，但是得不到一等奖也没有办法，但更加重要的是这种过程，至少给我留下了我努力的回忆，让自己不留遗憾。这种感觉也许是没有曾经全身心/志趣投入到一件事的人无法领会的吧。写到这里，真的想落泪了……

整篇文章写完了，希望各个部分能对不同的人有所裨益。第一段也许是给想看NOIP2017题解的人留的，第二段也许是给没有教练带着的自学OIer的，第三段也许能够给各位老师、家长或者任何用心阅读的人一点心灵上的触动与启发，第四段献给自己。也许我身边的人无法领会，但是这段美好的回忆会始终留在我的脑海中……永远也不会消失。

我的OI生涯虽然退役了，但是编程的爱好却永远不会消逝，因为高三的原因，对于计算机可能会暂停一段时间，但上了大学之后，我如果有时间的话，一定会参加ACM竞赛，继续编程之路。

最后非常感谢各位曾经对我OI生涯有过支持的人。包括我的父母，我的翱翔计划基地校老师贾老师（竞赛老师lsl,lxl），他在帮助我参加NOIP竞赛上给予了我极大的帮助，还有我翱翔计划的导师罗老师，以及我们中学的计算机老师赵老师，以及twd2,kkksc03,ltt等各位OJ站长，各位八十中同学zx,cjr，在北京独自作战的hzr，厦门的cyy，以及所有过去曾经解答过我OI问题的同学。

我的高中计算机生涯，就算没得一等奖，也圆满了。

唉，又想流泪了。。

PS：从来没写过一篇文章这么多字数……截止到现在已经4200+字数了。这一大段话我认为是我真情实感的最好表达了，之前一直想要表达也没能表达出来……今天终于一次性写出来了。。

Jack
写毕于 2017.11.12 23:39

注意：该文章请勿将文字复制转载，要转载请直接转发本文源链接，谢谢。

NOIP2017考前模版与考后写的D1T2

发表评论

考前模版

洛谷同余方程

发表评论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<bits/stdc++.h>
using namespace std;
long long exgcd(long long a, long long b, long long &x1, long long &y1){
if (b == 0){
x1 = 1; y1 = 0;
return a;
}
long long x, y;
long long r = exgcd(b, a%b, x, y);
x1 = y;
y1 = x - a / b*y;
return r;
}
int main(){
ios::sync_with_stdio(false);
long long a, b;
cin >> a >> b;
long long x, y;
exgcd(a, b, x, y);
cout << (x + b) % b;

}

做题做的心力憔悴
20180807更新：
exgcd证明过程参见：https://renjikai.com/cpp-number-theory/

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

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
ll d = exgcd(b, a%b, y, x);
y -= a / b * x;
return d;
}
int main() {
ll a, b, x, y;
cin >> a >> b;
exgcd(a, b, x, y);
cout << (x%b + b) % b;
}

洛谷机器翻译

发表评论

题号：1540

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

#include<bits/stdc++.h>
using namespace std;
int m, n;
int head = 0, tail = 0;
int arr[105];
int cnt;
int main(){
ios::sync_with_stdio(false);
cin >> m >> n;
m++;
for (int i = 0; i < m; i++){
arr[i] = -1;
}
for (int i = 1; i <= n; i++){
int word;
cin >> word;
bool flag = false;
for (int i = head; i != tail; i = (i + 1) % m){
if (arr[i] == word){
flag = true;
break;
}
}
if (!flag){
if (head == (tail + 1) % m)head = (head + 1) % m;
cnt++;
arr[tail] = word;
tail = (tail + 1) % m;
}
}
cout << cnt;
}

洛谷AC200题纪念

发表评论

祝愿自己NOIP2017取得最好成绩！

洛谷【模板】最近公共祖先（LCA）

发表评论

调了半天才调出来的东西啊……233，在写tarjan的循环时写错了，把_v_ask写成了_v，太容易写错了，一定要多加注意，这个模版还需要练习，线段树也是。。
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
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
61
62
63
64
65
66
67
68
69
70
71
72
73

#include<bits/stdc++.h>
#define MAXN 1000005
#define MAXM 1000005
#define EdgeLoop(e,node) for(int e=_first[node];e!=-1;e=_next[e])
#define EdgeAskLoop(e,node) for(int e=_first_ask[node];e!=-1;e=_next_ask[e])
int n, m, s;
int _father[MAXN];
int graph_m_ptr = 0, graph_m_ptr_ask = 0;
int _u[MAXN], _v[MAXN], _next[MAXN], _first[MAXN];
bool _visited[MAXN];
int _u_ask[MAXN], _v_ask[MAXN], _next_ask[MAXN], _first_ask[MAXN];
int _ans[MAXM];
int _find(int x){
if (_father[x] == x)return x;
return _father[x] = _find(_father[x]);
}
void _merge(int x, int y){//merge y branch to x branch
_father[_find(x)] = _find(y);
}
void insert_edge(int s, int t){
_u[graph_m_ptr] = s;
_v[graph_m_ptr] = t;
_next[graph_m_ptr] = _first[s];
_first[s] = graph_m_ptr;
graph_m_ptr++;
}
void insert_edge_ask(int s, int t){
_u_ask[graph_m_ptr_ask] = s;
_v_ask[graph_m_ptr_ask] = t;
_next_ask[graph_m_ptr_ask] = _first_ask[s];
_first_ask[s] = graph_m_ptr_ask;
graph_m_ptr_ask++;
}
void tarjan(int u){
_visited[u] = true;
EdgeLoop(e, u){
if (!_visited[_v[e]]){
tarjan(_v[e]);
_merge(_v[e],u);
}
}
EdgeAskLoop(e, u){
if (_visited[_v_ask[e]]){
_ans[e/2] = _find(_v_ask[e]);
}
}
}
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin >> n >> m >> s;
for (int i = 1; i <= n; i++){
_father[i] = i;
}
memset(_first, -1, sizeof(_first));
memset(_first_ask, -1, sizeof(_first_ask));
for (int i = 1; i <= n - 1; i++){
int x, y;
cin >> x >> y;
insert_edge(x, y);
insert_edge(y, x);
}
for (int i = 1; i <= m; i++){
int a, b;
cin >> a >> b;
insert_edge_ask(a, b);
insert_edge_ask(b, a);
}
tarjan(s);
for (int i = 0; i < m; i++){
cout << _ans[i] << endl;
}
}

树上倍增：

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
61
62
63
64
65

#include<bits/stdc++.h>
using namespace std;
int edge_ptr = 0;
struct edge{
int v;
int next;
}edges[1000005];
int head[500005];
int n, m, s;
int father[500005][25],depth[500005];
bool visited[500005];
inline void insert_edge(int s,int t){
edge_ptr++;
edges[edge_ptr].v = t;
edges[edge_ptr].next = head[s];
head[s] = edge_ptr;
}
inline void dfs(int u){
visited[u] = true;
for (int i = 1, len = 1; len <= depth[u]; i++, len <<= 1){
father[u][i] = father[father[u][i - 1]][i - 1];
}
for (int e = head[u]; e != -1;e=edges[e].next){
if (!visited[edges[e].v]){
depth[edges[e].v] = depth[u] + 1;
father[edges[e].v][0] = u;
dfs(edges[e].v);
}
}
}
inline int query(int x, int y){
if (depth[x] > depth[y])swap(x,y);
int diff = depth[y] - depth[x];
for (int i = 0, two = 1; diff != 0; two <<= 1, i++){
if (diff&two){
y = father[y][i];
diff -= two;
}
}
if (x == y)return x;
for (int i = log2(depth[x]); i >= 0; i--){
if (father[x][i] != father[y][i]){
x = father[x][i];
y = father[y][i];
}
}
return father[x][0];
}
int main(){
ios::sync_with_stdio(false);
memset(head, -1, sizeof(head));
cin >> n >> m >> s;
for (int i = 1; i <= n - 1; i++){
int x, y;
cin >> x >> y;
insert_edge(x, y);
insert_edge(y, x);
}
dfs(s);
for (int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
cout << query(x, y) << endl;
}
}

洛谷【模板】线段树 1

发表评论

题号：P3372

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cassert>
#include<vector>
#include<list>
#include<stack>
#include<queue>
struct node{
long long value;
long long lazymark;
}segment_tree[400005];
void build(int root, long long * arr, int start, int end){
segment_tree[root].lazymark = 0;
if (start == end){
segment_tree[root].value = arr[start];
return;
}
int mid = (start + end) / 2;
build(root * 2 + 1, arr, start, mid);
build(root * 2 + 2, arr, mid + 1, end);
segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}
void pushdown(int root,int start,int end){
if (segment_tree[root].lazymark == 0)return;
int mid = (start + end) / 2;
segment_tree[root * 2 + 1].lazymark += segment_tree[root].lazymark;
segment_tree[root * 2 + 2].lazymark += segment_tree[root].lazymark;
segment_tree[root * 2 + 1].value += segment_tree[root].lazymark*(mid - start + 1);
segment_tree[root * 2 + 2].value += segment_tree[root].lazymark*(end - mid);
segment_tree[root].lazymark = 0;
}
long long query(int root, int cstart, int cend, int qstart, int qend){
if (qstart > cend || qend < cstart)return 0;
if (qstart <= cstart&&cend <= qend)return segment_tree[root].value;
pushdown(root,cstart,cend);
int cmid = (cstart + cend) / 2;
return query(root * 2 + 1, cstart, cmid, qstart, qend) + query(root * 2 + 2, cmid + 1, cend, qstart, qend);
}
void update(int root, int cstart, int cend, int ustart, int uend, long long addvalue){
if (cend < ustart || uend < cstart)return;
if (ustart <= cstart&&cend <= uend){
segment_tree[root].value += addvalue*(cend - cstart + 1);
segment_tree[root].lazymark += addvalue;
return;
}
pushdown(root,cstart,cend);
int cmid = (cstart + cend) / 2;
update(root * 2 + 1, cstart, cmid, ustart, uend, addvalue);
update(root * 2 + 2, cmid + 1, cend, ustart, uend, addvalue);
segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}

using namespace std;
int n, m;
long long arr[100005];
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> arr[i];
}
build(1, arr, 1, n);
while (m--){
int op;
cin >> op;
if (op == 1){
int x, y;
long long z;
cin >> x >> y >> z;
update(1, 1, n, x, y, z);
}
else{//op==2
int x, y;
cin >> x >> y;
cout << query(1, 1, n, x, y) << endl;
}
}
}

zcysky标程：

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

#include<bits/stdc++.h>
const int N=100005;
typedef long long ll;
using namespace std;
int a[N],n,m;
inline ll read(){
ll f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
ll sumv[N<<2],addv[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}
inline void pushdown(int o,int l,int r){
if(!addv[o])return;
ll tag=addv[o];addv[o]=0;int mid=(l+r)>>1;
addv[lson]+=tag;addv[rson]+=tag;
sumv[lson]+=tag*1LL*(mid-l+1);sumv[rson]+=tag*1LL*(r-mid);
}
inline void build(int o,int l,int r){
if(l==r){sumv[o]=a[l];return;}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(o);
}
inline void optadd(int o,int l,int r,int ql,int qr,ll v){
if(ql<=l&&r<=qr){sumv[o]+=v*1LL*(r-l+1);addv[o]+=v;return;}
int mid=(l+r)>>1;pushdown(o,l,r);
if(ql<=mid)optadd(lson,l,mid,ql,qr,v);
if(qr>mid)optadd(rson,mid+1,r,ql,qr,v);
pushup(o);
}
inline ll querysum(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sumv[o];
pushdown(o,l,r);
int mid=(l+r)>>1;ll ans=0;
if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
if(qr>mid)ans+=querysum(rson,mid+1,r,ql,qr);
return ans;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
build(1,1,n);
while(m--){
int opt=read(),l=read(),r=read();
if(opt==1){
ll k=read();optadd(1,1,n,l,r,k);
}
else printf("%lld\n",querysum(1,1,n,l,r));
}
}

20180816更新：

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
61
62
63

#include<iostream>
using namespace std;

struct segmentTree{
typedef long long ll;
const static ll MAX=100000;
ll v[4*MAX],m[4*MAX];
inline static ll lson(ll r){return r*2+1;}
inline static ll rson(ll r){return r*2+2;}
void build(ll r,ll * a,ll s,ll e){
m[r]=0;
if(s==e){v[r]=a[s];return;}
ll md=(s+e)>>1;
build(lson(r),a,s,md);
build(rson(r),a,md+1,e);
v[r]=v[lson(r)]+v[rson(r)];
}
void pushDown(ll r,ll s,ll e){
if(m[r]==0)return;
ll md=(s+e)>>1;
m[lson(r)]+=m[r];
m[rson(r)]+=m[r];
v[lson(r)]+=m[r]*(md-s+1);
v[rson(r)]+=m[r]*(e-md);
m[r]=0;
}
ll query(ll r,ll cs, ll ce,ll qs,ll qe){
if(qe<cs||ce<qs)return 0;
if(qs<=cs&&ce<=qe)return v[r];
pushDown(r,cs,ce);
ll cmd=(cs+ce)/2;
return query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe);
}
void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv){
if(ce<us||ue<cs)return;
if(us<=cs&&ce<=ue){v[r]+=addv*(ce-cs+1);m[r]+=addv;return;}
pushDown(r,cs,ce);
ll cmd=(cs+ce)>>1;
update(lson(r),cs,cmd,us,ue,addv);
update(rson(r),cmd+1,ce,us,ue,addv);
v[r]=v[lson(r)]+v[rson(r)];
}
}ST;
typedef long long ll;
ll n,m;
ll a[100005];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
ST.build(1,a,1,n);
for(int i=1;i<=m;i++){
int op,x,y,k;
cin>>op;
if(op==1){
cin>>x>>y>>k;
ST.update(1,1,n,x,y,k);
}else{
cin>>x>>y;
cout<<ST.query(1,1,n,x,y)<<endl;
}
}
}

洛谷车站分级

发表评论

题号：P1983
算法标签：拓扑排序
洛谷题解地址：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1983
参考题解：作者: chenshaoqian 更新时间: 2016-09-25 21:08
作者: mangoyang 更新时间: 2016-09-24 17:20

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
61
62
63
64
65
66
67
68
69
70
71
72

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<list>
#include<stack>
using namespace std;
#define virtual_point_start 1000
int n, m;
int s[1005];
int virtual_point_ptr = virtual_point_start;
int indegree[3000];
int pass[1005][1005];
int path_dis[3000];
list<int> edge[3000];
vector<int> t_edge_to;
stack<int> cur_level;
bool execute(){
while (!cur_level.empty())cur_level.pop();
for (int i = 1; i <= n; i++){
if (indegree[i] == 0){
cur_level.push(i);
indegree[i] = -1;
}
}
for (int i = 1001; i <= virtual_point_ptr; i++){
if (indegree[i] == 0){
cur_level.push(i);
indegree[i] = -1;
}
}
if (cur_level.empty())return false;
while (!cur_level.empty()){
int cur = cur_level.top();
cur_level.pop();
for (list<int>::iterator iter = edge[cur].begin(); iter != edge[cur].end(); iter++){
indegree[*iter]--;
int point_dis = (cur <= 1000);
path_dis[*iter] = max(path_dis[*iter],path_dis[cur] + point_dis);
}
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> s[i];
for (int j = 1; j <= s[i]; j++)cin >> pass[i][j];
t_edge_to.clear();
int ptr = 1;
for (int j = pass[i][1]; j <= pass[i][s[i]]; j++){
if (pass[i][ptr] == j)ptr++;
else t_edge_to.push_back(j);
}
virtual_point_ptr++;
for (vector<int>::iterator iter = t_edge_to.begin(); iter != t_edge_to.end(); iter++){
edge[virtual_point_ptr].push_back(*iter);
indegree[*iter]++;
}
for (int se = 1; se <= s[i]; se++){
edge[pass[i][se]].push_back(virtual_point_ptr);
indegree[virtual_point_ptr]++;
}
}
while (execute());
int ans = 0;
for (int i = 1; i <= n; i++){
ans = max(ans, path_dis[i]);
}
cout << ans+1;
}

20180814更新：
题解：https://www.luogu.org/blog/24212/solution-p1983
主要是借鉴了一个开一个二维数组判断边是否加重的问题。
还有一个最重要的就是“由停车的站向不停车的站连边”问题，总是考虑不到。

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

#include<iostream>
#include<vector>
using namespace std;
int n,m;
bool visited[1002][1002];
int inDegree[1002],grades[1002];
vector<int> edges[1002];
vector<int> railStation;
vector<int> unStopStation;
vector<int> curGrade;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++){
railStation.clear();
unStopStation.clear();
int num;
cin>>num;
for(int j=1;j<=num;j++){
int t;
cin>>t;
railStation.push_back(t);
}
for(int j=0;j<railStation.size()-1;j++){
for(int k=railStation[j]+1;k<railStation[j+1];k++){
unStopStation.push_back(k);
}
}
for(int j=0;j<railStation.size();j++){
for(int k=0;k<unStopStation.size();k++){
if(visited[railStation[j]][unStopStation[k]])continue;
visited[railStation[j]][unStopStation[k]]=true;
edges[railStation[j]].push_back(unStopStation[k]);
inDegree[unStopStation[k]]++;
}
}
}
int maxV=0;
do{
curGrade.clear();
for(int i=1;i<=n;i++){
if(inDegree[i]==0){
curGrade.push_back(i);
inDegree[i]--;
}
}
for(int i=0;i<curGrade.size();i++){
grades[curGrade[i]]++;
for(int j=0;j<edges[curGrade[i]].size();j++){
grades[edges[curGrade[i]][j]]=max(grades[edges[curGrade[i]][j]],grades[curGrade[i]]);
inDegree[edges[curGrade[i]][j]]--;
}
maxV=max(maxV,grades[curGrade[i]]);
}
}while(curGrade.size());
cout<<maxV;
}

洛谷海底高铁

发表评论

题号：P3406
把数据类型都开成long long，不然等着丢分？？

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

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
long long track_dif[100005], track[100005];
long long P[100005];
long long A[100005], B[100005], C[100005];
long long cost;
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> P[i];
}
for (int i = 1; i <= n - 1; i++){
cin >> A[i] >> B[i] >> C[i];
}
for (int i = 1; i <= m - 1; i++){
int l = min(P[i], P[i + 1]), r = max(P[i], P[i + 1]);
track_dif[l]++;
track_dif[r]--;
}
for (int i = 1; i <= n - 1; i++){
track[i] = track[i - 1] + track_dif[i];
}
for (int i = 1; i <= n - 1; i++){
cost += min(track[i] * A[i], C[i] + track[i] * B[i]);
}
cout << cost;
}

杰克部落

梦想本不会发光，发光的是追梦的你

月度归档：2017年11月

OI退役

NOIP2017考前模版与考后写的D1T2

洛谷同余方程

洛谷机器翻译

洛谷AC200题纪念

洛谷【模板】最近公共祖先（LCA）

洛谷【模板】线段树 1

洛谷车站分级

洛谷海底高铁

2017 年 11 月
一	二	三	四	五	六	日
		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