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)

/ 注册

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

NC5026C

题意总共12道题，以A,B,C,D为答案的有na，nb，nc，nd个，且有一些题目答案要一致。思路答案一致想到并查集合并到一起，然后我就很蠢的开始想排列组合了，后来发现排列组合的情况很多，不好写，遂开始思考dp，发现还是不会，这时候瞟了一眼数据，这个数据范围很小，直接暴力模拟利用stl中的ne...

暴力

2020-04-11

1 717

NC5026B

题意你有n个苹果和m个香蕉，你可以花一天时间使得其中一种水果翻倍，或者花一天时间同时吃掉1个苹果和1个香蕉，苹果和香蕉必须同时吃掉。求最少多少天可以吃完？思路贪心：我们翻倍要做到既让水果得到最大程度的补充，又不能超过，则进行翻倍。这里苹果和香蕉是等地位的，为了方便我们先把大的给到,小的给到,看...

2020-04-11

1 624

NC5026A

题意 h，a，H，A，代表你的血量和攻击力以及毛球怪的血量和攻击力。求你能杀多少只毛球怪，若你能杀无限只，则输出"-1"。（你先手）思路计算你需要打一只毛球怪次他才会死，计算你每杀一只毛球怪所消耗的血量，由于你先手你所扣的血量为你攻击毛球怪的次数。若消耗的血量为0，则输出"-1"，否则输出，这里...

2020-04-11

0 723

NC13611

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

DP 组合数学

2020-04-10

0 724

NC13249

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

2020-04-09

0 558

NC13886

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

DFS 数据结构

2020-04-02

0 505

NC23053

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

预处理二分

2020-04-02

0 601

NC22598

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

树形DP DP

2020-04-02

0 545

NC82B

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

ST表数据结构

2020-03-31

3 804

NC50528

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

单调队列双端队列

2020-03-29

0 646