PKUSC 2022 口胡题解
\(PKUSC\ 2022\)口胡题解
为了更好的在考试中拿分,我准备学习基础日麻知识(为什么每年都考麻将 啊啊啊)
首先\(STO\)吉老师\(ORZ,\)真的学到了好多
观察标签发现,这套题覆盖知识点广,难度适中,是一套不可多得的题
\(DAY1\)
\(T1\)
考虑过程必然是,一个值小的在参加若干轮之后超过大的,然后目前值小的参加若干轮依次交替
首先考虑单个变量
我们枚举\(i\)向后跳的第一步,假设跳到\(i-j,\)然后后面的过程是
\(i->j\)表示进行若干轮之后,中间过程不超过\(i,\)最后一次直接到\(j\)
\(i->^{k}j\)表示\(i\)进行若干轮到\(j,\)中间过程在\([i,j]\)之间到的第一个数是\(k\)
\(x_{st}=i-j,x_{ed}=i+k\)
\(Sit_1:\)我们过程中没经过\(i-j+1 ...i\)里面的位置,等价于事件\(i-j->i+k\)
\(Sit_2:\)我们过程中经过了\(i-j+1 ...j,\)可以拆分为事件\(i-j->l\)和事件\(l->^i i+k\)
得到如下递推式
\(i\)从小到大计算\(p(i->i+k)\)
\(j\)从小到大计算\(p(i-j->^i i+k)\)
解方程得到\(p(i->i+k)\)
然后我们两个变量,设\((i,j)\)表示较大值为\(i,\)较小值为\(i-j\)
然后枚举\(k\)第一个大于\(i-j\)的值
\(k<=i,(i,j)->(i,i-k)\)
\(k>i,(i,j)->(k,k-)\)
复杂度\(O(nm^3)\)
\(T2\)
很\(nb\)的数据结构\(+\)容斥
其实\(sub_4\)已经极大提示了正解
我们能贡献的线段全部用颜色标出来,我们的贡献大概分成这几种类型
我们可以使用容斥,\(Sum-out,\)对于\(out\)我们只需要对于\(x,y\)分别维护两棵线段树使用扫描线解决
在\(x,y\)轴的线段树维护区间和(区间和乘导数)就很容易得到了
那么我们的正解只需要得到一个恰当的扫描序列,然后和\(sub_4\)一样做法,可以使用平衡树\((set)\)得到序列
这个序列保证了在询问后面的线段一定不会贡献,那么\(Sum\)一定不会算进去后面的线段,前面的线段直接扫描线即可
\(T3\)
最最基础的暴力分,可以二分答案\(+\)线性规划(单纯形随便跑)
最基础的暴力分,可以二分答案\(+\)网络流
正解,我们只需要找到一个能流满的最大流即可,使用\(Hall\)引理(我\(TM\)原来没听过,貌似全机房都不会,那没事了)
\(Hall\)引理(二分图存在完美匹配的充分必要条件)
对于右部点所有子集,\(Sum(left->x)>=Need(x),\)我们对于所有的式子求一个\(Min\)即可
\(DAY2\)
\(T1\)
当我看到第一个式子的时候就半掉线了
大概听懂了\(70\%\)
放上\(sol\)截图,我大概是胡不出来了
大概是一个转化成二分图求联通块方案数的问题
复杂度\(O(n^6)\)
\(T2\)
首先,这题怎么想都不会想到是随机,啊啊啊
首先对于颜色\(x\)的边共\(Num_x\)条,前\(Num_x-1\)条随机赋值,最后一条为前\(Num_x-1\)条的异或值
首先如果一条路径的异或和为\(0,\)大概率把包含的颜色所有边都包含了(为什么是大概率,可能会出现,两个不同颜色的边都不是\(0,\)异或出来\(0\),我们只需要\(mt19937(time(0))\)多次提交(看运气能否在\(32\)发以内\(AC\))即可
我们设\(v_i\)为\(1->i\)的路径权值,\(v_i\ xor\ v_j\)比较显然的是\(i->j\)路径的异或和,我们只需要对于\(v_i\)相同的求一个路径最长的即可
题目说了对于删点之后的操作,先求出最长路径,最最长路径外面的点答案必然是\(Max,\)内部的点\(x\),贡献可以分为,左边过来的,右边过来的,子树内部即可
然后我们最长路径从左往右扫一遍,从右往左扫一遍,维护一个可插入的数据结构,每个点都查询一下左右最大值即可
\(T3\)
比较套路的思路,比较套路的\(dp\)状态,基本上可以参考近几年的麻将题的\(dp\)思路
甚至可以搜索
吉老师\(:\)我们暴力搜索通过前\(3\)个\(sub\)的同学加了卡时之后可以获得前\(4\)个\(sub\),而我们暴力搜索通过前\(4\)个\(sub\)的同学可以通过增加卡时获得\(AC\)
。。。。。。。。。。。我会了,以后一定写卡时
最新文章
- Java线程池解析
- GitHub 实现多人协同提交代码并且权限分组管理
- 【转】MySQL中varchar最大长度是多少?
- contentResolver
- stm32的DFU使用方法
- 在一个文件中有10G个整数,乱序排列,要求找出中位数
- linux根目录详解
- Android得到控件在屏幕中的坐标
- ThinkPHP - 事务操作
- C++虚函数实现多态原理(转载)
- MySql_5-7安装教程
- Git学习:如何登陆以及创建本地代码仓库、并提交本地代码至Github(最简单方法)
- 老菜鸟学习:Javascript 将html转成pdf
- nginx实战四
- 分区实践 A PRIMARY KEY must include all columns in the table&#39;s partitioning function
- Angular2 不明真相第一个Demo例子
- Python 控制台进度条的实现
- R的农场
- ES6-浏览器运行环境配置方法
- DAY7-面向对象之绑定方法与非绑定方法
热门文章
- MySQL体系结构与数据类型
- 129_Power Pivot&;Power BI DAX不同维度动态展示&;动态坐标轴
- 以点类 Point 及平面图形类 Plane 为基础设计三角形类 Triangle
- 关于我学git这档子事(3)
- 浅谈BSGS和EXBSGS
- 优秀开源平台,前后端分离快速开发平台,一站式多端开发(PC+APP)
- 从零开始实现lmax-Disruptor队列(一)RingBuffer与单生产者、单消费者工作原理解析
- 【C++函数题目】重载求数组中最小值的函数
- 如何实现Springboot+camunda+mysql的集成
- BUUCTF-神秘龙卷风