IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 牛客白月赛27【题解】 -> 正文阅读

[数据结构与算法]牛客白月赛27【题解】

https://ac.nowcoder.com/acm/contest/6874#question

目录

巨木之森【树的直径】

在这里插入图片描述

#include<bits/stdc++.h> 
using namespace std;
typedef long long int LL;
const int N=1e5*4+10;
LL h[N],e[N],ne[N],w[N],idx;
LL n,m,dist[N],dist1[N],dist2[N],sum;
int ans;
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa,LL d)
{
	dist[u]=d;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		dfs(j,u,d+w[i]);
	}
}
void dfs1(int u,int fa,LL d,LL dist[N])
{
	dist[u]=d;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		dfs1(j,u,d+w[i],dist);
	}
}
int main(void)
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1;i<=n-1;i++)
	{
		int a,b,c; cin>>a>>b>>c;
		add(a,b,c),add(b,a,c);
		sum+=c;
	}
	dfs(1,-1,0);
	LL root1=1,len1=0;
	for(int i=1;i<=n;i++) if(len1<dist[i]) len1=dist[i],root1=i;
	dfs(root1,-1,0);
	LL root2=1,len2=0;
	for(int i=1;i<=n;i++) if(len2<dist[i]) len2=dist[i],root2=i;
	dfs1(root1,-1,0,dist1);
	dfs1(root2,-1,0,dist2);
	vector<LL>ve;
	for(int i=1;i<=n;i++)
	{
		LL temp=sum*2-max(dist1[i],dist2[i]);//减去最远的点
		ve.push_back(temp);
	}
	sort(ve.begin(),ve.end());
	int cnt=0;
	for(int i=0;i<ve.size();i++)
		 if(ve[i]<=m) cnt++,m-=ve[i];
	cout<<cnt<<endl;
	return 0;
}

乐团派对【贪心 / DP】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e6+10;
int a[N],n,maxv=0;
int main(void)
{ 
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],maxv=max(maxv,a[i]);
	if(maxv>n) puts("-1");
	else
	{
		sort(a+1,a+n+1);
		int cnt=0,ans=0;
		vector<int>ve;
		maxv=0;
		for(int i=1;i<=n;i++)
		{
			maxv=max(maxv,a[i]);
			cnt++;
			if(cnt==maxv) ve.push_back(cnt),ans++,cnt=0,maxv=0;
		}
		if(cnt<maxv)//说明最后一个不满足，那么倒着从后返回
		{
			for(int i=ve.size()-1;i>=0;i--)
			{
				cnt+=ve[i],ans--;
				if(cnt>=maxv) break;
			}
            ans++;
		}
		cout<<ans;
	}
	return 0;
}

#include<bits/stdc++.h> 
using namespace std;
typedef long long int LL;
const int N=1e5*4+10;
int n,a[N],dp,maxv[N];
int main(void)
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		if(i>=a[i]) dp=max(maxv[i-a[i]]+1,dp);
		else dp=0;
		maxv[i]=max(maxv[i-1],dp);
	}
	if(dp==0)  puts("-1");
	else cout<<dp;
	return 0;
}

光玉小镇【状压DP TSP】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=210;
LL f[1<<17][17],dist[25][25],n,m,t;
vector< pair<int,int> >ve;
int st[N][N];
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
char c[N][N];
void bfs(int x,int y)
{
	st[x][y]=0;
	queue<pair<int,int>>q; q.push({x,y});
	while(q.size())
	{
		auto temp=q.front(); q.pop();
		x=temp.first,y=temp.second;
		for(int i=0;i<4;i++)
		{
			int tempx=x+dx[i],tempy=y+dy[i];
			if(tempx<=0||tempx>n||tempy<=0||tempy>m) continue;
			if(st[tempx][tempy]!=-1) continue;
			if(c[tempx][tempy]=='#') continue;
			st[tempx][tempy]=st[x][y]+1;
			q.push({tempx,tempy});
		}
	}
}
int main(void)
{
	memset(dist,0x3f,sizeof dist);
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>c[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(c[i][j]=='S') ve.push_back({i,j});
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(c[i][j]=='T') ve.push_back({i,j});
    bool flag=0;
	for(int i=0;i<ve.size();i++)
	{
		memset(st,-1,sizeof st);
		bfs(ve[i].first,ve[i].second);
		for(int j=0;j<ve.size();j++) 
		{
			int x=ve[j].first,y=ve[j].second;
            if(st[x][y]==-1) flag=1;//不可达
			dist[i][j]=st[x][y];
		}
	}
	memset(f,0x3f,sizeof f);
	f[1][0]=0;
	LL cnt=ve.size();
	for(int i=0;i<(1<<cnt);i++)
	{
		for(int j=0;j<cnt;j++)
		{
			if(i>>j&1)
			{
				for(int k=0;k<cnt;k++)
				{
					int temp=i-(1<<j);
					if(temp>>k&1) f[i][j]=min(f[i][j],f[i-(1<<j)][k]+dist[k][j]);
				}
			}
		}
	}
	LL ans=0x3f3f3f3f;
	for(int i=1;i<cnt;i++) ans=min(ans,f[(1<<cnt)-1][i]+dist[i][0]);
    if(flag) puts("-1");
	else cout<<ans+t*(cnt-1);
	return 0;
}

巅峰对决【线段树】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
struct node
{
	int l,r,minv,maxv;
}tr[N*4];
int n,m,w[N];
void build(int u,int l,int r)//建树
{
    tr[u]={l,r};
    if(l==r) return;
    int mid=tr[u].l+tr[u].r>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
}
void pushup(int u)
{
    tr[u].maxv=max(tr[u*2].maxv,tr[u*2+1].maxv);
    tr[u].minv=min(tr[u*2].minv,tr[u*2+1].minv);
}
node query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];//包含
    else
    {
        int mid=(tr[u].l+tr[u].r)/2;
        int maxv=0,minv=1e9;
        if(l<=mid)
		{
			node temp=query(u*2,l,r);
		 	maxv=max(maxv,temp.maxv);//左边有交集
		 	minv=min(minv,temp.minv);//左边有交集
		}
        if(r>=mid+1)
		{
			node temp=query(u*2+1,l,r);
		 	maxv=max(maxv,temp.maxv);//左边有交集
		 	minv=min(minv,temp.minv);//左边有交集
		}
		node temp={0,0,minv,maxv};
        return temp;
    }
}
void modify(int u,int x,int v)
//u是根,x是位置,v是值
{
    if(tr[u].l==x&&tr[u].r==x)
	{
		 tr[u].minv=v;//叶子
		 tr[u].maxv=v;
	}
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid) modify(u*2,x,v);
		else modify(u*2+1,x,v);
		pushup(u);
    }
}
int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
 	for(int i=1;i<=n;i++)  modify(1,i,w[i]);
	while(m--)
	{
		int op,x,y; cin>>op>>x>>y;
		if(op==1) modify(1,x,y);
		else
		{
			node temp=query(1,x,y);
			if((temp.maxv-temp.minv)==(y-x)) puts("YES");
			else puts("NO");
		}
	}
    return 0;
}

使徒袭来【二分】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
int main(void)
{ 
	int n; cin>>n;
	double l=1,r=n;
	while(r-l>1e-6)
	{
		double mid=(l+r)/2;
		if(mid*mid*mid>=n) r=mid;
		else l=mid;
	}
	printf("%.3lf",l*3);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(void)
{ 
	int n; cin>>n;
	printf("%.3lf",3.0*pow(n,1.0/3));
	return 0;
}

核弹剑仙【dfs / 拓扑】

在这里插入图片描述
暴力dfs

#include<bits/stdc++.h>
using namespace std;
const int N=1e3*2+10;
int h[N],e[N],ne[N],idx;
int d[N],st[N],cnt[N],n,m;
bitset<1005>f[N];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
	st[u]=1;
	int sum=0;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(st[j]) continue;
		sum+=dfs(j);
	}
	return sum+1;
}
int main(void)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--)
	{
		int a,b; cin>>a>>b;
		add(b,a); 
	}
	for(int i=1;i<=n;i++) 
	{
		memset(st,0,sizeof st);
		cout<<dfs(i)-1<<'\n';
	}
	return 0;
}

拓扑

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idx;
int d[N],cnt[N],n,m;
bitset<1005>f[N];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort()
{
	queue<int>q; 
	for(int i=1;i<=n;i++) if(!d[i]) q.push(i);
	while(q.size())
	{
		int u=q.front(); q.pop();
		for(int i=h[u];i!=-1;i=ne[i])
		{
			int j=e[i];
			f[j]|=f[u],f[j][u]=1;
			if(--d[j]==0)  q.push(j);
		}
	}
}
int main(void)
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--)
	{
		int a,b; cin>>a>>b;
		add(a,b); d[b]++;
	}
	topsort();
	for(int i=1;i<=n;i++) cout<<f[i].count()<<endl;
	return 0;
}

虚空之力【贪心】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
string s1="ing";
int cnt[35],n;
string s;
int main(void)
{ 
	cin>>n>>s;
	for(int i=0;i<s.size();i++) cnt[s[i]-'a']++;
	int minv=1e9;
	for(int i=0;i<s1.size();i++) minv=min(minv,cnt[s1[i]-'a']);
	int sum=0;
	int temp=min(cnt['k'-'a'],minv/2);
	sum+=temp*2;
	cnt['k'-'a']-=temp,minv-=temp*2;
	temp=min(cnt['k'-'a'],minv);
	sum+=temp;
	cout<<sum;
	return 0;
}

社团游戏【前缀和】

在这里插入图片描述
暴力前缀和+剪枝。

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,k;
int s[N][N][26];
char c[N][N];
void init(int x,int y)
{
	for(int i=0;i<26;i++) 
		s[x][y][i]=s[x-1][y][i]+s[x][y-1][i]-s[x-1][y-1][i];
	s[x][y][c[x][y]-'a']++;
}
bool check(int x,int y,int xx,int yy)
{
	for(int i=0;i<26;i++)
	{
		int sum=s[xx][yy][i]-s[x-1][yy][i]-s[xx][y-1][i]+s[x-1][y-1][i];
		if(sum>k) return false;
	}
	return true;
}
int main(void)
{ 
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
	cin>>n>>m>>k; 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) cin>>c[i][j];
	if(k<=0)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cout<<0<<' ';
			}
			cout<<'\n';
		}
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) init(i,j);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
            int temp=min(n-i+1,m-j+1);
            int ans=0;
			for(int len=1;len<=temp;len++)
			{
				int x=i,y=j;
				int xx=i+len-1,yy=j+len-1;
                if(len*len<=k)
                { 
                    ans=max(ans,len);
                    continue;
                }
				if(check(x,y,xx,yy)) ans=max(ans,len);
				else break;
			}
            cout<<ans<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

前缀和+二分

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,k;
int s[N][N][26];
char c[N][N];
void init(int x,int y)
{
	for(int i=0;i<26;i++) 
		s[x][y][i]=s[x-1][y][i]+s[x][y-1][i]-s[x-1][y-1][i];
	s[x][y][c[x][y]-'a']++;
}
bool check(int x,int y,int xx,int yy)
{
	for(int i=0;i<26;i++)
	{
		int sum=s[xx][yy][i]-s[x-1][yy][i]-s[xx][y-1][i]+s[x-1][y-1][i];
		if(sum>k) return false;
	}
	return true;
}
int main(void)
{ 
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
	cin>>n>>m>>k; 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) cin>>c[i][j];
	if(k<=0)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cout<<0<<' ';
			}
			cout<<'\n';
		}
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) init(i,j);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
            int temp=min(n-i+1,m-j+1);
			int l=0,r=temp;
			while(l<r)
			{
				int mid=(l+r+1)/2;
				if(check(i,j,i+mid-1,j+mid-1))l=mid;
				else r=mid-1;
			}
            cout<<l<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

名作之壁【单调栈】

逃跑路线【思维】

在这里插入图片描述
只需判数的奇偶即可。

#include<bits/stdc++.h>
using namespace std;
int main(void)
{ 
	int n; cin>>n;
	int ans=0;
	while(n--) 
	{
		string s; cin>>s;
		int w=(s[s.size()-1]-'0');
		if(w&1) ans++;
		ans=ans%2;
	}
	cout<<ans;
	return 0;
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-16 11:26:44  更:2022-05-16 11:27:58 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 1:40:14-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码