复健

复健！

P.S. 因为前期本来复健了一点，但是现在才想起来我是不是得记录一下，所以前面的就当是回归手感了。

势必改掉乱开 \(LL\) 的坏习惯。

9.22

早上十点半来图书馆复健，做题如下。

T1 P1563 [NOIP 2016 提高组] 玩具谜题

直接异或判断方向，喜提 90 pts，下载到了一个超级大样例，看不出来是啥，但是感觉是在 0 1 反复横跳的问题。

查询题解发现没有判断 0 和 n，改完 A。

贴码

code

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n, m, np = 1;struct node 
{int dir;string name;
} a[N];inline int check(int num) { return (num % n + n) % n; }int main()
{scanf("%d %d", &n, &m);for(int i = 1; i <= n; ++ i) cin >> a[i].dir >> a[i].name;while(m -- ){int ddir, d;scanf("%d %d", &ddir, &d);if(ddir ^ a[np].dir) np = check(np + d);else np = check(np - d);np = !np ? n : np;}cout << a[np].name;return 0;
}

对于 T2 我想做一个违背祖宗的决定，开始猪国杀

祖宗不太允许我违背，今天读题但未动手。咕咕咕

今天结束

9.23

给室友讲了数组相关

9.24

开始时间 23点07分。

今日复健二分。

二分是一种折半的思想，通过每次取半来快速逼近目标值。

取中间值 \(mid\) 然后用 \(mid\) 进行验证，如果过大，则缩小有边界，反之，缩小左边界。

T1 P1024 [NOIP 2001 提高组] 一元三次方程求解

本题是对于小数的二分，对于含小数的二分通常会设置一个 \(eps\) 来确定最小二分限度，每次的二分缩小边界也可以直接写为 \(mid\) 的赋值。

code

#include <bits/stdc++.h>
using namespace std;const double eps = 1e-5;double a, b, c, d;inline double f(double n) { return a * n * n * n + b * n * n + c * n + d; }int main()
{cin >> a >> b >> c >> d;for(double i = -100; i < 100; i += 1){if(!f(i)) printf("%.2lf ", i);else if(f(i) * f(i + 1) < 0){double l = i, r = i + 1;while(r - l > eps){double mid = (l + r) / 2;if(f(mid) * f(i) < 0) r = mid;else l = mid;}printf("%.2lf ", l);}}return 0;
}

T2 P2678 [NOIP 2015 提高组] 跳石头

分析可知，本题求解最小值的最大值，同时可以知道，我们可以通过模拟来快速查验每一个可能的距离值，因此考虑二分。

题目中数据范围为 \(int\) 不需要开 \(ll\) 。

对于本题的 \(mid\) 如果不符合则说明跳跃距离仍然过大可以缩小，所以范围开到 \(r = mid - 1\) （此处边界在过程中验证了不可），反之则 \(l = mid\)。

code

#include <bits/stdc++.h>
using namespace std;const int N = 50010;int n, m, len;int a[N];inline bool check(int lm)
{int cnt = 0, pos = 0;for(int i = 1; i <= n; ++ i){if(a[i] - pos < lm) ++ cnt;else pos = a[i];}return cnt > m;
}int main()
{cin >> len >> n >> m;for(int i = 1; i <= n; ++ i) cin >> a[i];a[ ++ n] = len;int l = 0, r = len;while(l < r){int mid = (l + r + 1) >> 1;if(check(mid)) r = mid - 1;else l = mid;}cout << l;return 0;
}

今日到此为止，截止时间 00点30分。