devbox
逻辑思维
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

牛客周赛 Round 29 题解

作者：逻辑思维 | 2024-01-29 18:31:59

赞

踩

牛客周赛 Round 29 题解

牛客周赛 Round 29 题解

代码风格

后续目标代码写在solve()方法中

  1. #include<bits/stdc++.h>
  2. //#include<iostream>
  3. //#include<vector>
  4. //#include<cstdio>
  5. //#include<cmath>
  6. //#include<cstring>
  7. ​
  8. using namespace std;
  9. #define ll long long
  10. #define endl "\n"
  11. ​
  12. const int N = 2e5 + 10;
  13. const double eps = 1e-8;
  14. const double pi = acos(-1.0);
  15. const int INF = 1e9;
  16. const int MAXN = 2020;
  17. const int mod = 1e8 + 7;
  18. ​
  19. int prime[N];
  20. void check() {
  21.     memset(prime, 0, sizeof(prime)); //0 素数 1 不是素数
  22.     prime[1] = 1;
  23.     for (int i = 2; i <= N; i++) {
  24.         if (prime[i] == 0) {
  25.             for (int j = i * 2; j <= N; j += i) {
  26.                 prime[j] = 1;
  27.             }
  28.         }
  29.     }
  30. }
  31. ​
  32. bool cmp(int x, int y) {
  33.     return x > y;
  34. }
  35. ​
  36. void solve() {
  37. ​
  38. }
  39. ​
  40. int main() {
  41.     //  freopen("input.txt","r",stdin);
  42.     //  freopen("output.txt","w",stdout);
  43.     ios::sync_with_stdio(false);
  44.     cin.tie(nullptr);
  45.     cout.tie(nullptr);
  46.     int t;
  47.     cin >> t;
  48.     //  cin.ignore() ;
  49.     //  cin.clear();
  50.     //t = 1;
  51.     //check();
  52.     //这里根据具体情况来变动t,是输入还是默认为1
  53.     while ( t--) {
  54.         solve();
  55.     }
  56. }

A.小红大战小紫

思路

大小比较即可,如果数字很大,可以进行高精度大小比较即可

AC代码
  1. //这里直接给高精度模板了,低精度无意义
  2. void solve() {
  3.     string s1,s2;
  4.     cin>>s1>>s2;
  5.     int len_s1=s1.size();
  6.     int len_s2=s2.size();
  7.     if(len_s1!=len_s2){
  8.         cout<<(len_s1>len_s2?"kou":"yukari")<<endl;
  9.     }else{
  10.         for(int i=0;i<len_s1;i++){
  11.             if(s1[i]!=s2[i]){
  12.                 cout<<(s1[i]>s2[i]?"kou":"yukari")<<endl;
  13.                 return;
  14.             }
  15.         }
  16.         cout<<"draw"<<endl;
  17.     }
  18.         
  19. }

B.小红的白日梦

思路

模拟即可,每天如果白天没做梦就进行转移获得最大幸福度,否则就正常计算

AC代码
  1. //正常逻辑判断即可
  2. void solve() {
  3.     int n;
  4.     cin >> n;
  5.     string day, night;
  6.     cin >> day >> night;
  7.     int ans = 0;
  8.     for (int i = 0; i < n; i++) {
  9.         if (day[i] == 'N') {
  10.             ans += (night[i] == 'Y' ? 2 : 0);
  11.         } else {
  12.             ans += (2 + ((night[i] == 'Y') ? 1 : 0));
  13.         }
  14.     }
  15.     cout << ans << endl;
  16. }

C.小红的小小红

思路

利用find函数寻找子串即可,然后对该子串进行bool处理,随后依次输出即可

AC代码
  1. void solve() {
  2.     string s;
  3.     cin>>s;
  4.     vector<bool>b(s.size());
  5.     for(int i=0;i<s.size();i++) b[i]=false;
  6.     int pos1=s.find("xiao");
  7.     int pos2=s.find("hong");
  8.     for(int i=pos1;i<=pos1+3;i++) b[i]=true;
  9.     for(int i=pos2;i<=pos2+3;i++) b[i]=true;
  10.     cout<<"xiaohong";
  11.     for(int i=0;i<s.size();i++) if(!b[i]) cout<<s[i];
  12. }
  13. ​

D.小红的中位数

思路

先进行题目规律的探索,去寻找规律,即明显应该排完序后再看,如果去除几号元素,会发生中位数变化有什么规律,同时可以发现将数据分成奇偶来考虑,同时对半分进行考虑即可

AC代码
  1. struct data{
  2.     double value;
  3.     int pos;
  4.     int pos_sort;
  5. };
  6. ​
  7. bool cmp( struct data x,struct  data  y) {
  8.     return x.value > y.value;
  9. }
  10. ​
  11. ​
  12. void solve() {
  13.     int  n;
  14.     cin>>n;
  15.     //为更好处理下标问题,可以选择牺牲一个单位空间进行处理
  16.     vector<int>a(n+1),b(n+1);
  17.     vector<double>ans(n+1);
  18.     for(int i=1;i<=n;i++) {cin>>a[i]; b[i]=a[i];}
  19.     //利用一个额外vector来记忆原来顺序即可
  20.     //两种常见解法,一种利用中值判断即可
  21.     sort(a.begin(),a.end());
  22.     //排序后得到中间值,利用中间值来判断即可
  23.     if(n%2==0){//偶数情况下  如 1 2 3 4 5 6   6/2=3
  24.         int midNum1=a[n/2];
  25.         int midNum2=a[n/2+1];
  26.         for(int i=1;i<=n;i++){
  27.             //这里其实考虑了相等的情况,可以证明
  28.             if(b[i]<midNum2) ans[i]=midNum2*1.0;
  29.             else ans[i]=midNum1*1.0;
  30.         }
  31.     }else{ //奇数情况下 如  1 2 3 4 5   5/2=2
  32.         int midNum=a[n/2+1];
  33.         for(int i=1;i<=n;i++){
  34.             if(b[i]<midNum) ans[i]=(a[n/2+1]+a[n/2+2])/2.0;
  35.             else if(b[i]==midNum) ans[i]=(a[n/2]+a[n/2+2])/2.0;
  36.             else ans[i]=(a[n/2]+a[n/2+1])/2.0;
  37.         }
  38.     }
  39.     for(int i=1;i<=n;i++) cout<<fixed<<setprecision(1)<<ans[i]<<endl;
  40.     //如果想要得到排序后的数字的具体位置,那么就应该构建结构体来处理
  41. //  struct data mid[N+1];
  42. //  for(int i=1;i<=n;i++){ cin>>mid[i].value; mid[i].pos=i;}
  43. //  sort(mid+1,mid+n+1,cmp);
  44. //  for(int i=1;i<=n;i++){ mid[i].pos_sort=i;}
  45.     //后续处理与上面一致,无需再复杂化,只不过如果想构建,得用结构体才行
  46. }
​
​

E.小红构造数组

此题特别注意数据范围,数据大问题

思路

题目首先进行第一步直观的操作就是要得到一个数的全部质因数,及其对应的个数,这一步我们可以联想到欧式筛选法进行套用,便可以完成

第二步问题在于,我们应该如何去构建这个数组,即如何从数学上保证该数组满足条件,那么最开始我们可以想到的是利用每一次取两个最多的各一个,但这种我们没法去证明,只能模糊的得到当最多的个数>其余总和+1的情况是绝对不满足的,但我们无法证明其相反面是满足的,所以这里我们进一步采用填补法,插空法来论证,因为要求有相邻不同,排列那么很明显用插空法的思想来论证是比较好的,所以我们来采用一种构造方式

我们将最多的质因数先排列,然后第二多的去插空,可以发现,只要最多的n个的n-1个空被插满了,那么就肯定可以构造成功,后续的空是越来越多的,所以论证完毕

AC代码
  1. #define pii pair<int,int>
  2. #define pll pair<long long,long long>
  3. //#define int long long  一般不启用 如果启用那么main那里需要要改signed
  4. bool cmp( pii  x, pii  y) {
  5.     return x.first > y.first;
  6. }
  7. ​
  8. ​
  9. void solve() {
  10.     //用一个pll来存储即可,map也行,但无需去排序处理,避免浪费时间
  11.     vector<pll>a;
  12. //因为任何合数一定可以拆解成质因数,所以我们从小的数开始去逐渐拆解即可
  13.     ll x; //10^19
  14.     cin >> x;
  15.     //处理前,需要去特判一下,可以看到下面的循环是x从4开始的,所以可以对x<4进行处理即可
  16.     //同时由于x=2,3可以在后续处理掉,所以这里不进行特判
  17.     if(x==1){
  18.         cout<<-1<<endl;
  19.         return;
  20.     }
  21.     ll sum = 0; //记录因子数总和,来进行判断最大是否可行
  22.     for (ll i = 2; i * i <= x; i++) { //因为质因数分布在根号x两侧 或者x/2两侧
  23.         //特别注意这里的变化,如果因为前一个质数的全部没了,所以下一个一定是从i*i开始的
  24.         if (x % i == 0) {
  25.             ll cnt = 0;
  26.             while (x % i == 0) {
  27.                 cnt++;
  28.                 x /= i;
  29.             }//当2可以约分时,那么x就把2除完了,那么2的所有倍数就不行了,也就是关于2的合数就不可能%了
  30.             a.push_back({cnt, i});
  31.             sum += cnt;
  32.         }
  33.     }
  34.      if(x > 1) a.push_back({1, x}), sum += 1;  //当x=2,3是也可以这样处理
  35.     sort(a.begin(),a.end(),cmp);
  36.     //或者第三个参数为 greater<pii>()
  37.     if(a[0].first*2>sum+1){ //插空法判断  sum-n>=n-1才行
  38.         cout<<-1<<endl;
  39.         return;
  40.     }else{
  41.         vector<ll>ans(sum);
  42.         //然后依次隔空放即可
  43.         ll j=0;
  44.         for(ll i=0;i<sum;i+=2){
  45.             ans[i]=a[j].second;
  46.             a[j].first--;
  47.             if(a[j].first==0)j++;  //隔空来放就可以了,最多的情况是其余刚好给最大的插空完
  48.         }
  49.         for(ll i=1;i<sum;i+=2){
  50.             ans[i]=a[j].second;
  51.             a[j].first--;
  52.             if(a[j].first==0)j++;
  53.         }
  54.         cout<<sum<<endl;
  55.         for(ll i=0;i<sum;i++)cout<<ans[i]<<" ";
  56.     }
  57.     
  58. }
​
​

F.小红又战小紫

思路

题目的知识点进行分解理解,首先是分数取模问题,即逆元问题

x/y 对p取模 本质上就是x*y对p的逆元后再对p取模

(x/y)%p=a a**y%p=x ->

a X y X y^-1 %p=x X y^-1 %p -> a%p=x * y^-1 %p

所以这里就可以得到所谓的求x/y对p取模本质上就是x*y对p的逆元后%p

所以求a,问题在于求y对p的逆元,这里采用最简单的费马小定理和欧拉定理得到的编程实现

结合带mod的快速幂算法和求逆元算法,注意前提条件一定是y,p是互质的,通常取p是素数,即费马小定理这个特殊情况下,才可以运用这个快速幂模版来计算

由于概率是分数,我们就不能够进行直接相除之后再转化,不然那样会失真,所以我们需要将/完全转化为%操作,也就是(1-dpi-1,j+mod)%mod操作 将概率进行取模化

其次DP问题,我在代码注释里进行了更加详细的解释

AC代码
  1. //如果存在某一堆石子为2 必然使用技能1
  2. //如果不存在某一堆石子为2 必然使用技能2,此时胜率为100%
  3. ​
  4. //考虑到彼此之间存在特殊的关系,即小红进行操作时,如果石子全为1,则使用技能2必胜
  5. //如果不全为1,则使用技能1,但是使用是有取舍选择的,显然是两种选择,1种是选择堆为2的石子,消去一个,或者是选择堆为1的石子让其消失
  6. //同时,选择的概率也取决于当时的状态 所以明显需要使用到状态转移,动态规划进行考虑
  7. //故设置dp[i][j] 表征当前有i个石子数为1的堆,j个石子数为2的堆,此时先手方(小红)的获胜概率
  8. ​
  9. //i+j堆石子 那么 i/(i+j)的概率选择到消去1个石头  j/(i+j)的概率选择到消去2个石头中的1个石头
  10. //所以状态转移就出来了 dp[i][j]=dp[i+1][j-1]*j/(i+j)+dp[i-1][j]*i/(i+j)
  11. //然后可以知道 dp[i][0]=1  然后进行状态转移dp即可
  12. //这里存在一个问题,那就是动态规划必须是底层向前层推进,不可推进过程中收到之前的影响
  13. //如果这里设置 i,j  i表示堆为1的石子 那这样必然存在互相影响,因为转移只能i从小到大
  14. //而这里的i,j状态中i,j需要i+1层,所以肯定有问题
  15. //这里进行转化即可,i重新定义为全部的石子的堆数即可
  16. //dp[i][j]=dp[i-1][j]*(i-j)/i+dp[i][j-1]*j/i;
  17. //这里由于参照了数论中的取模运算,那么对最后的分数取模,我们在同步计算是就必须将/进行转化
  18. //更详细解释参考其他文档
  19. ​
  20. ll qkpow(ll a,ll b){
  21.     ll res=1;
  22.     ll mul=a%mod;
  23.     while(b){
  24.         if(b&1) res=res*mul%mod;
  25.         b>>=1;
  26.         mul=mul*mul%mod;
  27.     }
  28.     return res;
  29. }
  30. ​
  31. ll getInv(ll x){
  32.     return qkpow(x,mod-2);
  33. }
  34. ​
  35. ll dp[MAXN][MAXN]={0};
  36. void solve() {
  37.     int n;
  38.     cin>>n;
  39.     int num[3]={0};
  40.     for(int i=0,x;i<n;i++){
  41.         cin>>x;
  42.         num[x]++;
  43.     }
  44.     //有误!!!不删除进行对比
  45. //  for(int i=1;i<=n;i++) dp[i][0]=1;
  46. //  for(int i=0;i<=n;i++){
  47. //      for(int j=1;j<=n;j++){
  48. //          if(i!=0) dp[i][j]=((1-dp[i-1][j]+mod)%mod)*i*getInv(i+j)%mod+((1-dp[i+1][j-1]%mod))*j*getInv(i+j)%mod;
  49. //          else     dp[i][j]=((1-dp[i+1][j-1]+mod)%mod)*j*getInv(i+j)%mod;
  50. //          dp[i][j]%=mod;
  51. //      }   
  52. //  }
  53. ​
  54. ​
  55. for(int i=1;i<=n;i++){
  56.     dp[i][0]=1;
  57.     for(int j=1;j<=i;j++){
  58.         //同时这里的mod一定要完全%化 不然要出问题的
  59.         //(1-dp[i-1][j]+mod)%mod) 这一步操作是将概率进行取模化
  60.         //(i-j)*getInv(i)%mod)%mod   getInv本身就很大所以需要去%一次  在计算完后再进行%mod一次
  61.         //这里1减必须要注意,因为我们要考虑谁来操作,那么这一步获胜一定是在前面一人前面一步失败的基础上
  62.         dp[i][j]=((1-dp[i-1][j]+mod)%mod)*((i-j)*getInv(i)%mod)%mod+((1-dp[i][j-1]+mod)%mod)*(j*getInv(i)%mod)%mod;
  63.         dp[i][j]%=mod;//两个已经%mod的数同样需要再次%mod一次
  64.     }
  65. }
  66.     cout<<dp[n][num[2]]<<endl;
  67. }
​
​
​
​
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/44259
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号