凡尔赛卷卷

分类

做题笔记(85) 学习笔记(16)

/ 注册

全部文章（共101篇）

牛客多校补题 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

杭电第二场补题 A String Distance dp

String Distance 题目链接题目大意给两个字符串a，b。 a的长度是1e5，b的长度是20. 有两种操作：选一个串在随便哪个位置插入随便哪个字符。随便删除一个字符。有q次询问，每次询问给出一个l，r 问a串的 l ~ r 区间与b字符串，经过多少次操作，能使他们相等？废...

2020-09-15

0 422

牛客多校第5场补题 B Graph 异或最小生成树

Graph 题目链接题目大意给出一颗树，有两种操作，添加一条边，删除一条边。每个时刻必须满足如果有环那么环的边权异或和必须是0，必须是联通的。题解也就是先求一下每个节点到根节点的异或和，然后用这些值的异或当边权求个最小生成树。问题就是知道一些点的点权，边权是两个点权异或，...

2020-09-15

0 472

杭电第三场 Tokitsukaze and Rescue 图

Tokitsukaze and Rescue 题目链接题目大意给一张完全图，每个边有边权。问删掉k条边让从1到n的最短路最长，问这个最长的距离是多少？边权随机，点的个数: 50 题解做的时候，感觉到了这个题很暴力，但是没想到这么暴力。。做的题少，主要不知道边权随机是干嘛用的。。...

2020-09-15

0 722

杭电第四场 Go Running 二分图

Go Running 题目链接题目大意一些人在跑步，从任意一个位置开始，向左或向右跑，速度都为1 m/s。现在已经知道在ti 时刻xi位置上出现了至少一个人，问最少有多少人在跑步题解先说一说比赛的时候的不足: 想到了往右跑的人在任意时刻 t - x 一定是相等的。想到了往左跑的...

2020-09-15

0 500

牛客第六场补题数位dp Harmony Pairs

Harmony Pairs 题目链接题目大意 S(A) 代表A的每位数之和。求0 <= A <= B <= n 并且 S(A) > S(B) 的（A，B）对的数量。题解看到这道题，首先想到数位dp，然后就不会了。。状态表示：dp[i][j][f1][f2]...

2020-09-15

0 485