Closed Wizmann closed 4 years ago
比赛AB，赛后CDE。排名4736（？）
傻逼石锤了。
Code
有一个游戏，在特定的时间点会有两个统计信息：
易知，通关游戏的人次一定小于等于玩过游戏的人次（换句话说，每一次游玩都是独立的）。现在给定N个时间点的统计信息，问这些统计信息是否合法。
遍历一遍，然后校验以下信息：
一个国家有N个人，编号为i的人有a[i]单位的钱。
现在可以执行一个操作：随意选择M个人，将他们的钱平均分。
问在任意次操作之后，最多有多少人的钱多于X。
贪心的思路。把最富有的人的钱均分给穷人。
先对钱数a[]进行排序，编号从小到大枚举最多有多少人一起进行平均。然后再与X的值进行比较即可。
a[]
这题做不出来的傻逼之处在于。明明B题都给了类似思路的提示了，然后你还在那里强行YY结论。。。
有一个打怪游戏。玩家可以用枪打怪物，打一枪掉一点生命值。
N个怪物站一圈，每个怪物的生命值为a[i]。怪物的生命值降到0或小于0后，会自爆，对第(i + 1) % N个怪物造成b[i]的伤害。
问把怪物都打死最少需要几枪。
易得如下结论：
那么问题来了，从哪一个位置开始攻击最好呢？如果继续往这个方向思考下去，你会像我一样卡题（
现在换一个思路。如果我从位置0开始攻击到位置N-1，最终需要打K枪。那么我们从位置1开始攻击到位置N-1，需要打几枪？这个问题的答案很简单，我们把攻击怪物0的开销减掉，再加上怪物0自爆产生的伤害，就可以得到最终的结论了。如果我们再加上攻击完怪物N-1之后，攻击怪物0（怪物站成一个圈）所需要的开销，就可以得到从位置1开始攻击所需要的开销总和了。
所以，我们可以在O(1)的时间内，由位置M 推导出 位置M+1所需要的开销。总的时间复杂度是O(n)。
我是傻逼
给你一个有N个顶点的有向完全图（每一对顶点之间有一对双向边相连）。
你从一个顶点开始遍历，一定能不重复的遍历所有的边，并且回到最初的顶点。我们将你所经过的顶点依次记录下来，就可以描述这一条回路。
我们找到字典序最小的回路P[]，问这条回路上从第L到第R个顶点P[L...R]各是什么？
P[]
P[L...R]
本题当中的回路非常好构造，例如有n个点的图，则回路一定是：[1, 2, 1, 3, 1 ...., 1, n] ++ [2, 3, 2, 4 .... 2, n] ++ [3 ....] ++ [n - 1, n] ++ [1]
[1, 2, 1, 3, 1 ...., 1, n] ++ [2, 3, 2, 4 .... 2, n] ++ [3 ....] ++ [n - 1, n] ++ [1]
那么现在的问题就在于如何快速求第L项到第R项。再进一步说，我们要求出第L项的状态，后面的状态可以由递推得出。
首先我们要判断第L项是在第几段里。这个可以暴力求解，时间复杂度不会超过O(sqrt(n))。（二分也可以，但是没必要）
然后判断第L项在本段里是第几项。确定了位置之后，就可以往后进行推导了。注意边界条件即可。
PyPy要加输出外挂。
看了官方题解
给定一个数D。把D的所有因子都记做图中的一个点（包括1和D）。 如果因子x和y满足：x能被y整除，并且x/y为质数。则x和y之间有一条无向边。这条边的权值为x和y的因子数之差。
问给定图中任意两点A和B，问这两点间有多少条不同的最短路。（最短路指的是权值和最小的路径）
要找到最短路的种类数，首先要找到一条最短路。
假设我们有两个点u和v，u = a b v（这里a,b为质数）。那么u和v之间的最短路一定有一条经过[u / a, u / a / b]。因为只有除以质数因子，才能保证两点之间的权值和最小。
所以对于任意两个点u和v，其最短路一定经过gcd(u, v)。并且每一步都只会除以质数因子。所以我们对u到gcd(u, v)所经过的质数因子进行全排列，再对v到gcd(u, v)的质数因子进行全排列，然后相乘即可。
优化：因为对于每一组数据，D是不变的。所以我们只需要保留D的所有质数因子。否则会TLE。
我是傻逼。
Wizmann
commented
4 years ago Wizmann
commented
4 years ago
比赛AB，赛后CDE。排名4736（？）
A. Level Statistics
Code
题意
有一个游戏，在特定的时间点会有两个统计信息：
易知，通关游戏的人次一定小于等于玩过游戏的人次（换句话说，每一次游玩都是独立的）。现在给定N个时间点的统计信息，问这些统计信息是否合法。
解法
遍历一遍，然后校验以下信息：
B. Middle Class
Code
题意
一个国家有N个人，编号为i的人有a[i]单位的钱。
现在可以执行一个操作：随意选择M个人，将他们的钱平均分。
问在任意次操作之后，最多有多少人的钱多于X。
解法
贪心的思路。把最富有的人的钱均分给穷人。
先对钱数
a[]进行排序，编号从小到大枚举最多有多少人一起进行平均。然后再与X的值进行比较即可。C. Circle of Monsters
Code
题意
有一个打怪游戏。玩家可以用枪打怪物，打一枪掉一点生命值。
N个怪物站一圈，每个怪物的生命值为a[i]。怪物的生命值降到0或小于0后，会自爆，对第(i + 1) % N个怪物造成b[i]的伤害。
问把怪物都打死最少需要几枪。
解法
易得如下结论：
那么问题来了，从哪一个位置开始攻击最好呢？如果继续往这个方向思考下去，你会像我一样卡题（
现在换一个思路。如果我从位置0开始攻击到位置N-1，最终需要打K枪。那么我们从位置1开始攻击到位置N-1，需要打几枪？这个问题的答案很简单，我们把攻击怪物0的开销减掉，再加上怪物0自爆产生的伤害，就可以得到最终的结论了。如果我们再加上攻击完怪物N-1之后，攻击怪物0（怪物站成一个圈）所需要的开销，就可以得到从位置1开始攻击所需要的开销总和了。
所以，我们可以在O(1)的时间内，由位置M 推导出 位置M+1所需要的开销。总的时间复杂度是O(n)。
D. Minimum Euler Cycle
Code
题意
给你一个有N个顶点的有向完全图（每一对顶点之间有一对双向边相连）。
你从一个顶点开始遍历，一定能不重复的遍历所有的边，并且回到最初的顶点。我们将你所经过的顶点依次记录下来，就可以描述这一条回路。
我们找到字典序最小的回路
P[]，问这条回路上从第L到第R个顶点P[L...R]各是什么？解法
本题当中的回路非常好构造，例如有n个点的图，则回路一定是：
[1, 2, 1, 3, 1 ...., 1, n] ++ [2, 3, 2, 4 .... 2, n] ++ [3 ....] ++ [n - 1, n] ++ [1]那么现在的问题就在于如何快速求第L项到第R项。再进一步说，我们要求出第L项的状态，后面的状态可以由递推得出。
首先我们要判断第L项是在第几段里。这个可以暴力求解，时间复杂度不会超过O(sqrt(n))。（二分也可以，但是没必要）
然后判断第L项在本段里是第几项。确定了位置之后，就可以往后进行推导了。注意边界条件即可。
E. Divisor Paths
Code
题意
给定一个数D。把D的所有因子都记做图中的一个点（包括1和D）。 如果因子x和y满足：x能被y整除，并且x/y为质数。则x和y之间有一条无向边。这条边的权值为x和y的因子数之差。
问给定图中任意两点A和B，问这两点间有多少条不同的最短路。（最短路指的是权值和最小的路径）
解法
要找到最短路的种类数，首先要找到一条最短路。
假设我们有两个点u和v，u = a b v（这里a,b为质数）。那么u和v之间的最短路一定有一条经过[u / a, u / a / b]。因为只有除以质数因子，才能保证两点之间的权值和最小。
所以对于任意两个点u和v，其最短路一定经过gcd(u, v)。并且每一步都只会除以质数因子。所以我们对u到gcd(u, v)所经过的质数因子进行全排列，再对v到gcd(u, v)的质数因子进行全排列，然后相乘即可。
优化：因为对于每一组数据，D是不变的。所以我们只需要保留D的所有质数因子。否则会TLE。