Codeforces Round #877 (Div. 2) A-E

Posted on by hackdl

A

代码

#include 
using namespace std;
using ll = long long;

bool solve() {
    int n;
    cin >> n;
    int mx = -2e9, mi = 2e9;
    for (int i = 1;i > x;
        mi = min(x, mi);
        mx = max(x, mx);
    }
    if (mi > t;
    while (t--) {
        if (!solve()) cout

B

代码

#include 
using namespace std;
using ll = long long;

bool solve() {
    int n;
    cin >> n;
    int pos[3];
    for (int i = 1;i > x;
        if (x == 1) pos[0] = i;
        else if (x == 2) pos[1] = i;
        else if (x == n) pos[2] = i;
    }
    if (pos[2]  pos[1] && pos[2] > pos[0]) cout > t;
    while (t--) {
        if (!solve()) cout

C

题目

构造一个 (n times m) 的矩阵，矩阵中的元素是 (1 sim n times m) 的数字，每个数字只能出现一次，要求相邻元素差的绝对值不是个素数。

题解

知识点：构造。

方法一

按 (m) 奇偶性分类：

  1. (m) 是偶数，可构造形如：

    [begin{array}{l}
    &1 &2 &3 &4
    &5 &6 &7 &8
    &9 &10 &11 &12
    &13 &14 &15 &16
    end{array}
    ]

    可以保证左右的差的绝对值为 (1) ，上下的差的绝对值是 (m) 。

  2. (m) 是奇数，可构造形如：

    [begin{array}{l}
    &1 &2 &3 &4 &5
    &7 &8 &9 &10 &6
    &13 &14 &15 &11 &12
    &19 &20 &16 &17 &18
    end{array}
    ]

    可以保证左右的差的绝对值为 (1) ，上下的差的绝对值是 (m+1) 。

时间复杂度 (O(nm))

空间复杂度 (O(1))

方法二

可构造形如：

[begin{array}{l}
&1 &2 &3 &4
&9 &10 &11 &12
&17 &18 &19 &20
&5 &6 &7 &8
&13 &14 &15 &16
end{array}
]

可以保证左右的差的绝对值为 (1) ，上下的差的绝对值是 (2m) 或 (left( 2 leftlfloor dfrac{n-1}{2} rightrfloor – 1 right) m) 。

特别地，当 (n = 4) 且 (m) 是素数时无法满足，因此考虑 (n=4) 时特判，构造形如：

[begin{array}{l}
&1 &5 &9 &13 &17
&2 &6 &10 &14 &18
&3 &7 &11 &15 &19
&4 &8 &12 &16 &20
end{array}
]

时间复杂度 (O(nm))

空间复杂度 (O(1))

代码

方法一

#include 
using namespace std;
using ll = long long;

bool solve() {
    int n, m;
    cin >> n >> m;
    if (m & 1) {
        for (int i = 1;i > t;
    while (t--) {
        if (!solve()) cout

方法二

#include 
using namespace std;
using ll = long long;

bool solve() {
    int n, m;
    cin >> n >> m;
    if (n == 4) {
        for (int i = 1;i > t;
    while (t--) {
        if (!solve()) cout

D

题目

给定一个只包含 ( 和 ) 两种字符的字符串 (s) 。

现在要求从 (s_1) 出发，最终到达 (s_n) ，每次可以左右移动一个位置，并依次写下到达的位置的字符。

问通过 (s) ，最后能否写下一个合法括号序列。

题解

知识点：STL，贪心。

首先，若 (n) 是奇数无解。

题目其实要求我们，对于使得 (s) 不是合法括号序列的位置，需要找到其他位置修正它们。那么，我们可以得到朴素的合法性结论：

  1. 最后一个让 (s) 不是合法括号序列的 ( ，其右方一定要存在 )) 。
  2. 第一个让 (s) 不是合法括号序列的 ) ，其左方一定要存在 (( 。

到这里，其实已经可以通过将 (, ) 转换为 (1,-1) ，然后用线段树二分找到第一个前缀和小于 (0) 的位置（最左侧的不合法 ) ）和最后一个后缀和大于 (0) 的位置（最右侧的不合法 ( ），配合 set 保存 ((, )) 的位置判断是否存在即可。

但这样有点麻烦，我们可以进一步讨论使得 (s) 不是合法括号序列的位置特征和双括号的关系。

容易证明，对于最后一个不合法的 ) ，要么在一组 )) 内，要么在 (s_1) ；最后一个不合法的 ( ，要么在一组 (( 内，要么在 (s_n) 。 因此，这道题本质就是判断：

  1. 对于最后一个 (( ，其右方是否存在一个 )) 。
  2. 对于第一个 )) ，其左方是否存在一个 (( 。

特别地，对于 (s_1) 为 ) 或 (s_n) 为 ( ，也要认为是 )) 或 (( 。

到这里，其实用两个 set 分别维护 (( 和 )) 的位置，可以直接写了：

  1. 若 (( 和 )) 都不存在，那么有解。
  2. 若情况1或2不满足任意一个，那么无解。
  3. 否则有解。

不过，接下来官方题解的做法更加简洁。

考虑用 set 记录所有位置 (i) ，满足：

  1. 若 (i) 是奇数，满足 (s_i) 是 ) 。
  2. 若 (i) 是偶数，满足 (s_i) 是 ( 。

可以看到，第一个满足情况1的位置，只可能在 (s_1) 或第一个 )) 的位置；最后一个满足情况2的位置，只可能在 (s_n) 或最后一个 (( 的位置。

因此，我们可以通过类似的判断：

  1. 若没有位置满足，那么有解。
  2. 若第一个记录的位置是奇数或最后一个记录的位置是偶数，那么无解。
  3. 否则有解。

时间复杂度 (O((n+q) log n))

空间复杂度 (O(n))

代码

#include 
using namespace std;
using ll = long long;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    set st;
    for (int i = 1;i > ch;
        if (ch == '(' && !(i & 1) || ch == ')' && (i & 1)) st.insert(i);
    }

    while (q--) {
        int x;
        cin >> x;
        if (auto it = st.find(x);it != st.end()) st.erase(it);
        else st.insert(x);
        if (n & 1) {
            cout

E

题目

给定 (n,m,k) ，再给一个长度为 (n) 的整数数组 (a) 满足 (a_i in [1,k]) 。

求有多少不同的长度为 (m) 的整数数组 (b) ，满足 (b_i in [1,k]) 且 (a) 是 (b) 的子序列。

不同的定义：两个数组任意一个位置数字不同，可看做不同。

题解

知识点：线性dp，排列组合。

先考虑朴素的dp。

设 (f_{i,j}) 表示考虑了 (b) 前 (i) 个数字，且作为 (b) 的子序列的 (a) 的前缀的最长长度为 (j) ，有转移方程：

[f_{i,j} = begin{cases}
f_{i-1,j-1} + (k-1)f_{i-1,j} &,j

显然dp是会超时的，但是我们从中可以发现，整个过程和 (a) 一点关系都没。

因此，我们就假设 (a_i = 1) ，显然求不满足的比较容易。 (b) 共有 (k^m) 种，不满足的情况为 ( 个 (1) 且其他都不为 (1) ，因此不满足的情况有 $displaystyle $ 种，所以最终答案为：

[ k^m -sum_{i=0}^{n-1} binom{m}{i}(k-1)^{m-i}
]

其中组合数是 (m) 是 (10^9) 的，因此不可以用公式法预处理阶乘及其逆元，考虑用乘法公式递推：

[binom{m}{i} = frac{m-i+1}{i} binom{m}{i-1}
]

时间复杂度 (O(n log m))

空间复杂度 (O(n))

代码

#include 
using namespace std;
using ll = long long;

const int P = 1e9 + 7;
namespace Number_Theory {
    int qpow(int a, ll k) {
        int ans = 1;
        while (k) {
            if (k & 1) ans = 1LL * ans * a % P;
            k >>= 1;
            a = 1LL * a * a % P;
        }
        return ans;
    }
}
namespace CNM {
    using namespace Number_Theory;
    const int N = 2e5 + 7;
    int n, m, cn[N];
    void init(int _n, int _m) {
        n = _n;
        m = _m;
        cn[0] = 1;
        for (int i = 1;i > n >> m >> k;
    for (int i = 1, x;i > x;
    CNM::init(m, n);
    int ans = qpow(k, m);
    for (int i = 0;i > t;
    while (t--) {
        if (!solve()) cout

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: DHCP实验（GNS3 && wireshark）

DHCP 实验目标 1.认识DHCP工作过程 2.抓包分析DHCP Discover，Offer，Request，ACK，Release五种DHCP报文。 3.实现DHCP续约过程 实验任务 1.使用一个客户端和一个DHCP服务器，通过客户端申请IP地址的过程…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: