当前位置:   article > 正文

牛客小白月赛98 (个人题解)(补全)

牛客小白月赛98 (个人题解)(补全)

前言:

  昨天晚上自己一个人打的小白月赛(因为准备数学期末已经写烦了),题目难度感觉越来越简单了(不在像以前一样根本写不了一点,现在看题解已经能看懂一点了),能感受到自己在不断进步,希望在暑假能更努力一点吧,,少打点游戏,多学学算法,还有web的学习也要抓起来了,这几天不是在看高数就是在打游戏,感觉好堕落。

正文:

 链接:(1条未读私信) 牛客小白月赛98_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

A 骰子魔术:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[10005];
  4. int main(){
  5. int n,x;
  6. cin>>n>>x;
  7. for(int i=1;i<=n;i++){
  8. int d;
  9. cin>>d;
  10. a[d]++;
  11. }
  12. if(a[x])cout<<"YES";
  13. else cout<<"NO";
  14. return 0;
  15. }

桶排秒了。

B 最少剩几个?:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4. int n,res=0,ans=0;
  5. cin>>n;int o=n;
  6. while(o--){
  7. int x;
  8. cin>>x;
  9. if(x%2==1)res++;
  10. }
  11. int z=n-res;
  12. if(z>=res){
  13. ans=n-2*res;
  14. }
  15. else{
  16. ans=n-2*z-((res-z)/2)*2;
  17. }
  18. cout<<ans<<endl;
  19. return 0;
  20. }

因为奇数加偶数一定是奇数,奇数乘奇数一定为奇数,分两种情况讨论,当偶数数量大于奇数的时候直接用总数减奇数数量的两倍;当奇数大于偶数的时候先减去偶数的两倍在考虑剩下的奇数即可。

C 两个函数:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int mod=998244353;
  5. ll quickmod(ll a, ll b, ll c)
  6. {
  7. ll ans = 1;
  8. a = a % c;
  9. while(b)
  10. {
  11. if(b&1) ans = (ans * a) % c;
  12. b = b >> 1;
  13. a = (a * a) % c;
  14. }
  15. return ans;
  16. }
  17. int main(){
  18. int n;
  19. cin>>n;
  20. while(n--){
  21. ll a,x,ans;
  22. cin>>a>>x;
  23. if(x==1)ans=a*x%mod;
  24. else{
  25. ans=(((a*a)%mod)*((x)*(x-1)/2%mod))%mod;
  26. }
  27. cout<<ans<<endl;
  28. }
  29. return 0;
  30. }

我们可以将公式转化为

g(x)=ax......x=1

g(x)=a^{2}(\sum (n-1))=a^{2}(\frac{x(x-1)}{2})..........x>1

最后直接一边算一遍取模即可。

D 切割 01 串 2.0:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5 + 5;
  4. int dp[1000][1000];
  5. int pre[N],suf[N];
  6. int main(){
  7. int t = 1;
  8. while(t --){
  9. int n,l,r; cin >> n >> l >> r;
  10. string s; cin >> s;
  11. s = "#" + s;
  12. // 区间dp
  13. // dp[a][b] = dp[a][k] + dp[k+1][b] + 1;
  14. for(int i = 1; i <= n ; i ++){
  15. if(s[i] == '0') pre[i] = pre[i - 1] + 1;
  16. else pre[i] = pre[i - 1];
  17. }
  18. for(int i = 1 ; i <= n ; i ++){
  19. if(s[i] == '1') suf[i] = suf[i - 1] + 1;
  20. else suf[i] = suf[i - 1];
  21. }
  22. for(int len = 2 ; len <= n ; len ++){
  23. for(int i = 1 ; i <= n - len + 1; i ++){
  24. int j = i + len - 1;
  25. for(int k = i ; k < j ; k ++){
  26. int q0 = pre[k] - pre[i - 1];
  27. int q1 = suf[j] - suf[k];
  28. int res = abs(q0 - q1);
  29. if(res >= l && res <= r)
  30. dp[i][j] = max(dp[i][j],dp[i][k] + dp[k + 1][j] + 1);
  31. }
  32. }
  33. }
  34. cout << dp[1][n];
  35. }
  36. }

比赛时这题一直想用递归,根本没去想是dp,甚至是我练过的区间dp,导致我用递归一直暴内存,怎么优化都过不了。其实细想想这题确实就是区间dp,因为从小区间推导到大区间就免去了对一次切割产生两个子段进行·递归的过程,详情可以见代码。

 E and xor or:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=5e5+5;
  5. ll a[N];
  6. ll n,k1,k2;
  7. ll work(int x){
  8. ll ans=0,cnt=0;
  9. for(int i=1;i<=n;i++){
  10. bool flag=true;
  11. for(int j=x;j<=60;j++){
  12. int u=a[i]>>j&1;
  13. int v=a[i-1]>>j&1;
  14. if(u!=v){
  15. flag=false;
  16. }
  17. }
  18. if(flag)cnt++;
  19. else{
  20. ans+=cnt*(cnt+1)/2;
  21. cnt=1;
  22. }
  23. }
  24. ans+=cnt*(cnt+1)/2;
  25. return ans;
  26. }
  27. int main(){
  28. cin>>n>>k1>>k2;
  29. for(int i=1;i<=n;i++){
  30. cin>>a[i];
  31. }
  32. cout<<work(k2)-work(k1)<<endl;
  33. return 0;
  34. }

看了题解发现这题还挺简单,

利用前缀和的思想,用所有结果小于 2^k2的子数组个数 - 所有结果小于2^k1的子数组个数,即为答案。

发现这个  2^k 刚好只有一位(二进制下),要结果小于它,则必须满足在二进制中 k ~ 60 位中不能有 1。 根据题目条件,满足不能有 1 即这个子数组元素在k ~ 60位的每一位不能同时存在 1 和 0。

F 绝妙的手法:

看了下题解的代码直接给我吓跑了,代码量还挺大的。

2024.7.12补:

出题人出来说这题出错了,所以不用补了。这又何尝不是另一种补完呢(

后记:

  话说后天就考高数了我还一道题没写是不是有点不务正业了(

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/849007
推荐阅读
相关标签
  

闽ICP备14008679号