NC5026E 题意 把原题意转化为给你一个长为的字符串，求至少有个相同且不相交的长为(可为)的子串，为多少？ 思路 二分+哈希字符串 时间复杂度这道题不要求得到所求子串为什么，而要求子串所能取得最大长度，且答案具有严格单调性，故可以二分答案。那么如何验证？首先预处理字符串Hash得到Hash数组表示对应的Hash值power数组表示对应的有一个难点在于如何保证不相交？  我们在map的value中放入一个pair<int,int>，first放该字符串的结尾位置，second放该字符串的出现次数，当出现新的相同的hash值(相同的字符串)时我们验证新的位置减去上一个的位置是否，若...

题意 一张连通有向图，另一条边反向，是否缩短了1到n的最短路？保证开始给定的图从城市1可以到达城市n，若边反向后城市1不能到达城市n，我们视为最短路径长度没有变短。 思路 数据范围较大，最原始的暴力每次djikstra一遍肯定是TLE的，于是思考预处理，预先djiksra一遍。每次反向一条边和没反向有什么区别呢？想到直接在原图上加一条反向边，原来的边不管他不影响结果。这时候画个图当我们反转2←4这条路，使得其变为2→4，新的最短路路径的算法为 1到2的距离 + 4到2的距离 + 4到5的距离。我们将这个模型一般化，就是 和原先的最短路比较即可。问题是我们知道了1到i的最短路还不知道j到n的最短...

题意 总共12道题，以A,B,C,D为答案的有na，nb，nc，nd个，且有一些题目答案要一致。 思路 答案一致想到并查集合并到一起，然后我就很蠢的开始想排列组合了，后来发现排列组合的情况很多，不好写，遂开始思考dp，发现还是不会，这时候瞟了一眼数据，这个数据范围很小，直接暴力模拟利用stl中的next_permutation模拟，若符合条件则计数即可，跑了一下。咦，大家怎么都是dfs做的呢？其实dfs和next_permutation在这里应该都是一样的吧，我中间好像也想过用dfs。代码虽然看起来很长，但我觉得思路很好，不用动啥脑子，暴力就是了。 #include<bits/stdc+...

题意 你有n个苹果和m个香蕉，你可以花一天时间使得其中一种水果翻倍，或者花一天时间同时吃掉1个苹果和1个香蕉，苹果和香蕉必须同时吃掉。求最少多少天可以吃完？ 思路 贪心：我们翻倍要做到既让水果得到最大程度的补充，又不能超过，则进行翻倍。这里苹果和香蕉是等地位的，为了方便我们先把大的给到,小的给到,看了眼官方题解，是可以用数学公式优化到每次的，但是这题数据范围不大，直接这样模拟也能过。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; con...

题意 h，a，H，A，代表你的血量和攻击力以及毛球怪的血量和攻击力。求你能杀多少只毛球怪，若你能杀无限只，则输出"-1"。（你先手） 思路 计算你需要打一只毛球怪次他才会死，计算你每杀一只毛球怪所消耗的血量，由于你先手你所扣的血量为你攻击毛球怪的次数。若消耗的血量为0，则输出"-1"，否则输出，这里-1是代表给你留了一滴血活到最后。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const double eps = 1e-8; cons...

NC13611 题意 一棵有n个结点的树，我们有k种不同颜色的染料给树染色。当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同时，染色方案是合法的。请统计方案数。 思路 把题目转化为给你一颗n结点的树，将其分成个连通块涂上不同的颜色，此时发现染色方案的数量与这棵树的形状无关，仅与k和n有关，将其看为一个点集，每个点集可以涂一种颜色。   组合数学：分成个连通块可看做断条边，则可选边的方案数为C_{n-1}^{i-1}，每一个块可以取的颜色有种，又可以将连通块分为块不同颜色，最后总的方案数   DP #include<bits/stdc++.h> ...

NC13249 题意 给你一棵树，每个节点上有一个值，一开始树上所有节点均为白色，要求你每次选择一个白色节点染色，从该节点往根的链上小于的均被染色，求最小染色次数为多少？ 思路 DFS 贪心首先叶子结点是一定要染色的，我们考虑如何返回的时候构造最优方案，我们维护两个数组。回溯路径所能染色到的最远距离无须染色所能染色到的最远距离当的时候，意味着到该节点必须进行一次染色，此时不一定是选择该节点进行染色，可以选择回溯路径所能染色到的最远距离那个点进行染色。 #include<bits/stdc++.h> #pragma GCC optimize(2) using namespace st...

NC13886 题意 给你一颗n(偶数）结点的树，将其分为n/2对，求所有对数相连的路径之和最小为多少？ 思路 DFS 数据结构既然是图论那就先画图吧左图由于以2号结点为根节点的子树结点数(包括其自身)为3（奇数），那么显然这棵树上一定有个节点要从树外找一个节点相连，那么必须要经过2号结点与其父节点的这条路(2->1)。右图告诉我们如果能偶数配对的子树则不需要相连。叶子节点为子树的结点数一定为1显然一定会加上。DFS求子树的结点数，若结点数为奇数则需要该节点与其父节点相连的这一条边，若为偶数则不需要。 注意：多组数据要每次清空vector数组，然后置于cnt数组不需要memset是因为d...

NC23053 题意 给你一个字符串s，给你T组数据，每组数据输入一个字符串t，对该字符串判断是否为s的子串，若为子串则输出"YES"否则输出"NO"。  思路 预处理 二分查找 最坏复杂度数据范围这么大，暴力是肯定要超时的，贪心每次必取s串中的第一个没用过的字母和对应的t的字母进行匹配，这样才能让后面的选择余地更大。一开始我想到的是将s所有的字符储存入vector中，然后维护查找的起始点，查找所需字符，如果不超过vector的范围，则更新查找的起始点为查找到的对应下标，然后继续查找。后来看了别人的代码才知道更优秀的操作是把字符分类将其下标放入不同的vector容器中再用库函数upper_bo...

NC22598 题意 （题目数据范围M=N-1可知这是一棵树，一个边数为结点数-1的连通图一定为一棵树）给你一颗N个结点的树和对应边的权值，求以S结点为根节点去掉一些边使得不与叶子结点直接相连的最小代价为多少？ 思路 第一次做树形DP，设为结点的度为多少，重要结论：叶子结点的度一定为1，结合根节点的度也可能为1，可以只有一个儿子，所以回溯的条件应该是非根节点且度为1则return。如何判断是否为根节点呢，我们令根节点的父节点为-1，如果fa为-1则当前节点为根节点。DFS是从根节点找起，程序的计算应该是从叶子结点至下而上回溯。 #include<bits/stdc++.h> #de...

NC82B 题意 给你一个长为n的序列a和一个常数k有m次询问，每次查询一个区间内所有数最少分成多少个连续段，使得每段的和都 <= k如果这一次查询无解，输出""  思路 预处理 前缀和 ST表分两种情况考虑：  输出"" ，这种情况，用ans数组维护是否范围内存在的情况。 输出范围内所有数最少分成多少个连续段。首先预处理计算前缀和，利用二分查找前缀和的方式初始化，表示从第个位置开始分段，最多能到第几个位置。  注意点：  倍增跳跃的时候选择从大到小开始遍历，能跳大的且不超过R的时候先跳大的。例如5=4+1如果从小的开始找就会出现5!=1+2+4然后回溯在到5=1+4所以要倒着来。  #...

NC50528 题意 给你一个长度为n的数组，依次求长度为k的区间中的最小值，最大值为多少。 思路 单调队列（双端队列） 时间复杂度单调队列性质：  队列中的元素其对应在原来的列表中的顺序必须是单调递增的。   队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以求最小值的做法：维护一个单调队列，头部元素的下标为，尾部元素的后一位下标为，其中的值为（存数组中的下标）使得中的元素满足且即下标递增下标所对应的值也是有序的(可自定义）。最大值对应只是改变了对应值有序的排列方式。  #include<bits/stdc++.h> using namespace std; typede...

题意 由小写英文字母组成的长度为n的一个字符串，求不相同的长度为k的子串的数量对1e9+7取模。  思路  正难则反正难则反，我们求所有不同的子串，不如把所有子串的数量求出来再减掉所以相同的子串数量。若不去重求所有长度为k的子串的数量，则可由推出到第个数为止长度为的子串数量。不难理解,代表的是到第个数取了个数再加上第s[i]个数构成了个数。本题的难点在于如何去重。我们观察一个字符串。 打个简单的表让大家看一下 发现以结尾的长度的字符串会在中计算一次以为结尾的子串，而中又会计算一次以为结尾的子串，那么就重复计算了前面的那部分以为结尾的子串，显然后者包括前者且大于等于前者。 所以这里要用到来记录上...

NC15553 题意 给你n个数，选2个长度为k的连续区间，求他们加起来的和最大为多少？ 思路 前缀和预处理，然后利用前缀和计算k个数的最大数为多少，然后预处理从左边遍历到i为止最大的区间长度为k的和为多少，从右边遍历到i为止最大的区间长度为k的和为多少。扫一遍要选的第一个区间，扫的过程如果左右还有可以选的区间，则取他们的最大值和选的区间相加，记录最大值即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const double ep...