wty's blog

CF1552 BCD 比赛链接 B 由于最终获胜的运动员有且仅有一个，可以通过两两之间比较必有一人胜出得出 所以，如果有一个运动员可以击败其他所有运动员，那么将运动员编号 111 到编号 nnn，顺次比较，每次只留下获胜的一个运动员，那么将最后剩下的一个运动员再和全部运动员比较一次，如果失败则无解，成功则得解。可以用反证法证明，中间运动员一定不是要求的解。 点击显/

B Cobb 题目大意 给定一个长度为 nnn 的序列 {a1,a2,⋯ ,an}\{a_1,a_2,\cdots ,a_n\}{a1​,a2​,⋯,an​} 和 kkk，当 1⩽i<j⩽n1\leqslant i < j \leqslant n1⩽i<j⩽n 时，求最大的 i⋅j−k⋅(ai∣aj)i\cdot j-k\cdot(a_i|a_j)i⋅j−k⋅(ai​∣aj​

E. Boring Segments 题意 有一个大区间 [1,m][1,m][1,m]，给定 nnn 个小区间 每个小区间范围是 [li,ri](1⩽li<ri⩽m)[l_i, r_i] (1\leqslant l_i<r_i\leqslant m)[li​,ri​](1⩽li​<ri​⩽m)，每个小区间还有一个权值 wiw_iwi​ 定义两个区间中的点可以相互到达，当且仅

Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) D. Take a Guess 题意 有一个长度为 NNN 的序列每次你可以询问两个值的与值和或值，求出原序列中第k大值。 询问不能超过 2N2N2N 次。 思路 与位运算有关的恒等式请见blog中的这篇文章，下文使用了文章中一些恒等式。 对 a+b=(

Codeforces Round #737 (Div. 2) D. Ezzat and Grid 题意 给出一个 n⋅109n\cdot 10^9n⋅109 的网格，初始网格上的数字都是0，再给出 mmm 个横向区间该区间上的数字都是1 每个横向区间用 i,l,ri, l, ri,l,r 表示，第 iii 行上列号为 [l,r][l,r][l,r] 上的数字都是1，如 1,3,41, 3, 4

在oi时候曾经看过CDQ分治，但当时对于偏序这个概念的不理解（以为是什么高级东西），导致一直没有研究清楚CDQ分治，现在回头看CDQ分治，其实理解并没有那么的困难，下面通过举例来理解偏序这个概念，而不是死板的定义。 偏序关系 偏序关系 为一种二元关系（严格的定义可以看百度 偏序关系，需要满足三条性质）（这里简单理解为：作用在两个元素上的符号，如实数域上 ⩽\leqslant⩽、⩾\geqsl

使用vjudge进行题目评测，减少找题的工作量。 ~/.vimrc 中g++使用F5快速执行代码， autocmd filetype cpp nnoremap <F5> :w <bar> !g++ % -o %:r && ./%:r<CR> 2023.4月 2023.4.24. 《第一章 算法设计基础》 UVA - 11292

平行四边形不等式 2D1D 定义1（平行四边形不等式） 若二元实函数 f(x,y)f(x, y)f(x,y) 满足 ∀l1⩽l2⩽r1⩽r2\forall l_1\leqslant l_2\leqslant r_1\leqslant r_2∀l1​⩽l2​⩽r1​⩽r2​，有 f(l1,r1)+f(l2,r2)⩽f(l1,r2)+f(l2,r1)f(l_1,r_1) + f(l_2,r_2)

几何相关算法 向量命名空间 用pt命令空间内的Point类，实现基本的向量加减乘除运算，大小比较<以及相等==判断，内积dot和外积cross，向量长度length，向量夹角angle，向量旋转rotate，以及一些求交点，判断是否正规相交，判断是否点在线段上，计算点到直线、线段距离的函数。 #include <cmath> #include <string> #includ

该总结分为两部分，第一部分为博客中的算法题目分类，第二部分为一些经典算法。 ACM算法复习 在大三下学期开始重新复习算法，并做了以下一些记录笔记，优化了很多算法的写法： 平行四边形DP优化 线段树，普通线段树，动态加点线段树，区间上界限制操作，区间历史最值操作等 字符串相关算法，包含Trie树，KMP，AhoCorasick自动机，后缀数组，后缀自动机，Hash，回文串匹配Manach 日记