PKUSC游记

本文主要是介绍PKUSC游记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

凉凉

Day-1

提前一天出发，这个时间真的不好，动卧又坐不了，早班机太贵

Day0

早上去国家博物馆走了走，一个上午还没走完。
报道处效率极低，排队排出几十米。

Day1

早上数学和冬令营不一样，整个直接是笔试，（没法程序暴力计算了）
第一题因式分解，就会这一题，其他的全部乱搞，写了五六道题，做对的就一道？？

中午时间比较紧凑

题目

T1

n个数，排名定义为大于等于自己的数量。
有k个数翻倍，问对于每个数，有多少种情况排名不变。
n<100000

T2

n个数，求所有的排列的最大前缀和的和
一个排列的最大前缀和定义为最大的 $\sum_{i=1}^j a[i]，1<=j<=n$
$n<=20,a[i]<=10^9$

T3

主斗地？
斗地主！
斗地主的出牌规则，没有炸弹，没有王炸，四带二可以带王，没有3
你和另一个人两个人在玩，当两个人在同一轮出完所有牌时胜利，若一个人出完了另一个人没出完失败
明牌，绝顶聪明
他的牌你知道，有多少种牌的组合方法可以胜利，不考虑花色。

做题

T1一看很可做，好像求一求组合数搞一搞就行
第二题一看很可做，好像状压DP随意搞一搞就行
第三题……斗地主？
又来？
两道计数题，一道毒瘤题？？
先去看T1
发现可以考虑分为i是否翻倍来计算
不翻倍，就从翻倍后不影响排名的中选k个
然后翻倍的话看有排名上升了多少，再从可以变换排名的中选出对应数量，剩余的选剩余数量，类似就搞定了
一个小时过去，n方的过了
改数据结构，交了三四次还没过，只好对拍。
找到几个小错误，切掉时距离开场一个半小时。
考虑到第三题应该是毒瘤，就决定接下来三个半小时杠第二题。
然而……
其中各种奇奇怪怪的方法都想过，包括一个很接近正解的东西。
凉了，只水到25分。
出去问，其他人都150或160，BA230
BA怕是发达了。
第三题30分好像是很可做的。
第二题BA说DP求出前缀后缀大于0或者小于0 之类的乘一乘就行了。
心态崩了

晚上纯人力走三公里回酒店。

所以按照套路会不会明天三道计数题？？

Day2

面试

三个人都要我自我介绍，然后抓住里面一个点就开始坑人。
第一个人我说我研究过天文，然后就聊了两分钟天文。
第二个人好像对我们学校很熟悉，聊了三分钟学校。
第三个人可能是因为我是倒数第二个已经不耐烦了，让我讲完自我介绍就让我出去了？？

题目

T1

n个点排成一条链，第i个点与a[i]~i-1连有双向边
每次询问一个点到一个区间内所有点的最短距离和
保证区间在这个询问点的左边。
$n,q<=3*10^5$

T2

一个由0,1,?组成的字符串，？可以变成0或1。
设f[x]=1当且仅当字符串有一个长度为x的border。
求 $f[1]*1^2 xor f[2]*2^2 xor f[3]*3^2......xor f[n]*n^2$

T3

平面上有m个点，还有一个n个点的多边形。
多边形随机旋转一个角度后，问圈到的点的个数的期望。

做题

第一题一看很可做。
然而样例解释里写有可能先往右走再往左走。
接着发现往右走最多走一步。
然后发现往左走一定步数内能走到的距离一定是一段与x相连的区间。
这就可以70分了。
感觉数据结构一下就能过。
看第二题，
显然8分的n^2和10分的没有？是很好做的。
尝试用SA，SAM，KMP等去套，没套上。
看第三题计算几何？
我对计算几何一窍不通，直接弃掉。
先去码T1，先码了n方暴力，发现边数是n^3的，就变成了n^3暴力
然后去码我的70分，中途出了一些问题，到了开场两个小时才弄出70分。
100分想了半个钟想不到怎么优化，只好去搞第二题。
第二题先打了8分的暴力。
过了一段时间后发现把字符串反过来，两两对应相等的位置就和卷积的形式很像。
我naive的认为只要一个把？弄成0，一个弄成1，就可以判断1的个数是否匹配，就能过。
很高兴的去码FFT。
因为板子不够熟练，调了接近一个小时才弄出FFT。
过了样例后交，WA，TLE。
又调了一下发现当长度大于一半有重叠时，我这个做法就会有问题。
接着我想能不能在长度大于一半时有别的做法，发现我想不出来。
赶紧去码10分的KMP，搞完后比赛结束前3分钟过了18分。
心态崩了，100+ 都没有。
出去问大家，LJJ157（好像），BA200，其他人都100-
凉透了，BA应该稳了。
晚上找了个餐厅，吃烤鸭。

Day3

发约前先讲课。
D1T1就是直接搞，只有十几个人没过。
D1T2就是状压DP，前缀后缀，有几十个人过了。
本来这两题是两天的第一题的。
D2T170分基础上建树，然后用栈之类的就能搞定。
D2T2没发现一个数n-d不能成为border时，d为d的倍数的时候也不能成为border。
发现之后就直接FFT，枚举d，枚举约数就能搞定。
这两题本来是两天第二题。
吉老师上场了
“我记得有人说出题人不会毒瘤到出斗地主之类的和计算几何”
“斗地主有六种排列组合，已经用了两种了”
“出模拟题和计算几何最不容易出原题，所以我就出了”
…………
看来接下来四次比赛都会有斗地主咯？
Day1做题的正确姿势是半个小时切掉前两题，四个半小时搞第三题。
真有人搞出来了。
LJJ说的那个230提前离场的也被吉老师提到了，他留了张字条：“傻逼主斗地”。
计算几何题听完后之后感觉真的很清真。
求期望相当于求每个点在旋转后到多边形内的概率只和。
只要过原点做一个圆，圆上和多边形求交，就能知道有多少在多边形内的，就能求出概率。
然后就没了。