首页 > 其他分享 >省选计划(第一周)

省选计划(第一周)

时间:2023-07-17 23:25:03浏览次数:33  
标签:线段 log 第一周 省选 复杂度 个数 计划 练习册 k0

知识回顾:

  • 巩固:生成树,DP,分层图,简单数论,线段树。

  • 深入研究:网络流。

  • 简单了解/没学明白:FFT。

练题:

P6144 [USACO20FEB]Help Yourself P

定义 \(f_r\) 为以 \(r\) 结尾的线段集合的总贡献。

对于一个线段 \([l,r]\) 可以考虑分成 \([1,l)\), \([l,r]\) 和 \([r+1,n]\) 三种情况转移。

区间求和,区间乘 2,显然可以用线段树。

由于 k 次方的存在,线段树的每个结点还需维护 \(d_i\) ,表示值的 i 次方为多少。

复杂度 \(O(nk^2 \log k)\) 。

AT_abc280_d [ABC280D] Factorial and Multiple

先给 k 分解质因数,接着二分 x ,判断 x! 是否能包含 k 的所有因子。

而对于 x! 中质因子 d 的个数,可以在 \(O(\log x)\) 内计算出来,即:

\[\sum\limits_{i=1}^{\log_d x}\left\lfloor \frac{x}{d^i}\right\rfloor \]

每个因子都算一遍,判断大小即可。

P4568 [JLOI2011] 飞行路线

k 很小,直接建一个 k 层的分层图然后跑一边最短路。

Grid 2

很久以前在信友队里做过的一道题,偶然看见就又做了一下。

非常经典的容斥 DP。

定义 \(f_i\) 为从起点走到第 i 个障碍点的方案数,则转移方程为:

\[f_i=\dbinom{x_i+y_i-2}{x_i-1}-\sum\limits_{j(x_j\le x_i, y_j \le y_i)}^{n}f_j \cdot \dbinom{x_i-x_j+y_i-y_j}{x_i-x_j} \]

最后 \(f_n\) 即为答案。

P2261 [CQOI2007]余数求和

题目要求我们求出 \(\sum\limits_{i=1}^{n} k\mod i\) 。

稍微转化一下变为 \(n \cdot k - \sum\limits_{i=1}^{n}i \cdot \left\lfloor \frac{k}{i}\right\rfloor\) 。

可以用除法分块 \(O(\sqrt{n})\) 解决。

P5687 [CSP-S2019 江西] 网格图

64pts 很好拿,暴力建图暴力 kruskal。

然后我们发现其实只用考虑横条和纵条。

先将它们的权值从小到大排序,然后考虑加入当前条后又多少个边需要选上即可。

P1231 教辅的组成

网络流基础题。

原点 s 向练习册连边,练习册向答案连边,答案向终点 t 连边。边权均为 1。

为了防止同一本练习册被走多次,将其一本练习册拆为两个点,边权为1。

跑一边 dinic/EK 就行了。

P3171 [CQOI2015]网络吞吐量

显然可以先跑一边 spfa 求出 dis 数组。

然后只需要考虑在最短路上的边,即 \(dis_v==dis_u+w\)。

由于容量限制在点上,我们要拆点,之后就是各种连边。

OPTM - Optimal Marks

可以先将问题简化,逐位计算。

每个给定值的点的点权都变为了0/1。

把 0 连向 s,把 1 连向 t,求一边最小割就行了。

P4174 [NOI2006] 最大获利

最大权闭合子图模板题。

净收益 = 实际总收入 - 实际总成本 = 全部的收入项 - 放弃的收入项 - 必要的成本项 = 全部的收入项 - (放弃的收入项 + 必要的成本项)

后者就是一个最小割问题。

总结了一首打油诗:

成本收入两头连,依赖关系无穷边,从源找出最小割,全部收入往下减。

P4001 [ICPC-Beijing 2006] 狼抓兔子

平面图转对偶图,疯狂建边,跑一边最短路。

模拟赛:

校内模拟赛:

T1: 解方程

老套路题了,meet in the middle。

T2:序列

老 DP 题了,定义 \(f_{i,j}\) 为 i 的全排列中逆序对个数为 j 的个数,转移直接从 i-1 里找就行,可以用前缀和优化到 \(O(nm)\) 。

听说有更优的做法,之后研究一下。

T3:完全图

老生成树题了,按边权从小到大枚举每一条边,合并的时候计算一下端点分别在两个连通块里的边的个数,并将其边权定为 w+1。复杂度 \(O(n \log n)\)。

T4:平面上的点A

有点意思。

赛时做法:复杂度 \(O(n \log n \log n)\)。

考虑从大到小枚举 y 的坐标,然后二分 x 的坐标,利用树状数组快速计算出四个区域的个数。

设 k0~k3 表示从左上角顺时针区域的个数。

则我们可以定义 s 树状数组实时更新 k0 的大小。

然后再搞一颗维护以点的 x 坐标为关键字的树状数组,用来计算 (k0+k1),和一颗以点的 y 坐标为关键字的树状数组,用来计算 (k2+k3)。

相减即可得出 k0~k3 的值。

更优的做法:复杂度 \(O(n \log n)\)。

我们先二分答案 ans。

然后从下到上枚举 y 坐标。

可以发现上半部分的个数越来越少,下半部分的个数越来越多(废话。

于是可以用类似双指针的方法在上下两部分分别找到最后一个能使 k0 和 k2 小于等于 ans 的位置,并更新答案。

T5:密钥

简单题。

两两枚举,找到第一个不相同的位置,并连一条边,最后判断一下有没有环即可。

复杂度 \(O(能过)\)

标签:线段,log,第一周,省选,复杂度,个数,计划,练习册,k0
From: https://www.cnblogs.com/HQJ2007/p/17561591.html

相关文章

  • 省选计划(第三周)
    知识回顾:巩固:概率DP,错排,组合数深入研究:组合数,后缀数组,tarjan,2-SAT简单了解/没学明白:练题:[ABC280F]PayorReceive概率DP。定义\(f_i\)为把怪物打成i滴血的期望攻击次数。令\(p=\frac{p}{100}\)。则\(f_i=f_{i+2}\cdotp+f_{i+1}\cdot(1-p)+1\)。最终......
  • 省选计划(第二周)
    知识回顾:巩固:二分,倍增,优化DP,莫队,分数规划,网络流,二分图,贪心,set/map,KMP深入研究:分治(线段树分治),后缀数组,费用流简单了解/没学明白:线性基,边分治,数位DP,博弈论练题:[SCOI2015]国旗计划直接模拟复杂度\(O(n^2)\),显然会超时,于是考虑倍增。定义\(st_{i,j}\)表示从i这条......
  • 省选计划(第五周)
    知识回顾巩固:线段树,贪心深入研究:数论,容斥,除法分块,根号分治简单了解:lucas,prufer序列,莫比乌斯反演练题P2606[ZJOI2010]排列计数可以发现这符合小根堆的性质,把它建出来。定义\(f_u\)为以u为根的子树的方案数,转移方程为:\[f_u=\dbinom{siz_u-1}{siz_{2\cdotu}}\c......
  • 省选计划(第四周)
    第四周知识回顾巩固:2-SAT深入研究:概率与期望简单了解/没学明白:练题P3825[NOI2017]游戏很麻烦的2-SAT。如果没有x,就是个传统的问题。然后我们发现d的取值很小,考虑对于每个x枚举其类型为a还是c。为什么不枚举b呢?因为a、c已经包含b了。连边的时......
  • 省选计划 (第七周)
    练了好久CF&AT的题,现在要回归省选计划了!知识回顾巩固:二维树状数组深入了解:可持久化数据结构简单了解/没学明白:练题P3567[POI2014]KUR-Couriers主席树模板题。如果左子树的个数大于右子树的个数,则递归左子树,否则右子树。最后到达单点的时候就判断一下个数是否......
  • 省选计划(第六周)
    知识回顾巩固:Lucas,网络流,二分图深入研究:背包DP,树形DP,区间DP,状压DP。简单了解/没学明白:博弈论,插头DP练题Workingroutine读完题后以为矩阵可以相邻,费了一个小时去写...(可恶直接暴力交换复杂度是\(O(nmq)\),无法接受,考虑链表。对于每个点i,定义\(right_i\)为i的......
  • 暑假第一周总结
    周一:今天没有学习,在家玩了一天周二:今天看网课复习了一下python周三:今天进行python环境配置周四:今天玩了一天,没有学习。周五:今天进行数据库的连接。周六:今天继续连接数据库又看了一下爬虫的概念周日:今天玩了一天没有学习。......
  • 假期计划
    为表假期好好学习之决心,特此制定一份基于大尺度宏观计划和小尺度每日时间规划的假期学习计划。·每日时间规划\(7:30\)\(ard.\)起床,洗刷,吃饭。$8:30$开始上午学习具体学习内容:1:各科假期作业(语文、数学、英语、物理、化学、地理)2:学习优先级(语文\(\rightarrow\)英语\(\r......
  • 大二假期第一周博客
    这一周我没有写什么比较实际的代码,我把自己整个电脑重新装了一遍系统,同时整理了需要的应用和环境,在这一周里基本安装完成,我整理的所需的环境如下: 我这里简单描述一下这些东西。首先是我们的几大环境,分别是java,c++和python,这三个是我目前常用的环境。其中java环境所需资源较......
  • 暑假第一周总结
    第一周主要学习了python还有hadoop的前期内容,还有Linux的基本命令,shell的基本命令python里面学习了python的注释方法,python里面的基本的三个函数input(),print(),type(),python的格式化输出。Hadoop里面学习了Hadoop是什么,Hadoop的基本概念,Hadoop里面的三大分类HDFS,YARN,MapReduce。安装了......