题目链接https://codeforces.com/contest/1512

这一场打的中规中矩吧，毕竟人均五题。

A题

题意：给你一个数组，数组中只有两种数值，找出只出现一次的数值的下标。

思路：显然只有整个字符串全是'a'才无解，否则对字符串进行扫描，对称位置不是'a'的地方放'a'即可。
代码如下

int n;
int a[N];
map<int, int> mp;
 
int main()
{
	IOS;
	int T;
	cin >> T;
	while(T --)
	{
		mp.clear();
		cin >> n;
		for(int i = 1 ; i <= n ; i ++)
		{
			cin >> a[i];
			mp[a[i]] ++;
		}
		int num;
		for(auto x : mp)
			if(x.y == 1)
			{
				num = x.x;
				break;
			}
		for(int i = 1 ; i <= n ; i ++)
			if(num == a[i])
			{
				cout << i << endl;
				break;
			}
	}
 
	return 0;
}

B题

这题我开始看错题了，以为要构造的是正方形，wa了两发，我真sb。
题意：给你一个\(n * n\)的图， 其中有两个''符号，让你构造一个边与图的边平行的矩形，''位于该矩形的四个顶点上。

思路：显然只需要根据给出的两个点的位置，分类判断一下。
代码如下

int n;
char g[N][N];
int main()
{
	IOS;
	int T;
	cin >> T;
	while(T --)
	{
		cin >> n;
		for(int i = 1 ; i <= n ; i ++)
			cin >> g[i] + 1;
		int a, b, c, d;
		int cnt = 0;
		for(int i = 1 ; i <= n ; i ++)
			for(int j = 1 ; j <= n ; j ++)
			{
				if(g[i][j] == '*' && !cnt)
					a = i, b = j, cnt ++;
				else if(g[i][j] == '*') c = i, d = j;
			}
		if(a == c || b == d)
		{
			int sub = 1;
			if(a == c)
			{
				if(a + sub <= n)
					g[a + sub][b] = g[c + sub][d] = '*';
				else
					g[a - sub][b] = g[c - sub][d] = '*';
			}
			else	// b == d
			{
				if(b + sub <= n)
					g[a][b + sub] = g[c][d + sub] = '*';
				else
					g[a][b - sub] = g[c][d - sub] = '*';
			}
		}
		else
		{
			g[a][d] = '*';
			g[c][b] = '*';
		}
	
		for(int i = 1 ; i <= n ; i ++)
		{
			for(int j = 1 ; j <= n ; j ++)
				cout << g[i][j];
			cout << endl;			
		}
	}
 
	return 0;
}

C题

题意：给你一个01字符串，其中包含'?'，'?'可以转化为0或者1，现在问你能不能将所给字符串转换成恰好含有a个0和b个1的字符串

思路：首先直接贪心地把确定位置给确定了，比如当前位置是'1'，那么对称位置一定得是'1'，如果是'?'直接变'1'，否则无解。
然后看能不能将剩下的'?'转换成想要的0和1即可，具体看如下代码。
代码如下

int a, b;
char s[N];
 
int main()
{
	IOS;
	int T;
	cin >> T;
	while(T --)
	{
		cin >> a >> b;
		cin >> s + 1;
		int len = strlen(s + 1);
		int cnt = 0;
		bool flag = false;	//是否是奇数位中心是问号 
		bool res = true;
		for(int i = 1 ; i <= (a + b + 1) / 2 ; i ++)
		{
			int r = len - i + 1;
			if(s[i] != '?')
			{
				if(s[r] != '?')
				{
					if(s[i] != s[r])
					{
						res = false;
						break;						
					}
				}
				else
					s[r] = s[i];
			}
			else if(s[r] != '?')
			{
				if(s[i] != '?')
				{
					if(s[i] != s[r])
					{
						res = false;
						break;						
					}
				}
				else
					s[i] = s[r];				
			}
			else
			{
				if(((a + b) & 1) && i == r)	cnt ++;
				else cnt += 2;
			}
		}
		int cnt0 = 0, cnt1 = 0;
		for(int i = 1 ; i <= a + b ; i ++)
		{
			if(s[i] == '0') cnt0 ++;
			else if(s[i] == '1') cnt1 ++;			
		}
		if(cnt0 > a || cnt1 > b) res = false;
		if(res)
		{
			cnt0 = a - cnt0;
			cnt1 = b - cnt1;
			for(int i = 1 ; i <= (a + b + 1) / 2 ; i ++)
			{
				if(s[i] == '?')
				{
					int r = len - i + 1;
					if(i == r)
					{
						if(cnt0)	s[i] = '0', cnt0 --;
						else if(cnt1) s[i] = '1', cnt1 --;
					}
					else if(cnt0 > 1)
					{
						s[i] = s[r] = '0';
						cnt0 -= 2;
					}
					else if(cnt1 > 1)
					{
						s[i] = s[r] = '1';
						cnt1 -= 2;
					}				
				}
			}			
		}
		if(cnt0 || cnt1) res = false;
		if(!res) cout << -1 << endl;
		else cout << s + 1 << endl;
	}
 
	return 0;
}

D题

题意：给你一个长度为\(n + 2\)的数组，现在让你从中选择\(n\)个数字，使得剩下两个的其中一个是所选择的所有数字之和。

思路：显然不能选择最大的一个数字，直接排序，然后\(O(n)\)枚举。
代码如下

int n;
ll a[N];
ll s[N];
 
int main()
{
	IOS;
	int T;
	cin >> T;
	while(T --)
	{
		cin >> n;
		for(int i = 1 ; i <= n + 2 ; i ++)
			cin >> a[i];
		sort(a + 1, a + n + 3);
		for(int i = 1 ; i <= n + 1 ; i ++)
			s[i] = a[i] + s[i - 1];
		
		int d = 0;
		for(int i = 1 ; i <= n + 1 ; i ++)
		{
			if(s[n + 1] - a[i] == a[i] || s[n + 1] - a[i] == a[n + 2])
			{
				d = i;
				break;
			}			
		}
 
		
		if(!d) cout << -1 << endl;
		else
		{
			for(int i = 1 ; i <= n + 1 ; i ++)
			{
				if(i == d) continue;
				cout << a[i] << " ";				
			}
			cout << endl;
		}
	}
 
	return 0;
}

E题

题意：有一个长度为n的排列，现在问你能不能找到这个排列的一个形式A，使得它的\(\sum_{i = l}^rA[i] = s\)。

思路：显然在确定的区间长度下，能凑出来的数有一个最大值和最小值，如果在这个区间内，显然是有解的。
有解情况下的构造方式见代码。
代码如下

int n;
int s[N];
bool st[N];
 
int main()
{
	IOS;
	int T;
	cin >> T;
	while(T --)
	{
		int n, l, r, s;
		cin >> n >> l >> r >> s;
		
		int mind = 0, maxd = 0;
		for(int i = 1 ; i <= r - l + 1 ; i ++)
			mind += i;
		for(int i = n ; i >= n - (r - l) ; i --)
			maxd += i;
		int len = r - l + 1;
		if(s >= mind && s <= maxd)
		{
			int c = (s - mind) / len;
			int left = (s - mind) % len;
			int d = 0;
			for(int i = len ; i >= 1 ; i --)
				if(i + c + left <= n)
				{
					st[i + c + left] = true;
					d = i;
					break;
				}
			for(int i = 1 ; i <= len ; i ++)
			{
				if(i == d) continue;
				st[i + c] = true;
			}
			
			int cnt = 0, now;
			for(now = 1 ; now <= n ; now ++)
			{
				if(cnt + 1 == l) break;
				if(!st[now])
					cout << now << " ", cnt ++;
			}
			
			for(int i = 1 ; i <= n ; i ++)
				if(st[i])
					cout << i << " ";
			
			for(; now <= n ; now ++)
			{
				if(!st[now])
					cout << now << " ";
			}
			cout << endl;
			memset(st, false, sizeof st);
		}
		else cout << -1 << endl;
	}
 
	return 0;
}

F题

这题比赛的时候没写出来，等后面再补。
题意：

思路：
代码如下