题目大意 从点1出发，你要按顺序完成k个任务，每个任务有要求的起点终点。途中你可以在所在的位置建立一个传送门，而同时只能用两个传送门存在，如果超过两个，则必须（远程）关闭任意一个传送门。 解题思路 一 首先可以想到，所谓的k个任务有起点终点，就是按顺序走过2k个点，a->b,c->d这样的两个任务，可以转化为走过1->a->b->c->d这条路径。先想到一种暴力操作，每次求出dp[i][x][a][b]，表示已经完成i个任务，当前在x点，传送门分别在a,b。 二 如果我们要使用传送门来少走点路，肯定是走到一个接近x的传送门，在传送到接近终点的传送门。但是直接...

题目大意 有一个无穷大的二维网格，每个格子可以是1、2或者3，每个1旁边要有一个2和3，要使机器的占比最大。 解题思路 这道题当时卡住了我们好久，打表，枚举，玄学都用过了，结果解题方法居然这么简单。交错2和3，使每个1旁边恰好有一个2和3，而任意两个2和3不相邻。所以答案是2/3。 AC代码 言简意赅 #include<bits/stdc++.h> int main() { puts("0.666667"); }

题目大意 给定置换，求有多少个排列可以通过若干次这个置换，变成1到n的排列。 解题思路  如果一个置换中没有环，如{1,2,3}，只能找出一个符合条件的原排列：{1,2,3}。 如果有一个环，如{3,1,2}，由于环的长度为3（不同元素的数量），所以可以找出三种原排列：{1,2,3},[2,3,1},{3,1,2}。 如果有两个环，如{2,1,4,3}，由于两个环的长度分别为2（不同元素的数量），所以可以找出两种原排列：{1,2,3,4},[2,1,4,3}。  不难得出，如果有一个长度为n的环，那么可以找出n个原序列；而有多个环的时候，可以找出这些环长度的lcm。由于长度总和就是n，所以他们...

题目大意   给定一个1~n(2<=n<=500)的排列，有两种操作：   1.将倒数第二个数放到开头；   2.将第一个数放到最后；   连续的操作1（包括1次）称为一段。现在要将排列变成1~n，要使得段数尽可能少，输出这个最小值。   解题思路    我们可以想象出一个有n个数的圆盘，且有一个指针初始时指向最后一个元素处。   在这个圆盘上，连续的操作1，等价于改变指针指向的数的位置；而连续的操作2，等价于改变指针的位置。   所以，在这里只需要找出环上最长的一个上升子序列之后，再调整其余每一个数，所以答案就是剩下数的数量。    AC代码  #include<bits/...

题目大意   这道题从G题（Operating on a Graph ）延伸而来，附上G题大意：    给一个 n 个点的 Graph，第 i 个点一刚开始是第 I 种颜色，接着有 k 次操作，第 i 次操作有个参数 oi 代表颜色 oi 会侵略所有和自己相邻的颜色，于是所有和 oi 相邻的颜色全都变成 oi (若已没有颜色oi 已被侵略，则该次操作无效)，求最终每个点的颜色。        给出一棵具有n个顶点的树。设p是从0到n-1的排列，定义函数f(p)：p是输入运算符序列，f(p)是满足条件的操作数：执行第i个操作时，至少有一个顶点属于o[i]组。   令S为从0到n-1的所有可能排列...

题目大意   给定N个点构成的有根树，顶点编号从1-N，根节点为1号点。你可以选最多K个点（根必须选），使得所有点的最大“祖先距离”尽可能的小。   点x的“祖先距离”是在点x到根节点上的路径上，点x与第一个关键点的距离。若没有关键点，则距离为正无穷大。（例如1-2-3树上，关键点为2，则三个点的“祖先距离”分别为{+∞,0,1}。）   解题思路   借鉴了https://blog.csdn.net/tianyizhicheng/article/details/107512243的做法。   当答案一定的时候会有多种的k（比如说一条长度为4的链，放2个关键点和3个关键点的答案是一样的，都是1...

题目大意   把一个长为n(n<=105)的数划成若干段，使得划分出的数最大值和最小值的差尽量的小。（新数不能有前导 0）   解题思路   首先，要使最大差值尽可能小，脑袋一拍想到：如果把这个数每一位都划一段，不是最大值能控制在9以内了？   有了这个性质，再往里思考，因为最大是9，再脑袋一拍，就能想到划分只有两种情况：每段长度相等，或者长度最大差1。      对于每段长度相等的情况，我们只需要枚举长度n的每个因数，分别从前到后求出最大差，取min即可。   对于长度差1的情况，答案若要小于9，只可能是出现了99…9x和100…0y这样的划分，其中x=2...9中的数字, y=0.....

题目大意   给出一个集合的大小n，构造两个一样的集合A和B，分别包含{1,2,...,n}。   对两个集合中的不同数两两组合，每一对gcd(Api,Bqi)>1，求最多有多少对。   解题思路      思路一：   首先应该考虑有那些数不能参与匹配。显而易见1和大于n/2的素数一定没有匹配对象，可以直接忽略。  接下来考虑剩下的素数，倒序枚举每个素数p，找出所有未匹配的p的倍数，并且记下总数。 如果总数是偶数，那么这些数就可以完美两两匹配；否则留下2p（2的倍数最为常用，可以用于应对最后剩下的数），匹配其余的数。  最后只会留下一堆偶数，而它们两两都可以随意匹配。   AC代码  ...

题目大意   已知函数：     给定一些正整数对(ni, ci)，输出fci(ni)对1e9+7取余的值。   解题思路   官方题解已经简洁地叙述了：   观察公式，fc (x) 其实是 c 的若干次方，且指数要尽量大。最好的情况下，每次只消掉一个质因子。所以 fci(ni)就是cx的质因子个数。      我想到的是使用递归从n开始，每个数除了自己外最大的因数，直到一个素数或1。记录这个过程中递归层数，即要求c的几次幂。上来就打表存储，提升效率。（实际上和题解没区别）   AC代码   #include<bits/stdc++.h> using namespace&...

题目大意   其实这道题原题直译着实难理解，但是可以用一些形象的方式来理解：   给一个 n 个点的 Graph，第 i 个点一刚开始是第 I 种颜色，接着有 k 次操作，第 i 次操作有个参数 oi 代表颜色 oi 会侵略所有和自己相邻的颜色，于是所有和 oi 相邻的颜色全都变成 oi (若已没有颜色oi 已被侵略，则该次操作无效)，求最终每个点的颜色。（自官方题解PPT）   解题思路   对于颜色，在这里可以用并查集维护，根结点表示颜色。   操作一种颜色时，与其相连的所有点颜色都会改变，所以对于每个点至多会有一次侵略操作。   使用一组vector，记录第i种颜色所相邻的点，每次操作时...

题目大意 长度为n的排列是一个数组p = [p1,p2,...,pn] ，其中每个整数为1到n中的一个数，且每个数恰好出现一次。本题对于任意i，。（排列中的数两两对应）给定一个数组a （0≤a≤10^9，并且n是偶数且大于等于4）。 输出排列的最小和次小成本。（每对数之差的总和） 解题思路 显然最小花费很好求，对元素进行排序，对相邻的两两求差，求和即可。 次小的就比较棘手，我们先举几组样例，从小到大排序，并找出每组的次小匹配方案。将每个被减数标上'+'号，每个减数标'-'号。    1 1 3 4 5 9 2 3 5 8 1 3 5 6 7 8 9 10 13 14    - - + - + ...

题目大意   有t(1≤t≤105)次查询，每个查询给出两个正整数a,b（a，b≤2×106）。 输出一组满足以下条件的四个正整数c,d,e,f：     如果没有解决方案，输出“ -1 -1 -1 -1”。   解题思路   进行赛后冷静分析，可以归纳出三种情况，这三种情况只需在代码中依次判断：      情况一：b=1或者b是质数时，一定无解。这种情况很好理解。 情况二：gcd(a,b)!=1时，求出g=gcd(a,b)，一定存在一组解：c=a/g+1，d=b/g，e=1，f=b/g。    情况三：当gcd(a,b)=1，即ab互质时，因为这里b不是质数，可以分成两个相异质因数--d,f...

题目大意   爱丽丝右手掌的形状如下：        按顺时针或逆时针顺序给出手掌每个端点的平面坐标，输出每个手印是左手还是右手。形状可以旋转和平移，但是不会被放大或缩小。爱丽丝的左手掌形状与她的右手掌对称。    解题思路    由于各边的长度不会被放大或者缩小，长度都固定，所以可以通过边长来进行判断。      可以发现，手掌下方的这一条边是最长的，而这条边到大拇指的距离为6，到小拇指的距离为8。   所以只要找出这条唯一长9的边，然后找之前与之后边的长度即可。 但是由于输入方向不一定，所以要考虑用平面几何的向量来判断，找出手掌的方向。 在这种情况下，找到长为9的边（向量A）后，直接看下一...

题目大意   一个游戏包含n个阶段，每个阶段有四种类型： 类型0：没有鱼也没有蛤。 类型1：只有一只蛤。 类型2：只有一条鱼。   类型3：有一条鱼和一只蛤。    在每个阶段都可以执行四种操作之一： 1.用一只蛤换一包鱼饵。   2.如果有一条鱼，可以无需鱼饵抓到这条鱼。   3.无论在此阶段有没有鱼，都可以使用一包鱼饵捕获一条鱼。   4.跳过阶段。      要求求出每局游戏中能抓到鱼的最大条数。   给出样例数量（游戏次数）t (1≤t≤2.5×105)。每次游戏给出阶段数n(1≤n≤2×106)以及一个长度为n的字符串，s[i-1]为第i阶段的类型。n的总和不超过2×106。   解...