ICPC2018沈阳站游记

只能选两站,怀着去旅游的心理选了桂林,然后无脑跟阿嘤队选了沈阳。当时没发现两站是连着的……

day -x

闲下来的时候就是准备模板,重学了一些好东西,但是没做多少题。感觉脑袋变得不太灵光了。
队伍集体训练几乎没有,唯一一次是vp了2017沈阳站,结果我clone的比赛是从uva上拉的,没数据,一交就过……花五个小时打了场假比赛。

day 0

高铁八点发车,得五点半从村里出发。我们早早下去,在甲子钟冻得瑟瑟发抖。
结果褚大哥睡过了??
结果阿嘤他们楼的宿管大妈失踪了??
奔跑的阿嘤队↓

走到沙河站,腿都冻麻了。。

换了换座位和阿嘤队坐一起,大约十二点到的沈阳,一路扯扯皮很快就过去了。
出站之后打车去酒店,在沈阳打车好便宜!!
在某家M记吃午饭,一位店员大妈对我们说:麦当劳就愿意招你们东北大学的学生,因为你们素质很高!我们没敢承认我们其实是素质低的北邮学生O_O
发的参赛服在淘宝上可以搜到

感觉太蠢于是就无视规定没穿,结果就是我们只得在观众席上观看开幕式……快结束了才把我们放进去打热身赛。
热身赛三道题,一人切一题,很快写完了。每个人都写了一会儿代码,适应一下键盘,总体感觉海星。
热身赛前刚刚发的饭票,打完之后就被SR弄丢了。找了好几个志愿者,最终终于又要到了一份。中间遇到了一个志愿者,给我们留下了很大的心理阴影。
“你们哪个学校的?”
“北邮的。”
“北邮儿的?”(表情突变)
“大几的?”
“大一的。”
“北邮曾经给了我很大的伤痛。”
“那有个你们大二的学姐。”
本以为他和北邮怎么苦大仇深,听到这的我一脸黑线==

学校准备的自助还是很好吃哒哒哒~

本来立下flag,此生不碰2-sat。结果没有2-sat板子,不得已又看了一眼。结果发现我在考场上离正解只差三行代码,顿时感觉十分难受。

睡不好

day 1

睡不好

将头发梳成大人模样,穿上一身帅气夕阳红老年装。
M记里基本全都是ACMer。

九点钟,比赛开始了。
题面都很长,我找了一道题面看起来最短的C题开始读题,题意还是比较好理解的,就是将前k个数字冒泡排序之后序列的LCS\ge n-11…n的排列个数。我一开始考虑按照排序之后不在LCS里面的那个元素的大小与k的关系和位置是否在前k个分类,每种分类写出一个式子来算一算发现不对。后来发现四种情况中有两种情况会出现重叠,想了想发现没什么办法,就扔给SR跑路了。
与此同时,PY跟榜切掉了签到题,因为把==写成=查了很长时间(初学者*1)

SR拿着我的式子改,我写暴力让他找规律,最后找到了规律,开始写。写完之后WA了。原因是没加Cases#。加上之后WA*2,原因是n==k的情况是特判输出的,那里每加Cases。改完之后WA*3,我又看了看题目发现k可能>n,于是把特判的条件改了改,终于过了(初学者*2)。

当时我们rk30左右,寻找下一个突破口。
SR之前看的n\le 10^{18}的约瑟夫问题,满足\sum\min(步长,步数)\le 10^6,我和PY拿过来,翻开白书和具体数学,结合经典问题的递推思路开始想,但并没有什么结果。
PY又读了一道维护平面内满足到某个点欧式距离为给定值的整点的题目,貌似暴力可搞,我打个表发现所有完全平方数至多有一组平方和的划分方法,于是就写。写完之后TLE。原因是1000组数据每次memset大数组(初学者*3)。改成时间戳之后WA,发现时间戳写错了(初学者*4)。改完之后还是WA,发现打表的时候内层循环把i++写成j++,出来了错误的结论(初学者*5)。不过好在改过来之后所有数字总的划分数不多,于是就改成用vector存每个数字的两个平方数的划分方案。终于过了。
此时又从rk80+回到了rk30+,但是由于罚时爆炸,三题垫底。此时还有不到两个小时。

封榜前没再写题,第一次感受到离开手机查词之后的无助。词汇量太小,而翻词典翻的太慢,被各种卡题意。最后掉到了rk45,感觉这个罚时,很虚。

封榜后全队一起约瑟夫希望保住一块Ag,SR想出了一种挺靠谱的方法,是一种细节多的让人lao kuo teng的方法,按照我的理解,在50min内写完并且A掉是比较难的。但是孤注一掷,就让SR写吧。我和PY在一边双排自闭。在一旁看题,也没有想出哪道题有什么好写的方法。到最后SR写不完了,我们三个在悲伤中自闭完了剩下的十分钟。

比赛结束之后,我们不想看滚榜,打算直接去找家火锅店狂吃一通发泄一下。看着封榜后后面队伍的交题记录,我已经做好打铁的准备了…然而还没找到火锅店,fqk告诉我们卡线Ag了…

月加队打的很自闭,和我们一起卡线Ag了…

阿嘤队封榜之后也没过题,最后还是一个Ag…

总结

说实话,这块Ag真是给我一种白捞的感觉。。打成这样,各种初学者的低级错误。。只能感谢各位轻虐了…
和外校交流发现我们队训练少的可怜,像中大南大,并不能签到NOI比较靠前的选手,但是上大学以后刻苦训练最后能和清北叫板。等桂林打完,这个慌忙的赛季结束,该好好想想以后的路怎么走了。

[hdu6223][Shenyang Onsite 2017]Infinite Fraction Path

Link

每个点有一个出边,每个点上有一个字符。求字典序最大的长度为n的路径。

Solution

广义后缀数组!预处理一下一个点往后跳2^i步到的点,然后魔改一下后缀数组就好了。

Code

const int XN=150000+11,XLOGN=18;

int par[XN][XLOGN];
char v[XN];
void Work() {
    int n;fin>>n>>(v+1);
    for(int i=1;i<=n;++i)
        par[i][0]=((long long)(i-1)*(i-1)+1)%n+1;
    for(int b=1;(1<<b)<=n;++b)
        for(int i=1;i<=n;++i)
            par[i][b]=par[par[i][b-1]][b-1];
    static int temp[2][XN],cnt[XN],*x=temp[0],*y=temp[1],sa[XN];
    int m=256;
    std::fill(cnt+1,cnt+1+m,0);
    for(int i=1;i<=n;++i)
        cnt[x[i]=v[i]]++;
    std::partial_sum(cnt+1,cnt+1+m,cnt+1);
    for(int i=1;i<=n;++i)
        sa[cnt[x[i]]--]=i;
    for(int b=0;(1<<b)<n;++b) {
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[par[i][b]]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=1;i<=n;++i)
            y[cnt[x[par[i][b]]]--]=i;
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[i]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=n;i>=1;--i)
            sa[cnt[x[y[i]]]--]=y[i];
        std::swap(x,y);
        int p=x[sa[1]]=1;
        for(int i=2;i<=n;++i)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[par[sa[i-1]][b]]==y[par[sa[i]][b]]?p:++p;
        if((m=p)==n)
            break;
    }

    for(int i=1,p=sa[n];i<=n;++i,p=par[p][0])
        fout<<v[p];
    fout<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}

O(n)求字符串的最小表示

Problem

求一个字符串的循环移位中字典序最小的那个。

Solution

两个指针指向两个同构串的开头,比较它们的大小,较大的那个串的与另一个串相等的那一部分及其第一个不同的字符不可能是最小同构串开头,可以直接跳过。

Code

int MinimumRepresentation(int *a,int n) {
    ++a;
    int p1=0,p2=1,len=0;
    while(p1<n && p2<n && len<n) {
        if(a[(p1+len)%n]==a[(p2+len)%n])
            len++;
        else {
            (a[(p1+len)%n]>a[(p2+len)%n]?p1:p2)+=len+1;
            if(p1==p2)
                p2++;
            len=0;
        }
    }
    return std::min(p1,p2)+1;
}