Solution to the second weekly test of ACM intensive training of Hunan Institute of technology in 2022

A topic Will Missing

source ： Adapted from rescue

Investigate ： Joseph's mastery of the problem

difficulty ： Orange question

This problem is the classic Joseph problem , The difference is that the number is fixed as 2, And only need to output the number of the last person , If you don't understand, search Joseph's question .

B topic Christmas lights

source ： Adapted from expression bracket matching

Investigate ： The basic use of stack

difficulty ： Orange question

This topic uses a stack Remove bracket , If the current bracket is { , Put in stack, Otherwise check stack Is there a { Or empty .

C topic Under Hawkins

source ： Based on the [JLOI2009] Binary tree problem

Investigate ： Basic application of binary tree

difficulty ： Orange question

This question can be used dfs Realize the solution of depth , And in dfs Record the number of nodes in each layer , Finally, find the largest is the width .

#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 topic Best nanny

source ： Niuke Xiaobai moon race 6 H topic - ditch

Investigate ： graph theory , Minimum spanning tree

difficulty ： Yellow title

This topic is called minimum spanning tree Kruskal Board question , Those who don't understand can search .

#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 topic Winter dance

source ： Weekend dance

Investigate ： The basic use of queues

difficulty ： Orange question

This topic is to use queue Save the number , If the current person finishes dancing, just get out of the queue and rejoin the queue , And so on .

F topic Battle of Star City (Easy Version)

source ： Adapted from Niuke practice race 101 B topic - God of famine is here

Investigate ：dp( State machine )

difficulty ： Yellow title

For everyone , His sum parity is related to the next one , If the previous contribution is even , Then our current contribution must be even , Otherwise, it will be odd . If current bit i For even numbers 0-i There is just i - i / 2 + 1 An even number makes the current bit contribution an even number ,i / 2 Odd numbers make the current bit contribution odd , Because even numbers + Odd number = Odd number . about i In an odd number of , It is not difficult to find that even and odd numbers are (i + 1) / 2. Calculate the odd and even numbers and then directly dp Just transfer .

#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];// The second dimension is 0 For even numbers ,1 It's odd 
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  Contribute an odd number to the current bit ,y  For the even 
		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 topic Battle of Star City (Hard Version)

source ： Adapted from Niuke practice race 101 B topic - God of famine is here

Investigate ：dp( State machine ), number theory ( Divide and divide )

difficulty ： Green topic

dp The equation of follows F Consistent questions , The only difference is how to find odd and even numbers , Due to the large range of data , If violence solves each i The odd and even numbers owned , Then the time complexity is as high as , The data range is 1e5, The limit case is 1e10, Obviously it's going to be overtime . Therefore, this topic needs to use the idea of dividing into blocks , The time complexity can be optimized to , The limit case is 3e7 about , No timeout . For the practice of dividing and dividing blocks, please refer to 【 number theory 】 Divide and divide （ Number theory is divided into blocks ）_ Ci tree c The blog of -CSDN Blog _ Divide into blocks .

FG You can also enumerate some numbers by yourself , And find the rules , It's not hard to find out .