动态规划解法，dp[i]表示以i为开始的最长有效括号字符串的长度，只有以'('开始有可能出现有效括号串，对于每一个'('来说，要凑出一个有效的括号字符串 肯定是'('+一段有效的括号字符串+')' +一段有效的括号字符串 #include<iostream> using namespace std; const int MAXN = 1e5+10; int main() { string s; cin >> s; int ans = 0; int dp[MAXN]={0}; for(int i = s.length()-2 ;...

题号 NC20271名称 [SCOI2009]游戏 来源 [SCOI2009]戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 首先，对于任何的一组置换我们都可以把它换成若干的轮换（即A->B,B->C,C->D,D->A这样子转一圈），因为如果a变成b,b变成c……之后没有一个数变回a的话，在变化之后的数列里面a就没有了，所以一定会形成一个圈。那么对于一个有x个元素的轮换，显然换X次才能换回原样，那么对于所有的轮换，他们的LCM就是答案。于是问题就变成了：把n...

先把区间按区间的起始位置从小到大排序，然后从前往后看一遍，如果下一个区间的开始比前一个区间的末尾要小。那么这两个区间就可以合并。 #include<iostream> #include<algorithm> using namespace std; const int MAXN = 1e5+10; struct node{ int s,e; }Interval[MAXN]; bool visit[MAXN]; bool cmp(node a,node b) { if(a.s==b.s) { return a. e< b....

题号 NC16495名称 联合权值 来源 NOIP2014提高组复赛 赛 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 n个点n-1条边的无向连通图，其实就是一棵树，树上距离为2的点对是很简单的：只有两种——同一个父亲的两个儿子/一个点的儿子和父亲。我们考虑在dfs过程中去算，对于当前点，我们维护他儿子们和他父亲的最大值和次大值，然后就可以求出最大的联合权值。求和的时候，每遍历到当前点的一个儿子，就将他与当前点的父亲和之前的儿子的和乘起来，注意这样对于两个数对(a,b)和(b,a)...

第n个月的兔子可以分成4类，一类是成熟的兔子f(n-3)，第二类是刚出生的兔子f(n-3)，第三类是出生了一个月的兔子f(n-4)，第四类是出生了两个月的兔子f(n-5) #include<iostream> using namespace std; const int MAXN = 1e6+10; long long mod = 1e9+7; long long dp[MAXN]={0,1,1,1,2}; int main() { int n; cin >> n; int t = 0; long long sum = 0; ...

题号 NC50349名称 The XOR-longest Path 来源 信息学奥赛一本通 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 关于trie树的简单介绍：trie树又叫前缀树，字典树，他用一个树型结构来表示一个字符串集合。树中的每一条边上都有一个字符，从根节点到某一个位置经过的边就是一个字符串，注意因为有的串是另外的串的子串，所以我们可以用一个字符集里没有的字母（比如$)作为字符串结束的标志。这样拥有同样前缀的字符串在树上就会走相同的路径，在储存上节约了空间，在查找目标串...

题号 NC110867名称 Closest Equals 来源 CF522D戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 题意：对一个序列有m组询问，每次询问区间[l,r]内两个相同的数的最近距离是多少。对于每个元素，我们可以先求出上一个和他一样的数的出现位置记为pre[i]。然后每次查询的时候，查询的是[l,r]区间内pre[i]大于等于l的i-pre[i]的最小值——那么要怎么把pre[i]小于l的点排除在查询外？将询问离线，按照询问区间的右端点从左到右排序。从左到右扫描，对于每一个i和pre[i]只对l在pr...

题号 NC110615名称 Present 来源 CF460C戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 看到最小值最大——二分对于任何一个数字我们都需要将它加到大于等于ans，所以，从左往右扫描，对于每一个小于ans的值都将以他为左界的区间加上若干个1直到它等于ans，这个区间加操作可以用线段树等维护，也可以使用差分——虽然这里的操作不是离线的，但是每次修改的都是后面的区间，而每个点的值只会被之前的点修改到，所有我们可以保证对每个元素的求值都是在之前的所有区间修改之后的。（这里提醒大家思考时间轴的概念，对于修改...

题号 NC24950名称 Telephone Lines 来源 USACO英文版-2008 January Contest-Silver 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 两种解法：二分+验证验证：存在一种合理的方法使得升级花费不超过mid。于是我们把价格大于mid的边权看作1，小于mid的边权看作0，求最短路即可——这个可以使用01bfs，不会01bfs的同学可以看之前的每日一题：6月22日题目精讲-Three State。分层图最短路(dp思想)：用一个二维状态dist[x,k]表示到达了x这个点，...

比赛名称：牛客练习赛69 活动具体内容 9月11日22:00-10月12日18:00，写牛客练习赛69题目的题解，即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量 比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下 活动奖励： 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在10月13日下午审核，并给每篇题解发放5-60牛币 PS: 如果题解写的非常好，会增加其获得的牛币 如果题解写的非常水，会减少获得其获得的牛币 如果题解有抄袭行为，会...

题号 NC50381名称 道路和航线 来源 信息学奥赛一本通 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 比较基础的图论板子题，大家都会用spfa的优化给过了，这里不再赘述，我们来讲利用题目本身的性质来解题：题目当中说：双向边是非负的而单向边没有环，所以，我们可以先把有双向边链接的若干个点缩成一个点，然后点之间连上单向边之后这张图是一个有向无环图，所以跑广搜就可以了。而连通块内部因为边非负，所以可以dijkstra。 欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！ 活动奖励： 在牛客博客中写出题解...

题号 NC16735名称 网格图 来源 Wannafly挑战赛18 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 当前一步能怎么走与位置和前一步的方向有关，所以他们全部放在状态里——f[i][x][y][dir]表示第i步在(x,y)这个位置，是从dir方向而来，dir有五个值分别表示上下左右和原地踏步。复杂度为（要枚举自己的方向和上一个点的方向所以是）数组可以滚动压掉i的那一维。 欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！ 活动奖励： 在牛客博客中写出题解，并回复地址审核通过可获得（依据题目难...

一开始看题还以为是个贪心，后来仔细看了一下发现并不是，然后发现任务数，就上状压dp了，可以用一个大于0,小于(1<<n)的数字表示做了哪些任务，比如一共有8个任务，数字 的二进制是00100110就表示做了第2，3，6个任务， 表示做了 代表的这些任务的的最小延迟天数。那其实是从以下的三种情况转化来的。 可以发现，转化出dp[i]的情况在数值上都比i小，因为是把i的某一个二进制位变成了0.所以只需要从0开始遍历到(1<<n)-1,推一遍dp值揪可以了。 #include<iostream> #include<vector> using na...

题号 NC110489名称 Working out 来源 cf 429B戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 我们可以首先dp的求出四个顶点到每个点的最大值。然后枚举交点，实际上只有两种情况：如图：对应加起来取最大值即可。 欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！ 活动奖励： 在牛客博客中写出题解，并回复地址审核通过可获得（依据题目难度和题解的内容而定） 本道题目9月16日中午12：00之前写的题解有获得牛币资格~ .牛币兑换中心 牛客博客开通方式 如何开通牛客博客：https:/...