N. Fixing the Expression

思路

签到题，只改变中间的字符即可

code

void solve(){
	int a,b;
	char o;
	cin >> a >> o >> b;
	if(a>b){
		cout << a << ">" << b << endl;
	}
	else if(a<b){
		cout << a << "<" << b << endl;
	}
	else cout << a << "=" << b << endl;
	return ;
}

J. Waiting for…

思路

签到题，如果读入的是P字符，将候车人数累加
如果读入为B字符，分2种情况：

• 候车的人都能上车并且剩余的空座位大于等于一，输出YES
• 反之，将候车人数减去空座位的数量，输出NO

code

int a=0;
void solve(){
	char o;
	int n;
	cin >> o >> n;
	if(o=='P') a+=n;
	else{
		int sum=n-a;
		if(sum>=1){
			a=0;
			cout << "YES" << endl;
		}
		else{
			a-=n;
			cout << "NO" << endl;
		}
	}
	return ;
}

C. DIY

思路

将成对的数进行排序，找出其中第一小的数、第二小的数、第一大的数、第二大的数
输出这些数即可

code

void solve(){
	int n;cin >> n;
	vector<int> v;
	map<int,int> m;
	int sum=0;
	for(int i=1;i<=n;++i){
		int x;cin >> x;
		m[x]++;
	} 
	for(auto i : m){
		if(i.se>=2){
			sum+=i.se/2;
			if(i.se & 1){
				for(int j=1;j<=i.se-1;++j) v.push_back(i.fi);
			}
			else{
				for(int j=1;j<=i.se;++j) v.push_back(i.fi);
			}
			
		}
	}
	if(sum<4){
		cout << "NO" << endl;
		return ;
	}
	sort(v.begin(),v.end());
	int len=v.size();
	int a1=v[0],a2=v[2],a3=v[v.size()-1-2],a4=v[v.size()-1];
	cout << "YES" << endl;
	cout << a1 << " " << a2 << " " << a1 << " " << a4 << " " << a3 << " " << a2 << " " << a3 << " " << a4 << endl;
	return ;
}

L. Bridge Renovation

思路

先拼18 18 21 和 21 21 18
最多会剩下1 2 个木板，在让剩下的木板和25拼，最后向上取整

code

void solve(){
	int n;cin >> n;
	int ans=n*2/3;
	int k=n*2%3+n;
	cout << ans+(k+1)/2 << endl; 
	return ;
}

A. Bonus Project

思路

由于每个人都想让自己获利最多，那么排在前面的工程师有最佳选择权
先算出每个工程师最大的工作单位c，接下来判断工程师会不会罢工：

• 累加所有工程师最大的工作单位c，如果比k小，全部输出0
• 反之，倒着遍历数组，最后面的工程师干的工作单位c最多
  当工程师需要干的工作单位等于k时，结束循环

最后正序遍历数组即可

code

const int N=1e6+5;
int a[N],b[N],c[N],ans[N];
void solve(){
	int n,k,sum=0;
	cin >> n >> k;
	for(int i=1;i<=n;++i) cin >> a[i];
	for(int i=1;i<=n;++i) cin >> b[i];
	for(int i=1;i<=n;++i){
		c[i]=a[i]/b[i];
		sum+=c[i];
	}
	if(sum<k){
		for(int i=1;i<=n;++i) cout << 0 << " ";
		return ;
	}
	for(int i=n;i>=1;--i){
		if(k>=c[i]){
			ans[i]=c[i];
			k-=c[i];
		}
		else{
			ans[i]=k;
			break;
		}
	}
	for(int i=1;i<=n;++i) cout << ans[i] << " ";
	return ;
}

G. Guess One Character

思路

一道很有意思的思维题
对于3次询问确定一个值，很显然要我们去确定第一个字符或者最后一个字符
设 a = “1” 子串的个数 b= “11” 子串的个数
a-b 相当于将字符串去重，将连续的1变为单个1

例如：
11010111
a = 6
b = 3
a-b=3，字符串为10101

然后查询01子串的个数，设01子串的个数为c
如果a=b+c，则说明第一个字符为0
反之，第一个字符为1

怎么得来的？，让我们接着看这个样例
10101，显然01的个数为2，$2+3！=6$

如果我们将第一个字符1改为0，字符串为01010111
a=5
b=2
a-b,则字符串为010101
显然01的个数为3，2+3=5

如果第一个字符为0，那么b+c一定等于a，反之b+c+1=a，因为它少一个01子串，构不成等号了，需要加一

code

int ask(string s){
	cout << 1 << " " << s << endl;
	int res;cin >> res;
	return res;
}
void solve(){
	int n;cin >> n;
	int a=ask("11");
	int b=ask("01");
	int c=ask("1");
	if(a+b==c) cout << "0 1 0" << endl;
	else cout << "0 1 1" << endl;
	int x;cin >> x;
	return ;
}

B. Make It Equal

思路

将数组中所有元素变为相同的一个数字，很显然我们会想到二分
为什么呢，例如：

如果我们将一个序列全部变为3，假设这个序列长度为4，则
序列最终为 3 3 3 3
那么我们在对每个元素操作一次，它就会变为2 2 2 2
即在相同元素的序列操作n次，我们可以让所有元素全部减去一
因此它是具备单调性的

显然我们要让操作次数最少，就应该让这个数字尽可能大，因此二分求右边界
在check函数里面，对于一个数$a_i$

• 如果$a_i<=x$ 不进行操作
• 如果$a_i>x$ 操作$(a_i+1)/2\ast 2$ 向上取整

如果只操作一次，显然可能仍会有 $a_i>x$ 的情况，所以需要循环多次

由于每次变化，数组中整体的值减一，因此可以用sum统计数组中所有的值
如果无解，输出$-1$
有解，输出 $sum-r\ast n$

code

const int N=1e6+5;
int a[N],b[N],n;
bool check(int x){
	for(int i=1;i<=n;++i){
		b[i]=a[i]-x;
	}
	while(1){
		int flag=1;
		for(int i=1;i<=n;++i){
			if(b[i]>0){
				flag=0;
				b[i%n+1]+=(b[i]+1)/2;
				b[i]-=(b[i]+1)/2*2;
			}
		}
		if(flag) break;
	}
	for(int i=1;i<=n;++i){
		if(b[i]!=0) return false;
	}
	return true;
}
void solve(){
	cin >> n;
	int sum=0;
	for(int i=1;i<=n;++i){
		cin >> a[i];
		sum+=a[i];
	} 
	int l=0,r=1e9+1,flag=1;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid)) l=mid,flag=0;
		else r=mid-1;
	}
	cout << (flag?-1 : sum-r*n) << endl;
	return ;
}