本次比赛B C G H I K 题解

td1336065617 (codeforces max rating <1200 ) 出题：B C G H I K 其他题解请等，另一个出题人。

A.HHDU

知识点 输出语句 很明显输出 HHDU2025就行了

#include <iostream>
using namespace std;

int main() {
    cout << "HHDU2025" << endl;
    return 0;
}

B.是否大于2025

知识点 分支语句 按题面来就行了，判断一下。

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin>>a;
    if(a>2025){
        cout<<"YES";

    }else if(a<2025){
        cout<<"NO";

    }else{
        cout<<"=";
    }
}

C.K的倍数

按题面来，直接循环判断取余结果是否为0就行了

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int n, k, a[110000],num;
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] % k==0)
        {
            num++;
        }
    }
    cout << num;
    return 0;
}

G.丧尸塔防

1. 问题分析：
   • 病毒从城市1（DC）开始传播，通过道路向相连的城市扩散。
   • 建设堡垒的城市可以阻断病毒的传播路径。即一旦病毒到达某个未设堡垒的城市，该城及其所有子节点（未被阻挡的路径上）都会被感染。
   • 我们需要选择K个城市作为堡垒，使得未被感染的城市总人口最大。
2. 关键观察：
   • 阻断传播等价于在病毒的传播树上切断某些边。选择哪些边（对应哪些城市）作为堡垒是关键。
   • 阻断一个城市可以保护其子树的所有未被感染的城市。
   • 最优策略是选择那些可以保护最多人口的路径。
3. 贪心策略：
   • 在病毒的传播树（以城市1为根）中，对于每个节点计算其子树的总人口（包括自身）。
   • 贪心地选择子树人口最大的K个节点作为堡垒，这样能够最大化未被感染的人口。
4. 算法步骤：
   • 构建树结构：将输入的道路信息转化为树结构，根节点为城市1（DC）。
   • 计算子树人口：使用深度优先搜索（DFS）或后序遍历计算每个节点的子树总人口。
   • 选择最优堡垒：将子树人口排序，选择前K大的节点（不包括根节点，因为根节点已经被感染）。

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int N, K;
long long int Pi[110000];
int qxx_top[10000000],syd,jyh[110000];
struct dl {
    int next;
    int zd;
}qxx[1100000];
void add_qxx(int qd, int zd)
{
    qxx[++syd].next = qxx_top[qd];
    qxx[syd].zd = zd;
    qxx_top[qd] = syd;
}
long long int dfs(int x,int fx) {
    jyh[x] = 1;//验证数据用的
    long long int sum = Pi[x];
    for (size_t i = qxx_top[x]; i != 0; i = qxx[i].next)
    {
        if (qxx[i].zd!=fx) {
            if (jyh[qxx[i].zd] == 1)
            {
				exit(-10086);
                //验证数据是不是一棵树 如果存在边连接向非父节点的走过的点显然不是树
            }
            sum += dfs(qxx[i].zd,x);
        }
    }
    return sum;
}
vector<long long int> ans;
int main() {
    cin >> N >> K;
    if(N<1||K>1e5||K<1||K>1e5)
    return -1;
    for (int i = 1; i <= N; i++)
    { 
        cin >> Pi[i];
    }
    for (int i = 1; i < N; i++)
    {
        int u, v;
        cin >> u>>v;
         if(u<1||u> N||v<1||v> N)
          return -1;
		add_qxx(u, v);
		add_qxx(v, u);
    }
    jyh[1] = 1;
    for (int i = qxx_top[1]; i!=0; i=qxx[i].next)
    {
        ans.push_back(dfs(qxx[i].zd,1));
	}
    sort(ans.begin(), ans.end());
    long long int sum = 0;
    for (int i = ans.size()-1,j=1; i >= 0&&j<=K; i--,j++)
    {
        sum += ans[i];
    }
    cout << sum;
	return 0;
}

H.榜单重建

根据题面要求的规则，以提交时间升序排序，然后同时间AC在前，排序一下就行了，

实际上就是根据题面要求排序，然后通过队伍TeamName 和 ProblemID ,然后计算每题罚时和通过与否。

然后继续队伍罚时，排序一下，根据题面要求进行排名就行了。

如果WA了，那就是读题不仔细，我加粗那一堆都是排序和排名相关的细节，认真读题就能过。

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int n, m;
struct cpjl {
    long long int h, m, s, sum_s;
    string TeamName, ProblemID, Result;
};
vector<cpjl> cpjl_list;
unordered_map<string, int> team_map;
static bool cmp(cpjl& q, cpjl& p) {
 if (q.sum_s == p.sum_s)
   {
       if (q.Result == "AC"&&p.Result != "AC") {
           return true;
       }
       else if (q.Result != "AC" && p.Result == "AC") {
           return false;
       }
       else{
           return false;
       }
   }
   return q.sum_s < p.sum_s;
}
struct chengji {
    string TeamName;
    long long int time_sum;
    int ac_num;
    map<string, int> problem_map,time_p_map;
};
bool cmp_chengji(chengji& q, chengji& p) {
    if (q.ac_num != p.ac_num) {
        return q.ac_num > p.ac_num;
    }
    else {
        if (q.time_sum != p.time_sum)
            return q.time_sum < p.time_sum;
        else
        {
            return q.TeamName < p.TeamName;
        }
    }
}
map<string, chengji > team_score_map;
vector<chengji> chengji_list;
int main() {
    //cdx();
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cpjl cpjl1;
        char TeamName[210], ProblemID[210], Result[210];
        scanf("%lld:%lld:%lld %s %s %s", &cpjl1.h, &cpjl1.m, &cpjl1.s, &TeamName, &ProblemID, &Result);
        cpjl1.TeamName = TeamName;
        if (cpjl1.TeamName.length() > 200 || cpjl1.TeamName.length() < 1)return -2;
        cpjl1.Result = Result;
        cpjl1.ProblemID = ProblemID;
        cpjl1.sum_s = cpjl1.h * 3600 + cpjl1.m * 60 + cpjl1.s;
        cpjl_list.push_back(cpjl1);
    }
    sort(cpjl_list.begin(), cpjl_list.end(), cmp);
    for (int i = 0; i < cpjl_list.size(); i++)
    {
        if (cpjl_list[i].Result == "AC") {

            if (team_score_map[cpjl_list[i].TeamName].problem_map[cpjl_list[i].ProblemID] == 0)
            {
                
                team_score_map[cpjl_list[i].TeamName].problem_map[cpjl_list[i].ProblemID] = 1;
                team_score_map[cpjl_list[i].TeamName].time_p_map[cpjl_list[i].ProblemID] += cpjl_list[i].sum_s;
                team_score_map[cpjl_list[i].TeamName].ac_num++;
            }
        }
        else {
            if (team_score_map[cpjl_list[i].TeamName].problem_map[cpjl_list[i].ProblemID] == 0)
            {
                team_score_map[cpjl_list[i].TeamName].time_p_map[cpjl_list[i].ProblemID] += 20 * 60;
            }
        }
    }
    for (auto& team_score_map1 : team_score_map)
    {
		team_score_map1.second.time_sum = 0;
        for(auto &time_js:team_score_map1.second.problem_map)
        { 
            if(time_js.second==1)
				team_score_map1.second.time_sum += team_score_map1.second.time_p_map[time_js.first];
        }
        team_score_map1.second.TeamName = team_score_map1.first;
        chengji_list.push_back(team_score_map1.second);
    }
    sort(chengji_list.begin(), chengji_list.end(), cmp_chengji);
    for (int i = 0, j = 1; i < chengji_list.size(); i++)
    {
        if (chengji_list[i].ac_num < 1)return 0;
        if (i != 0 && (chengji_list[i - 1].ac_num != chengji_list[i].ac_num || chengji_list[i - 1].time_sum != chengji_list[i].time_sum))
        {
            j++;
        }
        cout << j << " " << chengji_list[i].TeamName << " " << chengji_list[i].ac_num << " " << chengji_list[i].time_sum << endl;
    }
    return 0;
}

I.魔法学院选课

这题通过读题可知，其的关键点是，如何确定一门课什么时候能学，学过拓扑序的同学一眼就可以知道，这就是bfs跑拓扑序过程中，进行一下线性dp而已。

想不明白的同学建议先补一下知识点，拓扑排序。

然后DP部分，就很容易想明白了，一门课只可能从连接到他的节点中魔力值和最高的前置节点集合，其实就是在每个节点，向其可以连接的子节点尝试一下专业，如果从当前节点转以后，子节点的魔力值和变大就保留。

qxx[i].u当前节点连接的点，a[qxx[i].u]当前节点连接的点自带的魔力值，当前节点的魔力值dp[di]。

因为在跑拓扑序时候，入队列时候就已经不可能有前置节点可以到点di了。

所以dp[i]表示i点结尾的链条的最大可能魔法值和。

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int qxx_idx, qxx_top[1100000];
struct bian_struct {
	int u, v, next;
}qxx[1100000];
int add_qxx(int x, int y, int v) {
	qxx[++qxx_idx].next = qxx_top[x];
	qxx[qxx_idx].u = y;
	qxx[qxx_idx].v = v;
	qxx_top[x] = qxx_idx;
	return 0;
}
struct dian
{
	int xd;
	long long int v;
};
int n, m, rd[1000000];
long long int a[110000],dp[110000],sum=0;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		dp[i]=-1e15;
	}
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		add_qxx(u, v, 1);
		rd[v]++;
	}
	int num=0;
	queue<dian>dl;
	for (int i = 1; i <= n; i++)
	{
		if (rd[i] == 0)
		{
			dl.push({ i, a[i] });
			dp[i] = a[i];
		}
	}
	while (dl.size())
	{
		num++;
		int di = dl.front().xd;
		dl.pop();
		for (int i = qxx_top[di]; i != 0; i = qxx[i].next)
		{
			rd[qxx[i].u]--;
			dp[qxx[i].u] = max(dp[qxx[i].u],a[qxx[i].u]+dp[di]);
			if (rd[qxx[i].u] == 0)
			{
				dl.push({ qxx[i].u,0 });
			}
		}
	}
	if (num != n)
	{
		cerr << "Error: Cycle detected in prerequisite relationships." << endl;
		return -1;
	}
	for (int i=1;i<=n;i++)
	{
		sum = max(sum, dp[i]);
	}

	cout << max(0LL,sum);
	return 0;
}

K.魔法学院选课

这个题通过读题后整理题意我们可以知道，其实就是在无向图上给了q个查询，每个查询k个点，问这K个点有没有可能同时在一颗最小生成树上。

所以只能讲一下可撤销并查集的思路。

这题整体分为两部分

判查询边是否在一个连通图，这里怎么来都行。

难点在于K个点有没有可能同时在一颗最小生成树上，这个做法有很多，我的标准程序是用的可撤销并查集（验题人八仙过海各显神通，很多方式我都看不懂）。

可撤销并查集需要先知道，克鲁斯卡尔跑最小生成树有这么两条定义。

定义wi为每一条边，对于任意wi，我们选择长度<wi的边构成的联通块是相同的 定义最小生成树中边长为wi的边条数有ci条，对于所有的最小生成树来说，wi和ci都是相同的

（想不明白画图就明白了）

人话就是，对于同权值选哪条边不会对大于或者小于这个权值的边的选择造成影响。

然后我们就可以做了。

对查询进行离线根据权值和查询编号排序。

然后跑克鲁斯卡尔算法的时候分层处理，

在每一层权值跑边之前，先跑一下查询，试试查询边，能不能插入到最小生成树。

每跑完同一个查询，属于这一层权值的边后，需要可撤销并查集回撤一下，然后跑其他查询。

如果有哪一个查询插入的过程插入不了，成环了，这个查询就是非法的。

全跑完就知道哪个查询非法了。

我判查询边是否在一个连通图，是最后进行的，正好跑最小生成树留下个并查集数组，直接拿并查集判就行了。

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
struct bian//原边
{ 
	int u, v;
	long long int w;
}bian_arr[210000];
struct chexiao {//撤销边
	int fs, ft, fs_size, ft_size;
};
struct chaxun
{ 
	int bh;
	bian bian1;
};
int s, t, n, m,q;
vector<chaxun> chaxun_arr;//确定这些边是否同时存在在最小生成树上
vector<chaxun> chaxun_arr1[210000];//确定这些边在同一颗树上
stack<chexiao>chexiao_stack;
int chaxunbiaoji[210000];//查询边标记
//原边排序
bool cmp(const bian& a, const bian& b) {
	return a.w < b.w;
}
bool cmp1(const chaxun& a, const chaxun& b) {
	if(a.bian1.w == b.bian1.w)
		return a.bh < b.bh;
	return a.bian1.w < b.bian1.w;
}
//查询边排序
long long int min;
int bcj[210000],bcj_size[210000];
int fin(int k) {//查找根节点 
	if (bcj[k] == k)return k;
	return fin(bcj[k]);
}
bool add_bcj(int s, int t) {
	int fs = fin(s);
	int ft = fin(t);
	if (fs == ft)return false;
	if (bcj_size[fs] < bcj_size[ft]) {
		bcj[fs] = ft;
		bcj_size[ft] += bcj_size[fs];
	}
	else {
		bcj[ft] = fs;
		bcj_size[fs] += bcj_size[ft];
	}
	return true;
}
bool add_bcj_chexiao(int s,int t) {
	int fs = fin(s);
	int ft = fin(t);
	if (fs == ft)return false;
	chexiao_stack.push({ fs,ft,bcj_size[fs],bcj_size[ft] });
	if (bcj_size[fs] < bcj_size[ft]) {
		bcj[fs] = ft;
		bcj_size[ft] += bcj_size[fs];
	}
	else {
		bcj[ft] = fs;
		bcj_size[fs] += bcj_size[ft];
	}
	return true;
}
int bcj_chexiao(chexiao chexiao1) {
	bcj[chexiao1.fs] = chexiao1.fs;
	bcj[chexiao1.ft] = chexiao1.ft;
	bcj_size[chexiao1.fs] = chexiao1.fs_size;
	bcj_size[chexiao1.ft] = chexiao1.ft_size;
	return 0;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <=n; i++)
	{
		bcj_size[i] = 1;
		bcj[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		cin >> bian_arr[i].u >> bian_arr[i].v >> bian_arr[i].w;
	}
	cin >> q;
	for (int i = 1; i <= q; i++)
	{
		int k;
		cin >> k;
		for (int j = 1; j <= k; j++)
		{
			int x;
			cin >> x;
			chaxun_arr.push_back({ i,bian_arr[x] });
			chaxun_arr1[i].push_back({ i,bian_arr[x] });
		}
	}
	sort(chaxun_arr.begin(), chaxun_arr.end(), cmp1);
	sort(bian_arr + 1, bian_arr + m + 1, cmp);
	for (int i = 1,j=0; i <= m;)
	{
		int cl_w = bian_arr[i].w,cxbh=0;
		for (; j< chaxun_arr.size() && bian_arr[i].w == chaxun_arr[j].bian1.w; j++)
		{
			if (chaxunbiaoji[chaxun_arr[j].bh])continue;
			while(cxbh!= chaxun_arr[j].bh&&chexiao_stack.size())
			{
				bcj_chexiao(chexiao_stack.top());
				chexiao_stack.pop();
			}
			cxbh = chaxun_arr[j].bh;
			if (!add_bcj_chexiao(chaxun_arr[j].bian1.u, chaxun_arr[j].bian1.v))
			{
				
				chaxunbiaoji[chaxun_arr[j].bh] = 1;
			}
		}
		while (chexiao_stack.size())
		{
			bcj_chexiao(chexiao_stack.top());
			chexiao_stack.pop();
		}
		for (; i <= m&&bian_arr[i].w== cl_w; i++)
		{
			add_bcj(bian_arr[i].u, bian_arr[i].v);
		}
	}
	
	for (int i = 1; i <= q; i++)
	{
		if (!chaxunbiaoji[i]) {
				int bj = 1,fzbj= fin(chaxun_arr1[i][0].bian1.u);
				for (int j = 0; j < chaxun_arr1[i].size(); j++)
				{
					int fa = chaxun_arr1[i][j].bian1.u;
					int fb = chaxun_arr1[i][j].bian1.v;
					if (fin(fa) != fzbj || fzbj!= fin(fb)) {
						bj = 0;
						break;
					}
				}
				if (bj) {
					cout << "YES" << endl;
				}else {
					cout << "NO" << endl;
				}
		}
		else {
			cout << "NO" << endl;
		}
	}
	return 0;
}