Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)

A题 Prison Break

原题链接

题意:

给定一个\(n \times m\)的方格阵, 要求打通最少的墙, 使得从每个格子出发都可以走到边缘。

思路:

要求从任意一个格子出发都可以到达边缘, 则每个格子开一个墙即可。

#include 
#include 
#include 
#include 

using namespace std;

void solve()
{
    int n, m;
    cin >> n >> m;
    //long long sum = 0;
    cout << n * m << endl;
    return;
}


int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();

    return 0;
}

B题 Restore Modulo

原题链接

题意:

给定数组\(a\), 求\(m , c\), 满足 \(a_{i + 1} = (a_{i} + c ) mod m\), (\(m > c\))

思路:

重点在\(0 \leqslant c < m\):
根据这一点有: \(a_{i} + c \leqslant 2 \times m\), 且当\(a_{i + 1} > a_{i}\)时, 一定有\(a_{i} + c\)没有溢出\(m\), 所以\(c = a_{i + 1} - a_{i}\)

当\(a_{i + 1} < a_{i}\)时, 一定是加\(c\)后溢出\(m\), 此时\(m = a_{i + 1} - c + a_{i}\)

判断是都对任意的\(i\)满足\(m, c\)

注意特别情况判断

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int a[N];

void solve()
{
    int n;
    cin >> n;
    int c, m = -1;
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);
    

    int flag = 1;
    int k = a[2] - a[1];
    for (int i = 2; i < n; i ++ ){
       if (a[i + 1] - a[i] != k){
           flag = 0;
           break;
       } 
    }

    if (flag){
        puts("0");
        return;
    }

    c = -1;
    m = -1;

    for (int i = 1; i < n; i ++ ){
        if (a[i + 1] == a[i]){
            puts("-1");
            return;
        }
        if (a[i + 1] > a[i]){
            int t = a[i + 1] - a[i];

            if (c == -1 || c == t)
                c = t;
            else{
                puts("-1");
                return;
            }

        }else{
            int t = a[i] - a[i + 1];

            if (m == -1 || m == t)
                m = t;
            else{
                puts("-1");
                return;
            }
        }
    }

    m = -1;

    for (int i = 1; i < n; i ++ ){
        if (a[i] > a[i + 1]){
            int t = a[i] - a[i + 1];

            if (m == -1 || m == t + c)
                m = t + c;
            else{
                puts("-1");
                return;
            }
        }
    }

    if (m == -1){
        puts("0");
        return;
    }


    for (int i = 1; i <= n; i ++ )
        if (a[i] >= m){
            puts("-1");
            return;
        }

    cout << m << ' ' << c << endl;
    return;
}


int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();

    return 0;
}