11.9 周一
最近真的好忙好忙，要准备演讲比赛，要策划活动
所以最近训练量会很少
三分算法
复习了一下了三分算法
其实蛮简单的。
一.可以用来求单峰函数极值点
二.和二分很像。这里要用两个mid。具体l和r的转移可以画图，举几个特例就可以得出，很简单的
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;double f(double x)
{return (x - 1) * (x - 1);
}int main()
{double l = 0, r = 2;while(r - l > 1e-10){double m1 = l + (r - l) / 3;double m2 = r - (r - l) / 3;if(f(m1) > f(m2)) l = m1;else r = m2;}printf("%.3f\n", l);return 0;
}
11.1 周三
现在就是有空就打cf比赛，认真补题，前四题一定要掌握，五六题尽量
复习了单调栈，挺简单的，可以用来维护一直单调的序列
P5788 【模板】单调栈
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 3e6 + 10;
struct node { int v, id; };
stack<node> s;
int f[MAXN], n;int main()
{scanf("%d", &n);_for(i, 1, n){int x; scanf("%d", &x);if(s.empty() || x <= s.top().v) s.push(node{x, i});else {while(!s.empty() && x > s.top().v){f[s.top().id] = i;s.pop();}s.push(node{x, i});}}_for(i, 1, n) printf("%d ", f[i]);return 0;
}
在刚D题，卡住了。独立思考，继续刚