牛客小白月赛46题解
A.
B.
显然有
的时候和只存在 
和 
两种数的时候无解。
其他情况就直接排序，如果正负数的交界出的两个数和为 的话，其中一个换成正负性一样但数字不一样大的，这样就完成了构造。
双指针+map维护每个单词出现的次数即可。
D.
显然可能走到的只有父亲，父亲的父亲，儿子，儿子的儿子，自己，父亲的儿子六种情况。分类讨论，父亲，父亲的父亲，儿子就直接看能不能到。这时顺便给父亲的父亲也加上就不用考虑儿子的儿子了。至于父亲的儿子，就看能不能1步到父亲，在看父亲1步能到的儿子数量（不包括自己）。
E.
我们先从小到大排序。对于每个人，我们先让他把能力小于等于他的人干掉，如果已经有了
次比赛或还差一个的话直接看能不能把最强的人用两个道具干掉（其他的由最强的干掉）。这时有一个特例，就是能力值为 
的人可以用乘 
的道具干掉能力值为 
的人，能力值为 
的人可以用除 的道具干掉能力值为 的人。这个特判一下，其他的例子可以对能力值最大的人
分类讨论排除。如果还差两次，看能不能用道具干掉剩下最强的和最弱的，其他还是由最强的干掉。如果差的不止两次肯定没戏。
F.
首先我们只考虑
和 
两个条件。可以先把 
的部分提出来算，这时对于每个满足 
的 
都是成立的。然后如果我们取一个小于 的 
，就只有 
到 
中的数可以作为 的取值，然后用等比数列求和的相关知识求就好了。这时我们尝试加进去 
的条件，发现当且仅当 
时不满足这个的条件且 ,所以只要减去这部分就行了。
最后，出题人为这场比赛出锅的题面，B题过水的数据和毒瘤道歉qwq
显然赢 次的概率是 
的。因此当赢的次数为 
或 
时可能性最大。
为偶数输出 
， 为奇数输出 
和 
即可。
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
if(n&1)cout<<n/2<<' '<<(n+1)/2<<endl;
else cout<<n/2<<endl;
} B.
显然有
其他情况就直接排序，如果正负数的交界出的两个数和为
#include<bits/stdc++.h>
#define mod 1000000007
#define N 1000005
#define int long long
using namespace std;
int n,a[N],cnt;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==0)puts("NO"),exit(0);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)if(i!=1&&a[i]!=a[i-1])cnt++;
if(cnt==1&&a[1]+a[n]==0)puts("NO"),exit(0);
puts("YES");
} C.双指针+map维护每个单词出现的次数即可。
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int data=10,n,k,l,r;
string word[N];
long long ans;
map<string,int>cnt;
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>word[i];
l=1;
for(int i=1;i<=n;i++){
while(i-l>k+1){
cnt[word[l]]--;
l++;
}
ans+=cnt[word[i]];
cnt[word[i]]++;
}
cout<<ans<<endl;
} D.
显然可能走到的只有父亲，父亲的父亲，儿子，儿子的儿子，自己，父亲的儿子六种情况。分类讨论，父亲，父亲的父亲，儿子就直接看能不能到。这时顺便给父亲的父亲也加上就不用考虑儿子的儿子了。至于父亲的儿子，就看能不能1步到父亲，在看父亲1步能到的儿子数量（不包括自己）。
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,u,f[N],son[N],w[N],ans[N];
long long dep[N];
struct node{
int to,dis;
};
vector<node>e[N];
void dfs1(int now){
if(f[f[now]]&&dep[now]-dep[f[f[now]]]<=2)ans[now]++,ans[f[f[now]]]++;
for(int i=0;i<e[now].size();i++){
int y=e[now][i].to;
if(e[now][i].dis==1)son[now]++;
if(e[now][i].dis<=2)ans[now]++,ans[y]++;
dep[y]=dep[now]+e[now][i].dis;
dfs1(y);
}
}
void dfs2(int now){
if(w[now]==1)ans[now]+=son[f[now]];
else ans[now]++;
for(int i=0;i<e[now].size();i++){
int y=e[now][i].to;
dfs2(y);
}
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
scanf("%d%d",&f[i],&w[i]);
e[f[i]].push_back((node){
i,w[i]
});
}
dfs1(1);
dfs2(1);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
} E.
我们先从小到大排序。对于每个人，我们先让他把能力小于等于他的人干掉，如果已经有了
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,k,ans[N],now,flag;
struct node{
int x,p;
}a[N];
bool cmp(node u,node v){
return u.x<v.x;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i].x,a[i].p=i;
sort(a+1,a+n+1,cmp);
if(a[n].x%4==2)for(int i=1;i<=n;i++)if(a[i].x==a[n].x/2)flag=1;
for(int i=1;i<=n;i++){
while(a[now+1].x<=a[i].x&&now<n)now++;
if(k-(now-1)>2)continue;
if(now>=k){
if(a[i].x*2>=a[n].x/2||(flag&&a[i].x>=a[n].x/4)){
for(int j=i;j<=n;j++)ans[a[j].p]=1;
break;
}
else continue;
}
else{
if(a[i].x>=a[n].x/2&&a[i].x*2>=a[now+1].x){
for(int j=i;j<=n;j++)ans[a[j].p]=1;
break;
}
else continue;
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<endl;
} F.
首先我们只考虑
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,k,ans;
int q(int x){
return x*(x+1)/2;
}
signed main(){
cin>>T;
while(T--){
cin>>n>>k;
if(k==1){
cout<<q(n-1)<<endl;
continue;
}
if(n>=k)ans=q(n-1)-q(k-2),n=k-1;
else ans=0;
if(k-1!=1&&1<=n&&k-1<=n)ans--;
int tmp=(k+1)/2;
if(tmp<=n)ans=ans-k*(n-tmp+1)+2*(q(n)-q(tmp-1));
cout<<ans<<endl;
}
} 最后，出题人为这场比赛出锅的题面，B题过水的数据和毒瘤道歉qwq
投递华为等公司10个岗位 >