当前位置：首页 > news >正文

牛客周赛 Round 35 (A~G)

news 2025/8/7 15:54:35

本次A~D较为简单，E是一道很好的构造题，FG主要就是考察组合数和约数个数

A.小红的字符串切割

思路：签到题

void solve()
{string s;cin>>s;int len=s.size();cout<<s.substr(0,len/2)<<endl<<s.substr(len/2);
}

B.小红的数组分配

思路：题意就是要我们根据已有数据分成两个一模一样的数组，那么就要满足所有数都是偶数个，然后再将每个数输出一半的次数即可

void solve()
{int n;cin>>n;vector<int> v(2*n);map<int,int> h;for(auto &t:v){cin>>t;h[t]++;}int f=0;for(auto t:h){if(t.se&1){f=1;break;}}if(f){cout<<-1;return ;}for(auto t:h){for(int i=0;i<t.se/2;i++)cout<<t.fi<<' ';}puts("");for(auto t:h){for(int i=0;i<t.se/2;i++)cout<<t.fi<<' ';}
}

C.小红关鸡

思路：排序+枚举+二分，根据题意要求最大概率，那么也就是用两个栅栏框住最多的鸡窝，那么也就是求在合法区间中鸡窝数的最大值，我们可以枚举左端点a[L]，然后二分查找大于等于a[L]+k的鸡窝的位置pos，如果存在a[L]+k这个鸡窝，那么a[L]~a[L]+k这个区间的鸡窝个数为pos-L+1，如果不存在a[L]+k这个鸡窝，那么a[L]~a[L]+k这个区间的最右边的鸡窝的位置为pos-1,那么这个区间的鸡窝个数为pos-1-L+1

void solve()
{int n,k;cin>>n>>k;vector<int> v(n);map<int,int> h;for(auto &t:v){cin>>t;h[t]++;}sort(v.begin(),v.end());int maxd=0;for(int i=0;i<n;i++){int x=v[i]+k;int pos=lower_bound(v.begin()+i,v.end(),x)-v.begin();if(h[x])maxd=max(maxd,pos-i+1);else maxd=max(maxd,pos-i);}double res=(maxd*1.0/n);printf("%lf",res);//题目没说保留几位小数且误差不超过1e-4，所以输出所有小数位的结果误差远低于1e-4
}

D.小红的排列构造

思路：先用set<int> s将1~n全部存一遍，在输入数据时，如果s中存在这个数，则删掉这个数，否则说明这个数要么就是重复出现，要么就是不在1~n这个范围中，那么用一个数组存一下它的位置。输入完以后，s中保留的数就是需要将对应位置修改的数。

void solve()
{int n;cin>>n;map<int,int> h;set<int> s;for(int i=1;i<=n;i++) s.insert(i);for(int i=1;i<=n;i++){int t;cin>>t;if(s.count(t))s.erase(t);elseh[i]=t;}cout<<h.size()<<endl;for(auto t:h){int pos=t.fi,x=t.se;cout<<pos<<' '<<(*s.begin())<<endl;s.erase(*s.begin());}
}

E.小红的无向图构造

思路：这道题每条边的权值为1，如果要构建一棵二叉树，首先边至少为n-1，且每一层都要与上一层相连。那么我们可以做以下分析：

（1）m<n-1，肯定是无解的

（2）m>=n-1 ，用vector<int> g[N]，存储每一层的节点，如果存在1~maxd(某个节点到1号节点的最短路径，也就是最大层数）中某一层为空，那么就无法构造出二叉树，无解。

（3）用vector<PII> ans 存储边，首先我们要构建一棵普通的二叉树，用第i层的所有节点连接第i-1层的第一个节点，ans.push_back({g[i-1][0],g[i][j]})，如果m>ans.size()，那么我们要考虑在同一层加边，或者第i层的所有节点与第i-1层除了g[i-1][0]的其他节点相连，如果这些操作都执行完了，仍不足m条边，则无解，否则遍历ans输出边

constexpr int N=1e5+5;
int a[N],n,m,maxd;
vector<int> g[N];
vector<PII> ans;void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];g[a[i]].eb(i);maxd=max(maxd,a[i]);}if(m<n-1){cout<<-1;return ;}for(int i=1;i<=maxd;i++){if(g[i].empty()) {cout<<-1;return ;}for(auto t:g[i])ans.pb({g[i-1][0],t});}if(ans.size()<m){//同一层的点相互连接for(int i=1;i<=maxd;i++){for(int j=1;j<g[i].size();j++){for(int k=j-1;k>=0;k--){ans.pb({g[i][j],g[i][k]});if(ans.size()==m) break;}if(ans.size()==m) break;}if(ans.size()==m) break;}//当前层的点与上一层除了第一个点以外的其它点连接if(ans.size()<m){for(int i=2;i<=maxd;i++){for(int j=1;j<g[i-1].size();j++){for(int k=0;k<g[i].size();k++){ans.pb({g[i-1][j],g[i][k]});if(ans.size()==m) break;}if(ans.size()==m) break;}if(ans.size()==m) break;}}}if(ans.size()<m) cout<<-1;else {for(auto t:ans)cout<<t.fi<<' '<<t.se<<endl;}
}

F.小红的子序列权值和（easy）

思路：任何一个数可以表示为p1^q1*p2^q2*...pk^qk，约数个数为（q1+1)*(q2+1)*...*(qk+1)。题目只有1~3这三种数，由于1比较特殊，所以我们只需枚举2和3的所有组合，ans+=C(sum2,i)*C(sum3,j)*(i+1)*(j+1)*temp,temp=pow(2,1的个数），因为每个1有选和不选两种情况，那么是否将1放到2和3这个组合种以及放多少就是temp种情况了

constexpr int N=1e5+5,mod=1e9+7;
int C[1005][1005];
map<int,int> h;void solve()
{int n;cin>>n;for(int i=0;i<n;i++){int x;cin>>x;h[x]++;}int temp=1;for(int i=0;i<h[1];i++) temp=temp*2%mod;for(int i=0;i<=n;i++)for(int j=0;j<=i;j++)if(j==0||j==i) C[i][j]=1;else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;int ans=0,three=h[3],two=h[2];for(int i=0;i<=two;i++)for(int j=0;j<=three;j++){ans+=C[two][i]*C[three][j]%mod*(i+1)%mod*(j+1)%mod*temp%mod;ans%=mod;}cout<<(ans-1+mod)%mod;//还要减去一种子序列为空的情况
}

G.小红的子序列权值和（hard）

相较于easy版本n的数据范围改成了1e5

easy版本我们使用的方法时间复杂度为O(n*n),这里我们使用O(nlogn)做法，C(a,b)=a!/ ((a-b)!*b!)，我们只需求1~n的阶乘，以及1~n的阶乘的逆元，根据easy版本我们得到公式C(cnt2,i)*(i+1)*C(cnt3,j)*(j+1)*2^cnt1,i属于[0,cnt2] ， j属于[0，cnt3]，i=0时，j属于[0，cnt3]时，ans1=C（cnt3,j)*（j+1)*2^cnt1,i=1时，j属于[0，cnt3]时，ans2=C(cnt2,1)*(1+1)*C（cnt3,j)*（j+1)*2^cnt1,

ans=ans1+ans2=(1+C(cnt2,1)*(1+1)) * (C（cnt3,j)*（j+1)) *2^cnt1,化简之后我们可以发现公式为 $2^{cnt1}\sum_{i=0}^{cnt2}C(cnt2,i)(i+1)\sum_{j=0}^{cnt3}C(cnt3,j)(j+1)$ ，所以求和部分只需分别用一个循环就可以搞定了

constexpr int N=1e5+5,mod=1e9+7;int fact[N],infact[N],n;
map<int,int> h;void solve()
{cin>>n;auto qmi = [&](int a,int b) ->int{int res=1;while(b){if(b&1) res=res*a%mod;b>>=1;a=a*a%mod;}return res;};auto C = [](int a,int b) ->int{if(a<b) return 0;return fact[a]*infact[a-b]%mod*infact[b]%mod;};fact[0]=infact[0]=1;for(int i=1;i<=n;i++){fact[i]=fact[i-1]*i%mod;infact[i]=infact[i-1]*qmi(i,mod-2)%mod;}for(int i=0;i<n;i++){int x;cin>>x;h[x]++;}int temp=1,c2=0,c3=0,cnt2=h[2],cnt3=h[3];for(int i=0;i<h[1];i++) temp=temp*2%mod;for(int i=0;i<=cnt2;i++)c2=(c2+C(cnt2,i)*(i+1)%mod)%mod;for(int i=0;i<=cnt3;i++)c3=(c3+C(cnt3,i)*(i+1)%mod)%mod;cout<<(c2*c3%mod*temp%mod-1+mod)%mod;//同样会有一种情况是空串
}

查看全文

http://www.mrgr.cn/news/13541.html