凡尔赛卷卷

做题笔记

学习笔记(16)

/ 注册

全部文章 / 做题笔记（共85篇）

牛客补题骚区间

骚区间题目链接题意给一个数组，问有多少个连续子序列l ~ r满足 a[l]是这个区间的次小值a[r]是这个区间的次大值。题解刚开始上去没什么想法，但是后来发现对于一个数， 1、当这个数是左边界时，从他右边比他大的第一个开始到比他大的第二个数之间的数都可能是右边界。 2、当这个数...

2020-09-15

0 399

牛客补题迁徙过程中的河流

迁徙过程中的河流题目链接题目大意有n个人要过河，每个人有过河的时间a[i]，每次船上只能有两个人，只有一艘船，过河的时间按照船上的人的过河时间的最大值算，问最短多长时间可以过河？题解不会做，，不会 dp数组：dp[i] 前i个过河需要的最短时间。想到了dp，但是不会转移，不知...

2020-09-15

0 464

牛客补题瘦了的牛牛去旅游图 dp

瘦了的牛牛去旅游题目链接题目大意给一个有向图，有边权。一个路径的密度 = 这条路上的边权和 / 这条路上边的数量。有q次询问，每次询问给两个点，问这两个点路径上的密度最小是多少。数据范围：点的数量n（50）边的数量m（1000）询问的数量q（1e5）题解我做的时候比较捞。...

2020-09-15

0 682

树形dp 西安邀请赛 J - And And And

J - And And And 题目链接题目大意给一棵树，然后算公式的含义：任意两个点之间的子路径异或和为0的数量和。题解自己做的时候比较呆，啥都看不懂。公式的意思是先两个for枚举两个点，然后再两个for枚举两个子路径，如果子路径异或和是0 那就答案加一。题解：先找子路径...

2020-09-15

0 469

2019icpc 西安邀请赛 E - Tree 树刨，nim博弈

E - Tree 题目链接题意两个人玩游戏，每次有几堆石头，每个人可以选一堆石头，从里面拿走任意个，最后没有石头拿的人输。（这个博弈，经典的nim博弈）现在有一棵树，有点权，有三种操作， 1 s t 1 ~ s路径上的节点的权值变为ai | t 2 s t 1 ~ s路径上的节点的权值变...

2020-09-15

0 569

牛客多校补题 Greater and Greater bitset

Greater and Greater 题目链接题目大意给一个长度为n的数组a （n <= 150000）一个长度为m的数组b (b <= 4e4) 问a中有多少个连续的子数组s满足也就是说问有多少个子数组每一个数字都大于等于b中的每一个数字题解大佬说这种4e4...

2020-09-15

0 533

牛客多校补题第二场 H Happy Triangle

Happy Triangle 题目链接题目大意有三种操作：插入一个值x 删除一个值x 给一个x 问是否在数组里是否有两个值，可以与x构成三角形。题解与x构成三角形可以分为几种情况 x是最大边的时候数组里比x小的最大的两个的和比x大就可以 x不是最大边的时候找一个值，存在另一个...

2020-09-15

0 435

牛客多校第二场 A All with Pairs

All with Pairs 题目链接题目大意给n个字符串，f(s1,s2) 代表 s1的前缀和s2的后缀相同的最长长度。求上面的那个式子。题解如果算的不是最长长度而是所有的话，就直接先hash一下后缀，在每个前缀里找有多少个后缀与这个前缀相等就可以。但是这个题要求最大值，并...

2020-09-15

0 559

牛客多校第一场补题 1 or 2 建图，一般图匹配带花树

1 or 2 题目链接题目大意给一个无向图，给一个长度为n的a数组问能不能删除一些边以后能不能让每个点的度数为ai 题解比赛的时候，因为数据水，用网络流，乱水过去了，后来才知道有反例，不能跑网络流。正解：建图方式：拆点，把这个点拆成ai个点，如果有一个边x- - - - -y ...

2020-09-15

0 444

杭电多校第二场 A Total Eclipse 并查集

Total Eclipse 题目链接题目大意给一个无向图，有点权。每次选一整个连通块，让这个连通块里的点权都减一，问最少操作几步可以让他们都减成0？减成0了就不能再减了，也就是这个点就删去了。题意给的不明确。他没说选的连通块尽可能大。。结果到最后了改了题面说连通块必须选尽可能大的。可...

2020-09-15

0 559