完结

我对ACM接触也算告一段落了。

想了很多，最好还是没有参加暑假的集训。其实几个月前我就有这样的想法了。

我大概是今年二月份才算开始真是接触ACM。虽然高中的时候晚自习无聊的时候看过紫书，但之后也没怎么写题目。寒假模拟赛硬着头皮做下来，深感欠缺。但是其实时间也不多了，所以寒假的最后时间基本就在看stl，写一些题目练习手感。开学之后两个星期，开始上洛谷刷专题。之后的选拔赛，侥幸做过类似的题目，所以勉强打过去了。

越是对ACM了解的深，越是明白ACM真的需要投入非常多的精力。之后有幸经过两场比赛，我也进一步确认了这一点。也许开始可以投机，但是ACM确实是属于实干者的比赛。对本来就是抱着功利心来ACM的我来说，大概已经丧失继续下去的理由了吧。所以我选择了在这个时间点，去看自己真正喜欢的东西。这段时间我在看plfa，我发现这可能才是我喜欢的东西吧。

但是，到6月为止的4个月，是我珍视的宝贵经历。虽然一直在迷茫，但是我也曾为了一个目标从几乎零开始奋斗。很感谢比赛时我的队友，他们在许多方面都给了我支持。虽然最后没有继续支持下去，我很抱歉。但是，我真的觉得他们对ACM有那种我不具备的热爱，所以我相信他们一定能取得很好的成绩。就算留下，我应该也只会拖他们后腿吧。

那么，这个临时的子博客也走向了完结。溜了溜了

DAY 1

起了个大早去长春站赶火车到吉林。中午教练请吃饺子，19人点了28盘，不得不感叹东北人作风真是剽悍Orz…

下午到了东北电力大学。第一天主要是签个到，然后打个热身赛。吐槽下发的原谅色T恤，材料实在是一般。不过东北电力大学的食堂好评，菜挺好吃的hhh

关于热身赛，学长说随便玩玩就好。之前好像还出过“出题人喜欢甜豆腐脑还是咸豆腐脑”这种题。除了水题之外，发信息题讨论出是Tarjan缩点+DFS，后来发现DFS也不用，统计出度1的点就行。B就是算24点，刚开始还不让交，限制交20发，大概就是猜答案的压测题。不过10题猜起来还是比较难，于是我写了个暴力BFS跑出了前7个长度为5，剩下3个靠穷举（反正就8种）。坑爹的是，前7个和样例是一模一样的Orz。E题看不懂，场上也没什么人交。赛后听说夏威夷吉他的解几乎就是正解了，夏威夷吉他nb！

DAY 2

赛前我和队友说，上来三个人看首、尾、中三题，肯定能命中一个水题。加上名字叫送分题，于是上来就看的J。队友火火看到题目带LCA就兴奋的跑去看了，@MakiseVon去看了A。看完题撇了一眼榜，发现I才是签到Orz，然后主程火火秒A。

然后我看着J标题是送分题，以为是很简单的那种n一大答案就固定的题，于是打表了前面然后贡献了一发罚时Orz。此时@MakiseVon说G是水题，于是换位看题，发现E是水题，于是开始推公式。帮着检查了下G，然后A了。我E也差不多了，于是换我A掉了E。然后帮队友确认了下D的题意，就去看其它题体面了。简单推了下A，发现操作次数远大于数据范围，于是感觉可以对部分情况特殊处理。然后队友问我若干堆物品不同堆取多个能不能搞，推了下其实就是 $2^{k} - k$ ，听队友讲了下D感觉可以，然后换火火码。然而上来就是WA，然后火火立刻发现问题，然后又WA了。检查了半天，@MakiseVon发现是初始化没搞。

然后撇了眼榜，和队友交流了下决定搞A。和队友简单说了下我之前思路，我说从出现1开始，然而队友推了下，感觉只有一个1的时候很难弄，两数相等的情况也难搞。

于是回到J，打算先打个大表，由于大数Java，于是换最熟悉的我打。打完表第一时间的想法竟然是求差值，然而找不到规律。转换思路，从式子 $\left\lfloor\cos ^{2}\left(\frac{(n-1) !+1}{n}\pi\right)\right\rfloor$ 推出 $\left( p-1 \right)! \equiv -1 \pmod{p}$ 。队友秒看出就是威尔逊定理，之前三个人对着素数表竟然没人看出来Orz…火火说线性筛怕写炸，于是换我写了个线性筛A了。

F看数据就想到Floyd，然而没讨论出什么，于是讨论转向处理环什么的。然后上厕所的时候我想到，魔改下Floyd就完事儿了，于是也A掉了。

然后又捡起了A题。队友推了下，否定了特殊处理就一个1的情况。我试着写了下边界数据，结合A题过的人真的很多，于是让队友写了个暴力+两个1的时候特判，然后就过了23333

H看到题就发现是高中数竞的折线计数问题，李胜宏老师书的例题。然而想不起来公式，就去看B。我开始想了个O(n)的算法，讲完本来都打算写了，结果@MakiseVon发现锅了，题面是树上路径而不是父子链。之后虽然想了几个算法，但复杂度都不行。

封榜后基本上在搞H。我想了个补矩形法，然后作差减去多余的路径，然而样例都过不了。于是最后封榜期间也没交题。赛后发现其实这就是斯特林数，我推的那个式子其实减错矩形了，改一改然后Lucas就行。

最后7题，封榜前12名，侥幸拿了个金。虽然我演了队友一发，但其实作为第一次正赛还是很满意的。黑框眼镜两小时多就9题几乎AK，之后开始扫雷。夏威夷吉他第三。学长nb！

晚上就是四省赛热身，开始队伍数据好像录入有问题，之后甚至所有人都交在team001。晚上脑子有点转不动了，于是也没怎么想，放弃思考。

DAY 3

四省赛完全陷入自闭。刚开始A完签到题J，队友说C是计算几何，由于我只准备了计算几何，于是我就来搞C。火火去开E了。C的算法基本上很快就出来了，然后换我码。然后我就开始疯狂演队友了，WA了一发之后，发现结果计算有点小问题，改了之后队友给了几组数据都ok，但是还是WA。和队友讲了一下算法，感觉是完全没有问题的。后来又整理了一遍，修改了几处可能错的地方，然而还是WA。这时候我的心态已经完全崩掉了，完全是恍惚的状态。

火火跟我讲了下E，讨论了下具体细节，感觉可以做于是换火火写E。我打印了下C，和@MakiseVon开始查。然后又是一波演，E没初始化WA了2发，好在之后A了。我搞C的时候队友好像推了下I，但是暴力T了（暴力也显然不行XD）。

我把剩下题目过了一遍，F没查找的化单次其实就是做个差分，于是我和队友说了下朴素可以搞，试试看能不能优化，然后我就去写C的对拍了。其实当时几个人心态都没了，已经完全不想打了。于是队友跟榜去搞B，B想的是贪心，但是具体搞不出来（赛后发现我题都看错了）。C的对拍拜托队友写了个式子，但是好像式子也是错的。之后队友试着玄学改动、部分重写然而都没能逃过WA的命运，然后就结束了。

其实C的算法确实没什么问题，唯一可能炸的应该就是判重是通过排序和循环。当时修改算法后要是改用map说不定就可以了。最可惜的是F，其实只用树状数组维护差分的两个前缀和就行。然而赛事心态崩了，根本没去继续想F，队友也没怎么看。如果当初C能早点A，F完全可以过，然而并没有如果。

总之非常自闭，最后由于罚时也就拿了铜。说到底，还是一WA大家的心态就完全崩了，没法冷静思考。连续比赛也很累，感觉完全没办法顺利思考。非常对不起队友，由于我的C影响了整场比赛。可以说是很遗憾了。

南昌ICPC邀请赛C.Angry FFF Party – 高精暴力

本来以为还是签完到就开始自闭，没想到今天的邀请赛还摸出一道C。这题看提交数其实不多，而且题目表达也挺复杂。简单来说，就是把一个数W拆成若干个Fib(Fib(x))之和，其中x各不相同。题目数据是 $1 \leq W \leq 10^{100000}$ ，乍一看好像很夸张。其实去算 $Fib \left( x \right) \leq 10^{100000}$ 就会发现，其实也就 $x \leq 317811$ ，再算 $Fib \left( x \right) \leq 317811$ ，发现其实也就28个数。不过这28个数真的挺长的，打表还真打不下，好在Fib现算一遍也就O(logN)。

然后拆数我写的就很low了，由于字典序最小，我就用了 $O\left( n^2 \right)$ 的朴素方法。其实只有2和5需要处理，但是第一次交的时候好像我其它地方漏了个条件，于是WA了。后来保险就用了，总复杂度是 $O\left( 28^2 T + \log N \right)$ 。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    // 打表，前28项
    final static int[] ind = {0,1,2,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811};
    static boolean[] inS = new boolean[30];
    static boolean[] used = new boolean[30];
    static BigInteger[] ff = new BigInteger[30];
    static int sCnt;

    static boolean check(BigInteger W, int st) {
        int curCheck = st;
        sCnt = 0;
        for (int i = 1; i < ind.length; i++) used[i] = false;
        while (W.compareTo(BigInteger.ZERO) > 0 && curCheck > 0) {
            if (!inS[curCheck] && W.compareTo(ff[curCheck]) >= 0) {
                W = W.subtract(ff[curCheck]);
                used[curCheck] = true;
                sCnt++;
            }
            curCheck--;
        }
        if (sCnt > 0 && W.equals(BigInteger.ZERO)) {
            for (int i = 1; i < ind.length; i++) inS[i] = inS[i] || used[i];
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int curInd, cnt;
        BigInteger fn_2, fn_1, fn;
        fn_2 = BigInteger.ONE;
        fn_1 = BigInteger.ONE;
        ff[1] = BigInteger.ONE; ff[2] = BigInteger.ONE; ff[3] = BigInteger.ONE;
        cnt = 2; curInd = 4;
        while (curInd < ind.length) {
            fn = fn_2.add(fn_1);
            fn_2 = fn_1;
            fn_1 = fn;
            cnt++;
            if (cnt == ind[curInd]) {
                ff[curInd] = fn;
                curInd++;
            }
        }
        // 读入
        Scanner sc = new Scanner(System.in);
        int T, curCheck;
        BigInteger W;
        T = sc.nextInt();
        while (T-- > 0) {
            W = sc.nextBigInteger();
            sCnt = 0; // 集合S大小
            // 初始化inS
            for (int i = 1; i < ind.length; i++) inS[i] = false;
            // 检查
            if (!check(W, ind.length - 1)) {
                // 失败
                System.out.println("-1");
                continue;
            }
            // 对每个数，向前分割
            BigInteger num;
            curCheck = ind.length - 1;
            while (curCheck > 0) {
                while (curCheck > 0 && !inS[curCheck]) curCheck--;
                if (!inS[curCheck]) break;
                // inS[curCheck] = true
                if (check(ff[curCheck], curCheck - 1)) {
                    inS[curCheck] = false;
                }
                curCheck--;
            }
            // 重新计算sCnt
            sCnt = 0;
            for (int i = 1; i < ind.length; i++) if (inS[i]) sCnt += 1;
            // 打印
            for (int i = 1; i < ind.length; i++) {
                if (inS[i]) {
                    System.out.print(i);
                    sCnt--;
                    if (sCnt > 0) System.out.print(' ');
                }
            }
            System.out.println();
        }
    }
}

JLU ACM 新生选拔赛思路笔记

A

0-1背包模板题，優しい的难度。

B

dp题，看的时候很眼熟，马上就想到类似最长公共子序列。每种状态有3种可行策略：匹配或者各退一步匹配空白。后来找到原题P1140，果然做过类似的。

C

题目给了一个线性同余随机数产生式：

$X_{n} = a X_{n-1} + b\ \rm {mod}\ c$

已知 $X_{n} = 1$ ，求最小 $X_{n-1}$ 。很容易想到可以转化为求线性同余方程最小解。设 $X = X_{n-1}$ 有，

$aX \equiv 1 - b \left( \rm {mod}\ c \right)$

然后就可以按照一般套路转化成

$aX + cy = 1 - b = gcd\left( a, c \right)$

然后使用拓欧求解。虽然考虑了一些非互素的情况，但是依旧WA，可能还是漏了什么情况。说到底，我“赶鸭子上架”式的数论学习还是不够。

D

题目有点长，看着晕就跳了……

E

RMQ没怎么学过。无论从数据范围还是从题目性质来说，都应该用到线段树求解。但是线段树我只是看了个原理，从来没写过题。虽然考场上临时磕磕绊绊写了个勉强能用，但后来发现题看错了，不是求区间最小而是以Ap为界。也不会转化，丢人了……

F

题目有点长跳了……应该是图论题，不过说实在跳了有点后悔。因为当时以为E、G我能写的，谁知道题全理解错了。

G

看题目直接想到了P1880石子合并，于是就按着区间DP的思路想。然而写完发现过不了样例，询问后意识到其实是题意理解错了，和石子合并还是有区别的。然而已经浪费了大量时间……短时间没想好怎么改于是就跳了。

H

找规律+模拟。

I

题中式子提出y，得到反比例函数，x、y应该分居y=x两侧，所以题目可以转化成a+1~a+sqrt(a)上的搜索。然而考虑到数据大不一定过、剩余时间不多，于是就回头看J。

J

虽然感觉和奇偶有关，但刚开始n=4算成7了，于是并没有找出规律。贪心没思路，dp也写不出转移方程，于是就没再想。最后几分钟，算了下发现n=4其实是6，猜测奇偶项是两个d=3的等差数列，试着写了下就A了。

后记

这次比起寒假模拟，低水平错误少了很多，提交都是1遍A，这是进步。但是同时也深刻感到自己在知识储备方面的不足，以及临场状况处理能力的缺失。能拿到Rank1，我个人觉得运气的成分较大。希望能以此勉励自己，进一步提高吧。

ACM手记

完结

2019CCPC吉林省/东北四赛记录

DAY 1

DAY 2

DAY 3

南昌ICPC邀请赛C.Angry FFF Party – 高精暴力

JLU ACM 新生选拔赛思路笔记

A

B

C

D

E

F

G

H

I

J

后记

UVA 12333 Revenge of Fibonacci

UVA 1597 Searching the Web

UVA 1596 Bug Hunt

UVA 12100 Printer Queue

UVA 10391 Compound Words

UVA 10763 Foreign Exchange