CCPC2019吉林省赛&&东北地区赛游记

深藏阁楼爱情的钟 2021-12-13 13:11 305阅读 0赞

***Preface***

第一次打正式的线下赛  
三天，两场热身赛两场正赛，有点累

--------------------

***Day 0***

一大早从大学城叫滴滴去车站，差点迟到qwq  
长春居然有早高峰堵车这种东西噗噗噗，最后勉强赶上了

在宾馆住下后带队老师说要请我们吃饺子，结果点了28盘把我们吃到吐orz  
中午和同房间的谷神仙愉快地打了会雀魂~

下午去报道，领了T恤，所有人都是A(Yuan)C(Liang)的颜色呢~  
看了下手册，队名各种搞怪233  
比如：  
cxk系列：“你打代码像cxk”、“鸡你太美”、“基拟钛镁”、“acm练习生”  
为难主持人系列：“我们一起学土拨鼠叫啊啊啊啊啊啊啊”、“以上是本次比赛全部获奖队伍感谢大家的支持与信任本次比赛到此结束请各位有序退场”  
其他梗系列：“4396”、“我套你猴子”、“我A不出来啊”  
......

热身赛下午五点开始，我们就在食堂待着等到四点吃饭，东北电力大学的伙食居然比我们的好233 按带队老师的说法，这里的老师工资都比我们的老师高

省赛热身赛还是比较快乐的

上来先敲个A+B

接着是一个没有输入的打表题，题意：给你一些数字问你能否用加减乘除算出24（最多只能交20次，样例输出注明不一定是正解）  
谷神仙打了个表，发现前面几个都和样例一样，就直接把样例交了上去结果WA了  
老老实实接着打表，发现除了最后三个数据打表跑不动了之外，其他和样例确实是一样的 出题人真骚 ，然后就开始猜后面三个，猜了三次A了 据说有些头铁队伍是手算的233

接着是图论，讨论了半天发现是个 水 题，tarjan缩点计个数就完事了

然后是一个概率题，答案是确定的，但是精度要精确到第n位  
神仙看了下样例输出：6.9、6.97  
然后盲猜答案是6.9666666...  
结果猜对了 真快乐 ，只是第一次交漏了个特判233

最后一个题题面有点烦，也没啥时间看了，就没管这个题了

回宾馆之后开始和其他几个队伍骚聊，十一点多一起搓了顿KFC，久违地在独卫洗了个热水澡，舒服了~  
睡前想起小破站最近把K-ON买回来了，就重温了一下

--------------------

***Day 1***

早上8点到，开幕式完之后就进场了  
坐着骚聊了半小时开始了

I题签到题，按题意模拟

A题，按题意模拟+剪枝 但我们一直怕T，结果瞎忙活了一会看别的题去了，后面补上了

G题，判断一个点是否在一条射线上，水题

E题，摆成n个小正方形，最少需要多少根火柴，推一下就行了

B题，想了很多种做法，都因为复杂度被否决了最后也没A

C题数据结构题，一看时间是12s，溜了溜了

D题，题意：是一棵有根树上所有点都有一个权，定义一个点集的价值是它们LCA的权，求所有点集的价值和，火神仙飞快地想到了做法：  
考虑一个点如果是某个点集的LCA，分两种情况：  
如果点集包含这点，那么余下的点只能从以这点为根的子树上选  
如果点集不包含这点，那么点集至少包含两个点，这两个点来自这一点的不同子树  
这点的贡献就是它的权乘上可行的点集数  
预处理出每个节点为根的子树的节点数，枚举每个点为LCA算下总贡献即可

J题，题意：给定一个整数n ，求 \\(\\lfloor\\)\\(cos^2(\\frac\{(n+1)!+1\}\{n\}\\pi)\\)\\(\\rfloor\\)  
显然只有当 \[(n+1)!+1\]%n=0 时结果为1，其他都是0  
打完表之后发现是n为素数时才满足这个条件，然后才想起来这个东西叫威尔逊定理233

F题，题意：给定一个无向连通图，点到点之间的距离都是最短的，在保证原图的连通性和点到点的距离最短的情况下尽可能地删边，求最后能剩下几条边  
跑一个类似Floyd的东西枚举一下就行了~

H题，题意：给定若干个u、若干个d，u表示+1，d表示-1 ，保证非负的情况下这些u和d有多少种排列方式  
一开始跑偏了，往数学折线图之类的想去了，结果就这样一直死磕到比赛结束，看到解题报告上“进栈出栈”瞬间就想到了卡特兰数！  
应该用卡特兰数的组合数形式+Lucas定理就能过了orz

最后9道题A7道，金末qwq  
第一次参加比赛，感觉很不错  
老实说我感觉我自己真的是零贡献  
打字慢，人又菜，全靠神仙带飞QAQ

吃完晚饭继续东北地区赛的热身赛  
然后自闭之旅就开始了

A题，Not A+B （这个是题目名233），水

B题，题意：求1-n有多少个数可写成 \\(a^\{a^\{...^a\}\}\\) 的形式（至少是 \\(a^a\\) ）  
这个时候我们已经很累了，脑袋都转不动，随便写了一下就交了  
WA  
WA  
打了表  
还是  
WA  
WA  
...  
最后发现 \\(3^\{3^3\}\\) 爆了long long还变回正数去了orz  
然后我们重新检查了一下表交上去A了

C题，题意：给定一个序列 \\(p\_1,p\_2,...,p\_n\\) 问有多少个数对 \\((i,j)\\) 满足 \\(i<j\\) ，\\(p\_i\\) 是 \\(p\_j\\) 的倍数  
一开始往分解因数那方面想了  
后来火神仙发现不用这么麻烦  
数据并不大，给每个数一个权，一开始为0  
从后往前遍历，每遍历到一个数就加上这个数的权，然后把数据范围内该数的倍数的权都加1即可

D题，题意：给出三个人的某次考试的选择题答案，选项只有ABCD，  
求使得三个人中最低分的那个人的分数最高的正确答案  
现场没想到，晚上回宾馆想了一下发现是个贪心模拟：  
简单写下步骤，  
尽可能地使正确题目数多，在这一前提下使得每个人的分数相同  
把每一道题按有几个人的选项是一样的分一下类，并按以下步骤处理

1.  对于三个人的选项都一样的题，显然这一题的正确答案应该就是这个选项
2.  对于有两个人的选项是一样的题，假设三个人是 \\(x\\) ，\\(y\\) ，\\(z\\)  
    记 \\(i\\) 和 \\(j\\) 的选项是一样的题的集合为 \\(ij\\)  
    则有 \\(xy\\) ，\\(xz\\) ，\\(yz\\) 三个集合  
    设最小的那个集合题目数为 \\(k\\)  
    则每个集合选 \\(k\\) 个题目出来，并从集合中删除，题目对应的正确答案就应该是两个人相同的那个选项  
    (1)如果三个集合题目数一样，那么就选完了  
    剩下0个有两个人的选项是一样的题，和三个人的选项都不一样的题  
    (2)如果有两个集合的题目数一样的  
    剩下若干个有两个人的选项是一样的题，和三个人的选项都不一样的题  
    (3)如果三个集合的题目数都不一样，不妨设剩下的较小的集合的题目数为 \\(t\\) ，同样的，剩下的两个集合中各选 \\(t\\) 个题目，并从集合中删除，题目对应的正确答案就应该是两个人相同的那个选项  
    剩下若干个有两个人的选项是一样的题，和三个人的选项都不一样的题
3.  做完以上两个步骤后，三个人所得分数相同且总和最大，且都转换为剩下若干或0个有两个人的选项是一样的题，和三个人的选项都不一样的题，剩下的问题就很就很简单了，不讲了

晚上回去带队老师又请吃饺子，顶不住了  
回到房间后继续和谷神仙打雀魂，继续和队友骚聊  
不过我发现我开始插不上话了  
谷神仙是真的神仙，神仙到我无法形容 有兴趣搜一下KAAAsS's blog  
夜深了

“吃泡面吗？”  
“为什么不呢？”

于是打电话到前台让送上了两个233  
吃完看了两集K-ON又睡了

--------------------

***Day 2***

很惨烈

J题，签到题

B题，一开始没读懂题，后来读懂了又想复杂了orz搞搞前缀和应该就得了

C题，题意：给定一些直线，问有交点的线对对数，重复的两条线也算一对  
谷神仙的做法和解题报告的是一样的，先算重合直线的对数，然后将边都平移到过原点，令平行或重合的直线为一个集合，并统计集合中线的数目，然后乘起来加上重合直线的对数即可，但是莫名其妙我们一直WA...WA到自闭

D题，不会

E题，我们过的第二个题，也是最后一题QAQ  
题意：给定一棵树，和每条边的边权，将原图中的边取出化为点，在原图中有公共点的两条边化为的点之间连一条边，边权为原来的两边之和，求新图的最小生成树边权和  
暴力建图是不行了，一开始我们就跳了，后来其他题都做不了就又回来做这个了  
最后火神仙想到了做法，考虑每个节点对答案的贡献，度小于2的点无贡献，否则，该节点的连边化为的点在新图中形成一个完全图（团），这一部分的最小生成树即是每个边化为的点向边权最小的边化为的点连边

F题，鬼畜博弈，不会

G题，题意：平面坐标系上给定若干由单位格子组成的正方形，求最小的移动格数使得所有正方形相交于一个单位格子  
当时没想到要横纵分开来考虑orz这样就只用考虑一维的了  
设一维时，交点为x ，\[l,r\]移动到x的代价为 \\(\\frac\{|l-x|+|r-x|-|r-l|\}\{2\}\\) ，则只需使 \\(\\sum\_\{i=1\}^n(|l\_i-x|+|r\_i-x|)\\) 最小，一个结论，x取所有l ，r的中位数时最优

D题，题意：有若干连续点，开始时高度均为0，每个点有一个目标高度，每次可选择一个区间使这段区间上的点高度加1 ，直到到达到目标状态。有两种操作，一种是选择一个区间，使得这个区间上的点的目标高度都加k ，一种是询问当前所有点高度都为0时，最少要经过多少次区间增高才能到达目标状态。  
先不考虑修改目标状态，则操作次数即为目标高度从左到右的上升高度之和（画个图看看就知道了），那么维护目标高度的差分前缀和、差分数组中的正数的前缀和即可，用树状数组或线段树优化。  
当时觉得这题看上去比较难，没有跟榜写orz血亏

I题，题意：给定一个非降序列 \\(a\_1,a\_2,...a\_n\\) ，求有多少个非降序列 \\(b\_1,b\_2,...b\_n\\) 满足 \\(b\_i \\leq a\_i\\) ，其中 \\(a\_i\\) ，\\(b\_i\\) 均为正整数  
设当前为第i位，数字为j的方案数为dp\[i\]\[j\]  
容易得出状态转移方程 \\(dp\[i\]\[j\]=sum\_\{k=1\}^jdp\[i-1\]\[k\]=dp\[i\]\[j-1\]+dp\[i-1\]\[j\]\\)  
然后，后面的优化就不会了，要用多项式乘法之类的orz

A题，巨难，解题报告都好几页

最后10道A两道，现场大多数队伍也差不多，混了个铜QAQ  
大一的一起自闭

最后自闭地去车站，自闭地上火车，自闭地回到大学城附近  
谷神仙表示之前吃KFC因为太晚了没有吮指原味鸡  
于是又去了一次233

--------------------

***Epilogue***

省赛很欢乐，东北地区赛的结果不尽人意  
有得有失吧qwq

转载于:https://www.cnblogs.com/MakiseVon/p/10909501.html