Codeforces Round 887 (Div. 2)

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\) 接下来为

我们可以直接预处理出正常的斐波那契额数列 \(\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\) 掉比它小的数，\(mid>1\) 就说明这个数存在(减去比它小的)，然后如果比它小的值都去掉了，那么就记录答案，否则就将答案范围放大

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;
  }