牛客白月赛29【题解】

https://ac.nowcoder.com/acm/contest/8564

• 进攻【贪心+二分】
• 二进制【位运算 思维】
• 积木【构造】
• 种树【贪心】
• 考试
• 项链【双链表模拟】
• 涂色
• 圆【圆的相切】
• 修改【思维 构造最小生成树】
• 克隆【欧拉序列】

前缀最大数组，然后二分找。

#include
using namespace std;
typedef long long int LL;

const int N=1e6+10;
const int mod=1e9+7;

int n,m,a[N],maxv[N],b[N],x[N],y[N];

struct node{int x,y;};
vectorve;
mapmp;

int main(void)
{ 
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>x[i];
	for(int i=1;i<=m;i++) cin>>y[i];
	for(int i=1;i<=m;i++) mp[x[i]]=max(mp[x[i]],y[i]);
	for(auto i=mp.begin();i!=mp.end();i++) 
		ve.push_back({i->first,i->second});
	maxv[0]=max(ve[0].y,0);
	for(int i=1;imaxv[i-1],ve[i].y,0});
	for(int i=0;i
		int index=lower_bound(b,b+k,a[i])-b;
		index--;
		if(index<0) continue;
		ans+=maxv[index];
	}
	cout< 
二进制【位运算 思维】 

 位运算的题目大部分都是只需考虑各个位即可。
 本题，只需操作三次即可。与，或，异或个一次。
 
#include
#define x first
#define y second
using namespace std;
typedef pair pii;
vectorve;
int main(void)
{
	int n; cin>>n;
	for(int i=0;i
		int a,b; cin>>a>>b;
		ve.push_back({a,b});
	}
	int a=(1<<20)-1,b=0,c=0;//与 或 异或  a=全1 目的是任意一个数与都是本身 
	for(int i=0;i<20;i++)
	{
		int w1=0,w2=1;//当前位是0 当前位是1
		for(int j=0;j
			int op=ve[j].x,w=ve[j].y;
			int now=0;
			if(w>>i&1) now=1;
			if(op==1)
			{
				w1=w1&now;
				w2=w2&now;
			}
			if(op==2)
			{
				w1=w1|now;
				w2=w2|now;
			}
			if(op==3)
			{
				w1=w1^now;
				w2=w2^now;
			}
		}
		if(w1==0&&w2==0) a-=(1< 
积木【构造】 
构造题咕咕了。
 
种树【贪心】 

 贪心，先用完小的再用大的。
 
#include 
using namespace std;
const int N=1e5*5+10;
int n,m,ans,l[N],r[N],w[N],d[N];
void dfs(int u,int d)
{
    if(!l[u])//不是叶子
	{
        if(d<=m) ans=max(ans,w[u]);//且可以是大剪刀
        return;     
    }
    dfs(l[u],d+1),dfs(r[u],d+1);
}
int main(void)
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b; cin>>a>>b;
		l[i]=a,r[i]=b;
	}
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++) if(l[i]&&r[i]) m++;
    m=(m+1)/2;//大剪刀
	dfs(1,0);
	cout< 
考试 
 
#include
using namespace std;

const int N=1e6+10;
const int mod=1e9+7;

int n,m,a[N],b[N];

int main(void)
{ 
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	int cnt=0;
	for(int i=1;i<=n;i++) if(a[i]==b[i]) cnt++;//相等的
	int ans=min(cnt,n-m)+min(n-cnt,m);
	cout< 
项链【双链表模拟】 
咕咕了
 
涂色 
 
#include
int main(void)
{
    int n,sum=0;
    while( scanf("%d",&n) != EOF )
    {
        sum=n+1;
        printf("%dn",sum%998244353);
    }
}
 
圆【圆的相切】 
 
#include
using namespace std;
typedef unsigned long long int LL;
int main(void)
{ 
	int t; cin>>t;
	while(t--)
	{
		LL x1,y1,r1,x2,y2,r2; cin>>x1>>y1>>r1>>x2>>y2>>r2;
		LL len=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
		if(len<(r1-r2)*(r1-r2))
		{
			puts("NO");
			continue;
		}
		if(len<=(r1+r2)*(r1+r2)) puts("YES");
		else puts("NO");
	}
	return 0;
}

 
修改【思维 构造最小生成树】 

 
 
#include
using namespace std;
typedef long long int LL; 
const int N=1e5*5+10;
int p[N],n,m; 
struct node{int a,b,c;};
bool cmp(node a,node b){return a.cve;
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
void solve()
{
	for(int i=1;i<=n;i++) p[i]=i;
	sort(ve.begin(),ve.end(),cmp);
	LL sum=0;
	for(int i=0;i
		int a=ve[i].a,b=ve[i].b,c=ve[i].c;
        if(find(a)==find(b)) continue;
		p[find(a)]=find(b);
		sum+=c;
	}
    mapmp;
    for(int i=1;i<=n;i++) mp[find(i)]++;
	if(mp.size()==1) cout<
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b,c; cin>>a>>b>>c;
		ve.push_back({a,b+1,c});
	}
	solve();
	return 0;
}
 
克隆【欧拉序列】 

 
 就是求欧拉序列，然后分组输出即可。
 
#include
using namespace std;
const int N=1e5*5+10;
int n,m,k;
int h[N],e[N],ne[N],idx,len,ans[N];
vectorve;
stackst;
mapmp;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
	mp[u]=1;
	ans[++len]=u; 
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(mp[j]) continue;
		dfs(j);
		ans[++len]=u;
	}
	return;
}
int main(void)
{
	memset(h,-1,sizeof h);
	cin>>n>>m>>k;
	while(m--)
	{
		int a,b; cin>>a>>b;
		add(a,b),add(b,a);
	}
	dfs(1);
	puts("YES");
	int w=ceil(2.0*n/k);
	queueq;
	for(int i=1;i<=len;i++) q.push(ans[i]);
	for(int i=1;i<=k&&q.size();i++)
	{
		int temp=min(w,(int)q.size());
		cout<
			cout<<" "<