2023.6.20 每日一题

原题链接

A: Educational Codeforces Round 115 (Rated for Div. 2) - E

B: Codeforces Round 698 (Div. 2) - C

A. Staircases - 2100

题目大意

给定一个 \(n\times m\) 的网格，每个格子为自由或者锁定，初始时所有格子均为自由的。

定义满足如下条件的路径为楼梯：

• 起点和终点均为自由的

• 路径上的所有点均为自由的

• 满足以下两种结构之一

  1.第二个格子在第一个格子右面，第三个格子在第二个格子下面，第四个格子在第三个格子右面，以此类推……

  2.第二个格子在第一个格子下面，第三个格子在第二个格子右面，第四个格子在第三个格子下面，以此类推……

此外，一个单独的自由格子也被视为一个楼梯。

给定 \(q\) 个询问，每个询问给定整数 \(x、y\)，并将格子 \((x,y)\) 颜色翻转。

输出每次操作后网格中不同楼梯的个数。

解题思路

首先我们肯定知道求不同的楼梯个数是通过一个二维的dp来解决。可以使用额外的一维来存储是否被锁定的数据。

因为我们只能向右向下走，那么很明显dp的转移就是左格子和上格子加一。当然因为单独一个自由格也算是一个楼梯，那么我们需要去重处理一下。

最后递归处理修改后的情况即可。

注：这里并不是dfs，只是递归习惯性命名dfs。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e3 + 10;
const int MOD = 1e9 + 7;

int n, m, q;
LL dp[N][N][2];
LL res;
bool vis[N][N];

void dfs(int x, int y, int op) {
    if (x > n || x < 0 || y > m || y < 0) return;
    res -= dp[x][y][op];
    dp[x][y][op] = 0;
    if (!vis[x][y]) {
        dp[x][y][op] = dp[x - !op][y - op][!op] + 1;
    }
    res += dp[x][y][op];
    dfs(x + op, y + !op, !op);
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j][0] += dp[i - 1][j][1] + 1;
            dp[i][j][1] += dp[i][j - 1][0] + 1;
            res += dp[i][j][0] + dp[i][j][1];
        }
    }
    res -= n * m;
    while (q--) {
        int x, y;
        cin >> x >> y;
        vis[x][y] = !vis[x][y];
        vis[x][y] ? res++ : res--;
        dfs(x, y, 0);
        dfs(x, y, 1);
        cout << res << endl;
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

B.Nezzar and Symmetric Array - 1700

题目大意

定义长度为 \(2 \times n\) 的数组 \(a\) ，\(a\) 中的元素不重复，并且对于任意一个下标\(i(1 \leq i \leq 2 \cdot n, i \ne j)\)，都能找到一个下标 \(j\)，使得 \(a_i = -a_j\) 。

现在给定一个数组 \(d\)，其中 \(d_i = \sum_{j=1}^{2n}|a_i -a_j|\)，问能不能通过数组 \(d\) 构造出数组 \(a\) 。

解题思路

其实就是数学贪心推式子嘛，看了看觉得洛谷的题解很不错，就不再分析了，直接把代码贴在下面。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

LL a[N], s[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= (n << 1); ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + (n << 1) + 1);
    for (int i = 1; i <= n; ++i) {
        if (a[i << 1] != a[(i << 1) - 1]) {
            cout << "NO" << endl;
            return;
        }
    }
    LL cnt = unique(a + 1, a + (n << 1) + 1) - (a + 1);
    if (cnt != n) {
        cout << "NO" << endl;
        return;
    }
    for (int i = 2; i <= n; ++i) {
        s[i] = s[i - 1] + (a[i] - a[i - 1]) / ((i - 1) << 1);
        if ((a[i] - a[i - 1]) % ((i - 1) << 1) || (a[i] - a[i - 1]) <= 0) {
            cout << "NO" << endl;
            return;
        }
    }
    for (int i = 1; i <= n; ++i) {
        a[1] -= s[i] << 1;
    }
    cout << (a[1] % (n << 1) || a[1] <= 0 ? "NO" : "YES") << endl;
}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}