欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 养生 > 牛客小白月赛98

牛客小白月赛98

2024/11/30 20:47:44 来源:https://blog.csdn.net/weixin_72696324/article/details/141231792  浏览:    关键词:牛客小白月赛98

牛客小白月赛98

A 骰子魔术

链接:https://ac.nowcoder.com/acm/contest/85598/A
来源:牛客网

题目描述

jackle 正在给他的朋友表演一个关于骰子的魔术:
jackle 会拿出一枚骰子,骰子的表面分别写上了从 1∽500 的数字,朋友会随便说一个 1∽500 之间的点数,jackle 都能保证百分之百的掷出这个点数。
当然 jackle 有备而来,他准备了 𝑛 枚特殊的骰子,第 𝑖 枚特殊骰子,可以保证每次掷出的点数都为 𝑎𝑖 。
jackle 想问你,他能不能只拿出一枚事先准备好的特殊骰子,成功完成这次魔术。

输入描述:

第一行输入 2 个正整数 𝑛 (1≤𝑛≤1000),𝑥 (1≤𝑥≤500),分别表示 jackle 准备的特殊骰子数量,朋友说的那个点数。
第二行输入 𝑛 个正整数 𝑎𝑖 (1≤𝑎𝑖≤500),分别表示每枚特殊骰子可以掷出的点数。

输出描述:

如果 jackle 可以成功完成这次魔术,请你输出 YES;否则请你输出 NO。

示例1

输入
5 3
1 2 1 3 12
输出
YES

说明

jackle 可以选择第 4 个骰子,因为 𝑎4=𝑥=3,所以他能百分之百掷出这个朋友说出的点数,所以可以完成这次魔术。

题解

判断ai里面有没有和X相同的

#include<bits/stdc++.h>
using namespace std;int n,x,a[1005];
int main(){int i,j,k;cin>>n>>x;for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<=n;i++){if(x==a[i]){printf("YES\n");return 0;}}printf("NO\n");return 0;
}
B 最少剩几个?

链接:https://ac.nowcoder.com/acm/contest/85598/B
来源:牛客网

题目描述

给定一个长度为 𝑛 的序列 𝑎,如果当前序列长度至少为 2,那么你每次可以做如下两种操作之一:
选择 𝑖,𝑗 (𝑖≠𝑗),如果满足 𝑎𝑖+𝑎𝑗 是奇数,那么你可以同时删除
𝑎𝑖,𝑎𝑗 。
选择 𝑖,𝑗 (𝑖≠𝑗),如果满足 𝑎𝑖×𝑎𝑗 是奇数,那么你可以同时删除
𝑎𝑖,𝑎𝑗 。
你可以执行上面的操作无数次,只要你满足操作条件,jackle 想问你序列最少剩几个数?

输入描述:

第一行输入 1 个正整数 𝑛 (1≤𝑛≤105),表示序列的长度。
第二行输入 𝑛 个正整数 𝑎𝑖 (1≤𝑎𝑖≤109)。

输出描述:

输出序列最少剩几个数?

示例1

输入
1
114514
输出
1

说明

只有一个数,啥也操作不了。

示例2

输入
2
9 9
输出
0

题解

和Round 52 C很像,都是消除数字的问题,这道题应该来说更简单一些。
找规律:相乘是奇数那么必须至少有一个是奇数,相加是奇数必须是一奇一偶
然后两两消除,只需要记录奇数偶数的个数就行
偶数和偶数消不了

#include<bits/stdc++.h>
using namespace std;int n,a[100005],s1,s2,ans;
int main()
{int i,j,k;cin>>n;for(i=1;i<=n;i++){cin>>a[i];if(a[i]%2==0)s1++;else s2++;}if(s2>=s1) ans=(s2-s1)%2;else ans=s1-s2;cout<<ans<<endl;return 0;
}
C 两个函数

链接:https://ac.nowcoder.com/acm/contest/85598/C
来源:牛客网

题目描述

jackle 给定两个函数:

f ( x ) = a x f(x)=a x f(x)=ax
g ( x ) = { f ( x ) x = 1 ∑ i = 1 x − 1 f ( f ( i ) ) x > 1 g(x)=\left\{\begin{array}{ll}f(x) & x=1 \\ \sum_{i=1}^{x-1} f(f(i)) & x>1\end{array}\right. g(x)={f(x)i=1x1f(f(i))x=1x>1
他有 𝑄 次询问,每次给定 𝑎,𝑥,请你计算 𝑔(𝑥) mod 998244353 的结果。

输入描述:

第一行输入 1 个正整数 𝑄 (1≤𝑄≤105),表示询问次数。
接下来 𝑄 行,每行输入 2 个正整数 𝑎,𝑥 (1≤𝑎,𝑥≤109)。
输出描述:
对于每组询问,输出 𝑔(𝑥)mod  998244353 的结果。

示例1

输入
3
1 1
2 2
9982 44353
输出
1
4
572321601

题解

额,感觉智商受到侮辱。就是这个markdown 写公式,有点造孽
拿出paper推下公式就行,代码里看结果吧,太难打

#include <iostream>
using namespace std;
using LL =long long;
int main() {int Q, a, x;long long sum;const int mod = 998244353;cin >> Q;for (int i = 0; i < Q; i++) {cin >> a >> x;if (x == 1) {cout << a%mod << endl;}else{// 使用数学公式计算sumsum = 1ll*(x - 1) * x / 2;sum = sum%mod * a%mod * a%mod;cout <<sum << endl;}}return 0;
}
D 切割 01 串 2.0

链接:https://ac.nowcoder.com/acm/contest/85598/D
来源:牛客网

题目描述

jackle 在校赛的时候出过一道 “切割 01 串” 的题目,如今他又出了一道切割 01 串的题目:
给定一个长度为 𝑛 的 01 串,定义如下操作为一次 “切割”:
将长度大于 1 的字符串分割为两个非空的连续字串,记分割出来的左侧字串 𝑎 中 0 的出现次数为 𝐶0 ,右侧字串 𝑏 中 1 出现的次数为 𝐶1 ,需要满足 𝐿≤∣𝐶0−𝐶1∣≤𝑅。
你每次切割完,都会得到两个新 01 串,你可以继续选择这些已经被你切出来的 01 串做切割,只要满足切割条件。
jackle 想问你最多可以切割多少次?

输入描述:

第一行输入 3 个整数,𝑛 (1≤𝑛≤500),𝐿,𝑅 (0≤𝐿≤𝑅≤500),分别表示字符串长度,和题目中的两个参数。
第二行输入 1 个长度为 𝑛 的 01 串。

输出描述:

输出最多能切割多少次?

示例1

输入
6 2 3
011011
输出
3

说明

其中一种切割次数最多的切法如下:
第一次切割可以切:0 ∣ 11011,然后选择 11011 这个串继续做切割。
第二次切割可以切:1 ∣ 1011,然后选择 1011 这个串继续做切割。
第三次切割可以切:1 ∣ 011。

题解

区间DP
dp[l,r] 区间[l,r]的对应的答案
然后判断在区间[l,r]中是否符合条件要求累加

#include<bits/stdc++.h>
using namespace std;
int n,l,r;
char s[505];
int cnt[505][2],dp[505][505];int main(){int i,j,k;cin>>n>>l>>r>>s+1;for(i=1;s[i];i++){for(j=0;j<2;j++)cnt[i][j]=cnt[i-1][j];cnt[i][s[i]-'0']++;}for(int len=1;len<=n;len++){for(i=1;i+len-1<=n;i++){for(j=i;j<i+len-1;j++){int c=abs((cnt[j][0]-cnt[i-1][0])-(cnt[i+len-1][1]-cnt[j][1]));if(c<=r&&c>=l) dp[i][i+len-1]=max(1+dp[i][j]+dp[j+1][i+len-1],dp[i][i+len-1]);}}}printf("%d",dp[1][n]);return 0;
}
E and xor or

链接:https://ac.nowcoder.com/acm/contest/85598/E
来源:牛客网

题目描述

给定一个长度为 𝑛 的序列 𝑎,jackle 想让你求出有多少个区间 [𝑙,𝑟] 满足如下条件:
1≤𝑙≤𝑟≤𝑛
2𝑘1≤(𝑎𝑙 & 𝑎𝑙+1 &…& 𝑎𝑟)⊕(𝑎𝑙 ∣ 𝑎𝑙+1 ∣…∣ 𝑎𝑟)<2𝑘2
其中 &,∣,⊕,分别表示按位与,按位或,按位异或。

输入描述:

第一行输入 3 个整数 𝑛 (1≤𝑛≤5×105),𝑘1,𝑘2 (0≤𝑘1<𝑘2≤109)。
第二行输入 𝑛 个整数 𝑎𝑖 (0≤𝑎𝑖≤1018)。

输出描述:

输出满足条件的区间数量。

示例1

输入
4 0 2
2 1 4 3
输出
1

说明

只有区间 [1,2] 满足条件:20≤(2 & 1)⊕(2 ∣ 1)=3<22

示例2

输入
6 0 4
7 6 7 6 7 7
输出
14
在这里插入图片描述

#include<bits/stdc++.h>
#define int long long
using namespace std;int n,k1,k2,a[500005],l[65][500005];signed main()
{cin>>n>>k1>>k2;for(int i=1;i<=n;i++)cin>>a[i];if(k1>=60){cout<<0;return 0;}int len=60;//1e18的二进制数长为60for(int k=0;k<len;k++)//枚举位数,然后用双指针算法处理出数组l[][]{int cnt0=0,cnt1=0;//0的个数,1的个数for(int i=1,j=1;j<=n;j++){int t=((a[j]>>k)&1);t?cnt1++:cnt0++;while(cnt0 && cnt1)//同时存在0和1{l[k][i]=j;int t=((a[i++]>>k)&1);t?cnt1--:cnt0--;}}}//符合条件的区间:f[l,r]的二进制数最高1的位数在[k1,k2-1]int ans=0;for(int i=1;i<=n;i++)//枚举左边界{int a=n+1,b=n+1;for(int k=k1;k<len;k++){if(l[k][i]==0)continue;if(k<=k2-1)a=min(a,l[k][i]);else b=min(b,l[k][i]);}if(a==n+1)continue;ans+=max(b-a,0LL);}cout<<ans;return 0;
}
F 绝妙的手法

链接:https://ac.nowcoder.com/acm/contest/85598/F
来源:牛客网

题目描述
本题出题时想到的贪心做法是错误的,评测数据也是按照出题时的std造的,目前本题没有正确解法,不建议大家做这道题。

给定一个长度为 𝑛 的序列 𝐴,你每次可以做如下操作:
每次选择两个不同的下标 𝑖,𝑗,令 𝐴𝑖=𝐴𝑖+𝐴𝑗
jackle 想问你最少操作几次,可以使得序列中恰好有 𝑚 个正数。

输入描述:

注意本题有多组测试数据。
第一行先输入 1 个整数 𝑇(1≤𝑇≤2×105),表示数据组数。
对于每组测试数据:
第一行输入 2 个整数 𝑛,𝑚 (1≤𝑛≤2×105,0≤𝑚≤2×105)
第二行输入 𝑛 个整数 𝐴𝑖 (−1012≤𝐴𝑖≤1012)。
题目保证 ∑𝑛≤2×105

输出描述:

对于每组测试数据:
如果能通过操作,使得序列中恰好有 𝑚 个正数,请你输出最小操作次数;否则请你输出
−1。

示例1

输入
1
4 3
-1 -1 1 2
输出
1

说明

显然操作一次即可:选择 𝑖=1,𝑗=4,令 𝐴1=𝐴1+𝐴4=−1+2=1,操作完之后 𝐴1=1,那么此时序列中恰好 3 个正数。

示例2

输入
1
5 3
0 0 0 0 0
输出
-1

说明

由于所有数都是 0,所以无论怎么执行 𝐴𝑖=𝐴𝑖+𝐴𝑗 ,序列中的数都还是 0,所以一定无法操作使得序列恰好出现 3 个正数。

示例3

输入
2
4 2
-10 1 1 1
6 4
4 -2 -2 -3 2 -4
输出
1
2

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com