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 ;
}