2020暑期D2-H 思路+证明主为自用，欢迎指正。 https://ac.nowcoder.com/acm/contest/5667/H 前置知识： 题意：给定一个集合MS和q种操作，操作共三种。1.插入x。2.删除x。3.查找MS中是否存在a、b，使得a、b、x构成三角形。能输出“Yes”，反之“No”。 思路：首先，三个数之间的差越小，构成三角形的可能性就越大，由于存在插入与删除的操作，否则集合排序，搜索找相邻即可。故，一定要用树的结构来实现插入与删除，由于要实现数之间差最小，容易通过前后缀存入相邻数据。设，a为b的前驱，若x为a、b中的最大边，若a+b>x，则成立；若x非最大边，...

2020暑期D2-C 思路+证明主为自用，欢迎指正。 https://ac.nowcoder.com/acm/contest/5667/C 前置知识：树中链的覆盖，节点A到节点B的经过尽可能少的点的路径（最短路径），亦可以理解成一种遍历经过的路径，经过的点和边都是覆盖。dfs序，树在dfs遍历时，树的节点出入栈时的序列。 题意：一颗具有n个节点的树，问是否存在尽可能少的链覆盖所有的节点。 思路：设s为叶结点数，则连最少存在s/2条，向下取整，可以简单理解链的端点取相邻的节点，路径将最短，即容易出现无法经过祖父节点的情况。结论一，链经过的节点应该尽可能多。故端点的选择间距尽可能大，容易想到二分叶...

2020暑期D3-D 思路+证明主为自用，欢迎指正。 https://ac.nowcoder.com/acm/contest/5668/D 前置知识： 题意：一无限大二维平面中，存在无穷的单位方格，所有方格初始为白色，现给n方格涂黑，要求存在m个点对。点对符合：上下左右相邻的点为异色。输入 n，m。输出 存在则‘Yes’，且给出符合坐标；否则‘No’。 思路：先判是否存在，不存在的情况同意输出‘No’。容易得到若有n个黑格，则点对数量m必然存在上下界，同时m必须为偶数（若存在黑格相邻，点对数量4n-2相邻次数）if(m>4n||m%2)，则为‘No’；设黑格存在与不同a行，不同b列。则点...

2020暑期D2-G 思路+证明主为自用，欢迎指正。 https://ac.nowcoder.com/acm/contest/5667/G 前置知识：sort(add1,add2,cmp)。 bitset定义以及其常用函数。 二分查找函数：lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。（pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。） upper_bound(起始地址，结束地址，要查...

2020暑期D1-F 思路+证明主为自用，欢迎指正。 https://ac.nowcoder.com/acm/contest/5666/F 思路+证明：a、b字符串可无限复制。若存在a、b可相等则输出‘=’，若不满足则判断‘>’&'<'。字符串比较首先分等长与不等长，由于求的是存在，故若存在相等则必然等长。（条件一，两无限字符串等长）设len1=len(a),len2=len(b)则令xlen1=ylen2,即求公倍数。（实际上可以写上最小，不过稍后证明内容包含，故这里扩大范围写成公倍数）若xa==yb（a复制x次==b复制y次）设x==y，则len1==len2，则a==...

简单图证：  #define _CRT_SECURE_NO_WARNINGS #include<cstdio> #include<algorithm> #include<iostream> using namespace std; typedef long long LL; const LL mod = 998244353; const LL N = 1010000; LL fib[2 * N + 2]; LL x1; LL x2; LL n; void set(LL X) { fib[1] = 1; fib[2] = 2; for(int i=3;i&lt...