A. Spy Detected!

传送门

题意

给你一个长度为n的数组让你找到一个与其他位置不相同的数的位置

思路

思路1:直接把值和位置放在结构体里面排序,不同的那个数字要么是第一个要么是最后一个,直接输出即可

思路2:很明显我们只需要看前三个位置的数的关系,如果有一个不一样的,那么直接输出即可,否则我们就从4往后找,找到第一个不同的数,然后直接输出位置

Code1:

#include
using namespace std;

const int N = 105;

struct Node {
    int x,y;
}a[N];

int n,t;

bool cmp(Node a, Node b) {
    return a.x < b.x;
}

int main()
{
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i = 1;i <= n; ++i) {
            scanf("%d",&a[i].x);
            a[i].y = i;
        }
        sort(a+1,a+1+n,cmp);
        if(a[1].x != a[2].x) {
            printf("%d\n",a[1].y);
        }
        else{
            printf("%d\n",a[n].y);
        }
    }


    return 0;
 } 

Code2

#include 
using namespace std;

const int M = 10000005;
int a[M];


int main(){
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, key;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }
        if(a[1] == a[2]) {
            key = a[1];
        }else if(a[1] == a[3]) {
            key = a[1];
        }else {
            key = a[2];
        }

        for(int i = 1; i <= n; i++) {
            if(a[i] != key) {
                printf("%d\n", i);
                break;
            }
        }
    }

    return 0;
}

B. Almost Rectangle

题意

给你一个n\times n 的矩阵,然后给你两个坐标不重复的,然后你需要任意添加两个 使得这四个*成为一个矩形

思路

我们只需要贴着已有的坐标点构造即可

1.如果当两个* 都在同一行,那么我们需要判断行的位置,如果在最后一行,那么我们新增的只有在x-1行,y坐标不变,否则新增的在x+1行

2.如果当两个*都在同一列,那么我们需要判断列的位置,如果在最后一列,那么我们新增的只有在y-1列,x坐标不变,否则新增的在y+1列

3.如果不在同一行或者同一列,那么我们只需要找到对称坐标即可 [x1] [y2]、[x2] [y1]

Code:

#include
using namespace std;

const int N = 405;

char mp[N][N];

int x[3],y[3];

int main()
{
    int n,t;
    cin>>t;
    while(t--){
    cin>>n;
    int cnt = 0;
    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= n; ++j) {
            cin>>mp[i][j];
            if(mp[i][j] == '*') {
                x[++cnt] = i;
                y[cnt] = j; 
            }
        }
    }
    int lx,rx,ly,ry;
    if(y[1] < y[2]) {
        lx = x[1];
        rx = x[2];
        ly = y[1];
        ry = y[2];
    }
    else {
        lx = x[2];
        rx = x[1];
        ly = y[2];
        ry = y[1];
    }   
    if(lx == rx) {
        if(lx > 1)
            mp[lx-1][ly] = mp[rx-1][ry] = '*';
        else
            mp[lx+1][ly] = mp[rx+1][ry] = '*';
    }
    else if(ly == ry) {
        if(ly > 1) 
            mp[lx][ly-1] = mp[rx][ry-1] = '*';
        else
            mp[lx][ly+1] = mp[rx][ry+1] = '*';
    }
    else 
        mp[rx][ly] = mp[lx][ry] = '*';
        for(int i = 1;i <= n; ++i) {
            for(int j = 1;j <= n; ++j) {
                putchar(mp[i][j]);
            }
            puts("");
        }
    }
    return 0;
 } 

C. A-B Palindrome

题意

给你一个a、b然后给你一个由0、1、?构成的字符串,?可以变成0或者1(变后不能更改),问你能否构造一个由0、1构成的回文字符串,并且0的数量等于a,1的数量等于b,,如果能构造出来,请输出回文串,否则输出-1

思路

很明显,当有一边为1或者0的时候我们必须要处理,当两边为?的时候我们第一遍不能处理,因为我们不能确定?表示的是0还是1,因为我们需要根据a和b的数量来决定用啥,所以第一遍循环我们先将左右两边不全为?的情况处理,并且统计两边为?的数量,

1.如果a或者b的数量小于0,那么一定不成立

2.如果?的数量不为0,并且a或者b为奇数或者a+b不等于?的数量那么也不成立,

3.否则就是成立的,最后一遍循环将两边为?的字符改为0或者1

Code

#include
#include
#include
using namespace std;
int a,b;

char str[200050];

int main() {
    int t;
    scanf("%d",&t);
    getchar();
    while(t--) {
        scanf("%d%d",&a,&b);
        scanf(" %s",str);
        int l = strlen(str);
        bool is = 1;
        int wenhao = 0;
        for(int i = 0; i < (l >> 1); ++i) {
            if(str[i] == '0') {
                a--;
                if(str[l-i-1] == '0') {
                    a--;
                } else if(str[l-i-1] == '1') {
                    is = false;
                } else if(str[l-i-1] == '?') {
                    a--;
                    str[l-i-1] = '0';
                }
            } else if(str[i] == '1') {
                b--;
                if(str[l-i-1] == '0') {
                    is = false;
                } else if(str[l-i-1] == '1') {
                    b--;
                } else if(str[l-i-1] == '?') {
                    b--;
                    str[l-i-1] = '1';
                }
            } else if(str[i] == '?') {
                if(str[l-i-1] == '0') {
                    a -= 2;
                    str[i] = '0';
                } else if(str[l-i-1] == '1') {
                    b -= 2;
                    str[i] = '1';
                } else if(str[l-i-1] == '?') {
                    wenhao++;
                }
            }
        }
        if(l & 1) {
            if(str[(l >> 1)] == '0') {
                a--;
            } else if(str[(l >> 1)] == '1') {
                b--;
            } else {
                if((a & 1) && a > 0) {
                    a--;
                    str[(l >> 1)] = '0';
                } else if((b & 1) && b > 0) {
                    b--;
                    str[(l >> 1)] = '1';
                } else {
                    is = false;
                }
            }
        }
        if(a < 0 || b < 0)
            is = 0;
        if(wenhao) {
            if((a&1) || (b&1)) 
                is = 0;
            if(a + b != wenhao * 2)
                is = 0;
        }
        if(is) {
            for(int i = 0; i < (l >> 1); ++i) {
                if(str[i] == '?') {
                    if(a) {
                        str[i] = str[l - i - 1] = '0';
                        a-=2;
                    } else {
                        str[i] = str[l - i - 1] = '1';
                        b-=2;
                    }
                }
            }
            puts(str);
        } else 
            printf("-1\n");
    }
    return 0;
}

D. Corrupted Array

题意

给你一个n表示的是a数组的长度,然后输入n+2个数表示的是b数组的数,b数组的数由a数组的元素+a数组元素和+一个x组成,怎么构造这个a数组使得满足这个条件,如果不能满足则输出-1

思路

看到数据很明显我们需要先排序,而且很显然a数组的元素和,必然存在b数组后两个元素中,如果前n个元素之和大于b[n+2]那么直接输出-1,否则此时的前缀和可能为a[n+1]或者a[n+2],我们先看第一种情况

①当 前缀和为a[n+1]的时候,那么直接输出前n个元素

②否则,此时前缀和就可能为a[n+2],x可能是前n+1个元素中的任意一个,我们之前通过预处理,可以知道前n个元素的和,我们只需要通过一层循环,假设前n+1个元素每个元素都可能是x,如果都不能满足条件就输出-1,否者就输出构造的数组

Code

#include
using namespace std;
#define ll long long 
const int N = 200005;

int t,n;
ll a[N];

int main()
{
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        n+=2;
        for(int i = 0;i < n; ++i) {
            scanf("%lld",&a[i]);    
        }
        sort(a,a+n);
        ll pre = 0;
        for(int i = 0;i < n -2; ++i) {
            pre += a[i];
        }

        if(pre > a[n - 1]) {
            puts("-1");
        }
        else {
            if(pre == a[n-2]) {
                for(int i = 0;i < n -2; ++i) {
                    printf("%lld ",a[i]);
                }
                puts("");
            }
            else {
                bool fg = false;
                ll ans = a[n - 1];
                for(int i = 0;i <= n - 2; ++i) {
                    if(pre + a[n-2] - a[i] == ans) {
                        fg = true;
                        a[i] = a[n-2];
                        break;
                    }
                }
                if(fg) {
                    for(int i = 0;i < n - 2; ++i) {
                        printf("%lld ",a[i]);
                    }
                    puts("");
                }
                else {
                    puts("-1");
                }
            }
        }

    }


    return 0;
}

本当の声を響かせてよ