题目描述  给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小 写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没 有M，则从串的开始算起）开始的解压结果（称为缓冲串）。bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。  输入描述: 输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。 输出描述: 输出仅一行，即压缩后字符串的最短长度。 示例1 bcdcdcdcdxcdcdcdcd 12 解题思...

A、斗兽棋 题目描述 高飞和zqf玩起了斗兽棋，每个人有四个棋子，分别是“elephant”，“tiger”，“cat”，“mouse”，分别代表大象、老虎、猫、老鼠，（大象吃老虎，老虎吃猫，猫吃老鼠，老鼠吃大象）其他都是平局，每次出一个棋子。你能知道谁能获得胜利吗？ 输入描述: 多组输入，每组输入包含一行，两个以空格分隔的字符串分别代表高飞和zqf出的棋子，保证两个字符串一定在上述的四个字符串中。 输出描述: 如果高飞赢了或者平局，输出"gaofei tql"，zqf赢了输出"zqf tianxiawushuan"。 输入 tiger elephant...

B、Boundary 参考兰子大佬的题解  问题大概就是给你二维平面的n个点，坐标都是整数，问你选取某一个点为圆心（这个点不一定要是给出的n个点中一个）使得在这个点为圆心过原点的情况下覆盖到给出的n点中最多的点，问最多覆盖几个点！   其实知道方法是可以写出来的，比赛的时候最开始看到0/80+……就觉得这玩意不简单，而且英语小白的我一开始没读出加粗的那句话，直接二重枚举认为给出的点才可能是圆心，WA的理所当然。。听说map计数给卡了常数太大了。。用了二元组去排序计算，还有知识点就是知道三个点的平面坐标求圆心坐标。。这玩意直接推式子再用克莱姆法则替换也能算到，涉及线性代数的知识）马上大二了哎嘿。...

B、Circle  题目描述现在我们要把1\ldots n1…n这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。输入描述:一行一个整数n(1≤ n≤ 1000)。输出描述:一行一个整数表示答案。  解题思路 互质对数最多，那么相邻的数字直接1 2 3 4 ……排列下去就行了把，输出n就行了。 print(int(input()))   D、绝地求生(pubg)  问题描述给出T组数据，每行输入a，b两个long long范围内的整数，求他们的最小公倍数  坑点就是会爆掉long long，要么__int128，或者用python。或者用a//gcd(a,b)*b都...

题目描述  给出n个点，m条边的情况，问如果要生成的最小生成树唯一需要删除的边权和是多少？  解题思路 最小生成树kruskal求法这里不多赘述，就是对边权排序之后，用并查集去连接集合，知道剩下一个集合结束。那么我们知道，如果要生成最小生成树唯一？为什么不唯一？就是因为存在连接两个集合中存在多种边权相同的方法。那么我们直接把这些边权相同的但是连接相同的两个集合的一些边，留下一条，其余删掉就是最终答案了。  #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll...

题目描述  小明现在要追讨一笔债务，已知有n座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为1的城市，欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天，而欠债人每天都会挥霍一定的钱，等到第k天后（即第k+1天）他就会离开城n并再也找不到了。小明必须要在他离开前抓到他（最开始为第0天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？输入描述:第1行输入三个整数n，m，k，代表城市数量，道路数量和指定天数第2-m+1行，每行输入三个整数u，v，w，代表起点城市，终点城...

题目描述  栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A'，满足(a'1+b1)%k = (a'2+b2)%k = …… = (a'm + bm)%k。输入描述:第一行一个数T，表示有T组数据。对于每组数据，第一行三个整数，n, m, k。第一行输入n个数, a1,a2,…,an, 表示A数列中的数，第二行输入m个数, b1,b2,…,bm, 表示B数列中的数。输出描述:每一组数据输出一行，满足条件的连续子序列数量。  解题思路 题目给出的数据比较难懂，子序列说明可以不连续，那和KMP有点类似问A串中有多少满足题目条件的子序列。再把条件转换一下。...

F、Infinite String Comparision  给出两个字符串a，b，询问的是在无限自循环连接的前提下两个字符串的大小关系  比赛时应付写法，无限循环不可能去真正在无限的时间才可能出答案，那么在一定时间的循环节之内就可以得到答案，也就是说如果你没有很好的办法去证明出正确的解法，那么我们根据题目给出的时间范围和数据输入，在一定的常数内通过游标的方式一直比较两个字符串，如果在一定次数内没有得到谁大谁小那么就直接跳出循环判断相等。否则就判断大小关系，常数可以自己把握。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC...

解题思路 题目很明确，最少的花费就是最小生成树的权值，我选择prim算法求最小生成树，比较简单，套板子主要理解prim里面的两栖边的意义。prim理解起来就不难了。  //无向图最小生成树 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) typedef long long ll; inline int read() { int s = 0, w = 1; char ch = getchar(); while (ch...

题目意思 给出t组数据，每组数据第一行n个节点m条边的无向图给出边权信息，问选其中三个点最短路径之和最大值为多少。 解题思路 既然要我们最短路可能要用到dijkstra，又因为点可以随意确定，所以只要枚举中间点k，对k求最短路里面最长的两条路之和在return主函数判断最大值即可。如果只有一条路记得return 0出去主函数。  #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <b...

题目意思 大水题，给出n个顶点的m条边的有向带权图。求从1到n的方法数有多少条？是不是很震惊，边权不同控制发出时间即可同一时间到达，所以边权的信息没什么用。 解题思路 我写的dfs，回溯法先求道各个入点的路径数，累加就是这个出度点的答案。使用记忆化搜索可以简化计算时间 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespac...

题目意思 给出n个点m条边，找出最小生成数的花费 解题思路 挺简单的最多100000个点，500000条边，可以看到是个稀疏图大概，采用kruskal求最小生成树  #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.ti...

题目意思 给出n个节点构成的一棵树，根节点权值为0，重儿子权值为父节点的权值，轻儿子为父节点权值+1。问最大的权值之和为多少？注释应该码的比较清楚用个递推算一下。 Code  #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);c...