9.28 周一
洛谷 P1024 一元三次方程求解
#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 a, b, c, d;double f(double x)
{return a * x * x * x + b * x * x + c * x + d;
}int main()
{scanf("%lf%lf%lf%lf", &a, &b, &c, &d);if(abs(f(-100)) < 1e-4) printf("%.2lf ", -100);_for(i, -100, 99){double l = i, r = i + 1, mid;if(f(l) * f(r) > 0) continue;if(abs(f(r)) < 1e-4) {printf("%.2lf ", r);i++;continue;}else if(f(r) > 0)while(l + 1e-4 < r){mid = (l + r) / 2;if(f(mid) > 0) r = mid;else l = mid;}elsewhile(l + 1e-4 < r){mid = (l + r) / 2;if(f(mid) < 0) r = mid;else l = mid;}printf("%.2lf ", mid);}return 0;
}用二分解方程
洛谷 P2678 跳石头
#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 = 5e4 + 10;
int a[MAXN], L, n, m;bool check(int k)
{int num = 0;_for(i, 0, n){int p = i + 1;while(a[p] - a[i] < k) {if(p == n + 1) return false;p++;}if(p != n + 1) num++;i = p - 1; }return n - num <= m;
}int main()
{scanf("%d%d%d", &L, &n, &m);_for(i, 1, n) scanf("%d", &a[i]);a[0] = 0; a[n+1] = L;int l = 1, r = L + 1, mid;while(l + 1 < r){mid = (l + r) >> 1;if(!check(mid)) r = mid;else l = mid;}printf("%d\n", l);return 0;
}这题逆向思维很重要
一开始想到枚举去掉的m岩石，必定超时
就反过来想，枚举距离，即枚举答案
最大的最小值，最小的最大值，八成和二分答案有关
判断答案时，就模拟跳的过程就好。不要枚举岩石
这道题对我而言的难度刚刚好，不会太难也不会太简单
今天干了三道题，还可以。难度设置挺合适的
全都自己独立做出
9.29 周二
不要做水题
做有思考，有价值，让自己想一段时间才能做出的题
锻炼思维
洛谷 P1803 凌乱的yyy / 线段覆盖
#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 = 1e6 + 10;
struct node
{int l, r;
}a[MAXN];bool cmp(node x, node y)
{return x.r < y.r;
}int main()
{int n;scanf("%d", &n);REP(i, 0, n) scanf("%d%d", &a[i].l, &a[i].r);sort(a, a + n, cmp);int ans = 0, p = 0;while(p < n){ans++;int t = p + 1;while(a[t].l < a[p].r && t < n) t++;p = t;}printf("%d\n", ans);return 0;
}一开始是用左端点排，wa
自己也举出了反例
然后尝试用用右端点排，对后来妨碍小
然后就ac了
洛谷 P1090 合并果子 / [USACO06NOV] Fence Repair G
#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;int main()
{int n, ans = 0;priority_queue<int, vector<int>, greater<int> > q;scanf("%d", &n);REP(i, 0, n){int x; scanf("%d", &x);q.push(x);}while(q.size() > 1){int x = q.top(); q.pop();int y = q.top(); q.pop();//printf("%d %d\n", x, y);ans += x + y;q.push(x + y);}printf("%d\n", ans);return 0;
}贪心很显然
主要是复习优先队列
默认从大到小
要从小到大可以负数或者greater<int>
明天刚国王游戏
比较难的贪心
还要写高精度（我很排斥，还是要面对吧）
9.30 周三
今天程序设计课展示了一波，非常快的做完所有题目，被称为大佬
有点飘哈哈
其实在竞赛方面我还是巨菜的
淡定淡定
谦虚低调
继续努力