默认分类 – 第 20 页

…

-.-无聊上twitter看了看… chrome提示这是Japanese页面，点击翻译… :Weary:

[HDOJ 4436 a.k.a 天津2012 F] 后缀自动机

【题意】

给定N个数字串，每个串的子串成一个数字，问这些数字放进一个set里面去重后和模2012是多少

【算法】
后缀数组也可以做，但是后缀自动机无疑简单一点。
类似于后缀数组，把所有串通过10这个不属于任意一个数字的元素串连在一起。
然后把结点按val直接sort一下，从前往后递推统计。
递推的时候记录两个值，到达这个结点的方案数way以及到达这个状态的数字之和sum。
每次接收一个c转移显然就应该是给下一个结点的sum加上$$\sum_{i = 1}^{way} (number_i * 10 + c)$$。
把这个式子的常数c拉出来就是$$way * c + 10 * \sum_{i = 1}^{way} number_i$$
亦即$$way * c + 10 * sum$$
就这样从前往后推一下就好了，最后把每个结点的sum值都加起来就是答案。
推的时候要注意的就只有两点

根节点不应该接收0开头的串，因为这会弄出有前导0的串从而导致重复，这个很显然吧。
所有的转移都无视10这个分支，因为那本身就是不应该走的…这个也很显然把。

【时间复杂度】
$$O(N * 11 + N \log N)$$
其中N为输入字符总数。后面的N lg N是因为我贪方便直接按val sort了，这一步用了链表跳一下很容易做到O(n)的。 11自然就是字符集大小了。
【空间复杂度】
$$O(N * 11)$$
【吐槽】
今天贴了后缀自动机的模板以后花了不到5分钟就过掉了…现场调了1小时没过是怎么回事，当时的做法是一模一样的 :Cry-Out: 难道又是模板敲错了？
好后悔没有把现场打印的代码拿回来。

#include 
#include 
#include 
#include 
#include 
using namespace std;

template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 250005;
const int Mod = 2012;

struct Node {
	Node *ch[11], *fa;
	int val;
	int way;
	int sum;
	Node(): 
		val(0), fa(NULL), way(0), sum(0) { 
		memset(ch, 0, sizeof(ch));
	}
}pool[N * 2 + 5], *last, *root;
vector  vec[N];

namespace SAM {
	int cnt;

	void init() {
		if (cnt)
			for (int i = 0; i < cnt; i++)
				pool[i] = Node();
		cnt = 1;
		root = &pool[0];
		last = root;
	}

	void add(int c) {
		Node *p = last, *np = &pool[cnt++];
		last = np;
		np->val = p->val + 1;
		for  (; p && !p->ch; p = p->fa)
			p->ch = np;
		if (!p) {
			np->fa = root;
		} else {
			Node *q = p->ch;
			if (p->val + 1 == q->val) {
				 np->fa = q;
			} else {
				Node *nq = &pool[cnt++];
				*nq = *q;
				nq->val = p->val + 1;
				q->fa = nq;
				np->fa = nq;
				for (; p && p->ch == q; p = p->fa)
					p->ch = nq;
			}
		}
	}
}

bool cmp(int i, int j) {
	return pool[i].val < pool[j].val;
}

int n, m;
char S[N], buf[N];

void calc() {
	int ans = 0;
	vector  vec;
	for (int i = 0; i < SAM::cnt; i++) {
		vec.push_back(i);
		pool[i].way = pool[i].sum = 0;
	}
	sort(vec.begin(), vec.end(), cmp);
	root->way = 1;
	root->sum = 0;
	foreach (it, vec) {
		int i = *it;
		Node *p = &pool[i];
		for (int c = i == 0 ? 1 : 0; c < 10; c++) {
			if (p->ch) {
				p->ch->way += p->way;
				p->ch->way %= Mod;
				p->ch->sum += p->sum * 10 + p->way * c;
				p->ch->sum %= Mod;
			}
		}
		ans += p->sum;
		ans %= Mod;
	}
	printf("%d\n", ans);
}

int main(){
	while (scanf("%d", &n) != EOF) {
		m = 0;
		SAM::init();
		for (int i = 0; i < n; i++) {
			scanf("%s", buf);
			int len = strlen(buf);
			for (int j = 0; j < len; j++) {
				SAM::add(buf[j] - '0');
			}
			SAM::add(10);
		}
		calc();
	}
}

金华赛区小结 —— By edward_mj@ArcadiaConvent

打星参赛被坑飞是对本次参赛的唯一总结。
吃喝玩乐的都让搞学长说完啦，我还是说说比赛的概况吧。
Board

开场zYc轻松过掉了水题I。

我看完A题以后，用3分钟左右写完提交了一下WA…原因是

sort(a, a + n, cmp);

写成了

sort(a, a + n);

下来看了好一会儿才发现，加上以后就过了。

zYc接着又把J题秒掉了

这之后就是悲剧的开始

我看完C以后觉得是很简单的bfs，于是很快写完以后发现过不了sample。
C的题意是这样子的

给定n个平行于坐标轴的矩形(buildings)，问从(sx, sy)走到(ex, ey)至少需要转多少次弯。

于是我又仔细看了一遍题目，对于路径唯一的要求就是不能”across the building”。而sample2里面就有两个矩形端点叠在一起却算是不能通过的情况，瞬间就觉得坑爹了。
问了一下，judge回答了保证矩形面积都是正的。
于是改了改，认定对角矩形端点重叠的情况(下图)，不允许走进那个重叠的点。

而这种并排的端点重叠，允许通过中间的点。

而这种被夹住的区域也认为不能通过

于是直接WA到死。

期间zYc在搞F的多项式以及H的三维凸包题，prowindy见K题有好些人过也将之干掉了。

WA了几次以后我去看了B和D，发现都是简单题。D是角度区间求并，B是简单的章鱼图上的dp统计(不知道为什么没人去做)，感觉都很扎实，而不是像C题这样题意不明不白的。

见我WA了这么几回，prowindy也跑过来弄C，并跟我说了这两种贴墙的走法应当是被允许的，而我自己并不是这么理解的。

接着prowindy告诉我下面的走法我弄错了，prowindy问起我为什么会写出这样一看就是错的代码，我只说我写的代码就是我想的那样的。
题目意思根本没有说清楚，我和prowindy的理解还是不一样，我认为这样是不能走的。既然我的理解WA了，直接让prowindy去重写了。

在他理清思路的期间，我把B的代码打完了，但是没调过样例(-_-概率加起来大于1了我会乱说)，zYc把三维凸包那题代码也补完，但是WA。

后来看着时间不多了，我也没想着上机调，让prowindy大概花了50分钟(期间我和zYc各种小改动，zYc最后还是把F的多项式题过掉了)把C搞完了，”6/298″，也算对得起这神坑了。

于是比赛结束。

6题

What a pity.

恭喜4队以明显错误的算法1Y C，再枚举角度水过D，最后还用猛犸那个很难用的三维凸包模板过掉H，7题第4并拿到季军(School Rank, 上交两个队伍只算一个了…)，简直如同神一般。 :Approve:

Summary:

缺乏自信
这个问题存在很久了，但是真没什么办法。
对于很多队过的题，我们过不了好像就不死心一样。
我觉得过的人比较多并不代表这个题目不坑，只能说明很多人现在在搞这题。
像这场的C，粗略估计影响了我们近3个小时。
从我过不了sample的那一刻，我就有预感C题会是个坑，因为各种东西完全没说清楚。而prowindy坚持说很清楚，就和现实中的一样，这时候我就应该直接放prowindy去搞的，因为我的理解根本不是那样。
而看了20分钟确信代码没错误的时候，我就应该不再插手这一题了。因为根本没办法估计到底要再花多少时间才能过掉。这种看不到未来的事情，做下去就是拼RP，RP好就搞定了，RP不好就废了。特别还是有大量靠谱的可做题的时候。
prowindy经常说

先搞有人过的题

我觉得这是缺乏自信最直接的表现。
这种思想我在上一年7月集训的时候也有过，但是很快就发现不对了。
特别是像我这样OI出身的，盲目跟风真是很不明智的选择。
像今年7月集训的个人赛里，我基本上就没怎么跟风过，看了知道是题意不坑，实现不坑就果断写，果断交。
只有我自己的时候，我能这么随意做，但是组队以后，不得不考虑队友的决策。
其实我觉得我们的策略应该是

跟风看题，先开写自己觉得扎实的，而不是人过的多。一个题目，如果你觉得还有可能要枚举题意，那么还是先弃为妙。原因还是上面说的，你根本无法估计你要花费多少时间才能得到一个Yes。

要相信自己少这一题，一样可以排到前面去(7月集训我就一直是这么想的)。
不是说“别人能过，我们为什么不能过？”这样的思想不对。
只是别人RP好，你能保证你自己RP好么？如果相信自己有碾压对面的实力，为什么要去拼RP？
赛后zYc对我开玩笑说：“如果我们从来没碰过C题，我觉得我们队8题妥妥的。”
其实这话还是挺有可行性的，就算没有C，搞掉B D (H or E)，就8题在手。
btw，看了一下最终的board，似乎被C坑飞的队伍不在少数…
准备不充分是我们这次的一大失误，上场的时候就只带了浙大模板，而不是像搞学长他们那样带了足足3个纸袋的资料

很多人觉得我们一队训练得少，但是我却有自己的看法。
想想我们组队训练的目的是什么？

做更多的题目，训练自己的思维？增长知识面？
加强编码能力？
加强团队的合作与默契？
知道任务该怎么分配？
…

其实前面两条都是自己练习效果更佳。
而第三条，往往组队以后你会不再那么关注一般不是由自己解决的问题了。这样会越来越容易导致你和队友根本讨论不起来，因为在某些方面，你们根本不在一个level…所以我更觉得自己的练习更为重要。
第四条，我觉得每星期训练一次，就很容易分清每个人该做什么了。没必要苛求组队训练量。
而训练量提上去的好处，我个人觉得大概还是防止偷懒吧，但这个理由其实不是很给力。
ACM/ICPC的训练每次都要占用一大段的时间(5个小时)，实际上很影响正常的活动(特别是要赶作业什么的-_-b)，而正常的作息以及活动对人的精神状态影响真的是很大很大，所以我不是那么愿意训练很多场。除非你们队伍平常都比较闲。

练一场要有一场的效果，总结一定要保证写好的。

最后，还是我一直说的，我觉得我们一队编码能力以及YY算法的能力都挺可以的，策略与精神状态是关键。
愿诸君共勉。

By edward_mj@ArcadiaConvent 2012.10.19 @ ZJG

天津赛区流水账

拖到都快金华赛区了-____-

出发前
去之前的心态是这样的

这场不出线，接下来秋学期考试什么的就有点麻烦了…
整理好要带的资料以后不知道为什么就有点燃起来了>_<
anyway，把能搞的搞过去就好，打不过的话也只能认命了，心态放好。

然后被shi哥说了一下……

「相手が強すぎる」や「自分が弱すぎる」などの言葉は、たまに冗談するのがわるくないけど。失敗の言い訳にするのはいけない。「進出できない」ばかり言ったら、本当に進出できなくなるぞ。去年もそう言っただろう。

想了很多东西。
shi哥之所以能成为奇迹的缔造者, 终究是有原因的。
不得不说，watashi对我的影响很大。不单单是知识以及比赛上的。
具体的大多是集训队内部的事情，考虑到个人隐私以及其它的一些东西，博客上就不说了吧。
终究是想通了一些东西，在做事情之前，就为自己的失败找好了借口与理由。这是有多negative。

对面以前都是国家队的，打不过是意料之中

自己刷的题没有别人多，打不过太正常了

别人以前随手就虐我10条街，现在能跟上就不错了

可悲的是现在看来这么圡的事情，自己居然没有察觉。
其实这种事情很经常发生的…所以人们给了它一个好听的名字：犯2。
10.19
翘掉了早上的两节课。打印各个队伍需要带去的资料，然后情绪高涨地出发了。
在公交车上思前想后，>_<还是给一个好感度100的MM发出了第一条搭讪短信~
blablabla聊得欢快，很快到火车站。
等了好久，联系了一下两个队友，他们在上了bus后发现太堵又下去找taxi，截不到taxi以后又回到了bus上…真是为比赛攒足了RP。
火车上和prowindy想看《吸血鬼猎人林肯》，但是字幕编码不对
最后由好男人fancy出手搞定(下图为fancy当天的衣服)

睡觉的时候在上铺各种碰头，这火车实在太窄了呀呀呀呀…
10.20
一醒来就看到prowindy坐在下面和大妈扯了起来。
大妈说泡多了一碗面，让prowindy吃掉… prowindy见我醒来，马上把这碗面推脱给睡眼朦胧的我，然后我很乖地吃掉了… :Angry:
快到站了，于是大家都陆陆续续集中起来。
爆一张dd学长的PP~看起来就充满战斗力的样子 :Roses-are-red:
下车以后dd学长发现把身份证丢了…momo.
于是大部队在火车站了一会儿.

所幸最后有惊无险.

接下来就是搭车去汉庭酒店，不知道为什么，别人都25块，我们1队+dd学长搭了35块…(T_T眼泪掉下来)

住宿办理好以后急忙跑去蹭车。幸好还是赶上了中饭。
吃饭到一半碰上了到处逛的老朱~哈哈，被拍了一张略显猥琐的

下午的试机赛很随意~我B写的Java WA了一遍，很快就秒完4题，似乎最后排在第五的样子。

上厕所的路上见到了中大的郭老师~~~
我说了句“郭老师好”，然后郭老师顿了一下缓过神来认出了我这货，跟我说了”你们浙大的题中大做得好，中大的题希望你们也做得好”。
我应了一下以后就屁颠屁颠地回座位上去了。

啦啦啦，试机赛本队合照(喂，我还没摆好pose啊！！！)~

晚上照例和猛犸看非诚勿扰攒RP…至于为什么看这个能攒RP，大概是去体会一下别人的心酸历程什么的吧…好像瞬间就把非诚勿扰黑了.

唔唔唔，睡前骚扰了一下那只可爱的MM >_<
10.21
正式赛要开始啦~好多好多选手在赛场外等着，期间prowindy多次调戏其ZJNU的学弟学妹，行为之恶劣令人发指。 :Who-s-the-man:
进去以后好像感觉身上buff没有来之前那么给力，于是给自己做了一些诸如“屠死你们这帮弱菜”之类自己骗自己的心理暗示，然后就开搞了。

prowindy上来看到A是麻将题，开写，有点复杂。
我看到D以后想了一下，没想到怎么做。
zYc看了K，说是数据结构题，让我来搞。
这时看到有好多人过B H了，zYc一看好像超水，直接就秒掉了。
我觉得K有点麻烦，大概要敲平衡树，于是先放放。
接下来我上手C题，直接就过不了sample…看了好久看不出错，这时队友很给力地搞掉了A、E。
我终于看出了一个不对劲的地方
```
for (int t = 0; t < 3; t++) b[i] = a[i];
```
改掉以后总算1Y了C题。
在本圡人打了这么久酱油以后，我们达到了5题(99min)。
粗略看了一眼其它题目，我决定去搞K。作为一个OIer，这种数据结构题要是都过不了就太秀下限了...但是敲完以后怎么测都RE...
我让zYc来对了好几遍模板，都说没错，于是我gdb了好一会儿，发现Splay完以后整棵树的size居然会增加，顿时就吓跪了，还以为自己的模板出了问题。
再仔细单步了一会儿，发现我rotate函数都敲错了...
```
void Node::rotate() {
	Node *x = f;
	bool o = f->ch[0] == this;
	x->set(!o, ch[o]);
	x->f->set(x->f->ch[1] == x, this);
	set(o, x);
	x->update();
	update();
}
```
写成了
```
void Node::rotate() {
	Node *x = f;
	bool o = f->ch[0] = this;
	x->set(!o, ch[o]);
	x->f->set(x->f->ch[1] == x, this);
	set(o, x);
	x->update();
	update();
}
```
于是我觉得以后最好还是我或者prowindy对模板好了，zYc一般看的比较粗略。
改过以后直接过sample，1Y，First Blood。
实在是不可容忍的失误，敲错模板居然浪费了这么多时间，这绝对不是一个强队所应该作出的事情。
训练的时候就经常这样，让zYc帮忙检查模板有没有问题，然后经常是敲错了但是zYc检查不出来。
这不是说zYc不认真怎么样，有时候人的习惯可能就是会造成各种奇怪的后果。
这种不需要什么技术含量的细心活大概就是zYc的弱点吧...(难道是太没技术含量导致集中不了注意力?)
于是剩下的时间我看了F，觉得用后缀自动机很好搞，应该很快能搞掉。
他们俩合力攻I...在zYc手写部分函数，prowindy解决程序主体框架的强势配合下，封board前过了I。
然后我的后缀自动机一直过不了sample，真是太圡了。
用SA估计早就撸过去了呀！-_-
我之前还用SA写过一个类似的题目，果然比赛的时候不应该写一些自己不十分熟悉的东西。
这一点是我策略的问题，也是自己平时没有足够努力的缘故...
而且选择了后缀自动机以后，两个队友对此完全没有了解，没办法帮我debug，SA就不一样了
对不起队友了。

赛后从郭老师那里收到了内幕消息，季军。真是出乎我们的意料，其实这场打的并不是特别顺，这个结果，大概也就是别的强队发挥不好的缘故吧。

贴一下PP~
这张是被acmicpc给偷拍了-___-，当时在拼命对Splay的模板。