尺取

尺取法小结

尺取法顾名思义是用尺子一段一段测量。测量物件长度通常是一端对其,看另一端的刻度得出答案; 借挑战上的话 尺取法通常是数组保存一对下标,即所选取的区间的左右端点,然后根据实际问题不断推进区间,在这其中可以根据已有经验保持右端点从上一状态继续推进。 (更多…)

luoyayu
字符串

Atcoder 88 D-Wide Flip

Time limit : 2sec / Memory limit : 256MB You are given a string $S$ consisting of 0 and 1. Find the maximum integer $K$ not greater than $|S|$ such that we can turn all the characters of $S$ into 0 by repeating the following operation some number of times. Choose a contiguous segment $[l,r]$ in $S$ whose length is at least $K$ (that is,$r-l+1\geq K$ must be satisfied). For each integer $i$ such that $l\leq i\leq r$, do the following: if $S_i$ is 0, replace it with 1; if $S_i$ is 1, replace it with 0. (更多…)

luoyayu
计算几何

HDU 6242 Geometry Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Alice is interesting in computation geometry problem recently. She found a interesting problem and solved it easily. Now she will give this problem to you : You are given $ N$ distinct points $ (X_i,Y_i)$ on the two-dimensional plane. Your task is to find a point $ P$ and a real number $ R$, such that for at least $ ⌈\frac{N}{2}⌉$ given points, their distance to point $ P$ is equal to $ R$. (更多…)

luoyayu
FFT

uva 12298 super poker

快速傅里叶变换模板题 题意:给出一副点数无穷大但只能是合数的扑克牌,四种花色$S,H,C,D$组合成一个数;给出区间$i∈[L,R]$问组成i的方案数有多少? 把每种花色看成多项式~$ inf$,幂次为合数的系数为$1$,否则为零,先$dft$四种花色编程点值表达,在相乘,用$idft$变成系数表达式,问组成i的方案数就是输出幂次为$i$的系数 (更多…)

luoyayu
位运算

2017 ICPC Xian Xor

题意:给出一棵树,$n≤5e4 $, $ \left(q≤5e4 \right)$次询问,每次询问三元组$ \left(u,v,k \right) $,返回从$ u $,到$v$ 上序号$ \left(from \ 0 \right)$为$ k$的倍数的点权连续异或。 (更多…)

luoyayu