第46届ICPC EC final游记

前言

因为在昆明区域赛中获得银首，高于csy,wh,zxh队和hzl,syr,tyy队，我队获得了EC名额。
此时我两个队友都决定退役了，所以这场比赛被当作了他们的最后一场比赛（然而后来又决定不退役了）。
这也是我的第一场线下XCPC（虽然在西安）。

Day -2（7.16)

因为宿舍不让住了，晚上跑到了校外和czq一起在gxy家住。

Day -1

摆烂，下午做了个核酸。

Day 0

去机房和hzl,xwj一起打多校。
下午打车去大秦酒店，在签到表上看到了CQU狂风之力。把行李放到屋子里以后又跑过来假装路过，站在签到表旁边，果然在狂风之力后面看到了wjl的名字。
此时我还没办入住（因为ljj办了所以我先去放了行李），本来想去领盒饭但队伍太长于是先去办了入住。
ljj在屋里打游戏，我在QQ群约人打麻将。先是去一个人屋里打，后来看一个围观的人很想打，我的QQ又一直响，就撤了。
gxy晚上才到，我出去接他进来，他带着宝石商人但是找不到人玩，后来听说有人因为房间没了被免费升级成了带麻将桌的总统套房，然后我又跑去打麻将了。
打了一晚上，回来发现gxy在给ljj讲感情故事，然后去小吃了一下瓜。gxy就打算回自己屋睡觉了。外面下雨了（房间里送了两把伞 好评），我出去送他，然后他说了一路自己非常emo，最后我俩决定点个外卖，然后在御膳宫一楼大厅吃。
大概两三点才回，我回去的时候ljj已经睡了。

Day 1

一觉睡到下午，gxy和ljj上午出去买了点零食，然后gxy在ljj床上睡午觉，ljj在沙发上睡午觉。下午都醒了以后我跑去参加开幕式，他们俩没来。
开幕式结束以后我又顺便自己打了热身赛。

A. 某签到题

记不清了

B.

给定\(x,y,z,s,n\leq 10^9\)。小明初始在\(s\)，走\(n\)步，走一步指：如果在\(x\)左边就向右\(y\)格；否则向左\(z\)格。问最后的位置。

Solution

特判走不到\(x\)点的情况，下面考虑能走到\(x\)点的情况。
最后一步如果向右走，则位置\(\in [x,x+y)\)，否则位置\(\in [x-z,x]\)。所以答案一定在\([x-z,x+y)\)。
枚举向左走了\(k\)步，则向右走了\(n-k\)步，最后的位置是\(s+ny-k(y+z)\)，在区间\([x-z,x+y)\)中有唯一对应的值。

C.

给由a~z组成的字符串\(s\)，问有多少个字串旋转180度不变。
\(|s|=1e5或1e6\)

Solution

记b,q,d,p,m,w,n,u,o,s,x,z分别为1,2,3,4,5,6,7,8,9,10,11,12，其他字母为0，使用\(h_1(s)=\sum_{k=0}^{|s|-1} 13^ks_k\)对所有前缀进行哈希。
记b,q,d,p,m,w,n,u,o,s,x,z分别为2,1,4,3,6,5,8,7,9,10,11,12，其他字母为0，使用\(h_2(s)=\sum_{k=0}^{|s|-1} 13^{|s|-k-1}s_k\)对所有后缀进行哈希。
记b,q,d,p,m,w,n,u,o,s,x,z为1，其他字母为0，建立st表。
枚举中间位置，二分子串长度，得到满足条件“\(h1\)与\(h2\)相等且子串中没有0”的最长子串，统计答案。
实际上不需要st表，只需要记录每个位置前一个和后一个0的位置，这样可以做到\(O(n)\)。

今天热身赛电脑开机密码是jbyctfxxm（举办永雏塔菲谢谢喵）。
热身赛结束以后去找wjl的位置，但他好像已经走了。

Day 2

八点起床，去吃早饭，然后去比赛。
今天正式赛电脑开机密码是gzjrr,ddjcc（关注嘉然然，顿顿解馋馋）。

A. DFS Order

签到题，队友过的，没读题。

I. Future Coder

给定\(n\)个数\(a_1,...,a_n\)，求 \(|\{(i,j):a_i*a_j<a_i+a_j,i<j\}|\)
\(n\leq 1e6,-10^9\leq a_i\leq 10^9\)

Solution

\(x*y<x+y \iff x*y-x-y+1<1 \iff (x-1)(y-1)<1 \iff (x-1)(y-1)\leq 0\)
统计\(a_i-1\)的正负即可。

L. Fenwick Tree

有一个大小为\(n\)的树状数组，每个结点的值为给定的（0或1）。每次操作可以选一个结点和一个实数，将该点到根的路径上所有点加这个实数，问最少几次全改成0。

Solution

树形dp

B. Beautiful String

队友做的，是拿铜的关键一题。
在尝试了手写哈希表，map，unordered_map，得到了无数个WA和TLE后，通过选取合适的哈希表的模数AC了此题。

D. Two Walls

计算几何
给定 \(A,B,C,D,E,F\) ，问从 \(A\) 走到 \(B\)，不经过线段\(CD\)和\(EF\)，最少转几次方向。

Solution

答案只可能是\(0,1,2,3\)，讨论即可。

E. Prof. Pang and Poker

打牌题，嗯讨论即可。

最后拿了铜，比赛结束后看到了wjl，打了个招呼，他们好像没考好，只有三题。