开始寒假集训了
先把这段时间做的题理一下
CF5C
求左右括号的最大匹配长度，一开始的想偏了， 然后越走越远。
正确的思路是，跑一次堆栈的匹配，这个是基本操作。然后在可行的情况下，左右拓展即可。
CF5D
物理题
这题就是把所有情况给想清楚就可以AC
CF5E
这题是看了dalao的题解，悟了很久之后做出来的。
一个圆环数列，求多少个数对之间（两个弧，有一个满足条件就可以）没有比他们大的数。
看完题目，脑子里就只有暴力，铁废物一个。
思路是找出每个数字两端刚好比他大的位置。
假设左边在l位置，右边在r位置，自己是pos
那么显然起码有两对 （l, pos） (pos, r) 。然后需要考虑在pos，r之间有和pos大小一样的情况，同样需要计入答案。
就不得不佩服dalao的思维。
#include <stdio.h> const int N = 1e6+10; int lef[N], rig[N], cou[N] = {0}, a[N], b[N]; int main() { long long ans = 0; int n, maxid; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", a+i); if(i==0) maxid = 0; else if(a[i] > a[maxid]) maxid = i; } maxid--; for(int i = 1; i <= n; i++) b[i] = a[(maxid+i)%n]; lef[1] = 1; for(int i = 2; i <= n; i++) { lef[i] = i-1; while(lef[i]>1 && b[lef[i]] <= b[i]) lef[i] = lef[lef[i]]; } for(int i = n; i >= 1; i--) { rig[i] = i+1; while(rig[i]<=n && b[rig[i]] < b[i]) rig[i] = rig[rig[i]]; if(rig[i]<=n && b[rig[i]]==b[i]) { cou[i] = cou[rig[i]] + 1; rig[i] = rig[rig[i]]; } } for(int i = 2; i <= n; i++) { ans += cou[i] + 2; if(lef[i]==1 && rig[i]==n+1) ans--; } printf("%lld ", ans); }
CF6D
有一排怪物，可以只能打 2 – n-1 的怪物，打i怪物，i本身收到a伤害， 左右怪兽收到b伤害。
一道有意思的dp题，dp[i][j][k] 表示在i个怪兽打了k下， i-1打了j下。
看完dalao的这个dp定义之后，我就想明白了dp的方程式怎么写，所以留个思路。
CF7C
考了一个exgcd 时间久远，都已经不记得怎么写了，默写一下
void exgcd(int a, int b, int &x, int &y) { if(b==0) { x = 1; y = 0; return; } exgcd(b, a%b, y, x); y -= a / b * x; }
CF6E
水题，上个树状数组就行。
CF7D
学到了dalao的双hash操作，看的我热血澎湃， dalao牛逼
CF8C
看到数据范围就应该想到是状压dp的，但是奈何魂飞九天，一点想法没有。
知道是状压之后，就交了一发，结果t了(1<<n *n* n 不t你，t谁)
然后再看题解，可以根据问题特性优化，对于这个问题来说 只要组合对就可以了，和顺序没有关系，那么我们只要保证有一个循环过去就可以了，而不需要双重循环。