Low

长春比完一直都很low，直到现在还是……
以这样的姿态结束自己最后一场Regional，实在是很遗憾吧。
大三这一个学期自己也不明白怎么熬到现在的。33的学分，每周来回ZJG训练4场。算一算路上花费1个半小时，每次训练5个小时，那么就是6.5*4 = 26个小时。也没算训练后补题的时间，其实根本就算不清楚……
这么多场训练下来，可以清晰地感受到今年1队比上一年要强上了太多了。结果Regional和网络赛打得都没上一年好。
感觉现在我或多或少看明白了一些原因，不过小结还是等我不怎么带情绪的时候写吧。
痛苦只是因为没有达到自己的预期
不在圈内的人知道结果只会跟你说：“又拿了块金牌，不错哦。”
在圈内的人只会觉得：“唔，ZJU今年还没有上一年强。”
嘛，上一年我带的1队在final打成那样……今年也没多少人看好我们吧。
\
历史总是惊人地相似。
\
4年前我准备NOI的时候亦是如此。
\
为何感觉从小到大我都是这样，无论小学初中还是高中……
前面尝到一点小甜头；在最后的关键时刻前一直被打成马，勉强晋级……；最后放手一搏，然后得到出乎自己意料的结果。
希望这回也不例外吧。
2014.6.25 ACM/ICPC World Finals 不远了。

SRM 598

250pt

给定100 \leq a[i] \leq 300，每个桶容量300，问最少多少个桶能装完给定的a[i]。

看到过的有两种做法，一种把数字从小到大排序，然后从大到小每次贪心装。我的做法是因为只有三个100能放进一个桶里，其它至多两个，那么就枚举有多少组100是三个三个叠在一起的，剩下用sort，每次小的值，找一个尽量大的值来匹配。

550pt

有两个剑士一开始距离为d，A剑士一回合可以移动mov1，攻击范围为rng1。B剑士一回合可以移动mov2，攻击范围为rng2。A、B轮流动，问最优策略下，谁赢或者平局。

先把双方第一步能秒杀的情况排除掉，然后就是看谁mov + rng大，这个值小的必定不能赢(反证一下)。然后这个值大的要看能不能追上另外一个人，如果追的mov比较小，必定平局。mov比较大的条件下，最近是追到对方的mov+rng+1，否则再近一步对方就要反扑了。于是判断mov_op+rng_op+1+mov_op(这是因为追到最近以后，对方可以后退一步才轮到进攻方攻击)这个值是否小于等于mov_me + rng_me，如果是，就是可以赢，否则不行。

写的时候想当然了，几行的代码就写挂了-。-

    string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d)  {
        if (mov1 + rng1 >= d) return WIN;
        if (mov1 + d <= mov2 + rng2) return LOSE;
        if (mov1 + rng1 > mov2 + rng2) {
            if (mov1 > mov2) {
                return mov2 + rng2 + 1 + mov2 <= mov1 + rng1 ? WIN : DRAW;
            } else {
                return DRAW;
            }
        } else if (mov2 + rng2 > mov1 + rng1) {
            if (mov2 > mov1) {
                return mov1 + rng1 + 1 + mov1 <= mov2 + rng2 ? LOSE : DRAW;
            } else {
                return DRAW;
            }
        } else {
            return DRAW;
        }
    }

1000pt

给定一棵边长为1的树，问最少在多少个点上添加信号塔，使得每个点对信号塔的距离序列互不相同。

枚举一个放信号塔的树根，然后dfs下去，统计没有填信号塔的子树数目(记为cnt)。里面最多只能有一个子树子树不填信号塔，所以ans += cnt – 1。比赛的时候也想到这个了，但是只证出他是必要条件，充分性没证出来- -b，于是就弄了个按覆盖个数的贪心果断跪了。再仔细想想怎么证吧。

[update]
-。-想了一下，充分性好像也是显然的，这样每个节点的不同分叉都可以分辨……也是充分的。

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template <class T> void checkmin(T &t, T x) { if (x < t) t = x; }
const int N = 55;
int n;
vector <int> E[N];

int dfs(int u, int fa) {
    int res = 0, cnt = 0;
    rep (i, E[u].size()) {
        int v = E[u][i];
        if (v == fa) continue;
        int tmp = dfs(v, u);    
        if (tmp == 0) {
            cnt++;
        } else {
            res += tmp;
        }
    }
    if (cnt > 1) {
        res += cnt - 1;
    }
    return res;
}

class TPS { 
    public: 
    int minimalBeacons(vector <string> linked)  { 
        n = linked.size();
        rep (i, n) E[i].clear();
        if (n == 1) return 0;
        rep (i, n) rep (j, n) if (linked[i][j] == 'Y')
            E[i].push_back(j);
        int ans = 0x7FFFFFFF;
        rep (i, n)
            checkmin(ans, dfs(i, -1));
        return ans + 1;
    }
};

弦图

今天在gym上被一题疑似弦图的题目卡了一下，后来猛犸随便乱搞就搞过去了。看了一下gcj上的solution，发现有用完美消除序列过的，于是就去温习了一下弦图。结果最后发现其实那个图根本不是弦图……只是碰巧那个最大势的方法求出来的顺序是靠谱的染色顺序罢了。写一下今天温习的内容吧。

  • 弦图的定义。任意size>3的环都存在弦。弦即环上不相邻两点之间的边。
  • 完美消除序列。$$v_i$$和$$v_{i+1}, … , v_n$$构成的诱导子图里，把和$$v_i$$相连的点拿出来，会成为一个团。
  • 完美消除序列的求法。令$$d_i = 0$$，然后每次选取d值最大的一个点拿出来放进序列头，再枚举该点的出边，把他们的d值加1。如此反复。
  • 完美消除序列的性质

    1. 按序列从后往前染色可得图的色数。在弦图里，色数等于最大团的size。
    2. 按序列从前往后贪心取可得最大独立集。在弦图里，最大独立集额等于最小团覆盖。
    3. 按上面最大势方法求出这个序列顺序以后，如果想知道该图是不是弦图，那么枚举每个点$$v_i$$，假设他在$$v_{i+1}, …, v_n$$里有边直接相连的点集为$$S = {x_1, x_2, … , x_m}$$然后只需判定$$x_1$$是不是和$$x_2, x_3, … , x_m$$都有边就可以了。
  • 完美图的定义。所有诱导子图满足色数等于最大团size的图。
  • 伴完美图的定义。所有诱导子图满足最大独立集等于最小团覆盖的图
  • 区间图总是弦图。并且按r排序就是他的完美消除序列。
  • 其实感觉很多不是弦图的题要求色数都可以用最大势的方法求出顺序然后贪心染……说不定就凑出正解的顺序过了……比如GCJ2009 R3 C

杭州赛区小结 —— by edward_mj@eternal reality

虽然是不是正式参赛，但是总结还是要有的。

开场看了E、F、G，然后猛犸期间看了H问了一下我怎么做，然后当时猛犸告诉我的题意是错的，但是也可以做- -b，初步推断是莫比乌斯反演弄一下，应该不太好搞。

看完后知道F是set蘑菇题，G是xor的数据结构题，E是数论题。看了一个H，发现题意理解错了，就是算算区间，树状数组就可以了。

board上A，B，C都过了好多，猛犸一下子就都秒了。

稍微推了一下E，发现好像只要解一个由两个方程构成的同余方程组就可以了，然后看到范围都是1018，一乘就爆64位整数，感觉能比H快一点，上去就用Java写……然后Java快写完了，发现悲剧了，同余方程前面的系数推的时候忘了乘。但是有了系数模板就用不了……

然后有了系数以后做法有点变化，稍微思考了一下，好像就麻烦起来了。跟肚子白说了题意。然后肚子白问这个东西是素数吗？然后我又看了一下，发现M是素数。又推了一会儿，似乎推出解法……期间猛犸又把I过了，然后由于不太确定解法，先去把H很快写掉了。然后回头权衡了一下E和G，G是一个树上求第k大异或路径的题目，其实只要把从根上来的路径异或值存下来，两个点之间的路径直接xor一下就可以得到了，根本不需要求lca之类的……当时我其实已经想到了不在树上的解法了(也就是已经知道正解了)，但是突然就脑残了，以为两个从根过来的异或值异或一下以后，还要弄一下lca的值。于是就不会做了。

跑去弄坑了一半的E，继续刚才的思路，又上机写回了C++，结果发现写完sample过不了，自己看看推导过程，- -b发现有一步推错了。但是已经没有多少时间了，然后就没再摸机器了。然后这时候看了一眼G，突然发现了刚才想的时候脑残的地方，一下子就会做了……但是却没有时间了，真是我了个去。

赛后我坑了一场的E题成为了全场没人过的题目……

然后比赛之后我看了K题的题意，刚看完就会做了……裸的费用流，然而这题我比赛的时候就只有肚子白看过，然后肚子白觉得条件太多了也一下子就弃坑了，估计也没有仔细想。然而实际上我觉得这是比EFG都简单的题目。

总得来说这场我坑队友坑得飞起，做了一整场的E还没坑出来。其实GK没脑残都是能一下就能过掉的。为什么会这样呢……我觉得还是太缺少讨论了。总结下来有那么几点是做得不够好的。

  1. K题只有肚子白知道题目，而且大概也没仔细想。这和上一年final差不多是同一个情况。最起码应该保证有人过但是没有秒掉的题至少两个人看过，不能就这样一个人粗略地看了一下。
  2. G题没有出纯粹是我脑残，实际上我都已经会做了……但是没有仔细在纸上画出来。导致没有看出和树这个结构根本没有关系。其实当时我只要和肚子白稍微讨论一下，就肯定会发现是哪个地方SB了。其实这题也好像只有我看过题目。
  3. E题全场就只有1个提交，而且还没有过(感觉是交错题了)。跟跟board其实还是很科学的。再就是，相比于数论，无疑我更懂的是数据结构。弃G写E完全不应该。今后在自己不那么擅长的领域，还是跟跟别人比较好。其实这题我会企图去碰的一个重要原因是很像我两三年前推过的同余方程并，结果就忘了当时怎么推的了。当然有点想抢FB大概也是一个原因。比赛里，还是先做自己熟悉的东西吧。不是说我搞不出来，重要的是不知道要花多少时间。
  4. 猛犸写了一场的题，这时候我和肚子白在遇到困难时没有很积极地讨论算法，演变成各自为战真的是很不应该。其实特别在没有题有很靠谱搞法的前提下，两个人合力攻一题多人过的才是比较正确的策略。也许彼此手上的题都差一点点，但是人SB的时候别人不点醒一下往往是会一直SB下去的。又想起上一年final回来，shi哥他们说的，每道题写之前如果不是很水，至少两个人知道算法和题目。如果没有这么做，WA了后20分钟或者花了好久写的还不清不楚的，再没人讨论基本就注定悲剧了。
  5. 猛犸赛后提到了为何我会产生E能过的错觉，其实这种错觉每个人都会犯。比如猛犸写J题的时候也会出现写一半不知道怎么写的情况。提防的方法无非是锻炼在上机前就能“看到”程序长什么样的能力。在摸机器前把每一步都想清楚，不要急。但是即使如此，产生这种感觉还是不可避免的。这也正是上面提到的，写之前要让队友知道算法的重要性。
  6. 世事大多如此，成王败寇。如果我一下子把E推对了，大家都不会喷我。悲剧的就是我推导的过程不够谨慎，每一步看起来都有理有据，结果还是有一步想当然了。但是不能就因为这次悲剧了，之后就畏首畏尾。如果下一次又推出一个自认为正确的结论，场上没人碰的，我还是会去交的。我觉得我们该做的是想办法通过合作等方式减少这种失误带来的影响，而不是全盘否定这样的决策。

其实这套题如果我今天发挥正常8题应该还是比较妥的。final前的训练和比赛无非就是三个目的。

  1. 保持手感
  2. 涨知识
  3. 磨合出对应各种情况下有效的策略

前两条都是可以自己练的，唯独第三条，是最重要也是最容易被忽略的。真心觉得最近我们训练的时候配合不多。我觉得有必要制定固定的队规，这样才能减少在脑袋发昏的时候造成的影响。这和肥羊说的要写小结并在比赛前看一遍是类似的，本质无非是对经验的总结。但我感觉凝练的若干条比零散的小结起到的作用可能更大。

能总结出错误也是一个很重要的能力，组队集训的时候我就觉得很多时候xpy的队伍总结不出自己犯的到底是什么错。虽然这次圡了，但该否定什么，不该否定什么，很多人心里好像没有数。人犯错很多时候是不可避免的，不应该被别人、前辈或者大家认为的大牛开两句玩笑，就觉得自己全盘做错了。每个人都肯定会有自己的想法，认真分析以后觉得别人的意见不合理就不要接受好了。在这里鄙视一下搞学长- -b，新人总结的时候就不要随便乱喷了，你的话很可能在他们眼里是权威。最后，奉上《激战》里的一句台词：怕，你就会输一辈子。