2023 ICPC 网络赛 第一场 部分题解 (待完善)
D Transitivity
题解:
根据题意可以推出结论: 如果存在连通块,那么这个连通块要满足条件,必然是满连通块.
一共有两种情况
1. 存在一个连通块不是满连通块
设cnt表示连通块的节点个数, num表示连通块边的个数
一个连通块的贡献 = cnt*(cnt-1)/2 - num;
那么最终答案 = 连通块贡献之和
2.所有连通块都是满连通块
因为我们至少需要添加一条边,所以此时等价于我们需要把两个连通块合并.
假设连通块A有x个节点,连通块B有y个节点,那么我们需要添加 x*y条边 才能满足条件.
所以即找到 最小和次小的连通块即可,答案 = x*y
AC代码:
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
vector<int> g[N];
int sz[N];//连通块大小
int cnt[N];//边的数量
int vis[N];
void solve()
{int n,m;cin >> n >> m;for(int i = 1; i<=m; i++){int u,v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}int Min1 = inf;//最小值int Min2 = inf;//次小auto dfs = [&](auto self, int u, int fa,int root)-> void{vis[u] = 1;sz[u] = 1;cnt[root]+=g[u].size();for(auto v: g[u]){if(vis[v]){continue;}self(self,v,u,root);sz[u]+=sz[v];}};auto cal = [&](int now, int sum)//计算贡献{return sum*(sum-1)/2 - now;};int ans = 0;int f = 0;for(int i = 1; i<=n; i++){if(vis[i]){continue;}dfs(dfs,i,-1,i);cnt[i]/=2;int val = cal(cnt[i],sz[i]);//连通块的贡献if(val != 0){ans+=val;f = 1;}else{if(sz[i] < Min1){Min2 = Min1;Min1 = sz[i];}else if(sz[i] <=Min2){Min2 = sz[i];}}}if(f){cout << ans << endl;}else{cout << Min1*Min2 << endl;}
}signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while (t--){solve();}return 0;
}
A Qualifiers Ranking Rules
题解:
按照题意模拟即可
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
struct node
{string s; // 学校名称int rank; // 比赛名次int t;node(string x, int y, int _t){s = x;rank = y;t = _t;}
};
int cmp(node a, node b)
{if (a.rank == b.rank){return a.t < b.t;}return a.rank < b.rank;
}
void solve()
{int n, t;cin >> n >> t;map<string, int> vis;vector<node> pos1;int cnt = 1;for (int i = 1; i <= n; i++){string s;cin >> s;if (vis.count(s)){continue;}pos1.push_back({s, cnt, 1});vis[s] = 1;cnt++;}cnt = 1;vis.clear();for (int i = 1; i <= t; i++){string s;cin >> s;if (vis.count(s)){continue;}pos1.push_back({s, cnt, 2});cnt++;vis[s] = 1;}vis.clear();sort(pos1.begin(), pos1.end(), cmp);for (int i = 0; i < pos1.size(); i++){if (vis.count(pos1[i].s)){continue;}cout << pos1[i].s << endl;vis[pos1[i].s] = 1;}
}
signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}return 0;
}
L KaChang!
题解: 找到最大的数Max,输出 max(2ll,(int)ceil(1.0*Max/k)) 即可
void solve()
{int n,k;cin >> n >> k;int Max = 0;for(int i = 1; i<=n; i++){int x;cin >> x;Max = max(Max,x);}cout << max(2ll,(int)ceil(1.0*Max/k)) << endl;;
}
I Pa?sWorD
题解:
设dp[i][S][ch] 表示只看前i个字母,且当前字符的出现状态为S,且最后一个字母是ch的方案数
(下面这些事伪代码,看不懂的可以直接看代码,有详细注释)
1.当前是 大写字母
dp[i][S| bit(2)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1 即上一层所有字符的方案数 - 上一层ch1的方案数
1.当前是 小写字母
(1)大写字母
dp[i][S| bit(2)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1 即上一层所有字符的方案数 - ch1的方案数
(2)填小写字母
dp[i][S| bit(1)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1 即上一层所有字符的方案数 - ch1的方案数
1.当前是 数字
dp[i][S| bit(0)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1 即上一层所有字符的方案数 - ch1的方案数
1.当前是 问号
枚举当前字符ch1, t表示当前字母是谁
dp[i][S| bit(t)][ch1] += dp[i-1][S][ch1];//其中ch2 != ch1 即上一层所有字符的方案数 - ch1的方案数
AC代码:
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
const int MOD = 998244353;
int add(int x, int y)
{x += y;while (x >= MOD)x -= MOD;while (x < 0)x += MOD;return x;
}int sub(int x, int y)
{return add(x, MOD - y);
}int mul(int x, int y)
{return (x * 1ll * y) % MOD;
}int binpow(int x, int y)
{int z = 1;while (y > 0){if (y % 2 == 1)z = mul(z, x);x = mul(x, x);y /= 2;}return z;
}int inv(int x)
{return binpow(x, MOD - 2);
}int divide(int x, int y)
{return mul(x, inv(y));
}int my_hash(char ch)//对字符进行哈希
{if (ch >= 'a' && ch <= 'z'){return ch - 'a' + 10;}else if (ch >= 'A' && ch <= 'Z'){return ch - 'A' + 36;}else{return ch - '0';}
}
int pos(int ch)//当前字符在二进制中的位置
{if (ch >= 10 && ch <= 35) // 小写表示第1位{return 1;}else if (ch >= 36 && ch <= 61) // 大写表示第2位{return 2;}else // 数字表示第0位{return 0;}
}int dp[2][10][70]; // 当前状态为S且最后一个字符是 ch 的方案数
int last[10]; // 状态为S时 所有的字符方案数之和
void solve()
{int n;cin >> n;string s;cin >> s;s = " " + s;//初始化部分int S = 0;int now;int ch; // 当前填入的字符编号if (s[1] == '?'){for (ch = 0; ch <= 61; ch++) // 当前填入ch{now = S | bit(pos(ch)); // 填入s[i]后,当前的二进制状态dp[1][now][ch] = 1;}}else{now = S | bit(pos(my_hash(s[1]))); // 填入s[i]后,当前的二进制状态ch = my_hash(s[1]);dp[1][now][ch] = 1; // 加上全部的if (s[1] >= 'a' && s[1] <= 'z')//如果是小写字母,还可以是大写字母{now = S | bit(pos(my_hash(s[1]) + 26)); // 填入s[i]后,当前的二进制状态ch = my_hash(s[1]) + 26; // 填大写字母dp[1][now][ch] = 1; // 加上全部的}}for (int i = 2; i <= n; i++){for (int S = 0; S < 8; S++)//{int sum = 0;for (int ch = 0; ch <= 61; ch++){dp[0][S][ch] = dp[1][S][ch]; // 滚动数组dp[1][S][ch] = 0; // 进行初始化sum = add(sum, dp[0][S][ch]);//表示上一层状态为S的所有字符的方案数}last[S] = sum; // 表示上一层状态为S的所有字符的方案数}for (int S = 0; S < 8; S++) // 枚举上一层的状态{int now;//表示填入字符后的状态int ch; // 当前填入的字符编号if (s[i] == '?'){for (ch = 0; ch <= 61; ch++) // 当前填入ch{now = S | bit(pos(ch)); // 填入s[i]后,当前的二进制状态dp[1][now][ch] = add(dp[1][now][ch], last[S]); // 加上全部的dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同,减去}}else{now = S | bit(pos(my_hash(s[i]))); // 填入s[i]后,当前的二进制状态ch = my_hash(s[i]);dp[1][now][ch] = add(dp[1][now][ch], last[S]); // 加上全部的dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同,减去if (s[i] >= 'a' && s[i] <= 'z') // 填入大写的{now = S | bit(pos(my_hash(s[i]) + 26)); // 填入s[i]后,当前的二进制状态ch = my_hash(s[i]) + 26;dp[1][now][ch] = add(dp[1][now][ch], last[S]); // 加上全部的dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同,减去}}}}int ans = 0;for (int ch = 0; ch <= 61; ch++){ans = add(ans, dp[1][7][ch]);}cout << ans << endl;
}
signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}return 0;
} 相关文章:
2023 ICPC 网络赛 第一场 部分题解 (待完善)
D Transitivity 题解: 根据题意可以推出结论: 如果存在连通块,那么这个连通块要满足条件,必然是满连通块. 一共有两种情况 1. 存在一个连通块不是满连通块 设cnt表示连通块的节点个数, num表示连通块边的个数 一个连通块的贡献 cnt*(cnt-1)/2 - num; 那么最终答案 连…...
Hadoop的HDFS高可用方案
一、Hadoop高可用简介 Hadoop 高可用 (High Availability) 分为 HDFS 高可用和 YARN 高可用,两者的实现基本类似,但 HDFSNameNode 对数据存储及其一致性的要求比 YARN ResourceManger 高得多,所以它的实现也更加复杂 1、HDFS系统高可用简介…...
【计算机基础】让我们重新认识一下Visual Stduio及其操作,知识点汇总!!
📢:如果你也对机器人、人工智能感兴趣,看来我们志同道合✨ 📢:不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍…...
使用Node构建私人代理池
在进行大规模数据采集时,经常会遇到网站反爬虫机制导致爬虫被封的问题。为了解决这个困扰,本文将向大家介绍如何利用Node.js构建私人代理池,提供稳定的代理,实现高效、可靠的爬虫操作。跟随本文一起学习,拥有解封爬虫的…...
2023年“羊城杯”网络安全大赛 决赛 AWDP [Break+Fix] Web方向题解wp 全
终于迎来了我的第一百篇文章。 这次决赛赛制是AWDP。BreakFix,其实就是CTFFix,Fix规则有点难崩。Break和Fix题目是一样的。 总结一下:败北,还是太菜了得继续修炼一下。 一、Break ezSSTI 看到是SSTI,焚靖直接一把梭…...
如何用好免费的ChatGPT
如何用好免费的ChatGPT 前言ChatGPT使用入口在线体验地址:点我体验 ChatGPT介绍ChatGPT初级使用技巧初级使用技巧:清晰明了的问题表达 ChatGPT中级使用语法中级使用语法:具体化问题并提供背景信息 ChatGPT高级使用高级使用:追问、…...
golang 实现带令牌限流的JWT demo
demo里提供了三个接口,认证取token,刷新token,获取信息,token过期前也会在header里写上新token(便于客户端更换) package mainimport ("fmt""net/http""sync""time&qu…...
【web开发】9、Django(4)ajax请求
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 一、Ajax是什么?二、使用步骤二、订单管理 提示:以下是本篇文章正文内容,下面案例可供参考 一、Ajax是什么? Ajax&…...
消息队列中,如何保证消息的顺序性?
本文选自:advanced-java 作者:yanglbme 问:如何保证消息的顺序性? 面试官心理分析 其实这个也是用 MQ 的时候必问的话题,第一看看你了不了解顺序这个事儿?第二看看你有没有办法保证消息是有顺序的…...
Shell别名的使用方法及管理技巧
文章目录 1. 引言1.1 概述1.2 目的1.3 适用范围 2. Shell和别名2.1 Shell简介2.2 别名的作用2.3 别名的语法 3. 创建别名3.1 临时别名3.2 永久别名 4. 别名的应用4.1 简化命令4.2 自定义命令4.3 提高工作效率 5. 管理别名5.1 查看别名5.2 修改别名5.3 删除别名 6. 实例演示6.1 …...
C/C++选择题好题分享
...
kafka副本机制
目录 前言 副本定义 副本角色 In-sync Replicas(ISR) 参考资料 前言 现在的很多的分布式系统都支持副本的机制,比如Mysql就有副本的机制,一般使用副本有如下特性和好处。 提供数据冗余。即使系统部分组件失效,系…...
服务注册发现_actuator微服务信息完善
SpringCloud体系里的,服务实体向eureka注册时,注册名默认是IP名:应用名:应用端口名。 问题: 自定义服务在Eureka上的实例名怎么弄呢 在服务提供者pom中配置Actuator依赖 <!-- actuator监控信息完善 --> <dependency><groupId…...
常见列表字典排序
一、列表排序 demoList [1, 3, 2, 4, 9 ,7]res sorted(demoList) # 默认升序# 降序 # res sorted(demoList, reverseTrue)print(res)二、字典排序 demoDict {"篮球": 5, "排球": 9, "网球": 6, "足球": 3}# sorted排序 res so…...
【Acwing1027】方格取数(动态规划)题解
题目描述 思路分析 错误思路: 贪心法,先走一次求出最大值,把走过的路上面的数值清零,然后用同样的方法再走一遍求最大值,然后让这两个最大值相加就是最后的结果。 很多人在看到这个题目的时候会有上面的思路&#x…...
合并区间:解决区间重叠问题的高效算法
合并区间:解决区间重叠问题的高效算法 leetcode 56. 合并区间 合并区间是一个常见的编程问题,通常涉及到一组区间,你需要将重叠的区间合并成更大的区间。这篇博客将介绍这个问题的背景,然后解释一个高效的解决方案,同…...
万字总结HTML超文本标记语言
一、前言:什么是网页? 网站是指在因特网上根据一定的规则,使用 HTML 等制作的用于展示特定内容相关的网页集合。网页是网站中的一“页”,通常是 HTML 格式的文件,它要通过浏览器来阅读。 网页是构成网站的基本元素,它通常由图片、链接、文字、声音、视频等元素组成。通常…...
Java线程池是如何保证核心线程不被销毁的
来源: Java线程池是如何保证核心线程不被销毁的_朝 花 拾 夕的博客-CSDN博客 对于Java中 Thread 对象,同一个线程对象调用 start 方法后,会在执行完run 后走向终止(TERMINATED)状态,也就是说一个线程对象是不可以通过多…...
新课程标准培养学生“高考物理关键能力”的实践研究课题文献综述
目录 一、高考物理能力的要求与评估标准 二、高考物理关键能力的定义与内涵...
急救车工业路由器应用提升急救效率:车联网、数据采集与远程诊疗
急救车作为医院里医疗急救过程中的重要组成部分,在智慧医疗物联网领域中急救车应用4G工业路由器实现网络部署与数据采集,通过工业4G路由器能够实时采集到病患的生理数据、救护现场音频与视频、GPS定位以及车辆运行状态等重要信息。这些数据将被传输到医疗…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
