2018HBCPC个人题解

---

补了八道，人又懒了。C.D.F.G题还是挺好的2333.

A. Mex Query

A. Mex Query

这大概是快一年前写的题了2333. 显然答案肯定不会超过200000.

#include<bits/stdc++.h>
using namespace std;
int T,a[200010];

int main()
{
    
	cin>>T;
	while(T--)
	{
    
		memset(a,0,sizeof(a));
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
    
			int x;
			scanf("%d",&x);
			if(x<=200010) a[x]++;
		}
		for(int i=0;i<=200010;i++)
		{
    
			if(!a[i])
			{
    
				cout<<i<<endl;
				break;
			}
		}
	}
}

---

B. icebound 的商店

就嗯完全背包。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+9;
int T,x,w[20],dp[3010];

int main()
{
    
	cin>>T;
	w[1]=1,w[2]=2;
	for(int i=3;i<=15;i++)
		w[i]=w[i-1]+w[i-2];
	dp[0]=1;
	for(int i=1;i<=15;i++)
		for(int j=w[i];j<=3000;j++)
			dp[j]+=dp[j-w[i]],dp[j]%=mod;
	while(T--)
	{
    
		int x;
		cin>>x;
		cout<<dp[x]<<endl;
	}
    return 0;
}

---

C. Nim Game

虽然之前看了一下尼姆博弈，但仍然觉得是玄学，直接白嫖代码了。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long t,n,m;//数据组数，堆数，游戏局数 
long long arr[1000005];//异或 
long long l,r; //区间左端和右端 
long long x,a;//区间异或的结果、每次读入的堆数 
long long ans;//结果 

long long p(long long b)
{
    
    long long a,c;
    long long int ans1,base;
    a=2;
    c=1000000000+7;
    ans1=1;
    base=a%c;
    while(b!=0)
    {
    
        if(b&1==1) ans1=(ans1*base+c)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return ans1;
}

int main()
{
    
	scanf("%lld",&t);
	while(t--)
	{
    
		ans=0;
		scanf("%lld%lld",&n,&m);
		scanf("%lld",&a);
		arr[0]=0;//注意设置一下arr[0] 
		arr[1]=a;
		for(int i=2;i<=n;i++)
		{
    
			scanf("%lld",&a);
			arr[i]=arr[i-1]^a;
		}
		for(int i=1;i<=m;i++)//第几次游戏 
		{
    
			scanf("%lld%lld",&l,&r);
			x=arr[r]^arr[l-1];
			if(x)
			{
    
				ans+=p(m-i);
				ans%=mod;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

---

D. Defending Plan Support

水博客的妙招：自我引用——

题目不给明哪个是根结点（所有节点都可以是根结点），可以通过一次dfs找到树的重心来尽量避免“树大根深”的情况。
树的重心：设max_part(x)表示在删除结点x后产生的子树中，最大的一棵的大小。使得max_part取最小值的结点p即为树的重心。

void dfs(int x)
{
    
	vis[x]=1;size[x]=1;//子树x的大小 
	int max_part=0;
	for(int i=head[x];i;i=nex[i])
	{
    
		int y=ver[i]; 
		if(vis[y]) continue;
		dfs(y);
		size[x]+=size[y];
		max_part=max(max_part,size[y]);//找最大子树 
	}
	max_part=max(max_part,n-size[x]);
	if(max_part<ans)
	{
    
		ans=max_part;//记录重心对应的最大子树规模 
		pos=x;//记录重心 
	}
}

找到一个点x，使得$F(x)=\sum w(i)\ast d(x,i)$最小，w(i)是结点i的权值，d(x,i)是d到i的距离。

#include<bits/stdc++.h>
#define llg long long
#define inf 0x3ffffff

using namespace std;

const int N=1e6+10;
int head[N],ver[N],nex[N],val[N],tot,n,dis[N],vis[N];
int size[N],pos,max_size,ans=inf;
long long minn=1e15;

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

void add(int x,int y,int z)
{
    
	ver[++tot]=y,dis[tot]=z,nex[tot]=head[x],head[x]=tot;
}

void dfs1(int x)
{
    
	vis[x]=1,size[x]=1;
	int max_size=0;
	for(int i=head[x];i;i=nex[i])
	{
    
		if(vis[ver[i]]) continue;
		vis[ver[i]]=1;
		dfs1(ver[i]);
		size[x]+=size[ver[i]];
		max_size=max(max_size,size[ver[i]]);
	}
	max_size=max(max_size,n-size[x]);
	if(max_size<ans)
	{
    
		ans=max_size;
		pos=x;
	}
}
long long dfs(int x,int d)
{
    
	//cout<<"x:"<<x<<" d:"<<d<<endl;
	vis[x]=1;
	long long sum=0;
	for(int i=head[x];i;i=nex[i])
	{
    
		if(vis[ver[i]]) continue;
		vis[ver[i]]=1;
		sum+=val[ver[i]]*(dis[i]+d);
		sum+=dfs(ver[i],dis[i]+d);
	}
	return sum;
}

int main()
{
    
	n=read();
	for(int i=1;i<n;i++)
	{
    
		int x=read(),y=read(),z=read();
		add(x,y,z);
		add(y,x,z);
	}
	for(int i=1;i<=n;i++)
		val[i]=read();
	dfs1(1);//找重心 
	//cout<<"pos:"<<pos<<endl;
	memset(vis,0,sizeof(vis));
	cout<<dfs(pos,0);
    return 0;
}

---

F. 神殿

QAQ QAQ QAQ QAQ QAQ

#include<iostream>
using namespace std;
int main()
{
    
    long long l,r;
    scanf("%lld %lld",&l,&r);
    while(l<=r)                                    
    {
                                                   
        if((l|l+1)>r)//(l|l+1)最低位的0变成1,大于r了变不成 
        break;
        l++;
    }
    printf("%lld",l);
    return 0;
}

---

G. K Multiple Longest Commom Subsequence

首先看看经典LCS

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],b[N],dp[N][N];
int n,m;
int main()
{
    
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
    
			dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
			if(a[i]==b[j])
			dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
		}
	
	cout<<dp[n][m];
    return 0;
}

然后把K个元素视作一个整体就可以了（=要加预处理）

#include<bits/stdc++.h>
using namespace std;
int T,n,m,k;
const int N=1010;
int a[N],b[N],c[N],d[N],dp[N][N];
inline int read()
{
    
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){
    if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){
    x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main()
{
    
	T=read();
	while(T--)
	{
    
		memset(dp,0,sizeof(dp));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
		k=read(),n=read(),m=read();
		queue<int>qa[N],qb[N];
		for(int i=1;i<=n;i++)
		{
    
			a[i]=read();
			qa[a[i]].push(i);
			if(qa[a[i]].size()==k)
			{
    
				c[i]=qa[a[i]].front();
				qa[a[i]].pop();
			}
		}
		for(int j=1;j<=m;j++)
		{
    
			b[j]=read();
			qb[b[j]].push(j);
			if(qb[b[j]].size()==k)
			{
    
				d[j]=qb[b[j]].front();
				qb[b[j]].pop();
			}
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
    
				dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
				if(a[i]==b[j]&&c[i]&&d[j])
				dp[i][j]=max(dp[i][j],dp[c[i]-1][d[j]-1]+k);
			}
		cout<<dp[n][m]<<endl;
	}
    return 0;
}

---

H. 跑图

BFS。

#include<bits/stdc++.h>
#include<vector>
using namespace std;
int n,m;
int mp[520][520],dis[520][520],cnt,vis[520][520];
int dx[4]={
    0,-1,0,1};
int dy[4]={
    1,0,-1,0};
struct Node
{
    
	int x,y;
};
queue<Node> q;

int main()
{
    
	cin>>n>>m;
	memset(dis,0x7f,sizeof(dis));
	for(int i=1;i<=n;i++)
	{
    
		for(int j=1;j<=m;j++)
		{
    
			cin>>mp[i][j];
			if(mp[i][j])
			{
    
				q.push((Node){
    i,j});
				dis[i][j]=0;
				vis[i][j]=1;
			}
		}
	}
	while(q.size())
	{
    
		Node temp=q.front();
		q.pop();
		//cout<<"temp.x:"<<temp.x<<" temp.y:"<<temp.y<<endl;
		for(int i=0;i<4;i++)
		{
    
			int x1=temp.x+dx[i],y1=temp.y+dy[i];
			if(x1>0&&x1<=n&&y1>0&&y1<=m)
			{
    
				dis[x1][y1]=min(dis[x1][y1],dis[temp.x][temp.y]+1);
				if(!vis[x1][y1])
				{
    
					vis[x1][y1]=1;
					q.push((Node){
    x1,y1});
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
    
		for(int j=1;j<m;j++)
		{
    
			cout<<dis[i][j]<<' ';
		}
		cout<<dis[i][m]<<endl;
	}
    return 0;
}

---

K. 520

“又到了五月了呢”，icebound望着五月的天空，眼角流出了泪痕。那一年，icebound还是一个懵懂的少年。那一年，她还是一个青涩纯真的少女。在那一次偶然的相遇之中，他们之间擦出了爱情的火花。他们欢笑着，奔跑着，他们展望着美好的未来，向往着幸福的明天。她像 icebound 心海中的灯塔，像icebound 头顶上的星辰，即使在海里浮沉，即使在夜里摸爬，心中也不会感到迷茫，感到阴寒。他们努力，奋进，向着六月的那一站前行。可是，美好总是短暂的。那海上的灯塔不再发出温情的光亮，那天空中的星辰不再绽放出温柔的色彩。那一站，到达了，icebound 得到了终点，但icebound 永远失去了她，也失去了他的心。

”侯门一入深似海，从此萧郎是路人“

今天是2018年5月20日，又是一年的520。这一天，icebound不小心读到上面的诗，icebound沉思着，回想起与她曾经的快乐时光，icebound留下了nn滴眼泪。icebound的每滴眼泪都带有太多的伤感之情了，以至于每滴眼泪都会感染到其他的生物，使得许多生物都一起掉下了眼泪。kk通过观察得知，当icebound流出nn滴眼泪时，所有生物产生的眼泪总数为2^n
。现在，kk需要你帮助他写一个程序，计算当icebound流出nn滴眼泪时，所有生物产生的眼泪总数P，对 20180520取模。

#include<bits/stdc++.h>
using namespace std;
const int mod=20180520;
int n;

int main()
{
    
	cin>>n;
	long long ans=1,base=2;
	while(n)
	{
    
		if(n&1) ans=ans*base%mod;
		n>>=1;
		base=base*base%mod;
	}
	cout<<ans;
    return 0;
}

---

L. icebound的账单

icebound从小就有记账的习惯。又到了月末icebound统计资金状况的时候。icebound每个月除了不停的挥霍以外，有时他会良心发现，勤工俭学，因此会有一些微薄的收入。然而icebound数学不好，需要你来帮助他统计他本月的资金状况。

你将会得到一份icebound的账单，一共有 n​ 行整数，其中正数表示icebound打工挣来的收入，负数表示icebound消费的支出。数据保证不会出现 0​ 。

如果icebound本月总收入大于总支出，请你输出“icebound is happy.”；如果本月总收入等于总支出，请你输出“icebound is ok.“；如果总收入小于总支出，请你输出"icebound is sad.”。

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
    
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){
    if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){
    x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,temp;
int main()
{
    
	n=read();
	for(int i=1;i<=n;i++)
	{
    
		int x=read();
		temp+=x;
	}
	if(temp<0) cout<<"icebound is sad.";
	if(temp==0) cout<<"icebound is ok.";
	if(temp>0) cout<<"icebound is happy.";
    return 0;
}

---