Codeforces Round #713 (Div. 3)

目录

• A. Spy Detected!
  • 题意
  • 思路
  • Code1:
  • Code2
• B. Almost Rectangle
  • 题意
  • 思路
  • Code:
• C. A-B Palindrome
  • 题意
  • 思路
  • Code
• D. Corrupted Array
  • 题意
  • 思路
  • Code

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;
	int cnt = 0;
	for(int i = 1;i 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  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