pamhip
pamhip
全部文章
题解
# BSGS(1)
# BZOJ(15)
# FFT(1)
# NOIP(5)
# 单调队列优化(1)
# 原根(1)
# 可持久化线段树(1)
# 回归试水之洛谷试炼场(17)
# 容斥原理(1)
# 并查集(4)
# 思维题(3)
# 扫描线(1)
# 搜索(1)
# 数论(14)
# 最小生成树(5)
# 最短路(1)
# 杂文(2)
# 构造题(1)
# 树形dp(1)
# 状压dp(1)
# 线段树(4)
# 网络流(6)
# 莫比乌斯反演(3)
# 莫队(1)
# 计数问题(1)
-------------图论---------(4)
-------------数据结构------(2)
-----------字符串--------------(2)
----------动态规划------(2)
对抗攻击(1)
比赛总结(2)
归档
标签
去牛客网
登录
/
注册
pamhip的博客
全部文章
/ 题解
(共40篇)
NC18386 字符串(尺取)
来自专栏
题意 小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的,当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中,长度最短是多少。 。 分析 对每个 ,我们要求最大的 ,使得 包含了所有小写字母。显然, 是单调递增的。于是我们开个桶记录一下每个字母出...
2020-06-18
1
956
CF650F2 Flying Sort (Hard Version) (思维)
来自专栏
题意 有一个数组 ,每次你可以选择一个元素放到最后面或者最前面,求将 排成不递减序列的最少次数。 可能有重复元素。 。 分析 由于这些数只和大小关系有关,我们先离散化一波,将值域变为 。观察发现,每个数如果要移动,最多只会移动一次。那么,次数 = n - 不移动的数字个数。我们考虑最大化不用移动...
2020-06-18
0
1293
NC19158 失衡天平(背包)
来自专栏
题意 终于Alice走出了大魔王的陷阱,可是现在傻傻的她忘了带武器了,这可如何是好???这个时候,一个神秘老人走到她面前答应无偿给她武器,但老人有个条件,需要将所选武器分别放在天平的两端,若天平平衡则可以将天平上的所有武器拿走,还好这个天平锈迹斑斑,只要两端重量相差小于等于m就会保持平衡,Alice...
2020-06-10
3
1021
东华大学2020年程序设计竞赛(同步赛)G Gaming with Mia(动态规划)
来自专栏
题意 有 个数,每个数取值范围为 。现在要在两两数之间插入 和 两种运算符,使得运算结果最大化,求最大化的结果。其中,。 分析 这里提供一种非主流做法。最终的形式肯定是一块块乘积相加的形式,于是我们考虑 。令 表示来到 时的最大值。那么 。其中, 指的是 这段区间每个数的乘积。由于 的...
2020-06-08
4
875
NC21228 [NOIP2018]货币系统(背包)
来自专栏
题意 组数据,有 种货币,每种货币有无限量,求最少的货币种类,使得所有种类的货币可以被表示。 。 分析 先将货币数值排序,如果 可以被前面的表示,那么 显然没用了。如果没被表示,就显然必须加入货币系统。怎么看能不能被表示呢?这不就是个背包吗=。=复杂度 代码如下 #include <...
2020-05-26
0
802
NC20154 [JSOI2007]建筑抢修(优先队列)
来自专栏
题意 有 个任务,每个任务有个完成时间 和截止时间 。问最多能完成多少任务。 分析 这道题还是挺难的QAQ。首先看到这题,我们可以先将问题转化一下:假设最终做的任务序列为 ,那么对任意 需满足 ,也就是: ... 我们现在要让这个序列尽量长。然后有一个基础的想法:对于每个 ,我们要求满足上...
2020-05-25
0
679
NC14414 小AA的数列(按位考虑 + 前缀和)
来自专栏
题意 小AA找到了一个数列,她想要知道这个数列中所有长度为偶数的区间异或和之和 。后来她发现这个问题太简单了,于是她加了一个限制,要求区间长度在[L,R]之间,然后她就不会了。。。请你告诉她问题的答案。其中,。 分析 和位运算有关的题统统按位考虑=。=,于是我们枚举二进制的每一位。问题转化为:有 ...
2020-05-22
0
904
NC19913 [CQOI2009]中位数图
来自专栏
题意 给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。其中,。 后言 看了别人的写法才知道我的写法有多s,b。大家就当看个乐吧TAT 后后言 我靠!原来题目中的数组是 的排列!!!!以下做法适用于任何数组!!! 可以不止...
2020-05-21
0
989
NC52275 图的遍历(求无向图的奇环)
来自专栏
题意 小sun最近为了应付考试,正在复习图论,他现在学到了图的遍历,觉得太简单了,于是他想到了一个更加复杂的问题: 无向图有n个点,从点1开始遍历,但是规定:按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法,不一定能够遍历整个图,所以现在小sun想问你,最少加几条边,可以完整的遍历...
2020-05-21
0
1150
CF600E Lomsat gelral(树上启发式合并)
来自专栏
题意 有一颗 个节点的树,以 为根节点,每个点有一个颜色 。设子树 中颜色出现次数最多的颜色集合为 ,记 。现在要求 。其中,。 分析 这种题叫做 ,也就是树上启发式合并。让我们先考虑暴力做法。就是以每个节点,对子树进行 ,然后开一个桶记录颜色出现次数,最后把颜色出现次数最多的颜色加起来。这样...
2020-05-20
0
806
首页
上一页
1
2
3
4
下一页
末页