显然赢 次的概率是 的。因此当赢的次数为 或 时可能性最大。 为偶数输出 , 为奇数输出 和 即可。
#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
全部评论
(6) 回帖