「刷题」THUPC泛做
刷了一下,写一下。
T1.
天天爱射击
可以这样想。
我们二分一下每一块木板在什么时刻被击碎。
然后直接用主席树维护的话是\(O(nlog^2n)\)的。
会\(T\),而且是一分不给那种。。。
那么换个想法,既然都用主席树了,还二分啥。
可以直接主席树上查区间排名。
似乎也可以整体二分。
复杂度\(O(nlogn)\)
T2.
机场
很神仙的一个网络流。
首先离散时间点。
然后先假设飞机都停到\(B\)区了。
那么一架飞机是否在\(A\)处停,有两种选择。
一种停一种不停。
分别建边,然后费用设为两种情况的代价即可。
这样某些流在某些事件溜出去,然后再混进来,这个过程中出去就相当于是在\(A\)停了一停。
求最小费用最大流即可。
费用就是答案。
T3
体育成绩统计
按题意模拟。
T4
玩游戏
我们发现我们只需要\(check\)出两人得分是否是个数\(n\)的等差数列求和。
如果不是判无解。
否则我们尽量用大的数给第一个人决策。
可以发现因为最小的数是1,所以无论如何都会存在解。
T5
小\(L\)的计算题
和清华集训2017生成树计数一样。
是那道题的套路之一。
T6
绿绿与串串
是一个类似马拉车+\(dp\)的东西。
一个点的回文如果右端点到\(n\)那么合法。
如果一个点的右端点合法并且左端点到\(1\)那么也合法。
代码特别妙。
T7
好图计数
一个比较厉害的\(dp\)。
我们发现联通的好图和不连通的好图是一一对应的。
设\(i\)个点的好图个数\(f_i\),\(i\)个点联通的好图个数是\(g_i\)。
那么当\(i>1\)的时候\(f_i=2g_i\)
设\(f_0=1\)。
设\(\{f\}\)的生成函数为\(F(x)\)。
那么\(F(x)=\sum\limits_{i=0}^{+\infty}f_ix^i\)。
然后考虑求\(F(x)\)。
因为一个好图的每一个连通块自然都是好图。
那么我可以用\(f\)和\(g\)来求出\(f\)。
考虑每一个连通块的大小和这种大小的连通块在图中存在的个数以及这种大小连通块的种类数。
那么有:
\]
那么用一下形式幂级数求和,然后开始倒腾式子。
F(x)&=\prod\limits_{i=1}^{+\infty}\left(\frac{1}{1-x^i}\right)^{g_i}\\
ln(F(x))&=\sum\limits_{i=1}^{+\infty}g_iln\left(\frac{1}{1-x^i}\right)\\
\frac{F'(x)}{F(x)}&=\sum\limits_{i=1}^{+\infty}\frac{g_iix^{i-1}}{1-x^i}\\
F'(x)&=F(x)\sum\limits_{i=1}^{+\infty}g_iix^{i-1}\sum\limits_{j=0}^{+\infty}x^{ij-1}\\
[x^n]F'(x)&=(n+1)f_{n+1}\\
&=\sum\limits_{k=0}^{n}f_k\left([x^{n-k}]\left(\sum\limits_{i=1}^{+\infty}g_iix^{i-1}\sum\limits_{j=0}^{+\infty}x^{ij-1}\right)\right)\\
&=\sum\limits_{k=0}^{n}f_k\sum\limits_{i|(n-k+1)}g_ii\\
\end{aligned}\]
设\(s_i=\sum\limits_{j|i}g_jj\)
然后求出\(f\)之后就可以顺手求出一个\(g\)来。
可以做一个\(O(n^2)\)的递推卡常过去。
或者就干脆做一个\(nlog^2n\)的分治\(NTT\)就行了。
T8
找树
似乎是远古杂题了。
事实上我们要求的就是每一种权值的方案数是否为0.
怎么做?
首先我们发现不能拆位来做。
就很恶心。
否则可以直接做矩阵树定理来求这个东西。
我们其实仍然可以拆位来做。
用\(exFWT\)来把每一位拆成点值。
然后直接用边缘矩阵树定理处理这个桶,求出每一个位置应当有的权值。
这相当于对所有的点值做一个树形乘法。
正好符合点值对位相乘的性质。
得到的新桶我们在\(exFWT\)回来就得到了最终的方案数数组。
\(exFWT\)的用法是在每一位可以用不同的位运算来计算。
只需要在不同的位用不同的\(FWT\)计算方法就可以。
正确性显然。
最新文章
- Basic Tutorials of Redis(9) -First Edition RedisHelper
- async.whilst 的一个简化版实现
- C++ 画星号图形——空心三角形(星号居中对齐)(核心代码介绍)
- 浏览器主页被hao123贱贱的篡改的一种方式
- python 核心编程课后练习(chapter 5)
- nginx location在配置中的优先级
- Question store (Repeated review)
- 现代程序设计——homework-01
- [Python笔记][第一章Python基础]
- Java中的字符串驻留
- pro-engineer&;UG
- JSP中的include有哪些?有什么差别?
- Dubbo死磕之扩展点加载ExetnsionLoader
- android 使用Retrofit2 RxJava 文件上传
- Apache Commons Beanutils 二 (动态Bean - DynaBeans)
- 【iCore4 双核心板_ARM】例程十:RTC实时时钟实验——显示时间和日期
- CSVN部署安装,实现web管理svn
- random库的常见用法
- Android HandlerThread和IntentService
- 存储类、链接和内存管理(c prime plus)
热门文章
- jquery实现强制刷新
- TypeScript 中装饰器的理解?应用场景?
- springmvc配置过程中遇到的一些问题总结
- 【Sass/SCSS 完整自学中文版教程02】SCSS 官方英文文档翻译整理
- 谷歌浏览器chrome安装插件报";程序包无效: CRX_HEADER_INVALID";错误
- Centos7 搭建sonarQube
- 自动化测试报告----allure2(一)
- 关于selenium添加使用代理ip
- Cookbook:pandas的学习之路——10 Minutes to pandas
- .Net Core 实现 自定义Http的Range输出实现断点续传或者分段下载