RainAir

题解

学习笔记(12)

/ 注册

全部文章 / 题解（共9篇）

【题解】牛客练习赛 68 题解

A 注意条件且互不相同，所以一个区间内最小未出现的自然数就等于不在这个区间内最小出现的自然数。预处理前缀后缀最小值就好了。代码链接 B 发现当时答案必为。于是我们只需要预处理的答案就好了。可以推式子或者前缀和处理。代码链接 C 我们考虑单组询问怎么做：实际上就是把所有的所...

2020-08-28

11 846

【每日一题】3月31日

我们考虑一个暴力的做法：每次从这个点找到它上面的第一个比他大的点跳过去。但是这样显然是过不了的。我们先丢掉询问给出的那个权每次就拿这个点上的权来跳答案如何快速处理。我们可以倍增：往上找了个答案之后的点在哪里。问题转化为处理这个也可以利用我们前面已经求出的f来计算：观察到随着 ...

2020-04-02

0 844

【每日一题】3月30

单调队列经典模板题。详细可以看代码。 #include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> #define LL ...

模板 trivial

2020-04-02

0 772

【每日一题】4月1日

树形dp 直接表示为根的子树处理完的代价转移的时候枚举是断掉当前的边还是断子树的边即可。 #include <algorithm> #include <iostream> #include <cstring> #include <climits>...

trivial

2020-04-02

0 848

【每日一题】4月2日

序列自动机模板题。建出后直接看能不能被自动机接受就可以了。 #include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> ...

trivial

2020-04-02

0 863

【每日一题】4月3日

注意到每对点一定是在某一个点（它们的lca）处合并。于是可以dp。设表示已经处理完了的子树当前是否剩余一个还没有配对的点（实际上等价于的奇偶性）。转移合并两个子树的时候考虑一下要不要两边的点配个对就好了。 #include<bits/stdc++.h> #define f...

trivial

2020-04-02

0 777

「NOI2017」游戏

建议大家去 UOJ 交题题目描述有场游戏和三种车，每个游戏可以选择用一种车，每个游戏可能要求不能使用某种车，也可能没有要求。给出个要求，表示如果第个游戏用了车，那么第个游戏要用车。求一种合法方案。，没有要求的游戏个数不超过。题解前置小知识：2-SAT链接建图...

2-SAT

2020-02-28

0 618

「八省联考2018」林克卡特树

主要是为了学习一波 wqs 二分。首先发现这个题目等价于把树切成 k+1 块每块内选个直径加起来，也就等价于在树上找条不相交的链使得收益最大。考虑树上每一条链都可以拆成两条深度单调的链，所以我们可以设表示现在在点已经选择了个链当前点的状态是（没有链经过/有一条单链待匹配...

动态规划凸优化

2020-02-28

0 770

「NOI2005」瑰丽华尔兹

题目链接题目大意现在有一个的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间和一个参数表示在时间时会向方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。其中 ,区间个数，区间最大的右端点...

动态规划

2019-07-19

0 709