- 博客(361)
- 收藏
- 关注
RSS订阅转载 AtCoder Grand Contest 037 简要题解
从这里开始题目目录Problem ADividing a String 猜想每段长度不超过2。然后dp即可。 考虑最后一个长度大于等于3的一段，如果划成$1 + 2$会和后面相同，那么划成$2 + 1$，如果前一段和前面相同，那么把前一段和前面合并。每次操作后段数都不会减少。所以存在一种最优方案使得每段长度不超过2。Code#incl...
2019-10-03 16:21:00
242
转载 AtCoder Grand Contest 038 简要题解
从这里开始比赛目录Problem A01 MatrixCode#include <bits/stdc++.h>using namespace std;typedef bool boolean;const int N = 1e3 + 5;int W, H, A, B;int main() { s...
2019-10-03 13:59:00
287
转载 loj 2955 「NOIP2018」保卫王国 - 树链剖分 - 动态规划
题目传送门 传送门 想抄一个短一点ddp板子。然后照着Jode抄，莫名其妙多了90行和1.3k。Code/** * loj * Problem#2955 * Accepted * Time: 2653ms * Memory: 25616k */#include <bits/stdc++.h>using nam...
2019-09-22 13:57:00
219
转载 Codeforces 1204D Kirk and a Binary String - 数学
题目传送门 传送门 群除我均会猜结论/找规律，sad.... 以下内容只保证代码能过system test，证明应该都是在纯口胡 约定下文中的$LIS$表示最长不下降子序列。 定义$zero(s)$表示串$s$中0的个数，$one(s)$表示$s$中1的个数。 约定字符串的下标从1开始。$s_{l, r}$表示$s$的$l$个字符开始到第$...
2019-08-21 16:27:00
221
转载 loj 6051 「雅礼集训 2017 Day11」PATH - 多项式 - 钩子公式
题目传送门 传送门 设 $m = \sum_{i = 1}^{n} a_i$。 总方案数显然等于 $\frac{m!}{\prod_{i = 1}^{n} a_i!}$。 考虑这样一个网格图，第 $i$ 行有 $a_i$ 个网格。 那么我们在这个网格中填 $1$ 到 $m$ ，如果保证每一行严格递增，那么第 $i$ 次移动后第 $j$ 维坐标就是...
2019-08-08 13:06:00
234
转载 NOI 2019 退役记
非常抱歉，因为不退役了，所以这篇退役记鸽了。转载于:https://www.cnblogs.com/yyf0309/p/11296569.html
2019-08-03 22:24:00
251
转载 Cipolla算法学习笔记
学习了一下1个$\log$的二次剩余。然后来水一篇博客。 当$p$为奇素数的时候，并且$(n, p) \equiv 1 \pmod{p}$，用Cipolla算法求出$x^2 \equiv n \pmod{p}$的一组解。 寻找一个$a$，使得$a^2 - n$是一个二次非剩余。 期望只用2次就能找到。 令$\omega \equiv \sqrt{a^2 - n...
2019-07-12 17:12:00
151
转载 loj 2719 「NOI2018」冒泡排序 - 组合数学
题目传送门 传送门题目大意 （相信大家都知道） 显然要考虑一个排列$p$合法的充要条件。 考虑这样一个构造$p$的过程。设排列$p^{-1}_{i}$满足$p_{p^{-1}_i} = i$。初始令$q = (1, 2, \cdots, n)$。依次考虑$i = 1, 2, \cdots, n$。设$x = p_i$，如果$q^...
2019-07-10 22:54:00
114
转载 loj 2135 「ZJOI2015」幻想乡战略游戏 - 动态点分治
题目传送门 传送门题目大意 给定一棵树，初始点权都为0，要求支持：修改点权询问带权重心 询问带权重心就在点分树上跑一下就行了。（枚举跳哪个子树更优） 剩下都是基础点分治。 学了一下11-dimensional的2.2k动态点分治，然后写抄出来只有1.9k？？？Code/** * loj * Problem#...
2019-05-01 14:43:00
143
转载 loj 3090 「BJOI2019」勘破神机 - 数学
题目传送门 传送门题目大意 设$F_{n}$表示用$1\times 2$的骨牌填$2\times n$的网格的方案数，设$G_{n}$$表示用$1\times 2$的骨牌填$3\times n$的网格的方案数.给定$l, r, k$，求$\frac{1}{r - l + 1}\sum_{i = l}^{r} \binom{F_{i}}{k}$.给定$l, ...
2019-04-27 16:00:00
151
转载 洲阁筛 & min_25筛学习笔记
洲阁筛给定一个积性函数$F(n)$，求$\sum_{i = 1}^{n}F(n)$。并且$F(n)$满足在素数和素数次幂的时候易于计算。显然有：$\sum_{i = 1}^{n} F(n) = \sum_{i = 1}^{\sqrt{n}}F(i) \left(\sum_{\sqrt{n} < p\leqslant n/i, p\ is\ a\ prime} F(p...
2019-02-23 23:24:00
429
转载 Thuwc 2019 & wc 2019 划水记
（此处不应有目录，爆零的过程应该慢慢看）Thuwc 2019 拖着箱子去广二，然后发现可以搬出去住酒店。好，然后箱子白搬了。Joker似乎说住宿体验极差，广二宿舍和林荫宿舍质量不相上下，想想wc时要被强制住校瑟瑟发抖。 然后来吐槽食堂。这边菜不放盐是什么毒瘤东西？整个干锅的辣椒是摆设？肉实则是白味？小火锅的辣椒酱很呛人？在土豆烧排骨里放糖真毒瘤！...
2019-01-30 22:24:00
139
转载 bzoj 3704 昊昊的机油之GRST - 贪心
题目传送门 传送门题目大意 给定一个数组$a$和数组$b$，每次操作可以选择$a$的一个子区间将其中的数在模4意义下加1，问把$a$变成$b$的最少操作次数。 首先求$b - a$，再差分，令这个数组为$c$。 那么操作的次数是这个数组$c$中正数的和。 现在可以做的是选择一个地方+4，它后面的某个地方-4。 考虑什么时候可以使得当前的...
2019-01-07 12:17:00
98
转载 luogu P4482 [BJWC2018] Border 的四种求法 - 后缀数组
题目传送门 传送门题目大意 区间border。 照着金策讲稿做。Code 1 /** 2 * luogu 3 * Problem#P4482 4 * Accepted 5 * Time: 8264ms 6 * Memory: 37924k 7 */ 8 #include <bits...
2019-01-07 12:01:00
163
转载 bzoj 3473 字符串 - 后缀数组 - 树状数组
题目传送门 传送门题目大意 给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串 先用奇怪的字符把所有字符串连接起来。 建后缀树，数每个节点的子树内包含多少属于不同串的后缀。 数这个东西，可以将每个串的后缀（被奇怪的字符分割开的地方认为它属于不同后缀）按dfs序排序，然后简单容斥就能统计出来。 对...
2019-01-07 11:23:00
121
转载 bzoj 1283 序列 - 费用流
题目传送门 传送门题目大意 给定一个长度为$n$的序列，要求选出一些数使得原序列中每$m$个连续的数中不超过$K$个被选走。问最大的可能的和。 感觉建图好妙啊。。 考虑把问题转化成选$m$次数，每次选出一个子序列， 要求两次选择的数的下标差至少为$m$。 这个很容易建图就能做。$i$向$\min\{T, i + m\}$连边，容量为1，费用为...
2018-12-29 22:08:00
121
转载 bzoj 3597 [Scoi2014] 方伯伯运椰子 - 费用流 - 二分答案
题目传送门 传送门题目大意 给定一个费用流，每条边有一个初始流量$c_i$和单位流量费用$d_i$，增加一条边的1单位的流量需要花费$b_i$的代价而减少一条边的1单位的流量需要花费$a_i$的代价。要求最小化总费用减少量和调整次数的比值（至少调整一次）。 根据基本套路，二分答案，移项，可以得到每条边的贡献。 设第$i$条边的流量变化量为$m_i$...
2018-12-29 21:21:00
91
转载 loj 6008 餐巾计划 - 费用流
题目传送门 传送门题目大意 （经典题还不知道题意？） 容易想到需要把未使用的餐巾和已经使用的餐巾分开。 设$X_i$表示第$i$天已经的使用餐巾的点，设$Y_i$表示第$i$天还未使用的餐巾的点 我们知道使用过的餐巾数量 = 洗出来的餐巾数量 + 购买的餐巾数量（一个餐巾被多次洗出来算多次）。 右边是啥，我们不清楚，但是我们清楚每一天新...
2018-12-28 23:02:00
217
转载 Codeforces Gym 101190M Mole Tunnels - 费用流
题目传送门 传送门题目大意 $m$只鼹鼠有$n$个巢穴，$n - 1$条长度为$1$的通道将它们连通且第$i(i > 1)$个巢穴与第$\left\lfloor \frac{i}{2}\right\rfloor$个巢穴连通。第$i$个巢穴在最终时允许$c_i$只醒来的鼹鼠最终停留在这。已知第$i$只鼹鼠在第$p_i$个巢穴睡觉。要求求出对于每个满足$1 \l...
2018-12-28 22:44:00
163
转载 loj 6037 「雅礼集训 2017 Day4」猜数列 - 动态规划
题目传送门 传送门题目大意 有一个位置数列，给定$n$条线索，每条线索从某一个位置开始，一直向左或者向右走，每遇到一个还没有在线索中出现的数就将它加入线索，问最小的可能的数列长度。 依次从左到右考虑每一位上填的数。 用$f_{L, a, R, b, S}$表示正在满足向右走的线索是$L$，前$a$个字符已经满足，正在满足向左走的线索是$R$，前$b...
2018-12-15 21:53:00
190
转载 bzoj 4770 图样 - 概率与期望 - 动态规划
题目传送门 传送门I 传送门II题目大意 有一个$n$个点的完全图，每个点的权值是$[0, 2^{m})$中的随机整数，两点间的边的权值是两点点权的异或和，问它的最小异或生成树的边权和的期望。 考虑求最大异或生成树的分治做法，每次按最高位分成$V_0,V_1$两个集合（如果不行，那么这一层就不管）。 然后再中间选一条最小边连接两个集合。两个集...
2018-12-14 22:00:00
105
转载 PKUWC 2017 Day 2 简要题解
*注意：题面请移步至loj查看。从这里开始Problem A 随机算法Problem B 猎人杀Problem C 随机游走 怎么PKU和THU都编了一些假算法，然后求正确率[汗]。 之前听说PKUWC 2017考了五道dp，看来是真的。[完蛋.jpg] 这三道题，2道概率，1道期望，和佬题组成一样。。。 （我只是把PK...
2018-12-09 20:03:00
106
转载 NOIP 2018 划水记
（此处不应有目录） （本来想咕掉这篇游记）Day -1 今天信心题，这个毒瘤出题人怎么出了一堆垃圾题（smallfat批判这个垃圾题）。 T2，T3是送分题。T1考了个noip根本不会考得类欧几里德算法。 下午敲树链剖分求lca板子，然后发现自己WA了。[内心崩溃.jpg] 有人颓generals。晚上为了练习写模拟，写了一个简化后的generals...
2018-12-08 21:07:00
100
转载 2018年山东省省队集训 Round 1 Day 2简要题解
从这里开始Problem A 生日礼物Problem B 咕咕Problem C 解决npc （相信来看这篇博客的人都有题面） T2以为可以线性递推，然后花了两个小时。然后想了两个小时T1，会了一个能过的算法。但是没时间写，sad.....比赛快结束时，发现T2模数$10^9+7$，内心mmp。Problem A 生日礼物题目大意 ...
2018-12-07 23:18:00
214
转载 湖南省队集训 Day 2
从这里开始Problem A 走路Problem B游戏Problem C有趣的字符串题 暴力分又没骗满sad.....Problem A 走路 $O(n^2)$动态规划是显然的。 更新方式有两种：一种是枚举它的倍数转移，一种是转移到它的约数。 考虑利用分块来平衡一下（像分块FWT一样）。 注意到若$x = ab...
2018-11-29 21:29:00
214
转载 一句话题解
有些题目觉得价值不是特别大，不值得想单独写一篇随笔，但不至于一句话都不提。（其实是想偷点懒）UVa Live 4327 单调队列优化动态规划。UVa Live 4015 $f_{i,j}$表示从$i$开始走，在$i$的子树内走到$j$最少要走的距离。$g_{i, j}$只是增加一个要走回$i$的限制。转移是显然的。UVa Live 4490 一种书被拿出来再放回去会不...
2018-11-06 22:50:00
117
转载 NOIP 2017 宝藏 - 动态规划
题目传送门 传送门题目大意 （家喻户晓的题目不需要题目大意） 设$f_{d, s}$表示当前树的深度为$d$，与第一个打通的点连通的点集为$s$。 每次转移的时候不考虑实际的深度，深度都当做$d$，寻找连接两个点集最小边集，如果能连接更浅的点，那么会在之前转移，所以即使转移非法也不可能成为最优解。 找连接两个点集的最小边集合可以预处理。 ...
2018-11-05 13:01:00
135
转载 NOIP 2017 逛公园 - 动态规划 - 最短路
题目传送门 传送门题目大意 给定一个$n$个点$m$条边的带权有向图，问从$1$到$n$的距离不超过最短路长度$K$的路径数。 跑一遍最短路。 一个点拆$K + 1$个点，变成一个DAG上路径计数问题。直接拓扑排序加动态规划，如果有一个$n$号点的剩余度数非0，就一个合法的路径上存在零环（这样可以无线走了）。 于是成功T掉了。 把拓扑排...
2018-11-05 12:55:00
88
转载 bzoj 4767 两双手 - 动态规划 - 容斥原理
题目传送门 传送门I 传送门II题目大意 一个无限大的棋盘上有一只马，设马在某个时刻的位置为$(x, y)$, 每次移动可以将马移动到$(x + A_x, y + A_y)$或者$(x + B_x, y + B_y)$。棋盘上有$n$个禁止位置不能经过，问马从$(0, 0)$走到$(E_x, E_y)$的方案数。 容斥是显然的。 每确定经过$...
2018-11-03 16:38:00
78
转载 Codeforces 101623E English Restaurant - 动态规划
题目传送门 传送门题目大意 餐厅有$n$张桌子，第$i$张桌子可以容纳$c_i$个人，有$t$组客人，每组客人的人数等概率是$[1, g]$中的整数。 每来一组人数为$x$客人，餐厅如果能找到最小的$c_j$使得$c_j \geqslant x$，那么就会把这张桌子分配给这些客人，并得到$x$的收益。 问期望的收益。 好像可以枚举每一种人数，...
2018-11-02 13:23:00
87
转载 浅谈Tarjan算法
从这里开始预备知识两个数组Tarjan 算法的应用求割点和割边求点-双连通分量求边-双连通分量求强连通分量预备知识 设无向图$G_{0} = (V_{0}, E_{0})$，其中$V_{0}$为定点集合，$E_{0}$为边集，设有向图$G_{1} = (V_{1}, E_{1})$，其中$V_{1}$为定点集合，$E_...
2018-10-30 20:59:00
144
转载 Codeforces 1027F Session in BSU - 并查集
题目传送门 传送门I 传送门II 传送门III题目大意 有$n$门科目有考试，第$i$门科目有两场考试，时间分别在$a_i, b_i\ \ (a_i < b_i)$，要求每门科目至少参加一场考试，不能在同一个时间参加两场考试，问最后参加的考试最早的时间是什么。 这几天，我怎么做的都是水题Emm.... 考虑先将$a_i, b...
2018-10-25 22:56:00
92
转载 Codeforces Gym 101623A Ascending Photo - 动态规划
题目传送门 传送门题目大意 给定一个长度为$n$的序列，要求划分成最少的段数，然后将这些段排序使得新序列单调不减。 考虑将相邻的相等的数缩成一个数。 假设没有分成了$n$段，考虑最少能够减少多少划分。 我们将这个序列排序，对于权值相同的一段数可以任意交换它们，每两个相邻数在原序列的位置中如果是$i, i + 1$，那么划分的段数就可以减少1....
2018-10-24 22:34:00
117
转载 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror) Solution
从这里开始题目列表瞎扯Problem AFind a NumberProblem BBerkomnadzorProblem CCloud ComputingProblem DGarbage DisposalProblem EGetting Deals DoneProblem FDebateProblem GMonsters a...
2018-10-21 22:32:00
102
转载 Codeforces 1045B Space Isaac - 数论 - Hash
题目传送门 传送门I 传送门II 传送门III题目大意 给定将$\left \{ 0, 1, \dots, m - 1\right \}$分成了不相交的两个非空集合$A$和$B$，给定$A$，问存在多少个整数$x$满足$0\leqslant x < m$且对于任意$a\in A, b \in B$满足$a + b\not \equiv x \pm...
2018-10-18 07:54:00
136
转载 NOIP 2017 列队 - Splay - 树状数组
题目传送门 传送点I 传送点II题目大意 （家喻户晓的题目应该不需要大意） （我之前咋把NOIP 2017打成了NOIP 2018，好绝望）Solution 1 Splay 每行一颗Splay，没有动过的地方直接一段一个点。 最后一列单独一颗Splay。 暴力模拟即可。Soluion 2 Splay II 我们考虑倒...
2018-10-15 13:31:00
132
转载 bzoj 1835 base 基站选址 - 动态规划 - 线段树
题目传送门 需要高级权限的传送门题目大意 有$n$个村庄坐落在一条直线上，第$i \ \ \ (i>1)$个村庄距离第$1$个村庄的距离为$D_i$。需要在这些村庄中建立不超过$K$个通讯基站，在第$i$个村庄建立基站的费用为$C_i$。如果在距离第$i$个村庄不超过$S_i$的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第$i$个村庄没有被覆盖，则需...
2018-10-15 08:15:00
130
转载 vijos 1605 双栈排序 - 贪心 - 二分图
题目传送门 传送门I 传送门II题目大意 双栈排序，问最小字典序操作序列。 不能发现两个数$a_{j}, a_{k}\ \ (j < k)$不能放在同一个栈的充分必要条件时存在一个$i$使得$j < k < i$且$a_{i} < a_{j} < a_{k}$。 证明？写个dfs就证完了（就是考虑任意一个三元组）...
2018-10-12 22:40:00
110
转载 bzoj 1078 [SCOI2008] 斜堆
题目传送门 传送点I 传送点II题目大意 给定一个（小根）斜堆的生成方式。如果$H$为空，或者插入的数$x$的权值小于根节点的权值，那么用$x$顶替$H$的位置，然后把$H$作为它的左子树。否则交换$H$根的左右子树，然后递归左子树。 给定一个斜堆，元素大小分别为$0, 1, \dots, n$，问字典序最小的插入序列。 （这...
2018-10-12 13:35:00
103
转载 bzoj 4358 Permu - 莫队算法 - 链表
题目传送门 需要高级权限的传送门题目大意 给定一个全排列，询问一个区间内的值域连续的一段的长度的最大值。 考虑使用莫队算法。 每次插入一个数$x$，对值域的影响可以分成4种情况：$x - 1$, $x + 1$都不存在。只有$x - 1$存在，等价于在一段后面添加一个数只有$x + 1$存在，等价于在一段前面添加一个数$x - ...
2018-10-11 19:35:00
98
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人