Q779’s Blog

CF1360E Polygon 题解 题目链接：CF1360E Polygon 题意： 然后给你个 \(n\times n\) 的地图，问你合不合法。\(n\le 1000\) 。 是不是有人和我一样想复杂了捏？其实代码很简单，直接考虑每个点就好了。 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x,int y) { x < y ? x = y : 0; } void down(int &x,int y) { x > y ? x = y : 0; } #define N ((int)()) int n; char a[55][55]; void solve() { cin >> n; bool ok = 1; for(int i=1; i<=n; i++) for(int j=1; j<...

CF1343E Weights Distributing 题解 题目链接：CF1343E Weights Distributing 题意： 给出一个有 \(n\) 个点，\(m\) 条边的无向图和一个长为 \(m\) 的权值序列 \(w\)。 你可以随意安排边权（每条边权对应 \(w\) 中的一个数，不可以重复）。 求 \(a\) 到 \(b\) 的最短路与 \(b\) 到 \(c\) 的最短路的和的最小值。 输入格式： 多组数据。每次给出 \(n,m,a,b,c\) 。第一行给出 \(n\) 个整数 \(w_i\) 。接下来 \(m\) 行给出边 \((u,v)\) 。 输出格式： 对于每组数据，输出最小值。 数据范围： \(1\le n-1 \le m \le \min\left\{\frac{n(n-1)}{2},~2\times 10^5\right\},~1 \le \sum n,\sum m \le 2 \times 10^5,~ 1 \le w_i \le 10^9\) 。 注意到 \(a\leadsto b\) 和 \(b \leadsto c\) 的最短路径...

洛谷CF1336A Linova and Kingdom 题解 题目链接：CF1336A Linova and Kingdom 题意： 给定 \(n\) 个节点的有根树，根是 \(1\) 号节点。 你可以选择 \(k\) 个节点将其设置为工业城市，其余设置为旅游城市。 对于一个工业城市，定义它的幸福值为工业城市到根的路径经过的旅游城市的数量。 你需要求出所有工业城市的幸福值之和的最大可能值。 输入格式： The first line contains two integers \(n\) and \(k\) ( \(2\le n\le 2 \times 10^5\) , \(1\le k< n\) ) — the number of cities and industry cities respectively. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) ( \(1\le u,v\le n\) ), denoting there is a road connecting cit...

CF1383A String Transformation 1 题解 题目链接：CF1383A String Transformation 1 题意： 给定两个长度相等的字符串 \(A,B\) ，最小化操作数使得 \(A\) 变成 \(B\) 。 一次操作定义为：在 \(A\) 中选取若干个相同的字母 \(x\) ，并将所有 \(x\) 改成字母 \(y(x<y)\) 输入格式： 多组数据，\(n=|A|=|B|\) ，然后两行 \(A,B\) 。 输出格式： 每组数据输出一行，表示最小花费。 数据范围： \(1\le \sum |A|, \sum |B| \le 10^5\) 。 依次考虑每个 \(a_i,b_i\) 。如果存在 \(a_i > b_i\) 一定无解；同理若 \(a_i=b_i\) 直接跳过 \(i\) 。 否则若 \(a_i < b_i\) ，如果 \(a_i\) 不能到达 \(b_i\) ，则连一条 \(a_i\) 到 \(b_i\) 的有向边并使答案加 \(1\) 。 如果 \(a_i\) 能到达 \(b_i\) ，这意味着我们可以让...

CF1387B1 Village (Minimum) 题解 题目链接：CF1387B1 Village (Minimum) 题意： 村里 \(n\) 个房子构成了一个 \(n\) 点 \(n-1\) 条边的树结构（下标从 \(1\) 开始），每条边长度均为 \(1\)。一开始每个房子里分别有一个村民。 现在所有村民都需要搬家（改变自己所在的点），搬家后依然需要满足每个房子里有且只有一个村民。也就是说，如果原本位于点 \(i\) 的村民搬到了点 \(v_i\)，那么应当满足： 对于任意点 \(i\)，有 \(i \neq v_i\)。 对于任意两个不同的点 \(i\) 与 \(j\)，有 \(v_i \neq v_j\)。 村民 \(i\) 搬家的花费是点 \(i\) 到点 \(v_i\) 的树上距离（即树上二点间相隔的边数），总花费为所有村民花费之和。求总花费的最小值及其方案。 输入格式： 第一行一个正整数 \(n\)，表示树的点数。 接下来 \(n-1\) 行每行二整数 \(a\) 和 \(b\)，表示树上有一条连接 \(a\) 和 \(b\)，长度为 \(1\) 的边。...

CF1385E Directing Edges 题解 题目链接：CF1385E Directing Edges 题意： 给定一张 \(n\) 个节点 \(m\) 条边的混合图，要求对无向边定向，使得原图不存在环。 输入格式： 多组数据，每组先给出 \(n,m\) ，然后 \(m\) 行形如 \(\mathtt{op\ x\ y}\) 。 若 \(\mathtt{op = 0}\) ，则该图存在无向边 \((u,v)\) 。若 \(\mathtt{op=1}\) ，则该图存在有向边 \(u\to v\) 。 输出格式： 如果可以做到，请输出 YES ，并输出这张图（次序随意）；否则输出 NO 。 数据范围： \(\sum n \le 2 \times 10^5,~\sum m \le 2 \times 10^5\) 。 考虑先无视无向边，然后对原图做一遍拓扑排序，如果已经有环了肯定无解。 否则对于所有无向边，我们直接让拓扑序小的指向拓扑序大的点。 这样原图就是一个 DAG （有向无环图）了。 时间复杂度 \(\mathcal{O}(Qn)\) 代码： #include <...

【物理】弹性碰撞与非弹性碰撞 常见误区 什么嘛，已经开始文化课了。又没说博客不能写文化课 一、弹性碰撞、非弹性碰撞及完全非弹性碰撞 弹性碰撞经历了两个阶段：形变阶段和恢复阶段。 形变阶段是「系统的动能」转化为「系统的弹性势能」。 恢复阶段是「系统的弹性势能」转化为「系统的动能」。 非弹性碰撞与弹性碰撞的区别在于恢复阶段，系统的弹性势能并未全部转化为系统的动能。 完全非弹性碰撞是一种特殊的非弹性碰撞，它没有恢复阶段，也就是说形变是永久的形变。 二、对两种碰撞认识的常见误区 “粘在一起”、“碰后共速”等关键词，意味着碰撞是完全非弹性碰撞。 完全非弹性碰撞动量守恒，动能不守恒，特点是碰后共速。 微观粒子发生碰撞时不一定直接接触。 当两个微观粒子相互接近到一定程度，就具有碰撞的特点。 正碰不一定是弹性碰撞。 因为正碰和弹性碰撞是从不同角度对碰撞进行分类的。 例：如图所示，三个质量相同的滑块 \(A,B,C\) 间隔相等地静置于同一水平直轨道上。 现给滑块 \(A\) 向右的初速度 \(v_0\) ，一段时间后 \(A\) 与 \(B\) 发生碰撞。 碰后 \(A, B\) ...

MacOS 下使用C++万能头文件 系统版本：MacOS Ventura 13.0, M1 真服了，SB iCloud 差点把我两年的文件全删了。 这里介绍一个不用终端操作的办法。 首先来到 /Library/Developer/CommandLineTools/SDKs/MacOSX13.0.sdk/usr/include 目录 可以在 访达 里按下 cmd + shift + G 然后粘贴进去，进入指定目录。 然后新建一个文件夹 bits ，并在 bits 文件夹中新建一个 stdc++.h 文件，推荐 Sublime Text。 stdc++.h 的代码： // C++ includes used for precompiling -*- C++ -*- // Copyright (C) 2003-2014 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistr...

CF1204C Anna, Svyatoslav and Maps 题解 题目链接：CF1204C Anna, Svyatoslav and Maps 题意： 对于 \(n(n \le 100)\) 个点有向无环图，给出一个由 \(m(m \le 10^6)\) 个点组成的的路径 \(p\)（不保证是简单路径，但保证对于 \(1 \le i < m,p_i\) 与 \(p_{i+1}\) 之间有边）， 要求从 \(p\) 中选出一个最短的子序列 \(v\)（假设长度为 \(k\) ），满足 \(v_1=p_1,v_k=p_m\) ，并且 \(p\) 是按顺序经过 \(v\) 的最短路径之一。 输入格式: The first line contains a single integer \(n\) ( \(2 \le n \le 100\) ) — the number of vertexes in a graph. The next \(n\) lines define the graph by an adjacency matrix: the \(j\) -th cha...

CF1209D Cow and Snacks 题解 题目链接：CF1209D Cow and Snacks 题意： \(n\) 种小吃，\(k\) 个客人，每个人喜欢两种编号不同的小吃。但是每种小吃在小吃店里只有一坨。 客人按顺序进入小吃店，会买走所有她喜欢且仍在店铺里的小吃。如果一个客人买不到任何一束小吃，那么她就会十分沮丧导致变成肥宅。现在你可以自己安排这 \(k\) 个人的顺序，使得肥宅的数量最小。 注意，只拿到一种小吃的客人不会变成肥宅。 输入格式： The first line contains integers \(n\) and \(k\) ( \(2 \le n \le 10^5\) , \(1 \le k \le 10^5\) ), the number of snacks and the number of guests. The $ i $ -th of the following \(k\) lines contains two integers \(x_i\) and \(y_i\) ( \(1 \le x_i, y_i \le n\) , \(x_i...

MacOS vscode 缺省源&配置文件 MacOS 的 vscode 配置。ubuntu 的到时候再说。 缺省源 更新日期：2022年11月02日 { // Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and // description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are: // $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the // same ids a...

洛谷P8818 [CSP-S 2022] 策略游戏 题解 题目链接：P8818 [CSP-S 2022] 策略游戏 题意： 小 L 和小 Q 在玩一个策略游戏。 有一个长度为 \(n\) 的数组 \(A\) 和一个长度为 \(m\) 的数组 \(B\)，在此基础上定义一个大小为 \(n \times m\) 的矩阵 \(C\)，满足 \(C_{i j} = A_i \times B_j\)。所有下标均从 \(1\) 开始。 游戏一共会进行 \(q\) 轮，在每一轮游戏中，会事先给出 \(4\) 个参数 \(l_1, r_1, l_2, r_2\)，满足 \(1 \le l_1 \le r_1 \le n\)、\(1 \le l_2 \le r_2 \le m\)。 游戏中，小 L 先选择一个 \(l_1 \sim r_1\) 之间的下标 \(x\)，然后小 Q 选择一个 \(l_2 \sim r_2\) 之间的下标 \(y\)。定义这一轮游戏中二人的得分是 \(C_{x y}\)。 小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明...