nocriz – 苔花如米小，也学牡丹开。

里程碑

上面这首歌本应是Jenny of Oldstones, 然而似乎有权限问题播放不了，那么就放另外一首吧。

Never wanted to leave, Never wanted to leave…
Jenny of Oldstones (Game of Throne)

信息学竞赛选手，往往退役之后会有一篇退役的文，我也如此。许多人将这篇文装点的像一个墓碑，似乎一切都结束了。在我眼中，这是一个里程碑，我仅仅退役了OI，而还有其他的算法竞赛要打，这也只是一个阶段性事件。

现在是星期六的下午三点二十五分，我还是坐在回学校的车上。下面分割线内的内容为省选直接结束后我写下的，那时候我的心态和现在差距很大。

JSOI 2019 二轮垫底记

现在是下午四点钟，我坐在回学校的火车上。经过一天的考试，我似乎神经已经抻直拉紧，再经不得一点波动。今天的比赛结果似乎很差，但是又没有那么差，于是或许我的成绩能够进队，如果我的计算没有出错的话。
既然看上去还没有退役，那么退役文自然是不会有的。
比赛比的很差，又似乎合情合理，就不再赘述了，当然题还是要补的，或许会把题解放上来。
T1不知道咋回事奇怪的假做法能得40
T2写了30，要T15去掉了，然后又挂了5pts，浪费大把时间
T3写了个30暴力。

唉……命运就是这样吧
下次加油。似乎目标就只有NOI了？

分割线

现在是下午7:19，我紧张的神经似乎已经舒展了一些。的确，我不希望一年半的OI生涯到这里就走到终点。大概算出自己能够进队的选手都会很高兴，但是我的心态确是忽上忽下不能平静，我只能坐在高铁上慢慢缓着，什么也不做。有时候我也在想，如果我2017年没能够成功报名上NOIP，现在的我又会在做什么？想想，绝对是在认真的学习文化课，学习数学和物理，并且尝试去做算法竞赛，但是课内内容的比重一定会更大。

感觉之前很迷信，一年之前，我问“强省弱校无学长无教练（去年没有）不停课选手有没有翻身机会”，自己感觉答案是没有。我还迷信需要集训才能变强，迷信需要在强校才能变强，迷信XXX是不可逾越的鸿沟。感觉学长和强的选手在身边的意义便是告诉你：XXX行，我也行，毕竟XXX又不是什么强的人，我和他也差不多。我似乎从来没有这样强的选手在身边，也感受不到这一点，直到自己去CTSC，看到所谓的“神仙”也是活生生的人，也并不是想象中的那样靠高强度的饱和训练获得成功。在我看到那些高水平选手仍然有时间学习自己的兴趣知识（与OI五官）或者发展特长，并能够和其他选手分享，我便觉得这真是一个理想的状态。许多强校的选手就有这个优势：举一个假想中的例子，现实中应该并不存在，但是也是很类似的：学校里有一个选手进了国家队，可能第二个选手觉得也“问题不大”，可能下一届的若干选手也觉得自己就是有这个潜力，于是这个学校第二年又进了好几个候选队。

事实上不是这样子的。我们可以考虑陈立杰和许多其他人的例子，只要会知识点就能做题，只要多打比赛做题速度就会增加，只要具有充分练习的思维能力就能够快速想题，这样就能快速做出一道题。一场比赛只要连续快速做出三道题就能够获得胜利（滑稽）。

如果你有兴趣搞OI，而且你在弱校，可以给你几个建议

可以首先定一个相当高的目标
自学就比较足够，如果没有条件停课集训不要气馁，可以加速自学

由于我也是比较弱的选手，可能这个建议也有不合适之处，您可以不必全信。让我们共同进步吧！

JSOI 2019 二轮垫底记

现在是下午四点钟，我坐在回学校的火车上。经过一天的考试，我似乎神经已经抻直拉紧，再经不得一点波动。今天的比赛结果似乎很差，但是又没有那么差，于是或许我的成绩能够进队，如果我的计算没有出错的话。

既然看上去还没有退役，那么退役文自然是不会有的。

比赛比的很差，又似乎合情合理，就不再赘述了，当然题还是要补的，或许会把题解放上来。

T1不知道咋回事奇怪的假做法能得40

T2写了30，要T15去掉了，然后又挂了5pts，浪费大把时间

T3写了个30暴力。

唉……命运就是这样吧

下次加油。似乎目标就只有NOI了？

分割线

现在是下午7:19，我紧张的神经似乎已经舒展了一些。的确，我不希望一年半的OI生涯到这里就走到终点。大概算出自己能够进队的选手都会很高兴，但是我的心态确是忽上忽下不能平静，我只能坐在高铁上慢慢缓着，什么也不做。有时候我也在想，如果我2017年没能够成功报名上NOIP，现在的我又会在做什么？想想，绝对是在认真的学习文化课，学习数学和物理，并且尝试去做算法竞赛，但是课内内容的比重一定会更大。

感觉之前很迷信，一年之前，我问“强省弱校无学长无教练（去年没有）不停课选手有没有翻身机会”，自己感觉答案是没有。我还迷信需要集训才能变强，迷信需要在强校才能变强，迷信XXX是不可逾越的鸿沟。感觉学长和强的选手在身边的意义便是告诉你：XXX行，我也行，毕竟XXX又不是什么强的人，我和他也差不多。我似乎从来没有这样强的选手在身边，也感受不到这一点，直到自己去CTSC，看到所谓的“神仙”也是活生生的人，也并不是想象中的那样靠高强度的饱和训练获得成功。在我看到那些高水平选手仍然有时间学习自己的兴趣知识（与OI五官）或者发展特长，并能够和其他选手分享，我便觉得这真是一个理想的状态。许多强校的选手就有这个优势：举一个假想中的例子，现实中应该并不存在，但是也是很类似的：学校里有一个选手进了国家队，可能第二个选手觉得也“问题不大”，可能下一届的若干选手也觉得自己就是有这个潜力，于是这个学校第二年又进了好几个候选队。

事实上不是这样子的。我们可以考虑陈立杰和许多其他人的例子，只要会知识点就能做题，只要多打比赛做题速度就会增加，只要具有充分练习的思维能力就能够快速想题，这样就能快速做出一道题。一场比赛只要连续快速做出三道题就能够获得胜利（滑稽）。

如果你有兴趣搞OI，而且你在弱校，可以给你几个建议

可以首先定一个相当高的目标

自学就比较足够，如果没有条件停课集训不要气馁，可以加速自学

由于我也是比较弱的选手，可能这个建议也有不合适之处，您可以不必全信。让我们共同进步吧！

在写下上面内容的时候，我还没有退役。然而我现在则是退役老年选手了，无论是心气还是动力都已经完全消除了。唉。大概分数固然足够不退役了，然而由于一些我无法改变的因素，还是退役了。详情可以看这里http://www.noi.cn/newsview.html?id=870&hash=B5DC8F&type=99

这是结束吗？我想不是。但是这的确像是结束：这一周我都颓而痛苦，无法做题，不仅仅一道题也没做，算法也没有学。省选题目也没有补，就像退役了一样。

这不是结束，这也不是开始的结束，这是开始进行到了一半而被斩断。

JSOI一轮/12省联考游记

游记

现在是星期三的夜里11:00，我终于有空闲下来写这篇早就应当写的游记了。我的确有许多所想，但囿于现状，恐怕不能够将这些想法都写在博客中。在我退役之后（很可能就在不远的将来，尽管），我将认真地写一篇更加发自真心的文章，从而为我信息学竞赛曲折的学习路程做一个小结。

省选是信息学竞赛中的一个重要节点，对我也当然一样如此。在一年之前参加省选时，我在现场也一样地有着期盼。那当然是一种无谓的希望，或许在未来看现在的我也是如此，可其实即使是无谓的希望，也能够带给人力量，也能使人进步——或许这种希望也并不完全是无谓的。

这篇文章本是一篇游记，对于要在开头扯这些没用的，我深表歉意。那么正文由此开始，既然暂时还没有退役，那么就让我在这里罗列一下我省选的经历吧。

继续阅读

奥利卡的诗

题目来源：

https://blog.csdn.net/u011056504/article/details/80006052

#include <queue>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define debug(x) cerr<<#x<<'='<<x<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();int f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
const int N = 600060;
vector<int> G[N],ed[N];
int n;
char str[N];
struct Seg{
	ll quad[N*4],lin[N*4],lazy[N*4],sumc[N*4];
	ll get_quad(int num,int l,int r){
		return quad[num]+(2*lin[num]+lazy[num]*(sumc[r]-sumc[l-1]))*lazy[num];//(x+y)^2 = x^2+2*x*y+y*2
	}
	void modify(int num,int l,int r,int ql,int qr){
		
		if(r<ql||l>qr)return;
		if(ql<=l && r<=qr){
			
			lazy[num]+=1;
			//cout<<"FIN OP\t id:"<<num<<'['<<l<<','<<r<<"] q:["<<ql<<','<<qr<<']'<<quad[num]<<' '<<lin[num]<<' '<<lazy[num]<<"  length:"<<sumc[r]-sumc[l-1]<<endl;
			return;
		}
		quad[num] = get_quad(num,l,r);
		lin[num] = lin[num]+lazy[num]*(sumc[r]-sumc[l-1]);
		lazy[num*2]+=lazy[num];lazy[num*2+1]+=lazy[num];lazy[num] = 0;
		int mid = (l+r)/2;
		modify(num*2,l,mid,ql,qr);
		modify(num*2+1,mid+1,r,ql,qr);
		lin[num] = lin[num*2]+lazy[num*2]*(sumc[mid]-sumc[l-1])+lin[num*2+1]+lazy[num*2+1]*(sumc[r]-sumc[mid]);
		quad[num] = get_quad(num*2,l,mid)+get_quad(num*2+1,mid+1,r);
		//cout<<"FIN OP\t id:"<<num<<'['<<l<<','<<r<<"] q:["<<ql<<','<<qr<<']'<<quad[num]<<' '<<lin[num]<<' '<<lazy[num]<<"  length:"<<sumc[r]-sumc[l-1]<<endl;
		
	}
}sgt;
struct automaton{
	int ch[N][26] = {0},mlen[N] = {0},fa[N] = {-1},la = 0,tot = 1;
	void extend(int x){
		//cout<<"EXTEND : "<<x<<" : "<<la<<endl;
		if(ch[la][x]){
			//cout<<"FND"<<endl;
			int p = ch[la][x];
			if(mlen[p] == mlen[la]+1){
				la = p;
				return;
			}
			int np = tot++;mlen[np] = mlen[la]+1;fa[np] = fa[p];fa[p] = np;
			memcpy(ch[np],ch[p],sizeof(ch[p]));
			int po = la;
			while(ch[po][x] == p) ch[po][x] = np,po = fa[po];
			la = np;
			return;
		}
		int np = tot++;mlen[np] = mlen[la]+1;int cp = la;
		while(cp!=-1 && !ch[cp][x]){ch[cp][x] = np;cp = fa[cp];}
		int q = ch[cp][x];
		if(cp == -1){
			fa[np] = 0;
		}else{
			if(mlen[q] == mlen[cp]+1){
				fa[np] = q;
			}else{
				int nq = tot++;mlen[nq] = mlen[cp]+1;fa[nq] = fa[q];
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				fa[q] = nq;fa[np] = nq;
				for(int cpo = cp;ch[cpo][x] == q;cpo = fa[cpo])ch[cpo][x] = nq;
			}
		}
		la = np;
	}
}sam;
int sz[N],hson[N],dfn[N],ord[N],top[N],depth[N],fa[N],tim = 1;
void dfs(int num){
	hson[num] = -1;
	sz[num] = 1;
	for(auto ct:G[num]){
		depth[ct] = depth[num]+1;
		fa[ct] = num;
		dfs(ct);
		if(hson[num] == -1 || sz[ct]>sz[hson[num]])hson[num] = ct;
		sz[num]+=sz[ct];
	}
}
void dfs2(int num){
	top[num] = (num == hson[fa[num]])?top[fa[num]]:num;
	dfn[num] = tim++;
	sgt.sumc[dfn[num]] = sgt.sumc[dfn[num]-1]+sam.mlen[num]-sam.mlen[fa[num]];
	//cout<<num<<' '<<dfn[num]<<' '<<sgt.sumc[dfn[num]]<<endl;
	if(hson[num]!=-1)dfs2(hson[num]);
	for(auto ct:G[num]){
		if(ct!=hson[num])dfs2(ct);
	}
}
void modify(int x){
	if(!x)return;
	//cout<<top[x]<<' '<<x<<','<<dfn[top[x]]<<' '<<dfn[x]<<endl;
	sgt.modify(1,2,sam.tot,dfn[top[x]],dfn[x]);
//	debug(sgt.quad[1]);
	modify(fa[top[x]]);
}
int main() {
	read(n);
	for(int i=0;i<n;i++){
		scanf("%s",str);
		int m = strlen(str);
		sam.la = 0;
		for(int j=0;j<m;j++){
			sam.extend(str[j]-'a');
			ed[i].push_back(sam.la);
		}
	}
	for(int i=1;i<sam.tot;i++){
		//cout<<sam.fa[i]<<"->"<<i<<endl;
		G[sam.fa[i]].push_back(i);
	}
	dfs(0);hson[0] = -1;
	dfs2(0);
	for(int i=0;i<n;i++){
		for(int j=0;j<ed[i].size();j++){
	//		cout<<i<<' '<<j<<' '<<ed[i][j]<<endl;
			modify(ed[i][j]);
		}
		cout<<sgt.get_quad(1,2,sam.tot)<<endl;
	}
	
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

#include <queue>

#include <cmath>

#include <bitset>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#define debug(x) cerr<<#x<<'='<<x<<endl

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

template<typename T> void read(T &x){

x = 0;char ch = getchar();int f = 1;

while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}

while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;

}

const int N = 600060;

vector<int> G[N],ed[N];

int n;

char str[N];

struct Seg{

ll quad[N*4],lin[N*4],lazy[N*4],sumc[N*4];

ll get_quad(int num,int l,int r){

return quad[num]+(2*lin[num]+lazy[num]*(sumc[r]-sumc[l-1]))*lazy[num];//(x+y)^2 = x^2+2*x*y+y*2

}

void modify(int num,int l,int r,int ql,int qr){

if(r<ql||l>qr)return;

if(ql<=l && r<=qr){

lazy[num]+=1;

//cout<<"FIN OP\t id:"<<num<<'['<<l<<','<<r<<"] q:["<<ql<<','<<qr<<']'<<quad[num]<<' '<<lin[num]<<' '<<lazy[num]<<" length:"<<sumc[r]-sumc[l-1]<<endl;

return;

}

quad[num] = get_quad(num,l,r);

lin[num] = lin[num]+lazy[num]*(sumc[r]-sumc[l-1]);

lazy[num*2]+=lazy[num];lazy[num*2+1]+=lazy[num];lazy[num] = 0;

int mid = (l+r)/2;

modify(num*2,l,mid,ql,qr);

modify(num*2+1,mid+1,r,ql,qr);

lin[num] = lin[num*2]+lazy[num*2]*(sumc[mid]-sumc[l-1])+lin[num*2+1]+lazy[num*2+1]*(sumc[r]-sumc[mid]);

quad[num] = get_quad(num*2,l,mid)+get_quad(num*2+1,mid+1,r);

//cout<<"FIN OP\t id:"<<num<<'['<<l<<','<<r<<"] q:["<<ql<<','<<qr<<']'<<quad[num]<<' '<<lin[num]<<' '<<lazy[num]<<" length:"<<sumc[r]-sumc[l-1]<<endl;

}

}sgt;

struct automaton{

int ch[N][26] = {0},mlen[N] = {0},fa[N] = {-1},la = 0,tot = 1;

void extend(int x){

//cout<<"EXTEND : "<<x<<" : "<<la<<endl;

if(ch[la][x]){

//cout<<"FND"<<endl;

int p = ch[la][x];

if(mlen[p] == mlen[la]+1){

la = p;

return;

}

int np = tot++;mlen[np] = mlen[la]+1;fa[np] = fa[p];fa[p] = np;

memcpy(ch[np],ch[p],sizeof(ch[p]));

int po = la;

while(ch[po][x] == p) ch[po][x] = np,po = fa[po];

la = np;

return;

}

int np = tot++;mlen[np] = mlen[la]+1;int cp = la;

while(cp!=-1 && !ch[cp][x]){ch[cp][x] = np;cp = fa[cp];}

int q = ch[cp][x];

if(cp == -1){

fa[np] = 0;

}else{

if(mlen[q] == mlen[cp]+1){

fa[np] = q;

}else{

int nq = tot++;mlen[nq] = mlen[cp]+1;fa[nq] = fa[q];

memcpy(ch[nq],ch[q],sizeof(ch[q]));

fa[q] = nq;fa[np] = nq;

for(int cpo = cp;ch[cpo][x] == q;cpo = fa[cpo])ch[cpo][x] = nq;

}

la = np;

}

}sam;

int sz[N],hson[N],dfn[N],ord[N],top[N],depth[N],fa[N],tim = 1;

void dfs(int num){

hson[num] = -1;

sz[num] = 1;

for(auto ct:G[num]){

depth[ct] = depth[num]+1;

fa[ct] = num;

dfs(ct);

if(hson[num] == -1 || sz[ct]>sz[hson[num]])hson[num] = ct;

sz[num]+=sz[ct];

}

void dfs2(int num){

top[num] = (num == hson[fa[num]])?top[fa[num]]:num;

dfn[num] = tim++;

sgt.sumc[dfn[num]] = sgt.sumc[dfn[num]-1]+sam.mlen[num]-sam.mlen[fa[num]];

//cout<<num<<' '<<dfn[num]<<' '<<sgt.sumc[dfn[num]]<<endl;

if(hson[num]!=-1)dfs2(hson[num]);

for(auto ct:G[num]){

if(ct!=hson[num])dfs2(ct);

}

void modify(int x){

if(!x)return;

//cout<<top[x]<<' '<<x<<','<<dfn[top[x]]<<' '<<dfn[x]<<endl;

sgt.modify(1,2,sam.tot,dfn[top[x]],dfn[x]);

// debug(sgt.quad[1]);

modify(fa[top[x]]);

}

int main() {

read(n);

for(int i=0;i<n;i++){

scanf("%s",str);

int m = strlen(str);

sam.la = 0;

for(int j=0;j<m;j++){

sam.extend(str[j]-'a');

ed[i].push_back(sam.la);

}

for(int i=1;i<sam.tot;i++){

//cout<<sam.fa[i]<<"->"<<i<<endl;

G[sam.fa[i]].push_back(i);

}

dfs(0);hson[0] = -1;

dfs2(0);

for(int i=0;i<n;i++){

for(int j=0;j<ed[i].size();j++){

// cout<<i<<' '<<j<<' '<<ed[i][j]<<endl;

modify(ed[i][j]);

}

cout<<sgt.get_quad(1,2,sam.tot)<<endl;

}

return 0;

}

ICPC EC-Final 游记

Day -1

先占个坑，希望能发挥好一点。

Day 1

这场打自闭了，可能将不会有游记。

[SDOI2013]随机数生成器

$$X_{i+1} \equiv a*X_{i}+b\ (mod\ p)$$

$$给出a,b,X_1,求满足X_{i} = t的最小i $$

这道题也是一道BSGS。

继续阅读

[Ahoi2013]差异

一个长度为n的字符串，Ti代表其以i开始的后缀，求

$$\sum_{1 \leq i < j \leq n}len(T_i)+len(T_j)-2*lcp(T_i,T_j)$$

其中len为长度，lcp为最长公共前缀。

继续阅读[Ahoi2013]差异

ICPC焦作赛区游记

ddd牛逼，ddd tql，ddd WF
CongDingDanPaiShang3k5

今天参加了ICPC焦作赛区的比赛，获得了金牌。尽管如同大多数人的大多数比赛经历一样，总是会觉得自己还能稍好一些，但其实这次出的锅已经相当的少，运气也算的上不错了。

继续阅读

NOIP2018游记终版

从哪里跌倒，就从哪里爬起来。人在这里，信心还有，希望还在。

今学年是我最后一年OI。这是我最后一次NOIP。在火车上似乎没有更好的事情可做了，我便把这几天NOIP的经历记录下来。我并不是什么强的选手，但我的经验可能也是有价值的。

继续阅读

「BZOJ3262」陌上花开

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

继续阅读「BZOJ3262」陌上花开

「BZOJ3757」苹果树

神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码，号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。

继续阅读「BZOJ3757」苹果树