首页 > 编程语言 >2025牛客寒假算法基础集训营2 ptlks的题解

2025牛客寒假算法基础集训营2 ptlks的题解

时间：2025-01-23 20:53:36浏览次数：1  
标签：00 题意 int 题解 代码 牛客 点击 集训营 void

A.一起奏响历史之音！

题意：

判断给定的音节序列是否仅由五声音调组成。

思路

签到题。

代码

点击查看代码 
void solve() {
	int n, f = 1;
	for (int i = 1; i <= 7; i++) {
		cin >> a[i];
		if (a[i] == 1 || a[i] == 2 || a[i] == 3 || a[i] == 5 || a[i] == 6) {

		} else {
			f = 0;
		}
	}
	if (f) {
		cout<<"YES\n";
	}else{
		cout<<"NO\n";
	}
}

B.能去你家蹭口饭吃吗

题意：

找出一个最大的x，满足x比数组中至少一半的数小。

思路

排序即可。

代码

点击查看代码 
void solve() {
	int n;
	cin>>n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		
	}
    sort(a+1,a+1+n,greater<>());
	cout<<a[(n+1)/2]-1<<endl;
	
}

C.字符串外串

题意：

给定n，m，构造长度为n，可爱值为m的字符串。

思路

发现当n-m>26或n=m时，无法构造出字符串；否则按照n-m的大小来构造字符串，详细见代码。

代码

点击查看代码 
void solve() {
	int n, m;
	cin >> n >> m;
	if (m == n||n-m>26) {
		cout << "NO\n";
		return;
	}
	s="";
	int k=n-m;
	for(int i=0;i<n;i++){
		s+='a'+i%k;
	}
	cout<<"YES\n";
	cout<<s<<endl;
}

D.字符串里串

题意：

定义字符串s的可爱度k为这样的一个最大整数，使得存在长度为k的连续子串a、长度为k的不连续子序列b，满足a=b。特别地，若不存在符合要求的a,b，则可爱度为0。求字符串的可爱值

思路

无

代码

点击查看代码 
无

E.一起走很长的路！

题意：

给定数组a，和区间[l,r]，操作是任选一个元素增加1或者减少1。求怎样在最少的操作数下满足任意$i\in[l+1,r],a_i\le\displaystyle\sum_{j=l}^{i-1}a_j $。

思路

区间和很容易想到用前缀和来解决，令\(S_i=\displaystyle\sum_{j=1}^{i}a_j\)，则有任意\(i\in[l+1,r],a_i\le S_{i-1}-S_{l-1}\Rightarrow S_{l-1}\le S_{i-1}-a_i\)。
记录数组\(c,c_i=S_{i-1}-a_i\)。
则我们只需改变数组c的区间[l+1,r]即可。由前缀和的性质可知，增大\(a_l\)是最优的操作，那么我们只要求区间[l+1,r]内的最小值，用数据结构去求c的区间最小值即可。

代码

点击查看代码 

int ans = 0,n,m;
int a[N], b[N], c[N];
priority_queue<int, vector<int>, greater<int>>q;
vector<PII>g;
string s;


const int MAX_LEN =2e5 ;
int seg_tree[MAX_LEN << 2];
int seg_tree1[MAX_LEN << 2];
int Lazy[MAX_LEN << 2];
int arr[MAX_LEN];
//从下往上更新 节点
void push_up (int root) {
	seg_tree[root] = max(seg_tree[root << 1], seg_tree[root << 1 | 1]);      //最小值改min
	seg_tree1[root] = min(seg_tree1[root << 1], seg_tree1[root << 1 | 1]);
}
//从上向下更新，左右孩子
void push_down (int root, int L, int R) {
	if(Lazy[root]){
		Lazy[root << 1] += Lazy [root];
		Lazy[root << 1 | 1] += Lazy[root];
		int mid = (L + R) >> 1;
		seg_tree[root << 1] +=  Lazy[root] * (mid - L + 1);
		seg_tree[root << 1 | 1] += Lazy[root] * (R - mid);
		seg_tree1[root << 1] +=  Lazy[root] * (mid - L + 1);
		seg_tree1[root << 1 | 1] += Lazy[root] * (R - mid);
		Lazy[root] = 0;
	}
}
//建树
//[L,R]就是对应arr数组里面的数
void build (int root, int L, int R) {
	Lazy[root] = 0;
	if(L == R) {
		seg_tree[root] = arr[L];
		seg_tree1[root] = arr[L];
		return ;
	}
	int mid = (L + R) >> 1;
	build(root << 1, L, mid);
	build(root << 1 | 1, mid + 1, R);
	push_up(root);
}

//区间查询
//查找区间[LL,RR]的最大/小值
int querymax (int root, int L, int R, int LL, int RR) {
	if (LL <= L && R <= RR) return seg_tree[root];
	push_down(root, L, R);     //每次访问都去检查Lazy 标记
	int Ans = 0;
	int mid = (L + R) >> 1;
	if(LL <= mid) Ans = max(Ans, querymax(root << 1, L, mid, LL, RR));    //最小值改min
	if(RR > mid) Ans = max(Ans, querymax(root << 1 | 1, mid + 1, R, LL, RR)); //最小值改min
	return Ans;
}
int querymin (int root, int L, int R, int LL, int RR) {
	if (LL <= L && R <= RR) return seg_tree1[root];
	push_down(root, L, R);     //每次访问都去检查Lazy 标记
	int Ans = 1e18;
	int mid = (L + R) >> 1;
	if(LL <= mid) Ans = min(Ans, querymin(root << 1, L, mid, LL, RR));    //最小值改min
	if(RR > mid) Ans = min(Ans, querymin(root << 1 | 1, mid + 1, R, LL, RR)); //最小值改min
	return Ans;
}
//区间修改 +-某值
//使得区间[LL,RR]的值都加上val
void update_Interval(int root, int L, int R, int LL, int RR, int val){
	if (LL <= L && R <= RR) {
		Lazy[root] += val;
		seg_tree[root] += val * (R - L + 1);
		seg_tree1[root] += val * (R - L + 1);
		return ;
	}
	push_down(root, L, R);
	int mid = (L + R) >> 1;
	if (LL <= mid) update_Interval(root << 1, L, mid, LL, RR, val);
	if (RR > mid) update_Interval(root << 1 | 1, mid + 1, R, LL , RR, val);
	push_up(root);
}
//单点修改 可以改为某值，或者+-某值
//把pos位置的值改成val
void update(int root, int L, int R, int pos, int val) {
	if(L == R){
		seg_tree[root] = val;    //点直接变为某值
		seg_tree1[root] = val;    //点直接变为某值
		return ;
	}
	int mid = (L + R) >> 1;
	if(pos <= mid) update(root << 1, L, mid, pos, val);
	else update(root << 1 | 1, mid + 1, R, pos, val);
	push_up(root);
}

void solve() {
	int n, m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
		arr[i]=b[i-1]-a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		if(l==r){
			cout<<0<<endl;
		}else{
			int x=querymin(1,1,n,l+1,r)-b[l-1];
			cout<<max(0ll,-x)<<endl;
		}
	}
}

F.一起找神秘的数！

题意：

对于给定的区间，从中选取两个整数，使得下式成立：x+y=(x or y)+(x and y)+(x xor y)，求解有多少对答案。

思路

打表发现只有x=y时成立。

代码

点击查看代码 
void solve() {
	int n, f = 1;
	cin>>n>>f;
	cout<<f-n+1<<endl;
	
}

G.一起铸最好的剑！

题意：

给定\(n，m\)，找到最接近\(n\)的\(m^k\)的k的最小值

思路

枚举即可。

代码

点击查看代码 
void solve() {
	int n, m,s=1;
	cin>>n>>m;
	if(m==1){
		cout<<s<<endl;
		return;
	}
	int p=m;
	while(p*m<=n){
		s++;
		p*=m;
	}
	if(abs(p*m-n)<abs(p-n)){
		s++;
	}
	cout<<s<<endl;
	
}

H.一起画很大的圆！

题意：

划定了一个矩形区域，在这个区域的边界选3个整点，使得三点画出的圆最大。

思路

随便画几个就知道了。

代码

点击查看代码 
void solve() {
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(b-a>=d-c){
		cout<<b<<' '<<d<<endl;
		cout<<a<<' '<<d-1<<endl;
		cout<<b-1<<' '<<d<<endl;
	}else{
		cout<<a<<' '<<c<<endl;
		cout<<a+1<<' '<<d<<endl;
		cout<<a<<' '<<c+1<<endl;
	}
	
}

J.数据时间？

题意：

略

思路

照着题意写就行了，我稍微取了点巧。注意编号范围到了1e20。

代码

点击查看代码 
int n,h, m,s=1;
	cin>>n>>h>>m;
	set<string> s1,s2,s3;
	for(int i=1;i<=n;i++){
		int hh,mm,dd;
		string x,z;
		cin>>x>>hh>>mm>>dd>>z;
		if(hh==h&&mm==-m){
			if(z>="07:00:00"&&z<="09:00:00"||
				z>="18:00:00"&&z<="20:00:00"){
				s1.insert(x);
			}
			if(z>="11:00:00"&&z<="13:00:00"){
				s2.insert(x);
			}
			if(z>="22:00:00"&&z<="23:59:59"||
				z>="00:00:00"&&z<="01:00:00"){
				s3.insert(x);
			}
		}
	}
	cout<<s1.size()<<' '<<s2.size()<<' '<<s3.size()<<endl;

K.可以分开吗？

题意：

求蓝色连通块相邻的灰色块的数量的最小值。

思路

很简单的bfs，直接写就行了

代码

点击查看代码 
int ans = 0,n,m;
int a[N][N], b[N][N], c[N][N];
priority_queue<int, vector<int>, greater<int>>q;
vector<PII>g;
int xx[4]={0,1,0,-1},yy[4]={1,0,-1,0};
void dfs(int x,int y){
	b[x][y]=1;
	for(int i=0;i<4;i++){
		int X=x+xx[i];
		int Y=y+yy[i];
		if(X<1||Y<1||X>n||Y>m)continue;
		if(a[X][Y]){
			if(!b[X][Y]){
				dfs(X,Y);
			}
		}else{
			if(!c[X][Y]){
				c[X][Y]=1;
				ans++;
				g.push_back({X,Y});
			}
		}
	}
}

void solve() {
	int s=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char x;
			cin>>x;
			a[i][j]=x-'0';
		}
	}
	int mx=1e18;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]&&!b[i][j]){
				ans=0;
				dfs(i,j);
				mx=min(mx,ans);
				for(auto[x,y]:g){
					c[x][y]=0;
				}
				g.clear();
			}
		}
	}
	cout<<mx<<endl;

}

标签：00,题意,int,题解,代码,牛客,点击,集训营,void
From： https://www.cnblogs.com/ptlks/p/18688609

相关文章

  • [BZOJ4833] 最小公倍佩尔数 题解
    在这篇题解中，我会将各个部分的证明分成不同的推导过程，以达到逐一击破的效果。引理1：\(f(n)=2f(n-1)+f(n-2)\)我的证明挺繁琐的，过程如下：\((1+\sqrt2)^{n-2}=e(n-2)+f(n-2)\sqrt2\)\((1+\sqrt2)^{n-1}=e(n-1)+f(n-1)\sqrt2\)\((1+\sqrt2)^{n-1}=(1+\sqrt2)^{n-2}(1+\sqrt......
  • [BZOJ4833] 最小公倍佩尔数 题解
    在这篇题解中，我会将各个部分的证明分成不同的推导过程，以达到逐一击破的效果。引理1：\(f(n)=2f(n-1)+f(n-2)\)我的证明挺繁琐的，过程如下：\[(1+\sqrt2)^{n-2}=e(n-2)+f(n-2)\sqrt2\]\[(1+\sqrt2)^{n-1}=e(n-1)+f(n-1)\sqrt2\]\[(1+\sqrt2)^{n-1}=(1+\sqrt2)^{n-2}(1+\sqrt......
  • 题解：洛谷 P1025 [NOIP2001 提高组] 数的划分
    题目https://www.luogu.com.cn/problem/P1025解法1：深度优先搜素准确来说是DFS+最优性剪枝。我们在上一次选择的数字之后的范围进行枚举，记录这次选择的结果。优化：记录之前的选择的数字之和，我们记为 ，那么枚举的范围为 。 记录的是选择的数字。如果顺利地枚举完了每一......
  • 题解：P4551 最长异或路径
    分析首先我们有如下结论：设两个节点到根节点的路径异或值为\(x_1,x_2\)，则这两个节点之间的路径异或值为\(x_1\operatorname{xor}x_2\)。因此可以先求出每个节点到根节点的路径异或值，那么问题就转化成了：从\(n\)个整数中选两个进行异或运算，得到的结果最大是多少。考虑使......
  • [BZOJ4671] 异或图 题解
    我能说什么！抽象了这！看到\(n\le10\)的黑题顿感大事不妙。我们考虑设\(f(i)\)表示将\(n\)个点划分为至少\(i\)个连通块时的方案数。我们可以暴力枚举每个点在哪个连通块里。划分方案是\(Bell(n)\le21147\)的。显然的，相同块内暂时忽略，不同块间不能有边。于是我们将每......
  • [BZOJ3622] 已经没有什么好害怕的了 题解
    发现难以维护差值，于是令\(K=\frac{n+k}2\)，这样就把问题转化为了“糖果”比“药片”大的组数为\(K\)的情况有多少种。设\(dp_{i,j}\)表示我们用前\(i\)个“糖果”和“药片”配对，至少有\(j\)组“糖果”比“药片”大，有多少种情况；\(c_i\)表示有多少个“药片”比第\(i\)个......
  • [BZOJ3622] 已经没有什么好害怕的了 题解
    发现难以维护差值，于是令\(K=\frac{n+k}2\)，这样就把问题转化为了“糖果”比“药片”大的组数为\(K\)的情况有多少种。设\(dp_{i,j}\)表示我们用前\(i\)个“糖果”和“药片”配对，至少有\(j\)组“糖果”比“药片”大，有多少种情况；\(c_i\)表示有多少个“药片”比第\(i\)个......
  • [BZOJ4665] 小w的喜糖 题解
    我们先假设同种糖间存在差异。设\(f_{i,j}\)表示前\(i\)种糖至少有\(j\)人拿到的糖和原来一样，\(c_i\)表示拿第\(i\)种糖的人的个数，则有：\[f_{i,j}=\sum_{k=0}^{\min(j,c_i)}f_{i-1,j-k}\binom{c_i}kc_i^\underlinek\]设\(g_i\)表示所有人中恰好有\(i\)人拿到的糖......
  • [FJOI2016] 建筑师 题解
    显然有一个\(dp\)思路。设\(f_{i,j}\)表示现在修了\(i\)栋楼，从第一栋楼外侧能看到\(j\)栋楼的方案数，显然有：\[f_{i,j}=\begin{cases}[i=0](j=0)\\f_{i-1,j-1}+(i-1)f_{i-1,j}(j\ne0)\end{cases}\]一眼\(f_{i,j}=\begin{bmatrix}i\\j\end{bmatrix}\)。那么答案即为：\[\s......
  • [BZOJ5093] 图的价值 题解
    考虑计算一个点的贡献，最后\(\timesn\)即为所求。显然一个点的贡献为\(\sum\limits_{i=0}^{n-1}\binom{n-1}ii^k2^{\frac{(n-1)(n-2)}2}\)，则有：\[\sum_{i=0}^{n-1}\binom{n-1}ii^k2^{\frac{(n-1)(n-2)}2}=2^{\frac{(n-1)(n-2)}2}\sum_{i=0}^{n-1}\sum_{j=0}^k\begin{Bmatrix}k......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99