Q779’s Blog

模拟赛题讲解[4] 来自 Roundgod 2022-07-26 noi.ac #2680 问题描述： Berland由 \(n\) 个城市和 \(m\) 条双向道路构成，其中第 \(i\) 条道路连接城市 \(a_i\) 和 \(b_i\) ，并且距离 \(c_i\) 公里. 你想要开车在Berland进行自驾游。已知车子的油箱最多能装 \(L\) 升油，并且车子每行进一公里都要耗费恰好一升油。当你到达某个城市的时候，你可以选择将油箱加满油(也可以不加)。你不能在道路中间加油。 现在给出 \(q\) 组如下形式的询问: 给定起点 \(s\) 和终点 \(t\) ，问如果初始时油箱装满从城市 \(s\) 出发，最少要多少次加满油才能到达城市 \(t\) ，如果无法到达输出 \(−1\). 输入格式： 输入第一行包含 \(3\) 个整数 \(n,m,L\)分别表示城市的个数，道路的条数以及油箱的容量。 接下来 \(m\) 行，每行包含三个整数 \(a_i,b_i,c_i(1\le a_i,b_i\le n,a_i\ne b_i)\) ，表示第 \(i\) 条道路连接的城市以及道路长...

模拟赛题讲解[3] 来自 Roundgod 2022-07-26 noi.ac #2679 题目描述： 给定一个无向图 \(G=(V,E)\) ，其中顶点个数 \(|V|=n\) ，边数 \(|E|=m\) 。顶点编号为 \(1−N\)， 边的编号为 \(1−M\) 。其中 \(i\) 号顶点有一个权值 \(h_i\) . 你现在可以从 \(1\) 号顶点开始沿着图上的边行走。你初始时的得分为 \(0\) ，当你经过一条边 \((u,v)\) 时，你的得分会如下更新: 1.如果 \(h_u>h_v\) ，你的得分会增加 \(h_u−h_v\) 。 2.如果 \(h_u<h_v\) ，你的得分会减少 \(2(h_v−h_u)\) 。 3.如果 \(h_u=h_v\)，你的得分会不变. 你想要知道，经过任意行走后(也可以不行走)，你可以得到的最大得分是多少? 输入格式： 输入第一行包含 \(3\) 个整数 \(n,m\) ，分别表示图的顶点数和图的边数。 接下来一行包含 \(n\) 个整数 \(h_1,h_2,\dots ,h_n\) ，表示每个顶点的初始权值。 接下来 ...

洛谷P8060 [POI2003] Sums 题解 题目链接：P8060 [POI2003] Sums 题目描述： 我们给定一个整数集合 \(A\)。考虑一个非负整数集合 \(A'\)，所有属于 \(A'\) 的集合的数 \(x\) 满足当且仅当能被表示成一些属于 \(A\) 的元素的和（数字可重复）。 比如，当 \(A = \{2,5,7\}\)，属于 \(A'\) 的数为：\(0\)（\(0\) 个元素的和），\(2\)，\(4\)（\(2 + 2\)）和 \(12\)（\(5 + 7\) or \(7 + 5\) or \(2 + 2 + 2 + 2 + 2 + 2\)）；但是元素 \(1\) 和 \(3\) 不属于 \(A'\)。 输入格式： 第一行有一个整数 \(n\)，代表集合 \(A\) 的元素个数。接下来每行一个数 \(a_i\) 描述一个元素。\(A = \{a_1,a_2,...,a_n\}\)。 接下来一个整数 \(k\)，然后每行一个整数，分别代表 \(b_1,b_2,...,b_k\)。 输出格式： 输出 \(k\) 行...

OI tricks 注意：本文不是成品，是动态更新的，可能出现各种小问题什么的 原简介： 平时做题的时候发现的一些技巧，还没有仔细整理 因此本文比较像草稿般的个人总结 1.终极快读（稳定&简单版）（较为麻烦但是还要快的见OI模板-其他） namespace FastIO { #define gc() readchar() #define pc(a) putchar(a) #define SIZ (int)(1e6+15) char buf1[SIZ],*p1,*p2; char readchar() { if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin); return p1==p2?EOF:*p1++; } template<typename T>void read(T &k) { char ch=gc();T x=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();
...

模拟赛题讲解[2] 来自 Roundgod 2022-07-25 noi.ac #2677 题目描述： 给定一个有向图 \(G=(V,E)\) ，其中顶点个数 \(|V|=n\) ，边数 \(|E|=m\) 。顶点编号为 \(1−N\) ，边的编号为 \(1−M\) ，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\) 。 Makima会从图中的某个顶点出发并重复沿着某条有向边行走。你需要计算:存在多少个顶点 \(v\) ，使得Makima可以从点 \(v\) 出发无限地走下去? 输入格式： 输入第一行包含 \(2\) 个整数 \(n,m\) ，分别表示图的顶点数和图的边数。 接下来 \(m\) 行，每行包含两个整数 \(a_i,b_i(1\le a_i,b_i\le n,a_i\ne b_i)\) ，表示第 \(i\) 条边从顶点 \(a_i\) 指向顶点 \(b_i\) 。 输出格式： 在一行中输出一个整数，表示满足条件的顶点个数。 输入1： 5 5 1 2 2 3 3 4 4 2 4 5 输出1： 4 输入2： 3 2 1 2 2 1 输出2： 2 数据范围：...

模拟赛题讲解[1] 来自 Roundgod 2022-07-25 noi.ac #2676 题目描述： 给定一个带权连通无向图 \(G=(V,E)\) ，其中顶点个数 \(|V|=n\) ，边数\(|E|=m\) 图中可能包含重边以及自环。顶点编号为 \(1−n\) ，边的编号为 \(1−m\) ，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\)，权值为 \(c_i\). 输入保证图中所有边的权值各不相同，即对于所有\(1\le i<j \le n\) ，都有 \(c_i\ne c_j\) 。 你现在需要处理 \(q\) 个询问,其中第 \(k\) 个询问是一个三元组 \((u_i,v_i,w_i)\) ，表示: 如果在图 \(G\) 中添加一条连接 \(u_i\) 和 \(v_i\) 权值为 \(w_i\) 的边得到图 \(G^{\prime}\) ，图 \(G^{\prime}\) 的最小生成树是否一定包含新添加的边? 询问保证对于所有 \(1 \le j \le m\) ，都有 \(w_i\ne c_j\) 。 输入格式： 输入第一行包含 \(3\) ...

CF1468J Road Reform 题解 题目链接：CF1468J Road Reform 题意： 给定一个有 \(n\) 个节点，\(m\) 条无向带权边的图，和一个参数 \(k\)，第 \(i\) 条边权值为 \(s_i\)。 现在你要保留这个图中的 \(n-1\) 条边使得这个图变成一棵树，然后你可以对这棵树上的任意边进行修改，每次修改可以使这个边的权值加上一或减去一。 现在你需要使所有边权的最大值正好等于 \(k\)，求所有保留方案的最小操作数。 \(T\) 组询问。 保证初始时给定的图满足任意两个点互相可达，没有重边或自环。 \(1\leq T\leq 10^3\) \(1\leq n\leq2\times10^5,n-1\leq m\leq \min(\frac{n(n+1)}{2},2\times10^5)\) \(\sum n,\sum m\leq2\times10^5,~1\leq k,s_i\leq 10^9\) 模拟赛A题爆零，于是有了这篇题解 感谢 @Roundgod老师的耐心解释 Orz 本题要根据最小生成树的情况分类讨论 如果最小生成树的最大...

CF1304E 1-Trees and Queries 题解 题目链接：CF1304E 1-Trees and Queries 题意： 题面是从模拟赛搬过来的，因此掺杂了某些奇怪的成分(? 注：和原题好像就x,y,a,b反了一下 A国总共有N一座美丽的城市，一共有N-1条道路两两连接这些城市，使得任意两座城市之间都通过道路连通。 小虚接到了公司出差的派遣，来到了A国，在经过七天繁忙的工作后，小虚终于有时间在回程之前好好在A国旅游了。 因为尚且不知道公司能报销的旅游额度，小虚哥罗列了很多份旅游计划。 每个旅游计划包括出发城市编号x，结束城市编号y，以及公司能报销的道路费用k（即公司报销的差旅费能让小虚最多走k条道路）， 勤俭持家的小虚哥当然不会放过这样的旅游好机会，因此他无论如何，一定会走满k条道路（这导致了小虚可能会重复走某些道路以及重复到达某些城市）， 因此，小虚想请你帮他计算一下，对于每一份旅游计划，是否存在一个可能的旅游顺序， 使得小虚从x城市出发，一共走k条道路（一定要走满k条），最终在城市y结束旅行， 同时，对于一份计划，聪明的小虚还留了一招，那就是这份计划可以允许小...

CF645D Robot Rapping Results Report 题解 题目链接：CF645D Robot Rapping Results Report 题意： \(n\) 个机器人，每个机器人有一个不同的级别，级别介于 \(1\sim n\)，高级别的可以打败低级别的，现在给出 \(n\) 个机器人的 \(m\) 场比赛胜负情况，问最少需要前几场比赛就可以确定每个机器人的级别。 输入格式 第一行两个整数 \(n\) 和 \(m\) 表示机器人个数和比赛场数，之后 \(m\) 行每行两个整数 \(u\) 和 \(v\) 表示机器人 \(u\) 打败机器人 \(v\)。 输出格式 如果这 \(m\) 场比赛可以确定每个机器人的级别则输出最少需要前几场比赛就可以确定，否则输出 \(-1\)。 数据范围 \(2\leq n\leq 10^5\)，\(1\leq m\leq \min(\frac{n\times (n-1)}{2},10^5)\)。 不难发现这里有个单调性 即越多的边越有可能确定每个机器人的级别 当然如果所有边都不能确定的话，就输出无解即可 所以解法一：二分可能...

洛谷P2704 [NOI2001] 炮兵阵地 题解 题目链接：P2704 [NOI2001] 炮兵阵地 题意： 司令部的将军们打算在 \(N\times M\) 的网格地图上部署他们的炮兵部队。 一个 \(N\times M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 \(\texttt{H}\) 表示），也可能是平原（用 \(\texttt{P}\) 表示），如下图。 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。 图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 对于 \(100\%\) 的数据，\(N\le 100\)，\...

CF898F Restoring the Expression 题解 题目链接：CF898F Restoring the Expression 题意： 给你一个数字字符串s，现在你要这个字符串切割成三个部分a,b,c, 即s=a+b+c(这里的+为字符串相加，即后面的字符串拼接在前面的字符串后面) 同时要满足a，b，c三个字符串代表的十进制数字满足 a+b=c (注意a,b,c都不能有前导0，如数字 0099 是非法的) 问是否有这样一种分隔方式,题目保证有一组解，输出+号最靠前的一组答案 输入一行一个字符串s, 输出一行，形如a+b=c，满足s=a+b+c（注意要输出'+'号和'='号） |s|<=1e6,'0'<=si<='9' input: 12345168 output: 123+45=168 模拟赛秒出结论，结果脑抽挂了。。 这题是字符串哈希，其实很好想 一般的字符串哈希函数都是这么定义的 ...

CF808G Anthem of Berland 题解 题目链接：CF808G Anthem of Berland 题意： 给定 \(s\) 串和 \(t\) 串，其中 \(s\) 串包含小写字母和问号，\(t\) 串只包含小写字母。 假设共有 \(k\) 个问号。 你需要给把每个问号变成一个小写字母，共有 \(26^k\) 种可能。 对于每种可能，设 \(t\) 匹配 \(s\) 的次数为 \(f_i\)，请输出 \(\max(f_i)\) 。 \(1\leq |s|,|t|\leq 10^5,|s|\times |t|\leq 10^7\) 样例三告诉你了，这题不是贪心。 设 \(f_i\) 表示前 \(i\) 个字符的最大答案 似乎不好转移，因为我们不知道上一个放的 \(t\) 在哪里 显然 \(f_i\) 可以从 \(f_{i-m}\) 转移过来，因为这里正好可以放得下一个 \(t\) 但是 \(t\) 是可以重叠放的，例如 \(t=\tt{aabaa}\) 于是我们直接跳 \(m\) 的 \(\tt{fail}\) 数组，然后一个个转移吗？ 不，因为我们不知道 \(...