A. Desorting
题目大意
给出一个长度为 \(n\) 的数组 \(a\) ,可以执行这个操作任意次。
选择一下标 \(i\), 使得 \(a_{1...i}\) 加上 \(1\) ，\(a_{i+1...n}\) 减少 \(1\)。
问最少几次操作使得数组 \(a\) 无序。
思路
首先如果 \(a\) 原本就无序的话是输出 \(0\)。
如果有序我们不妨进行如下操作：
找出最小的相邻两数差，对于以上说的操作我们可以画图
我们找到最小极差，将蓝色的方格当成 \(i\) 进行 \(\frac{x}{2}\) 次操作使得两个有颜色的方格持平，然后+1使得红色高度大于蓝色高度。
所以答案就是 \(\frac{\min\{a_i-a_{i-1}\}}{2}+1\)
int ans = 1e9 + 7;
for (int i = 1; i < n; i++)
ans = min(ans, a[i] - a[i - 1]);
cout << ans / 2 + 1 << endl;
B - Fibonaccharsis
题目大意
给两个正整数 \(n,k\) 问有多少个斐波那契数列的第 \(k\) 项为 \(n\).
思路
斐波那契额最小是 \(0,1,1,2,3...\) 到第 \(28\) 项就超过 \(2e5\) 了，所以超过 \(28\) 直接输出 \(0\)
设第一位 \(x\)，第二位 \(y\) 接下来为
\[x+y,x+2y,2x+3y,3x+5y... \]我们可以直接预处理出正常的斐波那契额数列 \(\text{F}\)
带进去可得第 \(k\) 项 \(n=F[k-2]x+F[k-1]y\)
枚举其中的一个值 \(x\), 如果 \((n-F[k-2]x)\bmod F[k-1]=0\) 那么答案加一
int ans = 0;
f[1] = f[2] = 1;
for (int i = 3; i <= 30; i++)
f[i] = f[i - 1] + f[i - 2];
for (int i = 0; i * (f[k - 2] + f[k - 1]) <= n; i++)
{
int temp = n;
temp -= i * f[k - 2];
if (temp % f[k - 1] == 0)
ans++;
}
C-Ntarsis' Set
题目大意
已知一个集合 \(S={1,2,3...,10^{1000}}\) ，同时有一个长度为 \(n\) 的序列 \(a\) ，表示我们每次都要删除 \(S\) 中的第 \(a_i\) 项，求经过 \(k\) 次操作后最小的数字
思路
我们发现只有当一个数比它小的数都删完后它有成为答案的机会，所以我们 \(check\) 掉比它小的数，然后如果比它小的值都去掉了，那么就记录答案，否则就将答案范围放大
bool check(LL k, LL mid)
{
while (k--)
mid -= lower_bound(a + 1, a + n + 1, mid) - a - 1;
return mid > 1;
}
while (l + 1 < r)
{
LL mid = (l + r) >> 1;
if (check(k, mid))
ans = mid, r = mid;
else
l = mid;
}