Contestant. Rank 900. Rating +46.

A. Ian Visits Mary

题意

给定一个点 \((a, b)\)，最多另找一个点作为支点，满足原点到该点的连线不经过其他点，或者原点到支点、支点到该点的连线都不经过其他点。

输出该点，或者支点和该点。

思路

（怎么解释得这么抽象）

\((0, 0) \rightarrow (a - 1, 1) \rightarrow (a, b)\)

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int a, b;
    cin >> a >> b;
    cout << 2 << '\n';
    cout << a - 1 << ' ' << 1 << '\n';
    cout << a << ' ' << b << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

抽象

B. Grid Reconstruction

题意

给定一个 \(2 \times n\) 的矩阵，将 \([1, 2n]\) 内的数字填入矩阵。

规定可以向下或向右移动，记从原点运动到 \((2, n)\) 经过的所有方格的数字为一个序列 \(a\)，序列 \(a\) 的贡献为 \(a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}\)。

输出一种填写方案，满足该方案下贡献的最小值为所有方案中最大。

思路

首先，我们下去后就上不来了，那么只要尽量导引其走向我们期望的最大值即可。

下面是一种构造方法：

\(\begin{array}{l}2n & 2 & 2n - 2 & 4 & 2n - 4 \ldots \\ 1 & n + 1 & 3 & n + 3 & 5 \ldots\end{array}\)

很显然，既然要更小，那么从 \(2\) 开始就会向下走，可以证明这种情况是最大的。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> ans(2, vector<int>(n));
    for(int i=0;i<n;i+=2) ans[1][i] = i + 1;
    for(int i=1;i<n;i+=2) ans[1][i] = n + i;
    for(int i=0;i<n;i+=2) ans[0][i] = n * 2 - i;
    for(int i=1;i<n;i+=2) ans[0][i] = i + 1;
    for(int i=0;i<2;i++) {
        for (int j = 0; j < n; j++)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

乱猜.jpg

C. Ian and Array Sorting

题意

给定一个序列 \(a\)，对于所有相邻的两个元素，定义一次操作为将这两个元素的值均加上或减去 \(1\)。

输出任意次操作后能否将序列变为不递减。

思路

首先，对于三个元素 \(a_{i - 1}, a_i, a_{i + 1}\)，如果 \(a_i < a_{i - 1}\)，我们就可以将 \(a_i, a_{i + 1}\) 加上 \(a_{i - 1} - a_i\)，这样就可以让前 \(i\) 个数不递减。

同理，如果 \(a_{i + 1} < a_i\)，我们就可以将 \(a_i, a_{i - 1}\) 加上 \(a_{i + 1} - a_i\)，这样就可以让后 \(i\) 个数不递减。

前者可以从前向后遍历，但不能保证最后一个数会不会小于倒数第二个数；后者可以从后向前遍历，但不能保证第一个数是否大于第二个数。

如果我们依次进行上面的操作，那么我们就能保证从前向后遍历存在的问题被解决了，并且我们已经在第一次遍历的时候保证第一个数小于等于第二个数了，所以从后往前遍历存在的问题也被解决了。

因此，依次进行上面的两个操作即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=1;i<n-1;i++){
        if(a[i] < a[i - 1]){
            a[i + 1] -= a[i];
            a[i] -= a[i];
            a[i + 1] += a[i - 1];
            a[i] += a[i - 1];
        }
    }
    for(int i=n-2;i>=1;i--){
        if(a[i + 1] < a[i]){
            a[i - 1] -= a[i];
            a[i] -= a[i];
            a[i - 1] += a[i + 1];
            a[i] += a[i + 1];
        }
    }
    cout << (a[0] <= a[1] ? "YES\n" : "NO\n");
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

说是乱猜和贪心，但其实也挺有道理的（x