2.18杂

先写一道题CF5E

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; char c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}
int n, p, m;
int a[maxn], h[maxn], s[maxn], cnt[maxn]; 
signed main() {
	n = read();
	int ma = 0;
	//1 2 4 5 3
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		if (ma < a[i]) ma = a[i], p = i;
	}
	for (int i = p + 1; i <= n; i++) h[++m] = a[i];
	for (int i = 1; i < p; i++) h[++m] = a[i];
	//h: 3 1 2 4
	//for (int i = 1; i <= m; i++) cout << h[i] << " ";
	cout << endl;
	int top = 0, ans = n - 1;
    for (int i = 1; i <= m; i++) {
        while (s[top] < h[i] && top) ans += cnt[top--];
        //cout << s[top] << " ";
        if (s[top] != h[i]) s[++top] = h[i], cnt[top] = 0;
        //cout << cnt[top] << " ";
		ans += cnt[top]++;
		//cout << ans << endl;
    }
    while (top > 1) ans += cnt[top--]; 
	cout << ans;
}

DP+单调栈即可，递推一下。

然后去开了场答辩会，听why说答辩。

就两周了，能讲个寄吧课，文化课都快学不懂了。

只能说6……