牛客小白月赛 84

A

签到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;void solve(){int n, m, x, y;cin>>n>>m>>x>>y;if(n-m>=y-x && y>=x) cout<<"Yes\n";else cout<<"No\n";
}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --){solve();}    return 0;
} 

B

• 常规解法 :$O(\sqrt{x})$

$a\ast b=gcd(a,b)\ast lcm(a,b)=\lambda$

对 $\lambda$ 因数分解, 找出所有 $a,b$ , 并验证 gcd 与 lcm

• 数论大师解法 $O(1)$

对任意正整数 a, b 都满足, gcd(a,b) | lcm(a,b)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define int long long
int x, y;
void sol1(){int t=x*y;for(int a=1; a<=sqrt(t)+1; a++){if(t%a==0){int b=t/a, gcd=__gcd(a,b);if(__gcd(a,b)==x&&t/__gcd(a,b)==y){cout<<a<<' '<<b<<'\n';return;}}}cout<<"-1\n";
}void sol2(){if(y%x==0) cout<<x<<' '<<y<<'\n';else cout<<"-1\n";
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --){cin>>x>>y;// sol1();sol2();}    return 0;
} 

C

贪心的构造 , 越往左边值越小

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;void solve(){int n, k, x;cin>>n>>k;bool f = true;int last=-1e9-10;for(int i=1; i<=n; i++){cin>>x;if(abs(x-last)<=k) continue;else if(last>x+k) f=false;else last=x-k;}if(f) cout<<"Yes\n";else cout<<"No\n";
}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --){solve();}    return 0;
} 

D

分情况讨论 , 最多讨论 16 中情况 , 但是其中 12 中可以快速讨论, 实际对答案影响的只有 4 种

#include<bits/stdc++.h>
using namespace std;
int n, Q;
int const N = 1e6+10;
int a[N];
int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin>>n>>Q;{string t; cin>>t;for(int i=0, len=t.size(); i<len; i++) a[i+1]=t[i]-'0';}int res=0;for(int i=1; i<=n; i++){if(!a[i]) continue;int j=i; while(j<=n && a[j]) j++; i=j;res++;}for(int i=1; i<=Q; i++){int l, r;cin>>l>>r;if(a[l]==0 && a[r] && a[l-1] && a[r+1]==0) cout<<res-1<<'\n';else if(a[l] && a[r]==0 && a[l-1]==0 && a[r+1]) cout<<res-1<<'\n';else if(a[l]==0 && a[r] && a[l-1]==0 && a[r+1]) cout<<res+1<<'\n';else if(a[l] && a[r]==0 && a[l-1] && a[r+1]==0) cout<<res+1<<'\n';else cout<<res<<'\n';}return 0;
} 

E

观察法

小蓝最近在异世界的国度中生活，最近国度中丞相的空缺，有两位候选人，我们称其中一人为 Dog 先生，另一人为 Cat 先生，他们俩因为谁上位的问题一直摩擦不断，国王也很无奈，于是请小蓝解决这个问题，小蓝想到了一个办法：给定长度为 n 的序列 a ， Dog 先生和 Cat 先生每次可以将序列 a 中的某个非零数减一，两人轮流操作， Cat 先生先手，若某人无法进行操作或者操作后出现以下局面则输掉比赛：

1、设 x 为序列 a 中的最小数，设 cnt[x] 为数字 x 在序列 a 中出现的次数，n−cnt[x]≤cnt[x]<n 。

2、x=0 且 cnt[x]=n 。

国王看到这个游戏觉得很好，于是下令谁赢得这场游戏谁就是新的丞相，已知 Dog 先生和 Cat 先生都发挥最佳，最终是谁成为了新丞相？

1. cnt[x] != n 时, cnt[x]>=(n+1)/2 败
2. cnt[x] == n && x==0 败

1. 如果序列长度为 1, 那么看操作次数即可判断谁胜谁负
2. 序列长度为 2, 
{x, x+y}, y>=2, 先手必败
{x, x+1}, x==0, 先手必败x!=0, 先手必胜
{x,x}
3. 序列长度大于 2, 当仅有 x==0时才会分出胜负, 否则比赛一直进行最终状态, cnt[0]=(n+1)/2, cnt[1]=n-cnt[0]

根据最终状态推演局面

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
int a[1000010];
void op(int x){cout<<(x==1?"Cat":"Dog")<<'\n';
}
void solve(){int n;cin>>n;for(int i=1; i<=n; i++) cin>>a[i];if(n==1){if(!a[1]) op(2);else if(a[1]&1) op(2);else op(1);}else if(n==2){if(a[1]>a[2]) swap(a[1], a[2]);int x=a[1], y=a[2];if(y-x>=2) op(2);else if(y-x==1){if(x==0) op(2);else op(1);}else{if(x==1) op(1);else op(2);}}else{sort(a+1,a+n+1);int num0=upper_bound(a+1,a+n+1, 0)-a-1;if(num0==n+1) op(2);else{int num1=upper_bound(a+1,a+n+1, 1)-a-1;num1-=num0;int final0=(n+1)/2;if(num0>=final0) op(2);else{long long s=0;for(int i=num0+num1+1; i<=n; i++) s+=a[i]-1;s+=(final0-num0);if(s&1) op(2);else op(1);}}}
}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while(T --){solve();}    return 0;
} 

F

dfs 剪枝搜索, 搜索到所有 f 数组都被满足即可

#include<bits/stdc++.h>
using namespace std;int n;
int f[50], a[50];
bool ok=false;bool check(int id){int res=0;for(int l=1; l+id<=n; l++){int r=l+id;if(a[l]==0 && a[r]==1) res++;}return res==f[id];
}void dfs(int l, int r, int id){if(ok) return;if(id==0){for(int i=1; i<=n; i++) cout<<a[i];ok=true;return;}if(l==r){a[l]=0;if(check(id)) dfs(l+1,r-1,id-1);a[r]=0;if(check(id)) dfs(l+1,r-1,id-1);}else if(l<r){for(int i=0; i<=1; i++) for(int j=0; j<=1; j++){a[l]=i, a[r]=j;if(check(id)) dfs(l+1, r-1, id-1); }}else{if(check(id)) dfs(l+1, r-1, id-1);}
}int main(){cin>>n;for(int i=1; i<n; i++) cin>>f[i];dfs(1,n,n-1);if(ok==false) cout<<"-1\n";return 0;
}