2023牛客暑期多校训练营4

A： Bobo String Construction

题意：构造给你一个字符串s,你需要构造一个长度为n的字符串s1,使得s + s1 + s中s只在首位两端出现。

思路：枚举全为0或者全为1两种情况看哪种符合即可

#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
const int N = 200010;

void solve(){
	int n;
	string s;
	cin >> n >> s;
	string s1,s2;
	while(n --){
		s1 += '1';
		s2 += '0'; 
	}
	string s3 = s1;
	s1 = s + s1 + s;
	int ui = 0;
	for(int i = 0; i < s1.size(); i ++){
		if(s1[i] == s[0]){
			string sw = s1.substr(i,s.size());
			if(sw == s) ui ++;
		}
	}
	if(ui > 2) cout << s2 << '\n';
	else cout << s3 << '\n';
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0;
}

F：Election of the King

题意：n个人投票每次都会把票投给离自己绝对值差最大的人，如果绝对值差一样就投给值更大的人，如果二者得票相同那么值更大的人优先淘汰，直到最后一个人成为国王。

思路：通过观察可以看出排序之后每次删除的都是两边的人，只要确定中间人即可，中间人分开两边用upper_bound会方便一点，要注意边界问题，每次是哪边人数较多那就删去另外一边的顶点即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N = 100010;

void solve(){
	int n;
	cin >> n;
	vector<int> v(n),v1;
	for(int i = 0; i < n; i ++) cin >> v[i];
	v1 = v;
	
	sort(v.begin(),v.end());
	
	int l = 0,r = n - 1;
	while(l < r){
		int tot = r - l + 1;
		
		int sum = v[l] + v[r] >> 1;
		int u = upper_bound(v.begin() + l,v.begin() + r + 1,sum) - (v.begin() + l);
		if(u * 2 >= tot) r --;
		else l ++;
	}
	int ans = find(v1.begin(),v1.end(),v[l]) - v1.begin();
	cout << ans + 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();	
	return 0;
}

L：We are the Lights

题意：存在一个 n * m的灯阵，每次你可以选择关闭或者打开一行（列）求最后多少灯亮着

思路：每盏灯的状况其实是由最后一步的操作来决定的，那只要从后往前推然后记录操作状态即可，即当前行列被操作过之后就不再操作了，然后当操作完一行（列），那么列（行）能够操作的数量--

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1000010;

struct node{
	int x,y,z;
}a[N];
//x表示状态，1表示行操作，0表示列操作，y表示对应操作对象
//z表示开关1开0关 
int r[N],l[N];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m,q;
	cin >> n >> m >> q;
	for(int i = 1; i <= q; i ++){
		string s1,s2;
		int u;
		cin >> s1 >> u >> s2;
		if(s1 == "row"){
			if(s2 == "on"){
				a[i] = {1,u,1};
			}
			else a[i] = {1,u,0};
		}
		else if(s1 == "column"){
			if(s2 == "on"){
				a[i] = {0,u,1};
			}
			else a[i] = {0,u,0};
		}
	}	
	int ans = 0;
	for(int i = q; i >= 1; i --){
		if(a[i].x == 0){
			if(r[a[i].y]) continue;
			
			r[a[i].y] = 1;
			
			if(a[i].z) ans += n;
			m --;//有一行不能改变了 
		}
		else{
			if(l[a[i].y]) continue;
			
			l[a[i].y] = 1;
			
			if(a[i].z) ans += m;
			n --;//有一列的开关无法变动 
		}
	}
	cout << ans; 
	return 0;
}