当前位置: 首页 > news >正文

10.22模拟赛总结

T1: P14023 [ICPC 2024 Nanjing R] 社交媒体

solution

我会暴力!

提前计算好每个好友的贡献,枚举选取哪两个好友,计算结果。

注意:map 不要在循环内开,否则会被卡到30pts!

时间复杂度 \(O(n ^ 2)\)

我做过P8817 [CSP-S 2022] 假期计划 !

考虑优化掉其中一个点。

枚举一个好友,更新其他好友的贡献,这样就可以贪心了。

注意计算对已经是好友的点的贡献

虽然我做过这道题但是考场上出现神秘错误,属于是运气不行了

code:

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int QWQ = 2e5 + 5;
map<int, int> g[QWQ];
void solve()
{int n, m, k, a[QWQ], f[QWQ], vis[QWQ], in[QWQ], U[QWQ], V[QWQ];int ans = 0;for(int i = 1;i <= k;i ++) g[i].clear();memset(vis, 0, sizeof(vis));memset(in, 0, sizeof(in));cin >> n >> m >> k;for(int i = 1;i <= n;i ++){cin >> f[i];vis[f[i]] = 1;}for(int i = 1;i <= m;i ++){cin >> U[i] >> V[i];int u = U[i], v = V[i];if(u == v && !vis[u]){in[u] ++;}g[u][v] ++, g[v][u] ++;if(vis[u] && !vis[v]){in[v] ++;}if(vis[v] && !vis[u]){in[u] ++;}if(vis[v] && vis[u]){ans ++;}}int res = 0, fi = 0, se = 0;for(int i = 1;i <= k;i ++){if(in[i] >= fi){se = fi;fi = in[i];}else if(in[i] >= se){se = in[i];}}res = max(res, fi + se);for(int i = 1;i <= m;i ++){int u = U[i], v = V[i];if(u != v && !vis[u] && !vis[v]){res = max(res, in[u] + in[v] + g[u][v]);}}cout << ans + res << endl;
}
signed main()
{int T;cin >> T;while(T --) solve();
}

T2:

小明和机器人一共会进行 \(T\) 轮游戏。

每轮游戏中,机器人会给小明一个长度为 \(N\) 的数列 \(a_1,\ a_2,\ ...,\ a_N\)

小明需要将这个数列转化为一棵大小为 \(N\) 的树,每条边的长度均为 \(1\)。,使得树上的任意节点 \(i\),到距离它最远的点的距离都是对应的 \(a_i\)

solution

考虑树的直径。

肯定是要把最大的点放在直径两端的,最小的点放在树的重心上,如果不能构造出这样的数,那么直接判无解。

然后把树拆成一条链,每次插入一个距离就尝试加入一个叶子节点。

构造不出来就输出无解

code

点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int QWQ = 1e5 + 5;
void solve()
{int n, a[QWQ], qwq[QWQ], sum;memset(qwq, 0, sizeof(qwq));cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];qwq[a[i]]++;}sort(a + 1, a + n + 1);if (a[1] < (a[n] + 1) / 2){cout << "No" << endl;return;}for (int i = a[n]; i >= (a[n] + 1) / 2; i--){int w = 2;if (i == a[n] / 2){w = 1;}if (qwq[i] < w){cout << "No" << endl;return ;}qwq[i] -= w;}if (qwq[(a[n] + 1) / 2]){cout << "No" << endl;}else{cout << "Yes" << endl;}
}
signed main()
{int T;cin >> T;while (T--)solve();
}

T3:P14015 [ICPC 2024 Nanjing R] 生日礼物

题意

给你一个序列,你可以执行任意次操作。每次可以执行以下三种操作之一:

  • 将任意一个 \(2\) 改为 \(0\)\(1\)
  • 选择两个相邻的 \(0\),删除它们,并将剩下的部分连接起来。
  • 选择两个相邻的 \(1\),删除它们,并将剩下的部分连接起来。

求能得到的最短序列的长度。

solution

神秘trick

将奇数位的 \(0\) 给替换成 \(1\)\(1\) 替换成 \(0\),那么每次消除就是消除序列中的 \(01\)\(10\)

当序列中不存在 \(2\) 时,记序列中 \(0\) 的个数为 \(cnt_0\)\(1\) 的个数为 \(cnt_1\),那么答案就是 \(|cnt_0 - cnt_1|\)

发现最后剩下的序列中要么全是 \(0\),要么全是 \(1\)

考虑序列中存在 \(2\) 的情况,尝试将 \(2\) 替换成 \(0\)\(1\) 中数量最少的那个,这样可以使答案达到最小。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
void solve() {string s;int cnt0 = 0, cnt1 = 0;cin >> s;for(int i = 1;i < s.size();i += 2) {if(s[i] == '0') s[i] = '1';else if(s[i] == '1') s[i] = '0';}for(int i = 0;i < s.size();i ++) {if(s[i] == '0') cnt0 ++;if(s[i] == '1') cnt1 ++;}for(int i = 0;i < s.size();i ++) {if(s[i] != '2') continue;if(cnt0 < cnt1) cnt0 ++;else cnt1 ++;}cout << abs(cnt0 - cnt1) << endl;
}
signed main() {int T;cin >> T;while(T --) solve();
}
http://www.hskmm.com/?act=detail&tid=36700

相关文章:

  • 从零开始制作操作系统—— 最简单的操作系统内核
  • 【CSP出版 | 最快投稿后一个月见刊 | 检索稳定】2025年艺术、教育与管理国际学术会议(ICAEM 2025)- 第六期
  • 【LeetCode 每日一题】120. 三角形最小路径和——(解法二)自底向上 - 实践
  • HDFS Java api操作-cnblog
  • 电网不平衡条件下DFIG风力发电机动态建模与控制
  • Pandas 深入学习【3】材料标准化处理 StandardScaler
  • C#实现CRC8、CRC16、CRC32校验算法
  • JAVA 开发者入门 AI:基于 JBoltAI 平台快速搭建第一个 AI 应用
  • 2025 年切纸机源头厂家最新推荐榜单:全自动 / 程控 / 大型等设备品牌评测,深度解析大鹏等企业实力
  • 成功案例分享|ArmSoM CM5赋能海洋保育,边缘AI守护鲸豚之声
  • 2025 年最新推荐走心机加工实力厂家排行榜:覆盖航空 / 医疗 / 汽车等多领域优质企业精选 不锈钢零件/高铁零件/精密数控走心机加工厂家推荐
  • 权威调研榜单:简易丝杆模组厂家TOP3榜单好评深度解析
  • Kerberoasting攻击剖析:Active Directory中的密码破解漏洞
  • 千疮百孔的心被恨与悲彻底剥离 Kill my memory 让我将快乐全忘记
  • 速尝鲜!PS 2026 新功能:移除工具 + 神经滤镜
  • KeyShot 2025最新安装包下载及详细安装教程,附永久免费中文安装包 KeyShot2025
  • 复矩阵的QR分解
  • 权威调研榜单:天津全屋定制整体橱柜方案TOP4榜单好评深度解析
  • 别再手动处理琐事了!用Coze搭建AI工作流,我每天白赚2小时
  • 单时段机组组合优化的粒子群算法实现(MATLAB)
  • 谎言 欺骗 鄙夷 如破碎瓦砾铺满地 利用陷害窒息莫名遭受唾骂遗弃
  • Day21-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\Stream-集合框架(stream)
  • 权威调研榜单:湖南张家界旅游团服务TOP3榜单好评深度解析
  • [GXYCTF2019]Ping Ping Ping 1
  • C# 元组 Tuple ValueTuple
  • Java语言的核心特性与大数据应用研究
  • 扣子Coze智能体万字教程:从入门到精通,一文掌握AI工作流搭建 - Leone
  • 轻量服务器Lighthouse + 1Panel + Halo,三步打造你的专属网站
  • (自用)如何使用 mt19937 生成随机数?
  • 第四章 windows实战-向日葵