题解1203 div cf

好可恶一道题，怎么没人告诉我输出之间有空行（ 思路是先抽象成图，然后跑一边dfs记录边的前后顺序。 对于不能成环的情况，只需要再开个数组记录度数判断奇点即可。 若存在奇点则break掉，剩下的跑dfs、 //produced by miya555 //stupid mistakes:1.多测要清空 ......

找点图论练习题写，发现hdu又寄了，那就发到blog里吧。 思路：tarjan缩点判断DAG中点数是否为1。若是，则该图为强连通图。 //produced by miya555 //stupid mistakes:多测记得清空 //ideas:tarjan模板 #include<bits/stdc+ ......

题目链接 首先可以想到设状态 \(k_1,k_2\) 表示小 \(a\) 和小 \(uim\) 分别表示他们目前取得的得分，那么最终的答案便是 \(k_1=k_2\) 的时候。 但是这样设置状态的复杂度无疑是高的。并且十分浪费，所以考虑设 \(z\) 表示 \(k_1-k_2\) 的值。那么 \(z ......

题目传送门 前置知识 快速幂 解法 推式子： \(\begin{aligned} Z_n+Z_{n-1}-2Z_{n-2}&=(Z_n-Z_{n-2})+(Z_{n-1}-Z_{n-2}) \\ &=(S_n+Q_n-S_{n-2}-Q_{n-2})+(S_{n-1}+Q_{n-1}-S_{n-2} ......

Problem 考察算法：拓扑排序 + \(DP\) + \(Dijkstra\)。 题目简述 给出一个无向无权图，问从顶点 \(1\) 开始，到其他每个点的最短路有几条。 思路 先求出 \(1\) 号点到每个点的最短路 \(d_i\) 。 分析每条边 $(x,y) $： 如果 d[x] + 1 = ......

Problem 题目概述 给你一个无向图，边权都为 \(1\) ，求：离 \(1\) 号点最远的点的编号、最远的距离、有几个点是离 \(1\) 号点最远的。 思路 直接用：优先队列 \(BFS\)，先求出 \(1\) 号点到每个点的最短路，存到 \(dis\) 数组中，然后再求 \(max(dis[ ......

数据库编码在航电系统中的作用是毋庸置疑的，对于编码的理解往往需要结合应用场景来进行分析，必要的时候还需要放到模拟机中进行验证，才能够真正找出飞行程序设计与机载系统的最终解释之间的差别。 今天要聊的飞越转弯衔接TF/CF航段的话题,是在今年一次研讨会议中，让我觉得眼界打开，对个人的程序设计理念都产生了 ......

Codeforces Round 699 & 772题解 今天手感确实不错，看来合理的训练配合合理的休息是很重要的。前些日子的努力没白费。不过，怎么说呢，现在的形势不是我把算法题和基础知识做好的就行了，该从系统的角度去作为一个ld去思考问题了，感觉自己还是有点欠缺的，不过我也在积极努力的学习中，希望 ......

C. Jellyfish and Green Apple 题解 显然\(n \% m =0\)，答案一定为\(0\) 如果\(n > m\)，我们显然可以将\(n / m\)的苹果分给每个人，然后再处理$n % m $ 如果\(n < m\)，我们一定会将所有苹果一直对半切直到\(n > m\)，所 ......

[POI2003] Monkeys 题解 正着做貌似不好做，发现猴子是否掉落取决于“最后一根稻草”，也就是最后撒手的那个猴子，那我们考虑倒着把猴子网拼回去。这样，每群猴子掉落的时刻就是与 \(1\) 号猴子连通的时刻。 利用并查集可以维护猴子的连通性，但是怎么更新答案呢？这里用 vector 进行了 ......

目录luogu P4233 射命丸文的笔记CF1498E Two Houses luogu P4233 射命丸文的笔记 link 如果一个竞赛图含有哈密顿回路，则称这张竞赛图为值得记录的。 从所有含有 n 个顶点（顶点互不相同）的，值得记录的竞赛图中等概率随机选取一个。 求选取的竞赛图中哈密顿回路数 ......

A题简单的模拟计算，注意上取整的实现。 B题计算每个房间对应的每个最迟时间点，在这些时间点最取最小值，保证能安全通过所有房间。 D题拿到手就可以发现是贪心，但发现两部分会有冲突，也就是重复计算的部分。故提前找到两个数的lcm然后不计算lcm的倍数，为其他参与计算的数安排剩余数种的最大值和最小值，最后 ......

CF906C Party 洛谷：CF906C Party Codeforces：CF906C Party Problem 有 \(n\) 个人，给定他们的初始认识情况，每次操作可以选择一个人，让他当前认识的所有的人都相互认识。 问至少操作几次使得所有人都相互认识，并给出任意合法且次数最少的操作方案。 ......

Problem 题目概括 $n \times m $ 的网格，有些格子是障碍格。\(0\) 无障碍，\(1\) 有障碍。机器人有体积，总是在格点上。 有5种操作： 向前移动 \(1/2/3\) 步 左转 \(/\) 右转 每次操作需要 \(1\) 秒。 求从 \(x_1,y_1\) 到 \(x_2, ......

Problem 考察知识点：二分、贪心。 题目描述 对于给定的一个数组，现要将其分成 \(M\) 段，并要求每段连续，且每段和的最大值最小。 思路 二分答案出每段和最大值的最小值，然后贪心检验是否满足。 难点在 \(check\) 上。 策略：每次开始循环，如果没有超范围，就一直选，知道选满为止，求 ......

题意 给定一个有向无环图，对于任意一条边 \((u_i, v_i)\)，有 \(u_i < v_i\)。 定义一次从节点 \(u\) 开始的移动为如下过程： \(\tt{Alice}\) 选择从 \(u\) 出发的且未被删除的一条边。 \(\tt{Bob}\) 在从 \(u\) 出发的且未被删除的边 ......

题目传送门 前置知识 单调栈 简化题意 在一个 \(n \times n\) 的正方形内找到最大的由 \(0\) 组成的子矩形的面积。 解法 令 \(f_{i,j}(1 \le i,j \le n)\) 表示从 \((1,j)\) 到 \((i,j)\) 中以 \((i,j)\) 结尾的均为 \(0 ......

题目大意 题目大意 给你 \(n\) ( \(1\leqslant n\leqslant 5\cdot 10^5\) ) 条线段 \([l_1, r_1], [l_2, r_2], \cdots, [l_n, r_n]\) ( \(1\le l_i < r_i\le 2n\) )。保证每条线段的端点 ......

A. Everyone Loves to Sleep #include<bits/stdc++.h> using namespace std; void solve() { int n, h, m, t; cin >> n >> h >> m; t = h * 60 + m; vector<int> ......

题目大意 给出一个大小为 \(n\) 的树，\(q\) 次询问，每次给出一个大小为 \(m\) 的点集，判断是否有一条链覆盖这些点（这条链可以经过其他点）。 \(n,\sum m\leqslant 2\cdot 10^5\) , \(q\leqslant 10^5\)。 提示 提示 1 思考将 $m ......

这场的G怎么这么毒瘤啊/kk 听说正解是DP？我爆搜头一个表示不服！ statement 找出三元组 \((S, a, b)\) 的数量，使得 \(S\) 在 \(a\) 进制下和在 \(b\) 进制下的差为 \(X\) ，其中 \(0 \leq S_i <(min(a, b, 10))\) 。 首 ......

A. Two Vessels Problem 题目 Sol & Code 签到题 #include <bits/stdc++.h> typedef long long ll; int min(int a, int b) { return a < b ? a : b; } int max(int a, ......

题意 已知 \(m\) 个坏素数 \(b_i\)，定义一个数 \(x\) 的分值 \(f(x)=f(\frac xp)+k\)，其中 \(p\) 为 \(x\) 的最小质因数，如果 \(p\) 为坏素数则 \(k=-1\)，否则 \(k=1\)，初始 \(f(1)=0\)，一个数组的分值为其中所有数 ......

打篇题解巩固一下。 题意 给你两个集合 \(A\) 和 \(B\)，对于任意 \(A\) 集合中的元素，我们可以进行 \(2\) 种操作：\(a_i\gets \left\lfloor\frac{a_i}{2}\right\rfloor\) 或 \(a_i\gets 2\times a_i\)。问最 ......

题目传送门 前言 中文题目可以看 link 。 前置知识 Kruskal 重构树 | 最近公共祖先 简化题意 给定一个 \(N\) 个点 \(M\) 条边的有向图，共有 \(S\) 次询问，每次询问从 \(L\) 到 \(H\) 所有的路径中最小的权值的最大值（多组数据）。 本题即最大瓶颈路问题。 ......

题目传送门 前言 本题样例有问题，如果想要样例可以去 vjudge 上。 本题提交后可能会出现 UKE ，建议前往 link 提交，而且本篇题解中所提供的代码也为 link 代码。 前置知识 Kruskal 重构树 | 最近公共祖先 简化题意 给定一个 \(N\) 个点 \(M\) 条边的有向图，共 ......

Codeforces Round 901 (Div. 2) A - Jellyfish and Undertale 解题思路: 卡在最后秒放。 若\(x_i > (a - 1)\):那么该\(x_i\)的贡献为\(a - 1\)。 否则，该\(x_i\)的贡献为\(x_i\)。 代码: #inclu ......

901DIV2 A~D A: 大于等于\(a-1\)的贡献都是a-1. void solve(){ int ans=0; int a,b,n; cin>>a>>b>>n; ans+=b; for(int i=1;i<=n;i++){ int x; cin>>x; if(x>=a) x=a-1; an ......

思路 要求最长长度，想到可以二分答案。 那么现在需要考虑如何快速验证答案是否正确。 可以 \(O(n)\) 枚举区间左端点，因为有了长度，所以可以直接获得右端点的值，直接验证右端点是否合法。 因为要求区间的每个数都是右边的数的倍数，所以可以提前预处理每个点最远的满足这个条件的右端点，直接判断合不合法 ......

思路 首先发现，无论是 AB 变 BC，还是 BA 变 CB，最重要的都是 A，因为 B 的数量不会变化，C 既不是变化所需要的，数量还会变多，只有 A 是需要的并且数量还会变少。 首先思考 AB 变 BC 的情况，什么情况下可以继续变化呢？很显然 AB 前还有 A就可以继续变化，而后面因为 C的出 ......