A. Minimums and Maximums
略
#include <bits/stdc++.h>
using namespace std;
int t;
int a,b,c,d;
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> t;
for(int i=0;i<t;i++){
cin>>a>>b>>c>>d;
if(min(b,d)-max(a,c) >= 0){
cout<<max(a,c)<<endl;
continue;
}
cout<<a+c<<endl;
}
}
B. Robots
分析:根据题意进行分析，为使得在其他机器人不溢出的边界的条件达到左上角的目标
只有存在(x_min,y_min)的位置有机器人，否则无法达成上述目标
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int t;
int n,m;
int min_l=N,min_r=N;
char g[N][N];
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin>>t;
while(t--){
min_l=N,min_r=N;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(g[i][j]=='R'){
min_l=min(min_l,i);
min_r=min(min_r,j);
}
}
}
if(g[min_l][min_r]=='R')cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
C. Binary String
分析:题目的题意为:给定一条只含有01的二进制字符串，可以在 左右两侧依次从左到右或者从右到左进行任意次删除操作(注意:可只删除左侧,只删除右侧，也可左右进行删除操作)
输出在经历删除操作后存在的所有可能的剩余字符串中max(num1,num2)的最小值
字符串中剩下0的字符数num0; (the number of characters 0 left in the string;)
从字符串中删除1的字符数num1(the number of characters 1 removed from the string.)
首先谈一下本人对这道题的心得
首先有个小技巧:二分 和 双指针 的出现往往困难伴随着前缀和 ,
原因在于无论二分还是双指针的实现都离不开单调性
在处理单调性的过程中可能遇到区间的性质需要快速解决
1.首先想到的是最特殊的情况的特判如下:
000000 000111 0000111110000
上述三种情况一定答案是0,即字符串左右两侧的0要优先去除且没有任何代价
2.首先看到字符串中只含有二进制串01，又在题目的第一个限定 字符串中剩下0的字符数 存在某个区间
s[i,j]求取区间剩余0的个数的操作=>前缀和数组pre[N]
例如
01000100
求某个区间s[i,j]内部的1的个数num1只需求num1=pre[j]-pre[i-1]即可
同理某个区间s[i,j]内部的1的个数num0=(i-j+1)-num1即可得到
3.尽可能使得num1和 num0的大小接近(num1和num0是此消彼长的关系)
方法一: 双指针
思路分析:假设s[i，j]为以i为左端点的最终剩余区间,当i移动到达s[i+1，j]的区间求取以i+1为左端点的最终剩余区间时,无论s[i]为0还是1，移动的结果必然导致=>num1增加或者不变,或者 num0减少或者不变,但 不可能都不变 (即此消彼长 )根据题意想要得到 最小值 就要尽量保持num1和num0的数量差值很小,因此 j 一定会右移去维护 |num1-num0|尽可能小
综上 i 和 j 的移动均具有单调性
代码描述
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,INT=2e9+10;
int sum[N];
string s;
int ans=INT;
int t,n;
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin>>t;
while(t--){
ans=INT;
memset(sum,0,sizeof sum);
cin>>s;
n=s.size();
s=' '+s;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+s[i]-'0';
if(sum[n]==n){
cout<<0<<endl;
continue;
}else if(sum[n]==0){
cout<<0<<endl;
continue;
}
for(int i=1,j=1;i<=n;i++){
while(j<=n && (j-i+1)-(sum[j]-sum[i-1])<sum[n]-(sum[j]-sum[i-1]))j++;
ans=min(ans,max((j-i+1)-(sum[j]-sum[i-1]),sum[n]-(sum[j]-sum[i-1])));
}
cout<<ans<<endl;
}
return 0;
}
方法二: 二分
1.剩余字符串中0的个数(此处的单调性为 在num0<num1时 num0增大一定越有利于取得最小值 )
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,INT=2e9+10;
int sum[N];
string s;
int ans=INT;
int t,n;
int main(){
cin>>t;
while(t--){
ans=INT;
memset(sum,0,sizeof sum);
cin>>s;
n=s.size();
s=' '+s;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+s[i]-'0';
}
if(sum[n]==n){
cout<<0<<endl;
continue;
}else if(sum[n]==0){
cout<<0<<endl;
continue;
}
int res=n-sum[n];
for(int i=1;i<=n;i++){
int l=i,r=n+1;
while(l<r){
int mid=(l+r)/2;
int left1=(mid-i+1)-(sum[mid]-sum[i-1]);
int left2=sum[n]-(sum[mid]-sum[i-1]);
if(left1>=left2)r=mid;
else l=mid+1;
ans=min(ans,max(left1,left2);
}
ans=min(ans,max((r-i+1)-(sum[r]-sum[i-1]),sum[n]-(sum[r]-sum[i-1])));
}
cout<<ans<<endl;
}
return 0;
}
2.删除的字符串中1的个数(此处的单调性为 在num0>num1时 num1增大一定越有利于取得最小值)
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,INT=2e9+10;
int pre[N],sur[N];
string s;
int t,n;
int ans=INT;
int main(){
cin>>t;
while(t--){
ans=INT;
memset(pre,0,sizeof pre);
cin>>s;
n=s.size();
s=' '+s;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+s[i]-'0';
}
for(int i=1;i<=n;i++){
int l=0,r=n;
while(l<r){
int mid=(l+r)>>1;
int left1=(mid-i+1)-(pre[mid]-pre[i-1]);
int left2=pre[n]-(pre[mid]-pre[i-1]);
if(left2<left1)r=mid;
else l=mid+1;
ans=min(ans,max(left1,left2));
}
ans=min(ans,max((l-i+1)-(pre[l]-pre[i-1]),pre[n]-(pre[l]-pre[i-1])));
}
cout<<ans<<endl;
}
return 0;
}
E. Moving Chips
状态机动态规划,状态转移函数为f[i][0/1/2]
其中i为第i列,
f[i,0]表示第 i 列最终的状态为 无Chips
f[i,1]表示第 i 列最终的状态为 仅仅第一个位置有Chips
f[i,2]表示第 i 列最终的状态为 仅仅第二个位置有Chips
最终的答案为min(f[n][1],f[n][2])
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 5, INF = 0x3f3f3f3f;
char g[2][maxn];
int f[maxn][3];
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n >> g[0] + 1 >> g[1] + 1;
for(int i = n; i; i--)
if (g[0][i] == '*' || g[1][i] == '*'){
n = i;
break;
}
for(int i = 0; i <= n; i++)
for(int j = 0; j < 3; j++)
f[i][j] = INF;
f[0][0] = 0;
for(int i = 1; i <= n; i++){
if (g[0][i] != '*' && g[1][i] != '*'){
f[i][0] = f[i - 1][0];
f[i][1] = min({f[i - 1][1] + 1, f[i - 1][2] + 2});
f[i][2] = min({f[i - 1][1] + 2, f[i - 1][2] + 1});
}
else if (g[0][i] == '*' && g[1][i] != '*'){
f[i][1] = min({f[i - 1][0], f[i - 1][1] + 1, f[i - 1][2] + 2});
f[i][2] = min({f[i - 1][0] + 1, f[i - 1][1] + 2, f[i - 1][2] + 2});
}
else if (g[0][i] != '*' && g[1][i] == '*'){
f[i][1] = min({f[i - 1][0] + 1, f[i - 1][1] + 2, f[i - 1][2] + 2});
f[i][2] = min({f[i - 1][0], f[i - 1][1] + 2, f[i - 1][2] + 1});
}
else{
f[i][1] = min({f[i - 1][0] + 1, f[i - 1][1] + 2, f[i - 1][2] + 2});
f[i][2] = min({f[i - 1][0] + 1, f[i - 1][1] + 2, f[i - 1][2] + 2});
}
}
cout << min(f[n][1], f[n][2]) << '\n';
}
}
