Q779’s Blog

模拟赛题讲解[7] 来自 Roundgod 2022-07-27 noi.ac #2682 题目描述： 给定一个有向图 \(G=(V,E)\) ，其中顶点个数 \(\vert V\vert=n\) ，边数 \(\vert E\vert=m\) 。顶点编号为 \(1-n\) ，边的编号为 \(1-m\) ，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\)。 你最少需要添加多少条有向边，才能使得能够从 \(1\) 到达所有顶点? 输入格式： 输入第一行包含 \(2\)个整数 \(n,m\)，分别表示图的顶点数和图的边数。 接下来 \(m\)行，每行包含两个整数 \(a_i,b_i(1\leq a_i,b_i\leq n,a_i\neq b_i)\) ，表示第 \(i\) 条边从顶点 \(a_i\) 指向顶点 \(b_i\)。 输入保证图中不存在重边和自环。 输出格式： 在一行中输出一个整数，表示最少需要添加的有向边条数。 输入1： 9 9 1 2 1 3 2 3 1 5 5 6 6 1 1 8 9 8 7 1 输出1： 3 输入2： 5 4 1 2 2 3 3 4 4...

模拟赛题讲解[6] 来自 Roundgod 2022-07-27 noi.ac #2683 题目描述： 给定一个连通无向图 \(G=(V,E)\) ，其中顶点个数 \(\vert V\vert=n\) ， 边数 \(\vert E\vert=m\) 。顶点编号为 \(1-n\) ， 边的编号为 \(1-m\) ，第 \(i\)条边连接顶点 \(a_i\) 和 \(b_i\)。输入保证图中不存在重边。 你现在需要对图中的每条边定向: 对于原图中的每条无向边 \((u,v)\)，你需要选择将它变为有向边 \((u,v)\)或者有向边 \((v,u)\). 对于图 \(G\)中的每个顶点 \(v\in V\)，定义 \(r_v\) 为将图定向之后 \(v\) 能够到达的顶点个数，你需要选择一种定向使得最大化 \(\min\limits_{v \in V}r_v\)，也就是最大化所有 \(r_v\) 的 最小值。输出这个最大化的值。 输入格式： 输入第一行包含 \(2\)个整数 \(n,m\)，分别表示图的顶点数和图的边数。 接下来 \(m\)行，每行包含两个整数 \(a_i,b_i(1...

# 洛谷P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G 题解 题目链接：P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G 题意： 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 \(A\) 喜欢 \(B\)，\(B\) 喜欢 \(C\)，那么 \(A\) 也喜欢 \(C\)。牛栏里共有 \(N\) 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。 对于 \(100\%\) 的数据，\(1\le N\le10^4\)，\(1\le M\le5\times 10^4\)。 首先考虑最简单的情况 如果给定的是一个DAG（有向无环图） 当且仅当存在两个及以上出度为 \(0\) 的结点时，答案为 \(0\) （无解） 但是题目给的不一定是DAG 注意到每个强连通分量内的结点两两可达 用这题的语言就是，某个强连通分量内的所有结点可以同时为“明星” 于是考虑强连通分量缩点，接下来就是DAG的情况了 注意此时的...

模拟赛题讲解[5] 来自 Roundgod 2022-07-26 noi.ac #2678 题目描述： 对于任意非负整数 \(x\) 和 \(m(2\le m\le 10)\) ，定义 \(f_m(x)\) 为 \(x\) 在 \(m\) 进制下的各位数字之和。给定两个整数 \(k\) 和 \(m\) 。你需要计算在所有满足是 \(k\) 倍数的正数 \(x\) 中,最小的 \(f_m(x)\) 值是多少。 输入格式： 输入第一行包含两个整数 \(k,m(2\le m\le 10)\) 。 输出格式： 在一行中输出一个整数，表示答案。 输入1： 5 10 输出1： 1 输入2： 79992 10 输出2： 36 输入3： 4 5 输出3： 4 数据范围： 对于 \(30\%\) 的数据，\(1\le k\le 100\) 对于 \(100\%\) 的数据，\(1\le k\le 10^6\) 题解： 尝试以最小的花费构造一个数使得其是 \(k\) 的倍数 如果我们把这个构造的过程放在模 \(k\) 的意义下 问题就转化为了，如何以最小的花费构造一个 \(0\) 设 \(d_x,~...

模拟赛题讲解[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结束旅行， 同时，对于一份计划，聪明的小虚还留了一招，那就是这份计划可以允许小...