Recent Blogs

  • [NOI2016] 旷野大计算

    UOJ-224

    神题。

    扑通一声跪下来,千古神犇vfk。


    早就听说了这个造计算机题。正好,前几天上洛谷的省选课,这个题目作为提答作业布置了下来。于是我就开始了我的愉快作死之旅啦~

    自己xjb乱搞,搞了56pts,发现不会做了XD

    于是参考了chrt的题解vfleaking的slide,各种卡,终于拿到了95pts…

    未完待续

    Read More...
  • 省选计划

    省选计划

    省选知识点如下,希望大家能监督我QAQ

    如果发现这边很久都没有打勾的话就在QQ上面喷我吧

    以及如果看到我水群就让我回去学OI

    希望能在省选之前把 的勾打上吧……

    Read More...
  • [NOI2009]变换序列

    链接:Luogu-P1963

    思路

    这个题目可以看出你真正理解了匈牙利算法没有。

    首先我们可以建立二分图的模型:每个位置可以有2种取值,于是我们把位置作为左边的点,取值作为右边的点。然后进行二分图匹配,只要有完美匹配,完美匹配就是一个可行解。

    Read More...
  • NOIP2017游记

    考完NOIP已经2个月了,也是时候写个游记了。

    Read More...
  • [NOI2014]魔法森林

    链接:Luogu-P2387

    这是我做的第一道非模板LCT题目……自己并没有想出来,看题解也看了好久,于是总结下做这个题目的思路。

    题意

    给出一个个点,条边的无向图,每条边都有权值,求一条从点到点的路径,使得这条路径上边的最大值之和最小。

    Read More...
  • 莫队笔记

    莫队是一种离线解决区间查询问题的算法。

    记得 NOIP 之前那段时间,见到一道查询区间颜色种类数目的题目,标签是树状数组。想了很久也没有想出来怎么用树状数组做,看题解才知道有莫队这种逆天的东西……srOOrz

    普通莫队

    以查询区间颜色种类数目为例。为了方便,假定元素个数为 ,查询数目为 .

    暴力开桶扫一遍,复杂度是 的。有没有更高效的算法呢?

    如果已经扫描到区间 ,那么转移到 , 都可以在 的复杂度内完成。既然是离线做,也许可以以某种顺序处理所有询问,利用相邻询问的共同信息,来达到较优化的复杂度。

    如何利用呢?

    Read More...
  • 雅礼集训day12-drink

    题面

    小C桌上有杯水排成一行,第杯水中有单位体积的水. 他会选择一个区间, 并拿一个初始为空的杯子(杯子的容积无限大),他可以重复无限次以下操作: • 选定任意一杯水, . • 使i和它拿着的杯子里的水的体积变为它们的平均值. 小C希望进行若干操作后最大化杯子里的水的体积,设为这个最大值.你需要求: \[ \sum_{i=1}^n\sum_{j=i}^n\frac{g(i,j)}{n^2} \]

    Read More...
  • WC2018学习计划

    离WC2018只有一个月了……

    雅礼集训:

    • 点/链分治
    • Mobius反演
    • Prufer序列 (做题)
    • FFT DFT FWT 多项式各种操作
    • 网络流和各种建模
    • 博弈DP
    Read More...
  • NOIP总结

    更新中

    Read More...
  • [ZJOI2006]物流运输

    链接:Luogu-P1772

    分析

    在输入时对每个码头的不可用时间进行差分。假设某一段连续的时间选择同一条运输路线,则可以通过Dijkstra求出这段时间的最短路长度,记作。总时间是,点数目是,那么预处理每个时间段内选择同一条路的代价的时间复杂度是。显然是可以承受的。

    Read More...
  • 浴谷八连测-R8-B

    题意

    给定个人的个关系,形如:,表示学科成绩高。求1号学生在最坏和最好情况下的排名。
    学科数目

    Read More...
  • [USACO14DEC]Piggy Back

    链接:Luogu-P3110

    分析

    分两种情况讨论。

    1. 。考虑二者在某个点处相遇。在这个点后两个人如果分别走,一定是沿着到的最短路。于是显然背着走更好。
    2. 。二者相遇后各自独立地沿着到的最短路走(其实是同一条路),比背着走更好。
    Read More...
  • 浴谷八连测-R7-B

    题意

    给定一个序列,求它的每个子区间的逆序对数和。包括长度为1的区间。 对于的数据,; 对于的数据,

    Read More...
  • 浴谷八连测-R6-A - 不可逆的重启动

    题意

    求两个串,的最长公共子序列。
    对于70%的数据,满足
    对于100%的数据,满足 ,所有字符都是小写字母。

    Read More...
  • 数论基础

    填坑ing…

    概述

    数论是研究整数的学问。初等数论的基础主要包括同余,扩展欧几里得定理,费马小定理,欧拉定理等。

    Read More...
  • [NOIP2011]观光公交

    链接:Luogu-P1315

    这个题目是在某模拟赛中看到的……并没有做过,当时认为是DP,没有注意到加速器会影响等车的时间,认为只影响坐车的时间。想到了差分。考试结束之前20分钟才发现不满足无后效性,于是完挂爆0。

    分析

    Why Greedy?

    • DP的状态难以设计,而且无法转移
    • 是序列问题,也没有明显的元素间关系
    • 最小化旅行的时间,是最优化问题 最优化 DP/贪心

    既然DP不行,就只有贪心咯

    Read More...
  • 烹调方案

    链接:Luogu-P1417

    思路

    看上去是一个01背包,不过价值随着时间的推移而改变,怎么办?
    先考虑2个物品的情况,即进行基于交换的贪心。时间足够的时候,到底是先取物品1再取物品2,还是先取物品2再取物品1。如果考虑清楚了2个物品的情况,就可以进行排序,再利用动态规划得解。

    Read More...
  • [ZJOI2007]棋盘制作

    链接:Luogu-P1169

    题意

    在一个的矩阵内,找出最大的、像国际象棋棋盘一样黑白交错的正方形和矩形。

    思路

    看到第一问,显然可以用二维平面DP完成:考虑设计状态:以为右下角的最大正方形。k=1表示在这个正方形中为黑,反之为白。因为要求黑白交错,所以把黑白也加入状态。

    Read More...
  • 悬线法学习笔记

    定义

    概念

    有效子矩形:内部不含有任何障碍点的矩形。
    极大有效子矩形:一个有效子矩形,如果不存在一个比它更大而且包含它的有效子矩形,就称它为极大有效子矩形。
    最大有效子矩形:整个矩形中面积最大的有效子矩形。
    约定使用表示障碍点的数量,整个矩形的大小为

    Read More...
  • 创意吃鱼法

    链接:Luogu-P1736

    题目大意

    有一个的矩阵,要在里面寻找一个尽可能大的正方形,使得这个正方形某条对角线上都是1,其他地方都是0。求这个正方形对角线长。

    Read More...
  • 多米诺骨牌

    链接:Luogu-P1282

    审题

    一个骨牌转与不转,改变了两行之间的差值。要求用最少的旋转次数,达到最小差值。

    Read More...
  • [NOIP2016]愤怒的小鸟

    题目链接:

    LYOJ:愤怒的南小鸟

    Luogu:愤怒的小鸟

    题目较长,请在OJ上查看

    Read More...
  • 占坑

    题解占坑列表:

    • ***棋盘制作
    • ***烹调方案
    • ***垃圾陷阱
    Read More...
  • [USACO]低价购买

    链接:Luogu-P1108

    这个题刚看到的时候我是懵逼的……着实被题解惊艳到了,完全想不到还有这么优美的解法。 这些解法来自各位dalao的题解,整理如下。

    Read More...
  • [USACO]家的范围

    链接: Luogu-P2733

    题意

    在正方形的区域内,有一些点有标记,求出边长大于等于2的,内部没有标记的每种不同正方形个数。正方形可以重叠。

    分析

    • 不同正方形的个数? 我们知道DP题目的常用方法是“看题说话”。我们可以根据题目信息直接定义状态吗?确定这个区域内的某一个正方形的两个量,分别是右下角(或者左上角等)的位置,以及它的边长。但是,以两者中的任意一个定义状态,都不方便写出转移方程。 怎么办呢?
    Read More...
  • 字串距离

    链接:Luogu-1279

    思路

    如何实现“插入空格”操作?

    定义状态为,表示字符串A中从第个字符到结尾,字符串B中从第个字符到结尾,所能得到的最小字串距离。显然,可以把都前移,也就是转移到。那空格怎么处理呢?我们用中的一个加1,另一个不变,来表示在某个字符的前面插入一个空格。

    Read More...
  • 排列LCS

    题目链接:Luogu-P1439

    思路

    按照题目中数据规模,直接跑LCS,复杂度为,只有50分。

    考虑到题目中给定的是两个排列,应该可以利用排列的某些性质。

    如果其中一个排列是,那么显然LCS就是另一个排列的LIS。

    Read More...
  • [NOIP2000]方格取数

    链接:Luogu-P1004

    思路

    考虑换成两次都从(0,0)出发 ,向右/下行走。 显然两者到达终点时走过的步数相同。 因此可以让二者每次都走一步,分4种情况讨论。 注意由于步数相同不可能二者位于同一列上下相邻两格。 于是唯一的特殊情况就是二者处于同一个格子,这时这个格子的数只能取一次。 特判处理即可。

    Read More...
  • [NOIP1999]导弹拦截

    链接:Luogu-P1020

    思路

    第一问是裸的最长下降子序列问题。

    第二问:

    Dilworth 定理:

    最长不降子序列长度,等于下降子序列划分数的最小值。

    其对偶定理,即

    最长下降子序列长度,等于不降子序列划分数的最小值。

    同样成立。

    我也不知道怎么证明的,要用到偏序集。但是因为和LIS问题有关,先记下来。

    第二问需用到此定理。

    最少需要的导弹系统数,实际上就等于最长不降子序列的长度。

    Read More...
  • 单调数据结构学习笔记

    这里的“单调数据结构”,指的就是单调栈和单调队列。

    单调栈

    特点

    先进的元素后出,求前/后缀最值。

    实现

    使用一个栈(这不是废话么233),每次在加入栈时维护单调性。不断弹出栈顶元素,直到栈顶元素大于将要加入 的元素,此时再将要加入的元素推入栈中。具体地讲,由于需要随机访问单调栈中的元素, 以便充分利用其单调的特性,常用一个数组来模拟栈。

    Read More...
  • KMP学习笔记

    推荐Menci神犇的Blog,KMP讲的很清晰。 在这里把Menci的学习思路复述一遍,以更好地理解KMP。 KMP 学习笔记-Menci

    字符串匹配朴素算法

    字符串匹配就是在目标串中寻找模式串。

    在朴素算法中,我们穷举每一个可以开始匹配的位置,然后逐一比较,如果无法匹配就向右移动一位模式串,直到找到匹配或者所有位置都无法匹配位置。

    Read More...
  • Todo List

    写给自己的话: 注意建模能力的训练,掌握每种算法对应题目的特点。学时优先看书。 写之前一定要考虑时间复杂度,想好再写!

    欢迎监督QAQ

    Read More...
  • [NOIP2013]货车运输

    题目链接:CodeVS 3287

    题意:给出一张无向图,每条边有一个边权,图上可以有重边,没有自环。求这张图上两点,之间所有路径上最小权值的最大值。若不能互相到达输出-1。

    1.审题

    1. 显然,无向图不一定是连通图,于是两点之间若要互相到达,必须在同一连通子图上。
    2. 最小权值的最大值:图上,两点间有着多条路径,需要找到一条路径,这条路径上所求的权值最小的边最大。
    Read More...
  • Hello,World

    你好,我是panda_2134,一名高二的OIer,目前正在准备省选。想拿NOI金牌。

    欲得其上,必取其中。

    但行好事,莫问前程。

    望你我共勉。

    2018/2/19

    WC考挂,Cu滚粗咯

    看省选咯

    Read More...