wweiyiのblog

【解题报告】 洛谷P1663 山 题目描述 给出一座山，如图。 现在要在山上的某个部位装一盏灯，使得这座山的任何一个部位都能够被看到。 给出最小的y坐标，如图的+号处就是y坐标最小的安装灯的地方。 输入格式 第一行一个数N，表示这座山由N个点构成； 接下来N行从左到右给出了这座山的构造情况，每行两个数Xi、Yi，表示一个折点，保证Xi>Xi-1 输出格式 仅输出一行，为最小的y坐标，当你的答案与标准答案相差不超过0.01时，则被认为是正确的。 输入输出样例 输入 #1 123456760 010 011 115 116 025 0 输出 #1 13.00 说明/提示 数据规模： 30%的数据，1≤N≤501\le N\le 501≤N≤50 100%的数据，1≤N≤5000,0≤Xi,Yi≤1061\le N \le 5000 ,0\le X_i,Y_i\le 10^61≤N≤5000,0≤Xi​,Yi​≤106，保证答案不超过10610^6106 思路 二分答案 读题，要在山上安装一个灯，让整个山都可以找到，说明这一盏灯和任意一个山的折点的连线和其他的山连成的线都不相交...

【清北学堂国庆刷题班】 Day1 T1 打扑克 题目描述 皮蛋为了讨好黑妞，想要跟她打扑克。 他们打的扑克是这样一种规则：有面值大小从1到n的扑克各一张。其中奇数牌在皮蛋手中，偶数牌在黑妞手中。每人每次只能出一张牌，先出完者获胜（遵循最基本的扑克规则：当对手出牌后，可以选择出一张比他大的牌，或者不管，让他再任意出一张牌）。假设皮蛋和黑妞都是足够聪明的人，都想让自己获胜。现在给定n和谁先出牌，那么谁会获胜呢？ 输入格式 第1行1个正整数T，表示数据组数。 接下来T行，每行2个正整数n,op，表示打一局牌。其中n如题所示，保证op∈{0,1}op\in \lbrace 0,1\rbraceop∈{0,1}，op=0表示皮蛋先出牌，op=1表示黑妞先出牌。 输出格式 T行每行1个数表示打一局牌的答案。0表示皮蛋获胜，1表示黑妞获胜。 样例数据 input 12325 010 1 output 1201 数据规模与约定 对于 40%的数据，n≤10n \le 10n≤10。 对于 70% 的数据，n≤10000n\le 10000n≤10000。 对于 100% 的数据,2≤n≤1010...

【解题报告】 洛谷P6733 间歇泉 题目描述 有一个间歇泉，冒出了 n 杯水，由于一些原因，每杯水的温度、体积不同。第 i 杯水的温度为 ci体积为 ai 现在混合任意两杯水，每混合两杯水都会得到一个新的温度值，求可能得到的第 kkk 高的温度值（不计热量损失）。 你的答案建议至少保留小数点后 3 位（与标准答案之差在 10−210^{-2}10−2 以内即视为通过）。 输入格式 第一行一个数 n,k，意义如题述。 接下来 n行，每行两个数 ai,c 输出格式 一行一个实数，表示混合后的水的第 kkk 高温度。 输入输出样例 输入 #1 1234565 11 54 25 32 31 4 输出 #1 14.500 说明/提示 样例 1 说明 第 1 和第 5杯水混合，得到 4.5的温度值。可以发现，这是可能得到的最高水温。 样例 2 见题目附件中 pour2.in 与 pour2.ans。 数据规模与约定 本题采用捆绑测试。 子任务 1（9 pts）：有 1≤n≤101\le n\le 101≤n≤10 子任务 2（40 pts）：保证 k=1k=1k=1 子任务 3（50 p...

【解题报告】 洛谷P1542 包裹快递 题目描述 小K成功地破解了密文。但是乘车到X国的时候，发现钱包被偷了，于是无奈之下只好作快递员来攒足路费去Orz教主…… 一个快递公司要将n个包裹分别送到n个地方，并分配给邮递员小K一个事先设定好的路线，小K需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。小K得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。 为了节省燃料，小K希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。 输入格式 第1行为一个正整数n，表示需要运送包裹的地点数。 下面n行，第i+1行有3个正整数xi，yi，si，表示按路线顺序给出第i个地点签收包裹的时间段为[xi, yi]，即最早为距出发时刻xi，最晚为距出发时刻yi，从前一个地点到达第i个地点距离为si，且保证路线中xi递增。 可以认为s1为出发的地方到第1个地点的距离，且出发时刻为0。 输出格式...

二分 这是一个二分算法的总结 对于算法来说，二分的确非常简单，被归类于基础算法，但是同样的，因为是基础算法，所以在竞赛中非常常用，今天距离CSP只剩下不到9天的时间了，我将利用这些时间对我的一些基础算法进行一些理解和总结，让csp得到尽量高的分数 1.狭义二分 当我们第一次见到二分的时候，我们是在一道题： 从一个有序数列中找到某个数的位置，这道题因为数列是有序的满足单调性，单调递增或者单调递减，所以我们可以使用二分算法，核心代码如下： 1234567//a为有序序列的数组int l=1,r=n;//n是数组的长度while(l<r){ int mid=(l+r)/2; if(x<a[mid]) r=mid;//x为要查找的数字 else l=mid+1;;} 最后l即为最后的答案 通过这个程序，我们知道了通过二分可以来进行对于查找的简化，大大降低时间复杂度，让程序运行更加高效，最主要可以获得更高的分数。 2.广义二分 因此我们从上面的例子可以明白，二分法实际上是对于一个单元函数具有单调性的时候，一个非常好的查找方法，因此我们可以运...

【清北学堂周末刷题班】 Day3 50分 A 30分 B20分 A 【问题描述】 你是能看到第一题的friends呢。 ——hja 众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。 给定一个只包含乘号、加号和数字的表达式，你需要替换其中一个位置的符号将表达式变为另一个表达式（可以替换为同样的字符，但前导零是不允许的），求所有合法情况得出的表达式的值的和。 【输入格式】 一行一个字符串代表表达式。 【输出格式】 一行一个整数代表答案。 【样例输入】 233 【样例输出】 9633 【样例解释】 不合法的串仅包括033,∗33,23∗,23+,+33 【数据规模与约定】 对于40%的数据，字符串长度不超过3。 对于80%的数据，字符串长度不超过10。 对于100%的数据，字符串长度不超过100。 思路 我考试的时候大概是想的是枚举，但是枚举数据量比较大，而且代码不太好实现，比较浪费时间，所以我只写了一个40%的规模，不超过3的字符串，但是只考虑了字符数量等于三的情况，白给了10分，剩下的我还没有听回放，先鸽一下 代码 30分 123456789101112...

OI WIKI 黄学长的博客 Codeforces镜像网站 BZOJ数据 LaTeX的使用 对拍教程 vector的使用 字符串匹配（hash算法） codeforces访问加速 线段树详解 校内OJ搭建 背包九讲 莫队详解 平面凸包详解 基环树 博客装饰教程 二分图匹配详解 ST表浅谈 可视化数据结构演示 树状数组详解 树状数组求逆序对 bitset使用指南 C++ goto的使用 树链剖分详解 dfs序与欧拉序 模拟退火算法 差分约束问题 网络流详解 氩洛谷背景样式 CSS学习 数学较全解 后缀自动机详解 线性基详解 图论画图网站 whk题库 各种Dp优化技巧 tuple详解

模板整理(持续整理中) 基础算法 二分 123456while(l<=r){ int mid=(l+r)/2; if(check(mid)) l=mid; else r=mid-1;} 快速排序 1234567891011121314151617void qsort(int l,int r)//应用二分思想{ int mid=a[(l+r)/2];//中间数 int i=l,j=r; do{ while(a[i]<mid) i++;//查找左半部分比中间数大的数 while(a[j]>mid) j--;//查找右半部分比中间数小的数 if(i<=j)//如果有一组不满足排序条件（左小右大）的数 { swap(a[i],a[j]);//交换 i++; j--; } }while(i<=j);//这里注意要有=...

（来自黄学长） 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 图的连通 连通分量 割点，割边 网络流 最大流...

【清北学国庆刷题班】 Day7 T1 water 题目描述 有一个长为n的序列aia_iai​，小Y希望数字总共不超过k种。 为了达到这个目的，她可以把任意位置修改成任意数，这个操作可以进行任意多次。 请你帮她求出最少需要修改几个位置可以达成目的。 输入格式 第一行两个整数n,k。 接下来一个n个整数aia_iai​。 输出格式 一行一个整数表示答案。 样例输入 125 22 2 1 1 5 样例输出 11 样例解释 把5(第5个位置的数）改成1或2就行了。 数据范围 对于30%的数据，n≤20n\leq 20n≤20 对于另外30%的数据，n≤5000n\leq 5000n≤5000 对于所有数据，满足q≤k≤n≤200000,1≤ai≤nq\le k \le n \le 200000,1\le a_i \le nq≤k≤n≤200000,1≤ai​≤n 思路 这道目是真的水，这个题目统计一下每个数字的数量和数字的种类，然后按数量从小到大排序，删除数量最小的k−kmorek-k_{more}k−kmore​种就可以了 代码 123456789101112131415161718...