2022牛客寒假算法基础集训营2

比赛链接

2022牛客寒假算法基础集训营2

C.小沙的杀球

题目描述

小沙特别喜欢杀球（又菜又爱杀），加上小沙是个体能怪，所以他经常杀不死还喜欢杀，小沙只能杀到后场的高远球，如果是前场的小球则没有办法杀球，今天小沙和他的双打搭档一起训练杀球，我们假设小沙的体能一开始为\(X\)，并且每次杀球体能都会消耗\(a\)点，每次非杀球都会恢复\(b\)点。现给出一段\(01\)序列，代表搭档打过来的球是小球还是高远球（\(0\)代表小球，\(1\)代表高远球），请问小沙这一场能最多杀多少个球。小沙的体能不能为负数。

输入描述:

第一行\(3\)个整数 \(0 \le x ,a,b \le 10^9\)，每个整数用空格间隔
第二行一行\(01\)字符串（字符串长度不超过\(10^6\)） 代表搭档打过来的是小球还是高远球。

输出描述:

输出小沙的最多杀球次数

输入

10 2 1
111111

输出

5

说明

我们可以选择第\(2 3 4 5 6\)次杀球最多\(5\)次

解题思路

贪心

很容易想到一个贪心策略：能杀球则杀球。\(\color{red}{如何证明这个策略是正确的？}\)假设能杀球但是选择不杀球，即将这次杀球的体力留给后面杀球，这次选择恢复体力，这样显然会导致杀球的机会更少，如果选择杀球后面即使不能杀球也可以恢复体力达到相同的效果，并且这样杀球的机会更多

代码

// Problem: 小沙的杀球
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23477/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms

// %%%Skyqwq
#include 

#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair PII;

template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int a,b,res;
char s[1000005];
LL x;
int main()
{
	scanf("%lld%d%d",&x,&a,&b);
	scanf("%s",s+1);
	for(int i=1;i<=strlen(s+1);i++)
		if(s[i]=='1'&&x>=a)
			res++,x-=a;
		else
			x+=b;
	printf("%d",res);
	return 0;
}

E.小沙的长路

题目描述

小沙有一个\(n\)个点的完全图(不知道定义可以点)，你可以给每条边选择方向，规定每条边只能走一次，请问n个点的完全图的最长路径，现在现在小沙想要知道它的最小值和最大值分别是多少？

输入描述:

输入一个正整数\(n\leq 10^9\)

输出描述:

一行内输出\(n\)个点的完全图，他的最长路的最小值和最大值，两个数中间用空格间隔

输入

3

输出

2 3

说明


从图中可以看到\(3\)个节点时，最长路最短是\(2\)，最大是\(3\)

解题思路

欧拉路径

对于最长路的最小值：
由于对于完全图而言，在有环情况下的最长路要比无环情况下的最长路要长，所以最长路的最小值一定是无环的，即只经过每个点一次，总长度为 \(n-1\)
对于最长度的最大值:
每条边只出现一次，即找欧拉路径，对于每个点度数为偶数的完全图而言，由于边也是连通的，其总是可以构造出一条欧拉回路，其总长度为 \(n\times (n-1)/2\)，而对于度数为奇数的完全图而言，其可以转换为删除尽可能少的边，使其构造成一条欧拉路径，即可以保留两个奇数度数的点作为起点和终点，这两个点之间不用删边，其余 \(n-2\) 个点的度数需要减一使其为偶数，即在这 \(n-2\) 个点中删除 \((n-2)/2\) 条边，所以这种情况下的最终答案为 \(n\times (n-1)/2 - (n-2)/2\)

  • 时间复杂度：\(O(1)\)

代码

// Problem: 小沙的长路
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23477/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms

// %%%Skyqwq
#include 

#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair PII;

template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

int main()
{
	int n;
	cin>>n;
	printf("%d %lld",n-1,1ll*n*(n-1)/2-1ll*(n%2==0)*(n-2)/2);
	return 0;
}

F.小沙的算数

题目描述

小沙不会计数，所以他想从小学数学开始学起，今天老师布置了一大堆算数题，但爱耍小聪明的小沙发现这么多的算数题中，他们中间的符号都是\(+\)或者\(\times\) 并且每个题\(+\)和\(\times\)的位置都是一样的
小沙想要快点去玩耍，所以求助好哥哥你帮帮他快速的计算出答案。
由于答案数字过大 所以我们对\(1000000007\)取模

输入描述:

第一行给定二个数\(n\)，代表有\(n\)个数进行计算，\(q\)代表有\(q\)次询问
\((2\leq n \leq 10^6,1\leq q \leq 10^5)\)
第二行给定一个长度为\(n-1\)的*+字符串，表示我们要进行的计算符号是什么
第三行
给定\(n\)个整数，代表这每个位置上的数字
随后\(q\)行每行两个数字\(x,y\)
代表着将第\(x\)个数字改成\(y\)
且\(x\leq n\)
本题所有数均为正整数，且小于\(1000000007\)
但并不保证计算过程中是否会出现大于\(1000000007\)的值

输出描述:

对于每次查询，回答出整个算式的答案，每个答案占一行
（本题中的每次查询均不独立，也就是说每次查询修改之后的数，都会永远的修改）

输入

5 3
++*+
1 1 3 1 1
4 2
1 7
5 6

输出

9
15
20

解题思路

区间问题，模拟，哈希，逆元

不妨把一段乘法看成一个数，即类似于区间段数，预处理每段乘法的值及用哈希表或数组存下乘法的所有数字的位置对应的乘法段的下标，每次询问时，如果当前数位于乘法位置，则修改该数所在乘法的值，这里可用该处的乘法值除以修改前的值得到其他数的乘积，进而修改答案及该段乘法值；如果当前数位于加法位置，直接修改即可。另外还需要计算出询问前的表达式结果，这个可以模拟

  • 时间复杂度：\(O(n)\)

代码

// Problem: 小沙的算数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23477/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms

// %%%Skyqwq
#include 

#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair PII;

template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int mod=1e9+7,N=1e6+5;
int n,q;
char s[N];
int m;
LL res,product[N],a[N];
unordered_map mp;
int ksm(int a,int b,int p)
{
	a=(a+p)%p;
	int res=1%p;
	for(;b;b>>=1)
	{
		if(b&1)
			res=1ll*res*a%p;
		a=1ll*a*a%p;
	}
	return res;
}
int main()
{
	mp.clear();
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	bool f=false;
	m=0;
	for(int i=1;i<=n-1;i++)
	{
		if(s[i]=='*')
		{
			if(!f)
			{
				m++;
				product[m]=a[i]*a[i+1]%mod;
				mp[i]=mp[i+1]=m;
			}
			else
				product[m]=product[m]*a[i+1]%mod,mp[i+1]=m;
			f=true;
		}
		else
			f=false;
	}
	int t=1;
	for(int i=1;i<=n-1;)
	{
		if(i==1)
		{
			if(s[1]=='*')
			{
				while(i<=n-1&&s[i]=='*')i++;
				res=product[t++];
			}
			else
			{
				if(i+1<=n-1)
				{
					if(s[i+1]=='+')res=(a[1]+a[2])%mod,i++;
					else
					{
						res=a[1];
						i++;
						while(i<=n-1&&s[i]=='*')i++;
						res=(res+product[t++])%mod;
					}
						
				}
				else
				{
					res=(a[1]+a[2])%mod;
					i++;
				}
			}
		}
		else
		{
			if(i+1<=n-1)
			{
				if(s[i+1]=='*')
				{
					res=(res+product[t++])%mod;
					i++;
					while(i<=n-1&&s[i]=='*')i++;
				}
				else
					res=(res+a[i+1])%mod,i++;
			}
			else
				res=(res+a[i+1])%mod,i++;
		}
	}
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int lst=a[x];
		a[x]=y;
		int bl=mp[x];
		if(bl)
		{
			res=(res+(y-lst+mod)*product[bl]%mod*ksm(lst,mod-2,mod)%mod)%mod;
			product[bl]=(product[bl]+(y-lst+mod)*product[bl]%mod*ksm(lst,mod-2,mod)%mod)%mod;
		}
		else
		{
			res=(res+y-lst+mod)%mod;
		}
		printf("%lld\n",res);
	}
	return 0;
}

H.小沙的数数

题目描述

有一个\(a\)数组，我们已知他的长度为\(n\)，\(a[+]\)的和为\(m\)，请问如果我们想要\(a[⊕]\)的值最大，数组\(a\)在满足\(a[+]=m\)时有多少种情况
我们定义\(a[+]\)指\(a_1+a_2....a_n\)的值
a[⊕]指\(a_1⊕a_2⊕a_3....a_n\) 的值
其中\(a\)数组全部都为非负整数。
答案对\(1e9+7\)取模

输入描述:

输入两个整数\(1\leq n \leq 10^{18},0\leq m \leq 10^{18}\)

输出描述:

输出一个整数表示方案数

输入

3 1

输出

3

说明

原数组可以为

0 0 1
0 1 0
1 0 0

这三种可能

解题思路

数学

结论：\(a+b \geq a \bigoplus b\)，异或为不进位的加法

由结论：\(a[\bigoplus ]=a[+]=m\)，由于异或值的固定的，进位会改变固定的异或值，所以不允许进位，另外还有一种理解：有数学公式：\(a+b=a\& b*2+a \bigoplus b\)，要使 \(a \bigoplus b\) 最大，即 \(a\& b=0\)，即每一位两两之间都要有 \(0\)，即二进制下每一位最多只能出现一个 \(1\)，且该位由 \(m\) 决定。另外，每一位的 \(1\) 的位置是互不影响的，且 \(1\) 的位置可以出现在数组中任意一个数的对应位上，即每一位的 \(1\) 由 \(n\) 种情况

  • 时间复杂度：\(O(logm)\)

代码

// Problem: 小沙的数数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23477/H
// Memory Limit: 524288 MB
// Time Limit: 2000 ms

// %%%Skyqwq
#include 

#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair PII;

template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int mod=1e9+7;
LL n,m;
int main()
{
	scanf("%lld%lld",&n,&m);
	n%=mod;
	int res=1;
	for(;m;m-=m&-m)res=1ll*res*n%mod;
	printf("%d",res);
	return 0;
}
2022牛客寒假算法基础集训营贪心模拟数学欧拉路径区间问题哈希乘法逆元

相关

使用webgl(three.js)搭建一个3D智慧园区、3D建筑，3D消防模拟，web版3D,bim管理系统——第

noip多校模拟30

哈希传递

2019.11.8模拟赛

[NOIP模拟赛] 2021.11.16

20211116 NOIP 模拟赛

项目实战：Qt+C#轨道交通行业高性能高流畅度模拟火车移动图像控件

ASP.NET Core管道深度剖析（2）：创建一个“迷你版”的管道来模拟真实管道请求处理流程

数据结构与算法之PHP查找算法（哈希查找）

NOIP模拟99(多校31)

算法总结篇---哈希和哈希表

20210628模拟赛解题报告

标签