摘要：
题目链接 题意分析 计数问题跑DP 这是常识原谅我第一时间没有想出来 我们用dp[i]表示搭乘第i辆车下车的方案数 最终的答案 就是把所有终点站ti=n的车下车的方案数累加 现在考虑怎么转移 我们先把所有车按照终点站排序 对于第i辆车 查找哪些车会停在[si,ti-1] 将这些车的方案累加到dp[i
阅读全文
posted @ 2021-02-07 22:16
tcswuzb
阅读(81)
推荐(0)
摘要：
题目链接 题意分析 位运算 我们一看就是要对于每一位考虑 对于按位与 a&b 如果对于b的修改超过了a的最高位 那么对于a&b的结果不会有任何影响 我们假设一开始s是0 每变动一位 ta与这一位是1的数的按位与的结果上1的个数的奇偶性就会发生改变 奇偶性改变 对应的正负性也会改变 我们从低位到高位讨
阅读全文
posted @ 2021-02-07 16:42
tcswuzb
阅读(81)
推荐(0)
摘要：
题目链接 题意分析 由于题目要求没有说一块特定的石头上必须要到一个特定的位置 而是要求每一个位置上有石头就行 所以我们把石头的原始位置与目标位置排序 这样也保证了石头之间的移动轨迹互不交叉 存在方案 必须满足如下两个条件 1.石头向左移动的总距离和向右移动的总距离必须相等 2.我们从左往右扫的时候
阅读全文
posted @ 2021-02-07 16:30
tcswuzb
阅读(86)
推荐(0)
摘要：
题目链接 题意分析 我们考虑从1到n不断进行维护 同时令mid=n/2 接下来我们讨论如何交换x,y这两个位置上的数 1.1≤x≤mid,mid<y≤n 1 x mid y n 使用两次交换 1-y x-n y n mid 1 x 使用一次交换 x-y x n mid 1 y 使用两次交换 1-x
阅读全文
posted @ 2021-02-07 16:12
tcswuzb
阅读(85)
推荐(0)
摘要：
题目链接 题意分析 考试的时候从这道题开始就一直在死 我们从0到k枚举第一批航班取消多少个 根据贪心取消的肯定都是最靠前的航班 同时维护一个指针用于维护第一批航班中没有取消的最早到达的第二批航班中的时间 看看从ta开始取消之后还能否到达第二批航班 不能的话就输出-1 能的话就就将其同当前维护的答案比
阅读全文
posted @ 2021-02-07 15:50
tcswuzb
阅读(63)
推荐(0)
摘要：
题目链接 题意分析 我们考虑一下 对于一个最简分数$\frac$ 在$k$进制下可以表示为纯循环小数 设其循环节长度为$l$ 同时令$[x]$表示x的小数部分 那么 \([\frac{x}{y}]=[\frac{xk^l}{y}]\) 也就是 \(\frac{x}{y}-\lfloor\frac{x
阅读全文
posted @ 2021-02-05 17:40
tcswuzb
阅读(127)
推荐(1)
摘要：
【题目链接】 题意分析 \(\sum_{i=1}^n\sum_{j=1}^n(ijgcd(i,j))=\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^n(dij)[gcd(i,j)=d]=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}
阅读全文
posted @ 2021-02-05 15:12
tcswuzb
阅读(74)
推荐(0)
摘要：
写在卸载之前 一个蒟蒻无力的挣扎 正式开始 【安利一个不错的博客】 我们有一个积性函数$f(n)$ 现在求 \(\sum_{i=1}^nf(i)\ \ (n≤10^9)\) 求解积性函数 我们很容易想到线性筛 但是这道题的话只用线性筛过不了 所以 就有了一个叫做杜教筛的东西 根据迪利克雷卷积 \(h
阅读全文
posted @ 2021-02-05 14:26
tcswuzb
阅读(165)
推荐(0)
摘要：
题目链接 题意分析 \(\sum_{i=1}^nx\%i=\sum_{i=1}^n(x-\lfloor\frac{x}{i}\rfloor i)=nx-\sum_{i=1}^n\lfloor\frac{x}{i}\rfloor i\) 想到了整除分块 这样的话复杂度$O(n\sqrt)$ 但是由于$
阅读全文
posted @ 2021-02-04 14:39
tcswuzb
阅读(78)
推荐(0)
摘要：
题目链接 题意分析 这道题就是要你推式子主要是俺也不懂什么高斯素数 对于 \(x^2+y^2=r^2\) 我们转化为 \(y^2=r^2-x^2=(r+x)(r-x)=dx*dy\ \ \ (x⊥y)\) 由于$x⊥y$ 那么我们一定可以转化为如下形式 令$x=s2\ \ \ y=t2$ \(y^2
阅读全文
posted @ 2021-02-04 13:31
tcswuzb
阅读(92)
推荐(0)
摘要：
题目链接 题意分析 一个图是二分图的充要条件：该图中不存在奇环 由于奇偶性的关系 复杂奇环的产生一定源于简单奇环 所以我们仅仅考虑删去一条边使得所有简单奇环被破坏 也就说 我们仅仅考虑简单环 首先 我们从这张图中拽出一个生成树 然后 对于非树边 如果加上去的话 必然会产生一个环 我们需要统计会产生奇
阅读全文
posted @ 2021-02-03 13:37
tcswuzb
阅读(100)
推荐(0)
摘要：
题目链接 题意分析 这道题正解好像是折半状压 但是俺就是喜欢模拟退火 每一次随机的话 就是交换两个数的位置 然后比较前一半和后一半 CODE: #include<bits/stdc++.h> #define INF 0x7fffffff #define N 2010 using namespace
阅读全文
posted @ 2021-02-02 20:07
tcswuzb
阅读(73)
推荐(0)
摘要：
题目链接 题意分析 这道题正解是啥我不清楚 我只是来联系一下模拟退火 关于模拟退火要注意的几点 1.初始温度$T$ 以及每一次降温的比例$ΔT$ 2.如果当前可以取代最优解的话 就取代 否则的话 就按照多项式复杂度$e^{\frac{Δf}}\(同\)\frac{rand()}$比较 大于的话 我们
阅读全文
posted @ 2021-02-02 19:03
tcswuzb
阅读(88)
推荐(0)
摘要：
题目链接 题意分析 首先 这是一道数学题 给你一个三角形 求出一个面积最小的正多边形 使得这个三角形的三个点都与其多边形点重合 如果你学过高中数学的话 应该明白 这个三角形与这个多边形共用一个外接圆 先求出三角形三边长$a,b,c$ 然后通过海伦公式求出面积$S_=\sqrt{p(p-a)(p-b)
阅读全文
posted @ 2021-02-02 15:45
tcswuzb
阅读(98)
推荐(0)
摘要：
题目链接 题意分析 其实关于这道题的话 最下面的题意概括已经说的很明了 关于这道题 我们的第一想法是DP $f_i$表示已经分好了前$i$个数字的最小代价 我们枚举k作为一段$[k,j]$的开头进行转移 \(f_i=min\{f_{k-1}+\max_{j=k}^ih_j\}(\sum_{j=k}^
阅读全文
posted @ 2021-02-02 11:47
tcswuzb
阅读(119)
推荐(0)
摘要：
题目链接 题意分析 这是一道花了一晚上+上午两个小时+下午两个小时干出来的题 真心不容易 首先 一看这道题的题面 对于多组询问求解第k小 就让人想到了整体二分 但是我们需要处理一个棘手的问题 怎么判断一条路径 u→v 被另外一条路径 x→y 覆盖呢？ 这个我们我们可以使用dfs序解决 这里我们令df
阅读全文
posted @ 2021-02-01 18:00
tcswuzb
阅读(124)
推荐(0)
摘要：
今天闲的蛋疼就复习一下数据结构 写在之前 树状数组是一个好文明 TA可以说是目前维护$O(\ nlogn\ )$数据结构当中常数最小的 一般来讲 维护序列的树形数据结构当中 往往是 树状数组 < 线段树 < 平衡树 神级操作 1.区间修改区间查询 树状数组可以说是把差分思想运用到极致的数据结构 没有
阅读全文
posted @ 2021-01-27 15:51
tcswuzb
阅读(208)
推荐(0)
摘要：
写在卸载之前 正在数论只会抄题解的道路上越行越远 正式开始 1.迪利克雷卷积 1)定义新运算$*$ 注意这里$*$不是乘法 $h,f,g$都是函数名称 定义 \(h=f*g\) \(h=f*g=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})
阅读全文
posted @ 2021-01-25 22:41
tcswuzb
阅读(194)
推荐(0)
摘要：
题目链接 题意分析 明眼人一看就会发现这是一道裸的Splay吧准确来说是平衡树可是本蒟蒻就会使用Splay 对于五种操作 转换成Splay就是 1.把指定元素放在序列首位 我们让该元素成为root 然后将ta的左子树合并到该元素的后继 2.把指定元素放在序列末尾 我们让该元素成为root 然后将ta
阅读全文
posted @ 2021-01-25 16:06
tcswuzb
阅读(131)
推荐(0)
摘要：
题目链接 题意分析 看这篇题解 默认你已经会LCT并且明白如何使用了 说实在的 这题跟【P3203 [HNOI2010]弹飞绵羊】简直如出一辙 首先 我们根据题意可以得到一棵树 如果i+power[i]≤n的话 那么i+power[i]就是i的父亲 否则就令n+1是i的父亲 可以发现 n+1就是这棵
阅读全文
posted @ 2021-01-24 23:55
tcswuzb
阅读(103)
推荐(0)
摘要：
题目链接 题意分析 对于每一个点i 都指向一个点fi 从而形成一个有向图 请问至少添加多少条边 可以将原图变成一个强连通图 并输出任一方案 啥是强连通图 对于一个有向图D 如果任意点vi,vj且vi≠vj 满足从vi到vj 从vj到vi 都存在一条路径使得其连通 那么有向图D就是强连通图 首先 我们
阅读全文
posted @ 2021-01-24 17:34
tcswuzb
阅读(144)
推荐(0)
摘要：
题目链接 题意分析 一看这道题我们 我们第一反应是枚举然后判断 但是这样的复杂度达到了$O(2^{30}*n)$ 很显然是过不了的 我们冷静一波可以发现 如果将每一个数的前15位以及后15位拆开的话 也就是只考虑15位 这个复杂度是可以接受的 那么我们可以考虑使用Meet in The Middle
阅读全文
posted @ 2021-01-23 18:18
tcswuzb
阅读(130)
推荐(0)
摘要：
题目链接 题意分析 一开始看的时候以为就是一道普通的二维数点问题 但是后来一看发现不是那么回事 因为ri的原因 存在我看得见你而你看不见我的情况 所以我们可以将这些点按照ri降序排序 这样后面的点如果可以看见前面的点 前面的点一定可以看见后面的点 这样的话就是二维数点问题了 但是我们发现这里的k很小
阅读全文
posted @ 2021-01-23 12:55
tcswuzb
阅读(126)
推荐(0)
摘要：
【题目链接】 题意分析 这道题感觉应做的话可以 但是巧法锻炼思维 首先 我们枚举正方形的左上角坐标 然后依次扫描四条边的长度 注意这里扫描有两种方式 平行于边以及平行于对角线 判断四条边的长度是否相等 这是第一个指标 然后 我们还需要判断这是否是一个独立的正方形 这里 我们可以使用搜索判断联通的1的
阅读全文
posted @ 2021-01-21 16:36
tcswuzb
阅读(171)
推荐(0)
摘要：
【题目链接】 失踪人口回归 题意分析 每一个问号 都可以被填为左括号或者右括号 并且有相应的代价 要求使用最小的代价使得最后的序列左右括号是匹配的 如果实在无法匹配就输出"-1" 这里的话 有一个非常有意思的思路 一开始把所有问号都填成右括号 然后顺序扫描 遇到无法匹配的情况的话 就把问号修改为左括
阅读全文
posted @ 2021-01-21 14:01
tcswuzb
阅读(168)
推荐(0)
摘要：
题目链接 题意分析 这道题就是上来一个多项式 \[ f(x_1,x_2,x_3)=a_0+a_1x_1+a_2x_2+a_3x_3+a_4x_1x_2+a_5x_1x_3+a_6x_2x_3+a_7x_1x_2x_3 \] 然后通过对于$x_1,x_2,x_3$不同的取值对应的函数值让我们得到这个多
阅读全文
posted @ 2020-12-07 23:51
tcswuzb
阅读(196)
推荐(0)
摘要：
题目链接 题意分析 我就是死在了这道题上 首先我们可以明白的是 所有$a_i$增加的上限就是$lim=Min_{1≤i≤n}b_i$ 然后我们令$c_i=lim-b_i$ 如果存在$c_i<0$的话 那是绝对不符合要求的 这样的话我们的操作就变成了 1.选择一个$k(1≤k≤n)$使得所有$c_1,
阅读全文
posted @ 2020-11-29 23:27
tcswuzb
阅读(221)
推荐(0)
摘要：
#【期末考试】 题目链接 题意分析 首先 做这道题的时候 我还是想感谢一下 看了看这套题目的数据范围 发现其实这是一道枚举题 我们发现一个学生会产生不愉快度仅仅会和最晚公布成绩的课程的公布时间有关 所以我们考虑枚举最晚全部课程公布的时间 对于当前枚举的时间t 我们计算一下已经超过这个时间的课程总数
阅读全文
posted @ 2020-11-28 19:41
tcswuzb
阅读(171)
推荐(0)
摘要：
题目链接 题意分析 怎么说呢 感觉这道题还是找规律套结论 首先 对于一个字符串 我们最直观的想法就是去掉一个字符 然后再在其余n个位置每个位置可以有m-1种字符插入 那么就存在n*(m-1)种方案 但是存在重复的 对于aaabbbccc这种存在一段连续相同字符的字符串 很显然 一段连续相同字符的话
阅读全文
posted @ 2020-11-24 08:55
tcswuzb
阅读(180)
推荐(0)
摘要：
题目链接 题意分析 插点题外话 我感觉我已经不可能再获得幸福了 因为 我已经被幸福包围了 珂朵莉，欢迎回家 每一次做这种题面都会泪目的 由于这种题只存在询问 所以我们不自觉的想到了莫队 首先 如果区间[l,r]中的一个数x出现了k次的话 那么ta在所有子序列里面出的次数就是$2^{r-l+1}-2^
阅读全文
posted @ 2020-11-24 00:16
tcswuzb
阅读(163)
推荐(0)
摘要：
题目链接 题意分析 我们计算出每一条边经过的概率是多少 然后概率大的边编号小 怎么计算概率 是一个问题 首先 我们存在一条边 这条边的两个端点是$u,v$ 经过两个端点的概率分别是$p_u,p_v$ 这两个端点链接的边数分别是$d_u,d_v$ 那么经过这条边的概率就是$\frac+\frac$ 怎
阅读全文
posted @ 2020-11-11 12:55
tcswuzb
阅读(135)
推荐(0)
摘要：
题目链接 题意分析 说实在的 被绿题卡了跟被驴踢了的感觉差不多 不过是概率问题 还是情有可原的捂脸 这道题 说白了 我们假设len是所有路径的长度和 sum是所有路径的数量 那么答案就是$\frac$ 首先的话 这是一道有向无环图的题 所以我们可以考虑来个拓扑排序 记录两个状态a[i]还有b[i]
阅读全文
posted @ 2020-11-11 11:18
tcswuzb
阅读(105)
推荐(0)
摘要：
题目链接 题意分析 真是一道很有意思的题 由于没有通法可以使用 所以我们分成三种情况讨论 1.一维 我们把所有的点顺序排序 然后扫一遍 维护一个数轴 扫到一个点的时候 就把数轴[x-D,x+D]范围内的所有点统计一下 然后再把这个点加入到数轴中 由于是单点修改区间求和 所以我们可以使用树状数组 注意
阅读全文
posted @ 2020-11-09 20:17
tcswuzb
阅读(213)
推荐(0)
摘要：
写在卸载之前 今天在做题的时候突然间看到的 【感谢来自大佬的指点】 心血来潮 就想着把这些做法好好的总结一下 正式开始 1.欧几里得距离 这个应该是比较好理解的了 对于两个点 \((x_1,y_1),(x_2,y_2)\) 两个点之间的欧几里得距离也就是二者之间的最短距离 \[ dis=\sqrt{
阅读全文
posted @ 2020-11-08 18:35
tcswuzb
阅读(733)
推荐(0)
摘要：
题目链接 题意分析 一道不错的旋转坐标系的题 首先 由于一个点的固定曼哈顿距离围成的点形成了一个斜正方形 所以我们旋转坐标系 将其转化为正方形 就是这样 然后我们考虑划分为若干矩形 是的每一个矩形内可以然同一种颜色 同时与ta周围的8个矩形不可以染同种颜色 就是这样子(图画的不太好 凑活着看一下吧)
阅读全文
posted @ 2020-11-08 18:33
tcswuzb
阅读(134)
推荐(0)
摘要：
题目链接 题意分析 首先我们一看就知道这是一道博弈论SG函数的题 但是由于斜线分割实在是不好处理 所以我们考虑一下转化坐标系 这样的话就很好做了 等等 这不就是曼哈顿转化为切比雪夫吗？ 然后的话 我们就可以正常博弈论了 首先进行黑白染色 因为我们发现黑板染色之后棋盘就可以分为互不影响的两部分 然后我
阅读全文
posted @ 2020-11-08 17:29
tcswuzb
阅读(161)
推荐(0)
摘要：
题目链接 题意分析 看数据范围就应该知道这是一道状压DP题了 一开始想的是设置dp[i][a] 表示第i行状态为a的方案数 那么状态转移的时候 \(dp[i][a]=\sum_{b=0}^{2^m-1}dp[i-1][b]\) 并且满足a与b并不冲突 但是要注意的是影响第i行的不只有第i-1行 还有
阅读全文
posted @ 2020-11-04 10:57
tcswuzb
阅读(254)
推荐(0)
摘要：
写在卸载之前 这个东西是前两天刷题的时候刷到的 觉得很有意思 加上之前就已经做了几道这样的题 所以干脆学习了一下 发现这里面还挺大有学问的 正式开始 一般来讲 贪心是优先选取眼前最优解 然后一路向前 不存在返回操作 但是 正是因为贪心优先选取眼前最优解 导致我们容易错失全局最优解 从而导致一步错步步
阅读全文
posted @ 2020-11-03 17:02
tcswuzb
阅读(264)
推荐(0)
摘要：
题目链接 题意分析 由于$A_i,B_i≤10$ 所以我们可以考虑把所有的泥土都分开讨论 也就相当于 2,3,1,4 转化之后就是如下 1,1,2,2,2,3,4,4,4,4 然后我们只考虑多出来或者少出来的泥土 如果当前是多的 那么我们就需要Y代价移走 到了下一个少的泥土时候 我们就存在两种选择
阅读全文
posted @ 2020-10-28 09:53
tcswuzb
阅读(139)
推荐(0)
摘要：
题目链接 题意分析 首先对于一个区间[L,R] 可以发现:Max-Min+L-R=0 如果你不知道该怎么维护的话 请看看这道题【CF526F Pudding Monsters】 现在关键是 对于一个区间怎么维护 首先可以证明的是 一个字串的本征区间是唯一的 因为两个区间的交也是区间 所以两个区间都包
阅读全文
posted @ 2020-10-23 07:18
tcswuzb
阅读(159)
推荐(0)
浙公网安备 33010602011771号