首页 > 其他分享 >2023 国庆 清北学堂笔记

2023 国庆 清北学堂笔记

时间:2024-04-12 22:46:27浏览次数:32  
标签:text 笔记 times 枚举 2023 清北 我们 dp dis

2023 国庆QBXT

未完结, 勿喷

Day 0

被GSS6卡了一整天 /kk

Day 1

挂大分

膜你赛125pts

原因是T1 100pts -> 50pts

被卡常力 啊啊啊啊

其实也不是被卡常了

我写的 \(\mathcal { O (n ^ 3 \log n) }\)

然而标算 \(\mathcal { O (n ^ 3) }\)

但有人 \(\mathcal { O (n ^ 4) }\) 也过去了啊啊啊

各种意义上的noip模拟赛

关于我被卡常

内存连续性!

不要把每次都改的东西放在第一维!!!

模拟赛题解

T1

Description

\(n * n\) 的网格中, 每个各自有一个颜色 \(c\) ( \(c\) 与 \(n\) 同阶 )

对于每一个格子, 求以他为左上角的并且内部颜色数量 \(\leq k\) 的正方形的数量

( \(k\) 为定值 )

Solution

正解神秘dp

但其实有一种比较好理解的做法是用类似莫队的方法去做

我一开始就用的这种

觉得实现太麻烦了就没写...

其实实现很简单~

我们先考虑一个朴素的 \(O(n ^ 4)\) 暴力

先 \(O(n ^ 2)\) 枚举一个点

然后再 \(O(n)\) 枚举一个边长

然后再开一个桶, 维护颜色数量

显然这不能过

我们考虑上面算法的瓶颈在哪里

对于每一个位置, 我们的桶都会被清空然后重新算

可是如果我们观察相邻两个位置的合法正方形

发现它们有大量重合

然后我们只需要利用这种重合就行

所以我们每次向右移动时, 把左边的和下边的从桶中删掉, 然后继续尝试扩展

然后我们又发现, 每一次, 我们每一次扩展 (加入右边和下边的) 或删除 (删去左边和下边的) 的复杂度为 \(O (n)\)

而且对于每一个点, 只会有一次删除, 所以删除次数为 \(n ^ 2\)

又因为必须加进来才能删除, 所以加入次数也为 \(n ^ 2\)

而且单次扩展或删除的复杂度又为 \(O(n)\)

所以总复杂度为 \(O (n ^ 3)\)

比 \(O (n ^ 3 \log n)\) 强

Day 2

这次真寄了

60pts

数据更逆天

质数上界改为2能过...

Day 3

省流: 寄了

这次是真寄了

某人没写 freopen 导致了0pts

显然这个人真的不是我真的不是我!

这个人是可爱的hyt

模拟赛

讲课 (dp)

容斥

要点:

  • 发现性质!

  • 找出条件

  • 展开条件, 把条件写成容斥的形式 (有一些条件, 要求一个都不能满足)

    例子:

    1. 与 \(n\) 互质 \(\implies\) 不是 \(n\) 的任何一个质因数的倍数

    2. 哈密顿路径 (恰好经过一次) \(\implies\) ①至多一次 ②至少一次 (长为 \(n\)的每个点都经过的路径)

    3. 钦定大于号

dp

设计状态时考虑如何对后面产生影响

状压dp

尝试用容斥的语言描述条件

然后将需要的变量压缩到状态中去

区间dp
  • 包含关系 or 相邻关系 => 区间dp

  • 分裂成 互不影响子结构

    如果对序列难以直接区间dp, 可以从值域上进行区间dp

    例如分裂成比当前区间最大值小的, 和比当前区最大值大的

树形dp

\(\mathcal {O (n ^ 3)}\)

难绷

简单dp优化

考虑去掉一维状态:

  • 考虑用其他的状态直接算出这一维

  • 考虑对后面的影响如何快速算出 (费用提前计算)

完了, 抽到粉兔徽章了, rp被用完了, 明天直接保龄

Day 4

模拟赛

T1

朴素的暴力可以直接对第一个和第二个数求 \(\text{lcm}\) , 然后再对刚刚的 \(\text{lcm}\) 和下一个数求 \(\text{lcm}\) , 然后就求完了..

但是这样不支持在算的过程中取模

因为我们取模回改变它的因子

比如说 \(10 ^ 9 + 8\) 显然含有 \(2\) 这个因子, 但对 \(10 ^ 9 + 7\) 取模以后, 变成了 \(1\) 没有 \(2\) 这个因子了, 这显然会对后面求 \(\text{lcm}\) 产生影响

所以, 我们考虑从质因子的角度考虑

首先, 如果我们把每个数分解成 \(\sum p_i ^ {r_i}\) 的格式

显然, 对于每一个 \(p_i\) , 所有数中这个 \(p_i\) 所对应的 \(r_i\) 的最大值都必须被乘到 \(\text{lcm}\) 里面

所以我们需要统计每个 \(p_i\) 在所有数中出现的最大次数

那么...开个桶?

可是 \(a_i \leq 10 ^ 9\) 啊

可是我们又发现, 所有 \(\geq 10 ^ 5\) 的质因数都不能出现两次以上, 也即它们的 \(r_i \leq 1\), 因为它们的平方一定大于 \(10 ^ {10}\) , 显然不会

T2

从某种状态到另一种状态的最小步数 \(\implies \text{bfs}\)

T3

第一次见到用部分分来误导选手的...

无良!黑心!啊啊啊啊啊啊!

好吧其实就算删了部分分我也不是很会

当时看到这个题, 小白逛公园在我脑海中一闪而过

然而我并不是很会合并..

啊啊啊啊啊

但其实如果仔细考虑了 \(p \leq 15\) 我直接枚举 \(p\) 的切分点来合并不就好了吗呜呜呜

额, 但其实还需要枚举前缀的长度 \(l\) 所对应的 \(10^l\) 模 \(p\) 的值

因为左区间的后缀放在右区间的前缀前时, 要乘以 \(10^l\)

所以 \(10^l\) 模 \(p\) 也要枚举

图论

生成树

T1

一个图上, 有白边和黑边两种边

求是否存在一个白边数量为斐波那契数列中的一项的生成树

Solution

设边权为白0黑1

求最小生成树和最大生成树

可以得到白边数量的上下界

又容易想到, 在白边最小的情况下, 把一条白边换成一条黑边, 就可以得到一棵新的生成树

所以, 我们知道所有白边数量在白边上下界中的生成树, 都存在

因此只需要判断是否白边数量上下界中是否存在斐波那契数列中的一项即可

T2 Tree I

wqs 二分

典!

T3

wqs 二分输出方案

random_shuffle 以后做 ...

最短路

\(\mathcal{O(n ^ 2)}\) 复杂度的 \(\text{dijkstra}\)

这很重要!

在稠密图上比 \(\mathcal{O(m \log n)}\) 跑的快的多


int dis[maxn];
bool vis[maxn];

inline int dij (int S, int T) {
    memset (vis, 0, sizeof (vis));
    memset (dis, 0x3f, sizeof (dis)); dis[S] = 0;

    for (int i = 1; i <= n; i++) {
        int now = 0;
        for (int j = 1; j <= n; j++) {
            if (dis[now] > dis[j] and not vis[j]) { now = j; }
        }

        for (int j = last[now]; j; j = es[j].pre) {
            int t = es[j].v;
            if (dis[t] > dis[now] + es[i].w) { dis[t] = dis[now] + es[i].w; }
        }

        vis[id] = true;
    }

    return dis[T];
}

差分约束
判负环

判负环, 显然需要 \(\text{spfa}\)

但有的毒瘤的题, 比如糖果, 卡 \(\text{spfa}\) 判负环

怎么办?

\(\text{spfa}\) 加上卡时

啊?

显然, 出题人要卡我们判负环, 我们就会因为入队次数太多而 \(\text{TLE}\)

所以, 当我们发现我们快要 \(\text{TLE}\) 的时候, 一定是出题人在卡我们, 也即一定存在负环

清奇的脑回路

倍增 \(\text{floyd}\) / 矩阵快速幂

就是把传统 \(\text{floyd}\) 中 \(dp[k][i][j]\) 表示前 \(k\) 个点中 \(i\) 到 \(j\) 的最短路

转化为了一个 \(\text{类floyd}\) , 用 \(dp[k][i][j]\) 表示走 \(k\) 步时, \(i\) 到 \(j\) 的路径数量

显然, 我们的 \(\text{类floyd}\) 是可以通过 \(\text{dp}\) 转移的

\[dp[a + b][i][j] = \min {dp[a][i][k] + dp[b][k][j]} \]

Day 5

神秘式子:

\[ P = a[i] \times a[j] \times a[k] + a[j] \times a[k] + a[k] \\ P = a[k] \times (a[i] \times a[j] + a[j] + 1) \\ P = a[k] \times (a[j] \times (a[i] + 1) + 1) \\ \]


\[P = a_i \times b_j \times b_k + a_j \times b_k + a_k \\ P - a_k = a_i \times b_j \times b_k + a_j \times b_k\\ \frac{P - a_k}{b_k} = a_i \times b_j + a_j\\ \frac{P - a_k}{b_k} - a[j] = a_i \times b_j\\ \frac{\frac{P - a_k}{b_k} - a[j]}{b_j} = a_i\\ \]

所以 \(n^2\) 枚举 \(i\) 与 \(j\)

Day 6

神秘式子

\[\frac{n \times (n - 1) \times (n - 2) ... \times (n - cnt + 1)}{cnt!} + n \]

根号 \(\implies\) 不停的开可以开成 \(1\)

贪心

证明: 考虑交换, 仍然最优

调度问题

Description
Solution

High Card Low Card P

考虑一个常见的套路, 枚举断点

如果我们存在一种方式可以求出

  • 前 \(i\) 个, 尽可能嬴的次数 \(f_i\)

  • 后 \(j\) 个, 尽可能输的次数 \(g_i\) (后半部分小的嬴)

然后, 又由于

Cycle

\(\text{hyt}\) 大佬有一个暴力做法居然过了

后来仔细想了想, 它实际上是在 \(\text{dfs}\) 过程中枚举了边 ( \(fa\) 与 \(u\) )

然后再 \(\mathcal{O(n)}\) 枚举一个出点 \(v\) , 如果 \(u\) 和 \(v\), \(v\) 和 \(fa\) 之间也有边, 那么, 这就是一个三元环

Day 7

省流: 怒挂100pts

挂分赛

T1

  • 70pts: 找规律

    \(1\) 的数量为 \(\dfrac{n ^ 2}{4}\)

  • 100pts: 矩阵的图论意义!

    首先我们知道, 找完 \(k = 2\) 的规律以后, 光在矩阵上看不容易发现性质

    我们又发现, \(A^k\) 特别像倍增 \(\text{floyd}\) 中的矩阵快速幂

    所以我们把初始的零一矩阵 \(A\) 看作某个图的邻接矩阵

    那么 \(A^k_{i, j}\) 的意义就是图中 \(i\) 到 \(j\) 有没有长为 \(k\) 的路径

    所以, \(k = 2\) 的图论意义就是: 使图中不存在长为 \(2\) 的链, 最多有多少边

    为了使边最多, 我们把图均匀分成两个子集 ( 每个子集大小为 \(\dfrac{n}{2}\) ) , 子集内部没有边, 子集之间可以有边

    那么边数 ( \(1\) 的数量 ) 就是 \(\dfrac{n}{2} \times \dfrac{n}{2}\)

    如果我们把它推广到不存在长度为 \(k\) 的链

    我们只需要把它分成 \(k\) 部分即可

T2

首先考虑根不变 ( 每个询问都满足 \(r = 1\) ) 的情况

杂题

#67. 新年的毒瘤

先求出所有割点

又因为删去以后要求是树

所以枚举所有割点, 把是树的留下

P5590 赛车游戏

我们发现, 必须要所有 \(1 \to n\) 的路径长度相等

如果设 \(dis_{u}\) 表示点 \(1\) 到 \(u\) 的最短路径长度

那么对于所有边 \(u, v\) , 我们有 \(dis_{u} + w_{u, v} = dis_{v}\)

证明:

首先, 在最短路中一定有 \(dis_u + w_{u, v} \leq dis_v\)

我们假设 \(dis_u + w_{u, v} < dis_v\)

那么 \(dis_v\) 必然不是由 \(dis_u + w_{u, v}\) 转移而来的

因此, 必然存在另一条更短的从 \(1\) 到 \(n\) 的路径

我们设他的长度为 \(dis_{other}\)

又因为我们要求

标签:text,笔记,times,枚举,2023,清北,我们,dp,dis
From: https://www.cnblogs.com/RainbowAutomaton/p/18132260

相关文章

  • 2023 暑假 正睿笔记
    Day1"基础"数据结构并查集每次合并集合,就在两个点之间连上边,询问就是看两个点是否在同一连通块但是朴素的并查集复杂度没有保证所以考虑优化路径压缩改变树的结构不会改变它的连通性我们考虑为什么我们之前复杂度会退化很重要一个原因就是有可能路径太长所以我们把......
  • 筛法学习笔记
    埃氏筛枚举质数\(p_i\),每次去除所有是\(p_i\)倍数的数,总效率大概是\(O(n\log\logn)\)。int_prm=0,prm[M];boolisprm[M];voidGet_phi(intn){ for(inti=2;i<=n;i++){ if(isprm[i])continue; prm[++_prm]=i; for(intj=i*i;j<=n;j+=i)isprm[j]=1; }}值......
  • 莫队学习笔记
    目录普通莫队初遇——从暴力谈起困境——乱跑的指针优化——顺路而为之带修莫队参考资料普通莫队初遇——从暴力谈起我们通过一道例题来讨论普通莫队。题目链接。观察数据范围,一个很直接的想法是:开一个数组\(cnt\),\(cnt_i\)表示在询问的区间内数字\(i\)出现的次数。对于......
  • SQL SERVER 从入门到精通 第5版 第三篇 高级应用 第10章 存储过程 读书笔记
    第10章存储过程 >.存储过程概述存储过程(storedprocedure)是预编译SQL语句的集合,这些语句存储在一个名称下并作为一个单元来处理.存储过程取代了传统的逐条执行SQL语句的方式.一个存储过程中可以包含增删改查等一系列SQL语句,当这个存储过程被调用时,这些操作也......
  • 算法学习笔记(13):同余最短路
    同余最短路是一种通过同余把状态分类,再通过建图跑最短路解决问题的算法。可以高效率解决一些特定的问题。非常的奇妙。算法鉴于学不懂,所以直接搬\(oi-wiki\)的题吧。呜呜呜。P3403跳楼机有一栋高为\(h\)的楼,初始在一楼,每次可以向上移动\(x\),\(y\),\(z\)层,也可......
  • 实验2 C语言分支与循环基础应用编程 王刚202383310053
    1#include<stdio.h>2#include<stdlib.h>3#include<time.h>4#defineN55intmain()6{7intnumber,i;8srand(time(0));9for(i=0;i<N;i++)10{number=rand()%65+1;11printf("20238331%04d\n",number);12}13sy......
  • idea2023激活码
    K384HW36OB-eyJsaWNlbnNlSWQiOiJLMzg0SFczNk9CIiwibGljZW5zZWVOYW1lIjoibWFvIHplZG9uZyIsImxpY2Vuc2VlVHlwZSI6IlBFUlNPTkFMIiwiYXNzaWduZWVOYW1lIjoiIiwiYXNzaWduZWVFbWFpbCI6IiIsImxpY2Vuc2VSZXN0cmljdGlvbiI6IiIsImNoZWNrQ29uY3VycmVudFVzZSI6ZmFsc2UsInByb2R1Y3RzIjpbeyJj......
  • node笔记1:vue+node+mongodb+studio 3T创建登录模块
    1.创建node项目:expressnodenpmipackage.json修改如下代码,便于每次修改代码都可以刷新页面:"scripts":{"start":"node-dev./bin/www"}2.如果配合node设置反向代理;3.添加mongoose模块提供数据库信息:npmimongoose--save4.以登录功能模块为例,项目文件如下:model......
  • VUE2.0版本学习笔记
    VUE2.0版本学习笔记脚手架安装npminstall-g@vue/clivuecreatevue2-practice#选择2.0版本如果执行中遇到错误,yarn的错误certificatehasexpired则执行yarncachecleanyarnconfigsetstrict-sslfalsecdvue2-practicenpmrunserve#初学者建议安装vsco......
  • 2023蓝桥杯 java A组 小蓝的旅行计划
    最小堆(优先队列)和区间树(线段树,红黑树)的结合java中有自己实现这两种数据结构的对象(1)最小堆(优先队列)PriorityQueue<int[]>minHeap=newPriorityQueue<>(newComparator<int[]>(){//int[]三个元素第一个cost第二个lim第三个tag @Override publicintcompare(int......