Codeforces Round #713 (Div. 3)

倒霉掉分场, 刚出两个题, 电脑不干了...好在前两题手速快,没有掉太多分.

A题 Spy Detected!

原题链接

题意

给一个序列, 序列中有一个数与其他数不同, 找到这个数的下标

思路

先在前三个数里面找到序列中相同的数是哪个, 然后遍历一遍就行了.

代码

#include 
#include 
#include 
#include 
#include 

using namespace std;

int a[110];

void solve()
{
    int n;
    int ans;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
    int t;
    if (a[1] == a[2])
        t = a[1];
    else{
        if (a[1] == a[3])
            ans = 2;
        else if (a[2] == a[3])
            ans = 1;
        cout << ans << endl;
        return;
    }
    for (int i = 1; i <= n; i ++ ){
        if (a[i] != t)
            ans = i;
    }
    cout << ans << endl;
    return;
}

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

B题 Almost Rectangle

原题链接

题意

给定一个方阵, 再给定两个点, 要求再寻找两个点, 是这四个点构成一个矩形.

思路

直接找就行了, 注意当已知的两个点为同行或同列时, 注意判断是否出界

代码

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 410;

char s[N][N];
int n;

void print()
{
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ )
            cout << s[i][j];
        cout << endl;
    }
}

void solve()
{
    int a = 0;
    int b = 0;
    int c = 0;
    int d = 0;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> s[i] + 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ){
            if (a == 0 && s[i][j] == '*'){
                a = i;
                b = j;
            }else if (c == 0 && s[i][j] == '*'){
                c = i;
                d = j;
            }
        }
    if (a == c){
        if (a > 1){
            s[a - 1][b] = '*';
            s[c - 1][d] = '*';
        }else{
            s[a + 1][b] = '*';
            s[c + 1][d] = '*';
        }
        print();
        return;
    }
    if (b == d){
        if (b > 1){
            s[a][b - 1] = '*';
            s[c][d - 1] = '*';
        }else{
            s[a][b + 1] = '*';
            s[c][d + 1] = '*';
        }
        print();
        return;
    }
    s[a][d] = '*';
    s[c][b] = '*';
    print();
    return;
}

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

C题 A-B Palindrome

题意

给定一个包含\(01?\)的序列, 要求将\(?\)换为\(1或0\),使得该序列为回文序列, 且一定有\(a\)个0, \(b\)个1.

思路

遍历两边:
第一遍:判断是否有已经不合法的位置(\(1->0\)), 同时将可以确定的\(?\)确定.
第二遍:将剩余位置的\(?\)转化为\(0或1\), 同时判断是否出现不合法情况

代码

#include 
#include 
#include 
#include 

using namespace std;

const int N = 2e5 + 10;

char s[N];
int a, b;
int n;
int mid;

void check()
{
    
    for (int i = 1; i < mid; i ++ ){
        if (s[i] == s[n - i + 1]){
            if (s[i] == '1')
                b -= 2;
            if (s[i] == '0')
                a -= 2;
        }else{
            if (s[i] != '?' && s[n - i + 1] != '?'){
                puts("-1");
                return;
            }else{
                if (s[i] == '?'){
                    s[i] = s[n - i + 1];
                    if (s[i] == '1')
                        b -= 2;
                    else if (s[i] == '0')
                        a -= 2;
                }
                if (s[n - i + 1] == '?'){
                    s[n - i + 1] = s[i];
                    if (s[i] == '1')
                        b -= 2;
                    else if (s[i] == '0')
                        a -= 2;
                }
            }
        }
    }
    for (int i = 1; i < mid; i ++ ){
        if (s[i] == s[n - i + 1]){
            if (s[i] == '?'){
                if (a && a != 1){
                    s[i] = s[n - i + 1] = '0';
                    a -= 2;
                }else if (b && b != 1){
                    s[i] = s[n - i + 1] = '1';
                    b -= 2;
                }
            }
        }
    }
    if (n % 2){
        if (s[mid] == '1'){
            b--;
        }
        if (s[mid] == '0')
            a--;
        if (s[mid] == '?'){
            if (a){
                s[mid] = '0';
                a--;
            }
            if (b){
                s[mid] = '1';
                b--;
            }
        }
    }
    int flag = 1;
    for (int i = 1; i <= n; i ++ )
        if (s[i] == '?'){
            flag = 0;
            break;
        }
    if (a != 0 || b != 0 || flag == 0)
        puts("-1");
    else{
        cout << s + 1 << endl;
    }
}

void solve()
{
    cin >> a >> b;
    scanf("%s", s + 1);
    n = a + b;
    if (n % 2)
        mid = (1 + n) / 2;
    else
        mid = (1 + n) / 2 + 1;
    /*
    for (int i = 1; i < mid; i ++ ){
        if (s[i] == s[n - i + 1]){
            if (s[i] == '1')
                b -= 2;
            if (s[i] == '0')
                a -= 2;
        }else{
            if (s[i] != '?' && s[n - i + 1] != '?'){
                puts("-1");
                return;
            }else{
                if (s[i] == '?'){
                    s[i] = s[n - i + 1];
                    if (s[i] == '1')
                        b -= 2;
                    else if (s[i] == '0')
                        a -= 2;
                }
                if (s[n - i + 1] == '?'){
                    s[n - i + 1] = s[i];
                    if (s[i] == '1')
                        b -= 2;
                    else if (s[i] == '0')
                        a -= 2;
                }
            }
        }
    }
    if (n % 2)
        if (s[mid] != '?'){
            if (s[mid] == '0')
                a--;
            else
                b--;
        }
    */
    check();
    //cout << s + 1 << "-->" << a << ' ' << b << endl;
    return;
}

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

D题 Corrupted Array

原题链接

题意

给定一个长度为\(n + 2\)的序列, 在序列中找到一个数\(k\)为剩余\(n + 1\)个数中的\(n\)个数之和.

思路

贪心, 首先对序列排序, 可以确定\(k\)一定为序列最大值或次大值:
证明:

若\(k\)不是最大值或次大值, 那么剩余的\(n + 1\)个数, 无论怎么选\(n\)个数, 一定会产生和大于\(k\).即\(k\)必须为最大或次大值.
\(k\)为次大值, 则\(x\)必须为最大值, 理由同上, 这时只需判断剩余数字之和是否为\(k\)
\(k\)为最大值, 先求出剩余\(n + 1\)个数字之和, 逐个判断\(x\),是否存在\(x\).

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N = 2e5 + 10;

int b[N];
int a[N];

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n + 2; i ++ )
        scanf("%d", &b[i]);
    sort(b + 1, b + n + 3);
    long long k = b[n + 2];
    long long y = b[n + 1];
    long long sum = 0;
    for (int i = 1; i <= n + 1; i ++ )
        sum += b[i];
    //cout << sum << ' ' << k << ' ' << y << endl;
    //选次大值:
    if (sum - y == y){
        for (int i = 1; i <= n; i ++ )
            printf("%d ", b[i]);
        puts("");
        return;
    }

    //选最大值:
    int del = 0;
    for (int i = 1; i <= n + 1; i ++ )
        if (sum - b[i] == k){
            del = i;
            break;
        }
    if (del != 0){
        for (int i = 1; i <= n + 1; i ++ )
            if (i != del)
                printf("%d ", b[i]);
        puts("");
        return;
    }
    puts("-1");
    return;
}   

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

codeforces练习赛

Codeforces Round #713 (Div. 3)

Codeforces Round #713 (Div. 3)

A题 Spy Detected!

题意

思路

代码

B题 Almost Rectangle

题意

思路

代码

C题 A-B Palindrome

题意

思路

代码

D题 Corrupted Array

题意

思路

相关

标签