文章作者: wweiyi
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 wweiyiのblog！
相关推荐
2021-11-19
【全程NOIP计划】初级数据结构1
【全程NOIP计划】初级数据结构1 在线：每次询问之后，立马可以得到查询结果 离线：知道所有需要查询的值，然后一次输出查询结果 STL中set的用法 用迭代器 并查集 可以支持一些不相交集合的合并和查询 我们可以树形结构来组织数据 同一个集合的元素组成一棵树 因为集合没有交，所以最终构建得到的是一个森林 将树的根节点作为集合的代表元 开始的时候为n个孤立的点 查询一个点所属集合 1234int get(int x){ return fa[x]=(x==fa[x]? x:get(fa[x]));} 这里做了一个路径压缩，使这颗树变得扁平，大大减小了查找的时间 合并 1234void merge(int x,int y){ fa[get(x)]=get(y);} 如果是启发式合并的话，是把较小的树插到较大的树 用处 1.可以做最小生成树 也就是kruskal算法 2.还可以用来判环 P3958 奶酪 思路 实际上处理一个上界，处理一个下界，然后判断上面和下面能不能连通就可以了非常简单 123456789101112131415161...
2021-11-19
【全程NOIP计划】分治与倍增
【全程NOIP计划】分治与倍增 分治 分治就是分而治之，化整为零的思想 分治的原理是把困难的大问题化解为简单的小问题 然后先解决小问题，然后根据小问题的答案解决大问题 它本质上不是一个算法，而是一个思想 比如快速幂，倍增求lca，归并排序，线段是cdq分治，甚至后缀数组FFT都利用了分治思想 分治虽然不经常出题，但是也非常有用 快速幂 快速幂可以在O(logb)O(logb)O(logb)的时间复杂度内计算aba^bab 方法很简单 注意到如果b是偶数，那么就可以先计算ab2a^{\frac{b}{2}}a2b,这样问题的规模就减少了一半 如果b是奇数，那么我们就可以计算ab2a^{\frac{b}{2}}a2b平方之后再乘a，问题规模同样以不大的代价减少了一般 这里的aba^bab就是大问题，而ab2a^{\frac b 2}a2b就是小问题了 12345678910111213141516171819long long f(long long a,long long b,long long c){ long long temp=f(a,b/2) ...
2021-08-01
【全程NOIP计划】模拟赛#2
【全程NOIP计划】模拟赛#2 爆零，实际上T2本来可以得20分的，那就是Rank57 0+0+0+0=0 我太水了qwq A.二进制 题目描述 在本题中，我们定义两种新的位运算。对于一个 nnn 位的二进制整数 xxx，定义对 xxx 进行递增或表示把 xxx 赋值为 xxx 和 x+1x+1x+1 的按位或。类似的，对 xxx 进行递减与表示把 xxx 赋值为 xxx 和 x−1x-1x−1 的按位与。其中，加法和减法都遵循自然溢出，也就是对 2n2^n2n 取模。在此基础上，定义 xxx 的距离表示从 000 开始，使用这两种运算达到 xxx 的最小运算次数。 给定一个 nnn 位的二进制整数 xxx。有 mmm 次操作，每次操作的格式是一个整数 vvv，具体意义如下： 如果 v>0v>0v>0，对 xxx 连续进行 vvv 次递增或。 如果 v<0v<0v<0，对 xxx 连续进行 ∣v∣|v|∣v∣ 次递减与。 每次操作之后，你需要输出 xxx 的距离。 输入格式 第一行输入两个整数 nnn 和 mmm，意义见题目描述。 第二行一...
2020-10-24
省选知识学习进度
（来自黄学长） 1.1 基本数据结构 数组 链表，双向链表 队列，单调队列，双端队列 栈，单调栈 1.2 中级数据结构 堆 并查集与带权并查集 hash 表 自然溢出 双hash 1.3 高级数据结构 树状数组 线段树，线段树合并 平衡树 Treap 随机平衡二叉树 Splay 伸展树 Scapegoat Tree 替罪羊树 块状数组，块状链表 5.* 树套树 线段树套线段树 线段树套平衡树 * 平衡树套线段树 6.可并堆 左偏树 *配对堆 *KDtree，*四分树 1.4 可持久化数据结构 可持久化线段树 主席树 可持久化平衡树 可持久化块状数组 1.5 字符串相关算法及数据结构 KMP AC 自动机 后缀数组 *后缀树 *后缀自动机 字典树 Trie manacher 1.6 图论相关 最小生成树 prim kruskal 最短路，次短路，K短路 spfa dijkstra floyd 图的连通 连通分量 割点，割边 网络流 最大流...
2021-11-19
【全程NOIP计划】图论算法
【全程NOIP计划】图论算法 最短路算法 常用的最短路算法SPFA,Dijkstra,Floyd算法 最短路问题，就是对于有权图的两个点，找到一条连接两个点的路径，使得路径的权值和最小 在说最短路算法之前，必须了解松弛的概念 其实n简单，如果a→b+b→ca \rightarrow b+b \rightarrow ca→b+b→c的距离比a→ca \rightarrow ca→c的小，那么就可以用前者代替a到c的距离 各种各样 最短路实际上就是不断做松弛操作 Floyd 可以求出图中任意两点的最短路，过程很简单 首先枚举松弛操作的中间点，再枚举松弛的左右两个点，然后做松弛操作 由于Floyd算法暴力枚举的特性，所以用邻接矩阵很方便 很显然，复杂度为O(n3)O(n^3)O(n3) 1234for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=min(a[i][j],a[i][k]+a[k][j]); 正确性 怎么证明正确性？ 对...
2021-08-30
【全程NOIP计划】模拟赛#6
【全程NOIP计划】模拟赛#6 30+85+0+0=115 rank16 继续努力!!! A典中典之序列逆向构造1 题目描述 给定一个长度为 kkk 的序列 b1,b2,…,bkb_1, b_2, \ldots , b_kb1,b2,…,bk。 给定一个正整数 mmm 表示值域，保证 1≤bi≤m1 \le b_i \le m1≤bi≤m。 我们称长度为 nnn 的序列 a1,a2,…,ana_1, a_2, \ldots , a_na1,a2,…,an 是有趣的，当且仅当满足如下条件： 仅有恰好一种选取子序列的方式，使得选取出来的子序列恰好就是序列 bbb。 它也满足 1≤ai≤m1 \le a_i \le m1≤ai≤m。 请求出字典序最小的有趣的长度为 nnn 的序列 aaa。 如果满足条件的 aaa 不存在，报告之。 输入格式 本题输入文件包含多组数据。 第一行，一个正整数 TTT，表示数据组数。对于每组数据： 第一行，三个正整数 k,n,mk, n, mk,n,m。 第二行，kkk 个正整数 b1,b2,…,bkb_1, b_2, \ldots...
评论
公告
这里记录 AI 与开发工具、嵌入式实践、算法竞赛档案，以及偶尔的随笔与创作。
从专题开始阅读 →
从专题开始阅读 →
