• 2018HBCPC个人题解

    文章目录

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

    A. Mex Query

    A. Mex Query

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

    #include
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;
			}
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    B. icebound 的商店

    在这里插入图片描述

    就嗯完全背包。

    #include
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;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    C. Nim Game

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

    #include
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    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;//记录重心 
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    在这里插入图片描述
    找到一个点x，使得 F ( x ) = ∑ w ( i ) ∗ d ( x , i ) F(x)=\sum{w(i)}*d(x,i) F(x)=∑w(i)∗d(x,i)最小，w(i)是结点i的权值，d(x,i)是d到i的距离。

    #include
#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:"<
	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:"<
	memset(vis,0,sizeof(vis));
	cout<<dfs(pos,0);
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76

    F. 神殿

    在这里插入图片描述

    QAQ QAQ QAQ QAQ QAQ

    #include
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;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    G. K Multiple Longest Commom Subsequence

    在这里插入图片描述

    首先看看经典LCS

    #include
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;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

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

    #include
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    H. 跑图

    在这里插入图片描述
    BFS。

    #include
#include
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:"<
		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;
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    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
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    L. icebound的账单

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

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

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

    #include
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;
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
  • 相关阅读:
    osi七层模型
    STM32--EXTI外部中断
    构建白平衡色温坐标系
    JSP语法基础习题
    R语言颜色细分
    [Java Base]Java 8 ~ Java17新特性
    军训场G,H
    记一次生产环境内存占用过高的排查
    LayUi-----------用户管理
    2023年03月 C/C++（八级）真题解析#中国电子学会#全国青少年软件编程等级考试
  • 原文地址：https://blog.csdn.net/m0_60630928/article/details/126073588