Meul

分类

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1) 题解(75)

/ 注册

TA的专栏 13篇文章 1人订阅

11eyes的每日一题

3篇文章 852人学习

11eyes的排位日记

10篇文章 946人学习

0篇文章 0人学习

全部文章（共181篇）

NC13611

NC13611 题意一棵有n个结点的树，我们有k种不同颜色的染料给树染色。当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同时，染色方案是合法的。请统计方案数。思路把题目转化为给你一颗n结点的树，将其分成个连通块涂上不同的颜色，此时发现染色方案的数量与这棵树...

DP 组合数学

2020-04-10

0 716

NC13249

NC13249 题意给你一棵树，每个节点上有一个值，一开始树上所有节点均为白色，要求你每次选择一个白色节点染色，从该节点往根的链上小于的均被染色，求最小染色次数为多少？思路 DFS 贪心首先叶子结点是一定要染色的，我们考虑如何返回的时候构造最优方案，我们维护两个数组。回溯路径所能染色到的最远距离...

2020-04-09

0 552

NC13886

NC13886 题意给你一颗n(偶数）结点的树，将其分为n/2对，求所有对数相连的路径之和最小为多少？思路 DFS 数据结构既然是图论那就先画图吧左图由于以2号结点为根节点的子树结点数(包括其自身)为3（奇数），那么显然这棵树上一定有个节点要从树外找一个节点相连，那么必须要经过2号结点与其父节点...

DFS 数据结构

2020-04-02

0 493

NC23053

NC23053 题意给你一个字符串s，给你T组数据，每组数据输入一个字符串t，对该字符串判断是否为s的子串，若为子串则输出"YES"否则输出"NO"。思路预处理二分查找最坏复杂度数据范围这么大，暴力是肯定要超时的，贪心每次必取s串中的第一个没用过的字母和对应的t的字母进行匹配，这样才能...

预处理二分

2020-04-02

0 594

NC22598

NC22598 题意（题目数据范围M=N-1可知这是一棵树，一个边数为结点数-1的连通图一定为一棵树）给你一颗N个结点的树和对应边的权值，求以S结点为根节点去掉一些边使得不与叶子结点直接相连的最小代价为多少？思路第一次做树形DP，设为结点的度为多少，重要结论：叶子结点的度一定为1，结合根节点的...

树形DP DP

2020-04-02

0 541

NC82B

NC82B 题意给你一个长为n的序列a和一个常数k有m次询问，每次查询一个区间内所有数最少分成多少个连续段，使得每段的和都 <= k如果这一次查询无解，输出"" 思路预处理前缀和 ST表分两种情况考虑：输出"" ，这种情况，用ans数组维护是否范围内存在的情况。输出范围内所有数最...

ST表数据结构

2020-03-31

3 794

NC50528

NC50528 题意给你一个长度为n的数组，依次求长度为k的区间中的最小值，最大值为多少。思路单调队列（双端队列）时间复杂度单调队列性质：队列中的元素其对应在原来的列表中的顺序必须是单调递增的。队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以求最小值的做法：维护一个单调队...

单调队列双端队列

2020-03-29

0 640

NC4853C

题意由小写英文字母组成的长度为n的一个字符串，求不相同的长度为k的子串的数量对1e9+7取模。思路正难则反正难则反，我们求所有不同的子串，不如把所有子串的数量求出来再减掉所以相同的子串数量。若不去重求所有长度为k的子串的数量，则可由推出到第个数为止长度为的子串数量。不难理解,代表的是到...

DP

2020-03-28

4 809

NC15553

NC15553 题意给你n个数，选2个长度为k的连续区间，求他们加起来的和最大为多少？思路前缀和预处理，然后利用前缀和计算k个数的最大数为多少，然后预处理从左边遍历到i为止最大的区间长度为k的和为多少，从右边遍历到i为止最大的区间长度为k的和为多少。扫一遍要选的第一个区间，扫的过程如果左右还有...

2020-03-27

28 905

NC13230

NC13230 题意输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。需要求出所有可能...

区间DP

2020-03-26

1 780