题目链接：https://ac.nowcoder.com/acm/contest/5674/K 题目大意：有一个土拨鼠在节点1，一个橘子在节点n，在t时刻之前土拨鼠向着n走，橘子不动，从t时刻开始，橘子开始抓土拨鼠，土拨鼠开始跑，土拨鼠 1m/s， 橘子 2m/s，问还有多长时间橘子才能抓到土拨鼠。 解题思路：幸好是一个直线运动，没有二维的考虑。首先要求的 t 时刻土拨鼠的位置，然后土拨鼠需要逃跑，所以得与 n 点背向而跑，这时候有俩种可能1.土拨鼠可以跑的路很长，orange抓到它也没跑到尽头。2.土拨鼠可以跑的路很短，土拨鼠跑到路的尽头等待orange来抓它所以得求土拨鼠能跑的最远距离， ...

题意：一共有m天，每天有k[i]件衣服，每条衣服有值a[i],欲选取n件衣服，使得选择出的n条衣服的值的最大差值最小。​解题思路：采用尺取法，根据区间的特征交替推进左右端点求解，可以避免了大量的无效枚举，本题区间间枚举都是根据区间特征有方向的枚举。适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，即通过改变两端点的位置得到有效解答。 #include<bits/stdc++.h> using namespace std; const int MAX = 2e6+5...

题目来源： https://ac.nowcoder.com/acm/contest/5672/B 题意： 将n×m个口罩打包成若干份，要求打包完后无论是分给n家医院还是m家医院，都能够均分。要求输出总份数最少的方案中字典序最大的。（1≤T≤100,1≤n,m≤104） 解题思路：dfs+递归，关键是在约束条件下同时满足两个条件，所以要一步步推衍。 #include <bits/stdc++.h> using namespace std; int n, m; vector<int> ans; void dfs(int n, int m) { if(n < m) sw...

题目来源：https://ac.nowcoder.com/acm/contest/5673/G题意：一套牌有四种属性，每种属性都有三种特征，shapes (one, two, or three), shape (diamond, squiggle, or oval), shading (solid, striped, or open), color (red, green, or purple)，如果是*，可以选任意一种。给出n套牌，每套牌给出[<number>][<shape>][<shading>][<color>]，问有没有三张牌符合同一属...

题目来源：https://ac.nowcoder.com/acm/contest/5673/K题意：有n道菜，第i道菜的利润为ai，且有bi盘。你要按照下列要求给顾客上菜。每位顾客至少有一道菜给顾客上菜时，都必须从第一道菜开始，上连续的编号的菜，例如，你可能给一位顾客 上的菜为第一道，第二道，第三道，但是不能为只上第二道而不上第一道，或者第一道，第三道中间缺少第二道。求这些菜能够容纳的最大顾客数，并且求出在容纳最多顾客时的利润最大为多少。 解题思路：首先要求最大利润，可以采用贪心策略，在满足条件时，优先选取利润最大的，由于是 1~i的连续的菜，可以先求出前i份菜的利润的前缀和。然后按利润前缀和...

题目来源：https://ac.nowcoder.com/acm/contest/5670#submit/%7B%22problemIdFilter%22%3A209988%2C%22statusTypeFilter%22%3A5%7D题意：给你一个p的全排列，有两种操作：选择倒数第二个挪到第一个把第一个挪到最后一个如果是连续的第一种操作，则只花费1，第二种操作不花费。问最少的花费使得p的全排列变成一个顺序的排列。 题目思路：最少花费，分析了一下，要了解这个两个操作的本质，其实画了一下发现，实际是把最后一个数挪到前面任意两个数之间，那么思路就是：因为任意一个数花费为0可以成为最后一个，而最后一...

题目来源：题意：给定排列 p，每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价，求给 p 排升序最优策略下最小代价的期望，对 998244353 取模。 思路：最优策略，感觉有点像dp，但其实不是，枚举又怕超时间了，可以将问题等价转化一下：因为枚举的是可以设置分割点的区间，分割点k格一个，所以把这个区间向前移动k的倍数格因此，可以将所有的区间向前移动，一次k格，与其他区间出现交集，但是需要考虑两端的交集，这是一个问题。可以将一个区间的左端点+1，右端点右边的位置-1，然后求前缀和。这样可以得到，每个位置的数值就是重叠在上面区间的个数。最后找一下有没有满足条件的数值。 #includ...

题目来源；https://ac.nowcoder.com/acm/contest/5669/B 题意：求  思路：代入数值计算得出最后的答案一定是输出的n的幂，然后就是确定这个幂的指数，先预处理出所有数的最大因子（1）只要这个最大因子不是 1，指数就要加 1；（2）接着找这个最大因子的最大因子是不是1 ，不是 1 的话继续上面的操作；如果最大因子是1的话就输出答案：（就是个迭代） #include<bits/stdc++.h> using namespace std; const int N = 1e6+1; const int mod = 1e9+1; int f[N]; int...

题目链接：https://ac.nowcoder.com/acm/contest/5668/E 题意：给一个序列s，在这个序列里面找出两种不同序列的两两匹配，使得所有两两匹配的差的和最小，输出这个和。 关键词：找规律与动态规划。 做题思路：硬规律，害，推断出长度是4与6的划分（推不出来就GG了，还是要多看看多积累），然后再用动态规划。 #include <bits/stdc++.h> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn=2e6+10; ...

题目来源：https://ac.nowcoder.com/acm/contest/5668/F 题意：c/d-e/f=a/b,这里给出a，b，求可行的c，d，e，f（这里要求d与f值小于b） 解题思路：这是一道数论题，需要一定的数学知识去将这个问题转化为我们熟悉的问题。先通分变为（cf-be）/df=a/b，再假设a1/b1为a/b的最简化的分数。具体验证方法如下： 。所以问题转化为一个求b的互质因子问题。再一个大的范围内求出第一个被b整除的质数d，然后求f #include <bits/stdc++.h> using namespace std; #define mem(a,b)...

题意：有一个图，有n个点，m条边，点的下标从0到n，对于点i，其开始时属于i—— groud，总共操作q次，每次操作时给出一个n，将所有与n——group直接相连的group加入到n-groud中，在所有操作结束后，求每个点所在的group。在所有操作结束后，求每个点所在的小组。 做题历程：初见不知题中意，再见已是补题人。 做题方法，此题要运用到并查集还有链表，首先是并查集是什么？我搜了一下举例说明。   #include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back ...

题目来源:https://ac.nowcoder.com/acm/contest/5668/C 题意:按顺时针或逆时针顺序给出手掌每个端点的平面坐标，输出每个手印是左手还是右手。形状可以旋转和平移，但是不会被放大或缩小。爱丽丝的左手掌形状与她的右手掌对称。 做题历程:初看此题以为是一个统计图一样的玩意,后来发现是每次给20点,通过这20个点判断左右手,这就需要去寻找几何规律了。 解题思路：首先根据题目的几个样例寻找其中的几何关系，运用这个几何关系我们来寻找判断左右手的一般性规律。可以发现，手掌下方的这一条边是最长的，而这条边到大拇指的距离为6，到小拇指的离为8。所以只要找出这条唯一长9的边，然...

题目来源：https://ac.nowcoder.com/acm/contest/5667/F 题意：给定一个n* m的矩阵A，A(i,j)=lcm(i,j)（最小公倍数），求所有A中的所有k* k的子矩阵中元素最大值之和。 做题历程：很不巧，这题也不是我负责，但队友过了，可不是那么轻松，而且此题也蕴涵着很多知识点，我不是很了解，所以还是拿来分析分析。  解题思路：如果直接按照思路来，把这个矩阵用二维数组整出来，然后再一一求子矩阵，再求子矩阵中的最大值，那时间肯定会爆掉。所以得用上巧妙的方法来解这一题。在这里我学习了一下，要用上单调队列来进行预处理（什么是单调队列，手推见上图），类似于滑动窗口...

题目来源：https://ac.nowcoder.com/acm/contest/5667/B 题目大意：给你n个点，找出一个过原点的圆，使得这个圆经过最多的点。 做题历程：比赛的时候这题是由队友负责的，过了一会儿就给他过了，但是具体情况我没怎么亲身去感受，所以还是别人的，现在自己亲自感受一下。 解题目主要思路：三个不共线点确定一个圆。因为原点已经确定了，所以只需要在给定的点中找两个点，找到一个点，然后再找到一个点（就是枚举了），然后通过推出来的三点确定一个圆的圆心，再来判断其它点有多上个在这个圆上。   #include<bits/stdc++.h> using namespac...