2022年湖南工学院ACM集训第二次周测题解

A题 Will的失踪

来源：改编自解救

考察：约瑟夫问题的掌握程度

难度：橙题

本题是经典得约瑟夫问题，区别在于报数是固定为 2，且只需要输出最后一个人的编号，不懂的去搜约瑟夫问题。

B题 圣诞灯光

来源：改编自表达式括号匹配

考察：栈的基本运用

难度：橙题

本题用一个stack去存括号，若当前括号为 { ，则放入stack，否则检查stack是否有 { 或为空即可。

C题 霍金斯镇的地底

来源：改编自[JLOI2009]二叉树问题

考察：二叉树的基本运用

难度：橙题

本题可以用 dfs 实现对深度的求解，并在dfs的过程中记录每层的节点数量，最后找出最大的即为宽度。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,fa[1005],de[1005],tot,head[1005],s,kuan,shen,pika[1005];
struct node
{
	int to,next;
}edge[1005];
void add(int u,int v)
{
	edge[++tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot;
}
void dfs(int x,int fath)
{
	fa[x]=fath;
	de[x]=de[fath]+1;
	for(int i=head[x];i;i=edge[i].next)
	{
		if(edge[i].to!=fath)
		{
			dfs(edge[i].to,x);
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		shen=max(de[i],shen);
		pika[de[i]]++;
	}
	for(int i=1;i<=shen;i++)
	{
		kuan=max(kuan,pika[i]);
	}
	cout<<shen<<" "<<kuan<<endl;
    return 0;
}

D题 最佳保姆

来源：牛客小白月赛6 H题-挖沟

考察：图论，最小生成树

难度：黄题

本题为最小生成树Kruskal板子题，不懂的可以去搜一下。

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int s,t,d;
	bool operator<(const edge& y)const
	{
		return d<y.d;
	}
}e[500005];
int n,m,i,f[100005],ans;
int get(int x)
{
	if(f[x]==x)return x;
	return f[x]=get(f[x]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)f[i]=i;
	for(i=1;i<=m;i++)scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].d);
	sort(e+1,e+m+1);
	for(i=1;i<=m;i++)if(get(e[i].s)!=get(e[i].t))
	{
		ans+=e[i].d;
		f[get(e[i].s)]=get(e[i].t);
	}
	cout<<ans<<endl;
	return 0;
}

E题 冬日舞会

来源：周末舞会

考察：队列的基本运用

难度：橙题

本题为用queue存一下编号，若当前此人跳完了舞则出队列并重新加入队列即可，以此类推。

F题 星城之战(Easy Version)

来源：改编自牛客练习赛101 B题-荒神在此

考察：dp(状态机)

难度：黄题

对于每一位而言，他的总和奇偶性跟上一位是相关的，若上一位贡献为偶数，那么我们当前位贡献也得是偶数，否则就为奇数。若当前位 i 为偶数则 0-i 之间恰好只有 i - i / 2 + 1 个偶数使得当前位贡献为偶数，i / 2 个奇数使得当前位贡献为奇数，因为偶数 + 奇数 = 奇数。对于 i 为奇数时，不难发现偶数和奇数个数均为 (i + 1) / 2。算出奇数偶数个数后直接dp转移即可。

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 998244353;
using namespace std;
ll dp[20202000][3];//第二维的0代表偶数，1为奇数
int main() {
	int n;
	cin >> n;
	dp[1][0] = 1, dp[1][1] = 1;
	for (ll i = 2; i <= n; i++) {
		ll x, y; //x 为当前位贡献为奇数的个数，y 为偶数
		if (i % 2 == 0) {
			x = i / 2, y = i + 1 - i / 2;
		}
		else {
			x = (i + 1) / 2, y = (i + 1) / 2;
		}
		dp[i][1] = dp[i - 1][0] * x % mod;
		dp[i][1] = (dp[i][1] + dp[i - 1][1] * y) % mod;
		dp[i][0] = dp[i - 1][1] * x % mod;
		dp[i][0] = (dp[i][0] + dp[i - 1][0] * y) % mod;
	}
	cout << dp[n][0] % mod;
	return 0;
}

G题 星城之战(Hard Version)

来源：改编自牛客练习赛101 B题-荒神在此

考察：dp(状态机)，数论(整除分块)

难度：绿题

dp的方程跟 F 题一致，唯一的区别在于如何求出奇数偶数个数，本题由于数据范围较大，若暴力求解各 i 所拥有的奇数偶数个数，那么时间复杂度高达，而数据范围为 1e5，极限情况为 1e10，显然会超时。因此本题需要使用整除分块的思想，时间复杂度可以优化至，极限情况为 3e7 左右，不会超时。关于整除分块的做法可以参考【数论】整除分块（数论分块）_辞树c的博客-CSDN博客_整除分块题目。

FG两题也可以用自己枚举一些数，然后找规律，不难发现。