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;
}
D.万恶的发牌员
问题为一次刷新刷出 9 张一模一样的牌的概率，以分数给出。
所以可以分为两部分解：
- 对于分母而言，即是求所有牌 (n * m) 里任意取 9 张的取法个数，求组合数即可，即 C(n * m , 9)。
- 对于分子而言，每一种牌有 m 张，在 m 张中取出 9 张为该种牌的所有取法，乘 n 种，即 n * C(m , 9)。
化简可以同时除两个数的最大公约数，由于数据过大，需要使用辗转相除法。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int main(){
LL n , m; cin >> n >> m;
//分母
LL x = 1;
for(int i = 0 ; i < 9 ; i ++){
x *= n * m - i;
}
for(int i = 0 ; i < 9 ; i ++){
x /= i + 1;
}
//分子
LL y = 1;
for(int i = 0 ; i < 9 ; i ++){
y *= m - i;
}
for(int i = 0 ; i < 9 ; i ++){
y /= i + 1;
}
y *= n;//n种牌
LL gcd = __gcd(x , y);//最大公约数
y /= gcd;
x /= gcd;
cout << y << endl << x;
}
E.世界（easy）
根据题意，我们只需要维护两个栈，使用 l , r 表示。
- 遇到字符: 直接添加至 l 中。
- 遇到 '-' : 若 l 不为空，将 l 的顶部元素放入 r 中。
- 遇到 '+' : 若 r 不为空，将 r 的顶部元素放入 l 中。
最后反向输出 l 中的元素，再正向输出 r 中的元素即可。
注：由于数据点十分宽松，所以解法并不唯一。
#include <iostream>
#include <stack>
using namespace std;
int main(){
int n; cin >> n;
string s; cin >> s;
stack<char> l , r;
for(int i = 0 ; i < n ; i ++){
if(s[i] == '+'){
if(r.size()){
l.push(r.top());
r.pop();
}
}
else if(s[i] == '-'){
if(l.size()){
r.push(l.top());
l.pop();
}
}
else{
l.push(s[i]);
}
}
while(l.size()){
r.push(l.top());
l.pop();
}
while(r.size()){
cout << r.top();
r.pop();
}
return 0;
}
F.迷雾中的数字桥梁
分析题意，我们首先需要对输入的数据生成其前缀和数组。
紧接着，处理询问时，我们可以注意到数据范围十分大，因此循环暴力做法不可取。
但也可以发现，当输入的数为正整数时，前缀和数组必然单调递增，因此可以使用二分查找来确定左右边界。
若存在，按要求输出，不存在，输出-1。
需要特别注意，此题输入输出的数据过于庞大，输出换行时不可以使用 endl ，endl 会多次刷新缓冲区造成超时。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int n, m;
int a[N];
ll s[N];
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
while(m --)
{
ll l, r;
scanf("%lld %lld", &l, &r);
auto idx_l = lower_bound(s + 1, s + 1 + n, l) - 1;
auto idx_r = upper_bound(s + 1, s + 1 + n, r);
if(*idx_l != 0 && *idx_r != 0)
{
//cout << *idx_r << " " << *idx_l << endl;
cout << *idx_r - *idx_l << "\n";
}
else cout << "-1" << "\n";
}
return 0;
}
G.丧尸塔防
- 问题分析：
- 病毒从城市1（DC）开始传播，通过道路向相连的城市扩散。
- 建设堡垒的城市可以阻断病毒的传播路径。即一旦病毒到达某个未设堡垒的城市，该城及其所有子节点（未被阻挡的路径上）都会被感染。
- 我们需要选择K个城市作为堡垒，使得未被感染的城市总人口最大。
- 关键观察：
- 阻断传播等价于在病毒的传播树上切断某些边。选择哪些边（对应哪些城市）作为堡垒是关键。
- 阻断一个城市可以保护其子树的所有未被感染的城市。
- 最优策略是选择那些可以保护最多人口的路径。
- 贪心策略：
- 在病毒的传播树（以城市1为根）中，对于每个节点计算其子树的总人口（包括自身）。
- 贪心地选择子树人口最大的K个节点作为堡垒，这样能够最大化未被感染的人口。
- 算法步骤：
- 构建树结构：将输入的道路信息转化为树结构，根节点为城市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;
}
J.世界（hard）
该题与 easy 版本的区别为添加了复制与小世界的定义：
- 对于小世界，我们可以将 E 题中的栈设定为存储一个字符串，匹配括号存储即可。每次使用 递归 + 分治 处理该小世界的所有内容：
- 若当前小世界的字符没找到任何需要操作的字符，则返回小世界的所有元素至上一层世界。
- 维护两个存储字符串的栈 l , r;
- 遇到字符: 直接添加至 l 中。
- 遇到 '-' : 若 l 不为空，将 l 的顶部元素放入 r 中。
- 遇到 '+' : 若 r 不为空，将 r 的顶部元素放入 l 中。
- 遇到 '*' : 将 l 的顶部元素添加至 l 中。
- 遇到 '(' : 寻找与其匹配的后括号，找到后将递归处理好的该段字符串添加至 l 中。
- 答案依次拼接反向 l 中的元素，和正向输出 r 中的元素即可。
- 维护两个存储字符串的栈 l , r;
- 若当前小世界的字符没找到任何需要操作的字符，则返回小世界的所有元素至上一层世界。
特别注意：本题需要尽量减少对于字符串的操作，常数过大会造成超时。
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
using namespace std;
bool fbs(string u){
for(auto i : u){
if(i == '+' || i == '-' || i == '*' || i == '(')
return 1;
}
return 0;
}
string dfs(string s){
if(! fbs(s)){
return s;
}
stack<string> l , r;
//deque<string> l , r;
for(int i = 0 ; i < s.size() ; i ++){
string t = "";
if(s[i] == '+'){
if(! r.empty()){
l.push(r.top());
r.pop();
}
}
else if(s[i] == '-'){
if(! l.empty()){
r.push(l.top());
l.pop();
}
}
else if(s[i] == '*'){
if(! l.empty()){
l.push(l.top());
}
}
else if(s[i] == '('){
int j = i + 1 , cnt = 1;
while(1){
if(s[j] == '('){
cnt ++;
}
else if(s[j] == ')') {
cnt --;
}
if(cnt == 0) break;
t += s[j];
j ++;
}
i = j;
l.push(dfs(t));
}
else{
t += s[i];
l.push(t);
}
}
string ans = "";
while(! l.empty()){
r.push(l.top());
l.pop();
}
while(! r.empty()){
ans += r.top();
r.pop();
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
string s; cin >> s;
cout << dfs(s);
}
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;
}
京公网安备 11010502036488号