Problem - A - Codeforces
如果y大于0,那么肯定YES,因为可以左右操作,一直等到同一行,然后可以始终保持同一行,然后进行左右操作去追赶即可
如果y小于等于0,则只要y大于于等于-1则YES,因为始终保持差一行,进行左右操作去追赶,最后进行斜方向操作一次即可
所以只要y大于等于-1则YES,否则NO
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n;
void solve() {
cin>>n;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
if(y>=-1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--) {
solve();
}
return 0;
}
Problem - B - Codeforces
首先a肯定是要的且是完整连续的,然后其它的只能在a的前面插入或者在a的后面插入
所以只要求出b的最长连续子段为a中子序列的长度,然后前后再插入
暴力枚举b的子段,然后判断是否为a的子序列,记录最长长度maxn
答案即为len(b)-maxn+len(a)
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
string a,b;
bool check(string s){
int n=s.size();
int cnt=0;
for(int i=0;i<(int)a.size();i++){
if(a[i]==s[cnt]) cnt++;
}
if(cnt==n) return true;
return false;
}
void solve() {
cin>>a>>b;
int maxn=0;
for(int i=0;i<(int)b.size();i++){
for(int j=0;j<=i;j++){
string tmp=b.substr(j,i-j+1);
if(check(tmp)) maxn=max(maxn,i-j+1);
}
}
cout<<b.size()-maxn+a.size()<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
Problem - C - Codeforces
二分答案
check:记录均为1的数量,以及均为-1的数量,均为0的不用管,没有1的不用管,只有一个1的就只选1
如果可以做到两部电影均大于等于x,则true
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],b[N];
int n;
bool check(int x){
int sum1=0,sum2=0;
int cnt1=0,cnt_1=0;
for(int i=1;i<=n;i++){
if(a[i]==1&&b[i]==1) cnt1++;
else if(a[i]==-1&&b[i]==-1) cnt_1++;
else if(a[i]==1||b[i]==1){
if(a[i]==1) sum1++;
else sum2++;
}
}
if(sum1<x){
int t=min(cnt1,x-sum1);
sum1+=t;
cnt1-=t;
}
if(sum2<x){
int t=min(cnt1,x-sum2);
sum2+=t;
cnt1-=t;
}
if(sum1<x||sum2<x) return false;
if(sum1-x+sum2-x+cnt1>=cnt_1) return true;
return false;
}
void solve() {
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int l=-2e9,r=2e9;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}