10.8 模拟赛题解

0x01

首先，不得不说，这次模拟赛考察了基础算法，尤其是DFS，我觉得我还有很多不足，尤其是在暴力拿分的部分。

然后由于评测机的问题一开始强行爆零，后来换了台电脑测拿了100pts，至少不是倒一......

0x02

A. stone

题目大意：给定一个单调不降序列，其最大值为 \(k\) , 每次可以使序列中的最小数字变成次小数字，求出使整个序列全部变为 \(k\) 的方案数。

样例：

input : 
4 
1 1 2 3

output :
5

这道题做法很多，看到求方案数，其实第一反应就应该使用dp来做，实际在考场上写了个假的贪心，死的很惨.

考虑动态规划做法。

设计状态：\(dp[i]\) 表示 第 \(i\) 个数需要调整的次数。

边界条件：\(dp[n] = 0\); 目标 \(dp[i]\).

转移方程：if(a[i+1] > a[i]) dp[i] = dp[i+1] + 1; if(a[i+1] == a[i]) dp[i] = dp[i+1];

通过这个转移方程，我们注意到更新dp数组要从 \(n-1\) 到 1。

为什么要逆序呢？因为很容易发现这个dp的依赖关系永远是较大的元素转移给较小的元素。

\(Code:\)

#include <bits/stdc++.h>

using namespace std;

int n, ans, a[MAXN], dp[MAXN];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    dp[n] = 0;
    for(int i = n-1; i >= 1; i--) {
        if(a[i+1] > a[i]) dp[i] = dp[i+1] + 1;
        if(a[i+1] == a[i]) dp[i] = dp[i+1];
    }

    for(int i = 1; i <= n; i++) ans += dp[i];

    printf("%d", &ans);
    return 0;
}

时间复杂度 \(O(N)\) , 可以通过本题。

B. matrix

题目大意：求一个数字\(k\)在一个蛇形矩阵中具体的位置。已知 \(0\le k\le10^{18}\)

蛇形矩阵是甚么东西呢？

1,  2,  9,  10, ...
4,  3,  8,  11, ...
5,  6,  7,  12, ...
16, 15, 14, 13, ...

大概长这样。

我们把这个蛇形矩阵变得更蛇形一点.....记为蛇形矩阵(2).

         1, 
      4, 3, 2,         
    5, 6, 7, 8, 9, 
16, 15, 14, 13, 12, 11 
....

我们观察到一个规律

数字范围   含有数据数
   1     |     1
  2~4    |     3
  5~9    |     5
 10~16   |     7
 17~25   |     9

规律十分明显，等差数列。

我们对这个等差数列求个前缀和，有 \(pre_i = i ^ 2\).

于是我们想到，第 \(i\) 行的数字取值范围为 \([(i-1)^2+1, i^2]\)

对于一个输入数据 \(k\)，我们可以先对它开根号，记录以下两个数据。

a = floor((double)sqrt(k));
b = ceil((double)sqrt(k));

知道 \(b\) 相当于 知道了在图(2)中的行数。

这个时候我们又发现，需要对 \(a^2+1\) 的奇偶性分类讨论：

1. 如果 \(a^2+1\) 是奇数，那么在蛇形矩阵(2)中的这一行是从左到右递增的；
2. 如果是偶数，那么就是递减的。

为什么会用到这个性质呢？因为要计算 \(k\) 和 图(2) 中每一行起点的差值来计算他在原图中到底是在行上还是在列上。

请仔细理解这句话。之后，代码就呼之欲出了。

\(Code:\)

/*L7 xuzhengyang

思路：根据打表发现一个规律
先算sqrt(k), 然后向下取整，记为a，向上取整，记为b, 则s[a]+1 <= k <= s[b]
注意分奇偶讨论

*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int t;
ll k;

int main() {
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);

    read(t);
    while(t--) {
        read(k);

        ll a = floor((double)sqrt(k));
        ll b = ceil((double)sqrt(k));
        bool flag = 0;

        if(a == b) a--;

        if(b & 1) {
            if(k - a * a <= b) {
                printf("%lld %lld\n", b, k - a * a);
                continue;
            } 
            if(k - b * b >= -b){
                printf("%lld %lld\n", b * b - k + 1, b);
                continue;
            }
        } else {
            if(k - b * b - 1 >= -b) {
                printf("%lld %lld\n", b, b * b - k + 1);
                continue;
            }
            if(k - a * a - 1 <= b) {
                printf("%lld %lld\n", k - a * a, b);
                continue;
            }
        }
        a = 0, b = 0;
    }
    return 0;
}

C. boxing

不会，先隔这。