本次比賽B C G H I K 題解

td1336065617 (codeforces max rating <1200 ) 出題：B C G H I K 其他題解請等，另一個(gè)出題人。

題號知識點(diǎn) 題目名難度預(yù)計(jì)通過比例難度對應(yīng)洛谷難度對應(yīng)codeforces 出題人

A	輸出語句	HHDU	easy	100%	入門	0	北冥12131
B	分支語句	是否大于2025	easy	80%	入門	400	td1336065617
C	循環(huán)語句+分支語句+數(shù)學(xué)運(yùn)算	K的倍數(shù)	easy	70%	入門	400	td1336065617
D	組合數(shù)學(xué)	萬惡的發(fā)牌員	easy-mid	30%	普及	800	北冥12131
E	字符串模擬/單調(diào)棧/雙端隊(duì)列	世界（easy）	easy-mid	20%	普及	800-1000	北冥12131
F	前綴和+二分	迷霧中的數(shù)字橋梁	mid	10%	普及	800-1200	北冥12131
G	樹+搜索	喪尸塔防	mid	10%	普及	800-1200	td1336065617
H	模擬+排序	榜單重建	mid-hard	5%	普及	1200-1400	td1336065617
I	拓?fù)湫?線性動(dòng)態(tài)規(guī)劃	魔法學(xué)院選課	mid-hard	3%	普及	1400-1500	td1336065617
J	字符串分治+雙端隊(duì)列	世界（hard）	hard	1%	普及	1400-1600	北冥12131
K	最小生成樹的原理+可撤銷并查集+離線查詢	魔法大陸的連通謎題	very hard	1‰	省選	2000-2200	td1336065617

A.HHDU

知識點(diǎn) 輸出語句很明顯輸出 HHDU2025就行了

#include <iostream>
using namespace std;

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

B.是否大于2025

知識點(diǎn) 分支語句按題面來就行了，判斷一下。

#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的倍數(shù)

按題面來，直接循環(huán)判斷取余結(jié)果是否為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（DC）開始傳播，通過道路向相連的城市擴(kuò)散。
- 建設(shè)堡壘的城市可以阻斷病毒的傳播路徑。即一旦病毒到達(dá)某個(gè)未設(shè)堡壘的城市，該城及其所有子節(jié)點(diǎn)（未被阻擋的路徑上）都會被感染。
- 我們需要選擇K個(gè)城市作為堡壘，使得未被感染的城市總?cè)丝谧畲蟆?/li>
關(guān)鍵觀察：
- 阻斷傳播等價(jià)于在病毒的傳播樹上切斷某些邊。選擇哪些邊（對應(yīng)哪些城市）作為堡壘是關(guān)鍵。
- 阻斷一個(gè)城市可以保護(hù)其子樹的所有未被感染的城市。
- 最優(yōu)策略是選擇那些可以保護(hù)最多人口的路徑。
貪心策略：
- 在病毒的傳播樹（以城市1為根）中，對于每個(gè)節(jié)點(diǎn)計(jì)算其子樹的總?cè)丝冢òㄗ陨恚?/li>
- 貪心地選擇子樹人口最大的K個(gè)節(jié)點(diǎn)作為堡壘，這樣能夠最大化未被感染的人口。
算法步驟：
- 構(gòu)建樹結(jié)構(gòu)：將輸入的道路信息轉(zhuǎn)化為樹結(jié)構(gòu)，根節(jié)點(diǎn)為城市1（DC）。
- 計(jì)算子樹人口：使用深度優(yōu)先搜索（DFS）或后序遍歷計(jì)算每個(gè)節(jié)點(diǎn)的子樹總?cè)丝凇?/li>
- 選擇最優(yōu)堡壘：將子樹人口排序，選擇前K大的節(jié)點(diǎn)（不包括根節(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)已經(jīng)被感染）。

#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;//驗(yàn)證數(shù)據(jù)用的
    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);
                //驗(yàn)證數(shù)據(jù)是不是一棵樹 如果存在邊連接向非父節(jié)點(diǎn)的走過的點(diǎn)顯然不是樹
            }
            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.榜單重建

根據(jù)題面要求的規(guī)則，以提交時(shí)間升序排序，然后同時(shí)間AC在前，排序一下就行了，

實(shí)際上就是根據(jù)題面要求排序，然后通過隊(duì)伍TeamName 和 ProblemID ,然后計(jì)算每題罰時(shí)和通過與否。

然后繼續(xù)隊(duì)伍罰時(shí)，排序一下，根據(jù)題面要求進(jìn)行排名就行了。

如果WA了，那就是讀題不仔細(xì)，我加粗那一堆都是排序和排名相關(guān)的細(xì)節(jié)，認(rèn)真讀題就能過。

#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.魔法學(xué)院選課

這題通過讀題可知，其的關(guān)鍵點(diǎn)是，如何確定一門課什么時(shí)候能學(xué)，學(xué)過拓?fù)湫虻耐瑢W(xué)一眼就可以知道，這就是bfs跑拓?fù)湫蜻^程中，進(jìn)行一下線性dp而已。

想不明白的同學(xué)建議先補(bǔ)一下知識點(diǎn)，拓?fù)渑判颉?/p>

然后DP部分，就很容易想明白了，一門課只可能從連接到他的節(jié)點(diǎn)中魔力值和最高的前置節(jié)點(diǎn)集合，其實(shí)就是在每個(gè)節(jié)點(diǎn)，向其可以連接的子節(jié)點(diǎn)嘗試一下專業(yè)，如果從當(dāng)前節(jié)點(diǎn)轉(zhuǎn)以后，子節(jié)點(diǎn)的魔力值和變大就保留。

dp[qxx[i].u] = max(dp[qxx[i].u],a[qxx[i].u]+dp[di]);

qxx[i].u當(dāng)前節(jié)點(diǎn)連接的點(diǎn)，a[qxx[i].u]當(dāng)前節(jié)點(diǎn)連接的點(diǎn)自帶的魔力值，當(dāng)前節(jié)點(diǎn)的魔力值dp[di]。

因?yàn)樵谂芡負(fù)湫驎r(shí)候，入隊(duì)列時(shí)候就已經(jīng)不可能有前置節(jié)點(diǎn)可以到點(diǎn)di了。

所以dp[i]表示i點(diǎn)結(jié)尾的鏈條的最大可能魔法值和。

#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.魔法學(xué)院選課

這個(gè)題通過讀題后整理題意我們可以知道，其實(shí)就是在無向圖上給了q個(gè)查詢，每個(gè)查詢k個(gè)點(diǎn)，問這K個(gè)點(diǎn)有沒有可能同時(shí)在一顆最小生成樹上。

所以只能講一下可撤銷并查集的思路。

這題整體分為兩部分

判查詢邊是否在一個(gè)連通圖，這里怎么來都行。

難點(diǎn)在于K個(gè)點(diǎn)有沒有可能同時(shí)在一顆最小生成樹上，這個(gè)做法有很多，我的標(biāo)準(zhǔn)程序是用的可撤銷并查集（驗(yàn)題人八仙過海各顯神通，很多方式我都看不懂）。

可撤銷并查集需要先知道，克魯斯卡爾跑最小生成樹有這么兩條定義。

定義wi為每一條邊，對于任意wi，我們選擇長度<wi的邊構(gòu)成的聯(lián)通塊是相同的定義最小生成樹中邊長為wi的邊條數(shù)有ci條，對于所有的最小生成樹來說，wi和ci都是相同的

（想不明白畫圖就明白了）

人話就是，對于同權(quán)值選哪條邊不會對大于或者小于這個(gè)權(quán)值的邊的選擇造成影響。

然后我們就可以做了。

對查詢進(jìn)行離線根據(jù)權(quán)值和查詢編號排序。

然后跑克魯斯卡爾算法的時(shí)候分層處理，

在每一層權(quán)值跑邊之前，先跑一下查詢，試試查詢邊，能不能插入到最小生成樹。

每跑完同一個(gè)查詢，屬于這一層權(quán)值的邊后，需要可撤銷并查集回撤一下，然后跑其他查詢。

如果有哪一個(gè)查詢插入的過程插入不了，成環(huán)了，這個(gè)查詢就是非法的。

全跑完就知道哪個(gè)查詢非法了。

我判查詢邊是否在一個(gè)連通圖，是最后進(jìn)行的，正好跑最小生成樹留下個(gè)并查集數(shù)組，直接拿并查集判就行了。

#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;//確定這些邊是否同時(shí)存在在最小生成樹上
vector<chaxun> chaxun_arr1[210000];//確定這些邊在同一顆樹上
stack<chexiao>chexiao_stack;
int chaxunbiaoji[210000];//查詢邊標(biāo)記
//原邊排序
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) {//查找根節(jié)點(diǎn) 
	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;
}

#哈爾濱華德學(xué)院第十六屆程序設(shè)計(jì)競賽##哈爾濱華德學(xué)院第十六屆程序設(shè)計(jì)競賽題解#