icontofig | 发布于 2019-09-11 08:23:30 | 阅读量 381 | 思维题 筛法
发布于 2019-09-11 08:23:30 | 思维题 筛法
The 2019 Asia Nanchang First Round Online Programming Contest A.Enju With math problem 思维题 欧拉筛
题目大意给出100个数,求问是否存在某个连续的100个φ值,使得两者一一相等。 1≤ai≤1.5*108 题解首先其实能想到的是KMP,但是无奈这个ai太大了,用欧拉筛没办法筛出来,而且时间也不够,因为还有多组数据。 但是能够预处理一些φ还是好的,这样能降低所有数据都需要暴力算φ带来的复杂度。 然后我们猜想,是不是这100个数里面一定会有一个数对应的φ恢复到φ-1的时候是素数,也即两个相邻素数一定相隔100以内?答案是否定的,这个可以通过打表来检查出来。 但是我们可以找到另一个问题,这100个数的φ-1中,要么就是有至少一个素数,要么就是有一个数为一个≤13的素数和一个大素数的乘积。 这样我们
继续阅读
icontofig | 发布于 2019-09-06 22:19:42 | 阅读量 359 | Trie 思维题 hash
发布于 2019-09-06 22:19:42 | Trie 思维题 hash
2018 ACM/ICPC Asia Jiaozuo Regional K.Counting Failures on a Trie  Trie 思维题 倍增 Hash
题目大意给出一棵trie树和一个字符串,然后对于每一次询问l,r,在Trie树上对子串[l,r]进行匹配。如果在某个字符处失配,则重新跳回Trie树根节点并忽略这个字符继续匹配。 求问对于每一个询问,在匹配过程中会失配几次,且最终会到达哪个节点。 题解暴力搜索必然是n^2的,对于此题1e5还有多组数据的情况想都不要想。 而每一次失配我们都会重新回到起点。 于是我们可以用预处理从每个位置的下一个位置开始的子串第一次的失配位置是在原字符串中的哪个位置。由于在这个位置我们会失配回到起点然后再次从这个位置的下一个位置开始,所以应该可以想到这个失配过程是完全可以去倍增的!。我们可以用倍增来处理失配次数,
继续阅读
icontofig | 发布于 2019-09-02 23:23:58 | 阅读量 615 | 思维题 扫描线 树状数组
发布于 2019-09-02 23:23:58 | 思维题 扫描线 树状数组
2019 南京网络赛 A.The beautiful values of the palace 思维题+扫描线+树状数组
题目大意每个点的数值是通过一个从中心最大值开始的蛇形矩阵确定的。其中有m个点上的权值可用,对于q个询问,输出左下角为(x1,y1),右上角为(x2,y2)的矩阵区域内所有可用点的权值经过处理后的和。 处理的方法是,将原权值所有数位上的数相加。 题解此题估计是模仿NOIP2014普及组T3的蛇形矩阵出的规律题目。 首先n为奇数,n*n为奇数,地图大小为 一定为奇数,所以 x = x − n/2 − 1y = y  - n /2 - 1;t = max(abs(x),abs(y)); //确定该点在第几圈螺旋 if(x >= y)ans = n ∗ n
继续阅读
icontofig | 发布于 2019-08-27 20:06:53 | 阅读量 601 | 思维题
发布于 2019-08-27 20:06:53 | 思维题
2018-2019 ACM-ICPC, Asia Shenyang Regional Contest  K. Let the Flames Begin 经典约瑟夫问题 + 思维
题目大意n个人围成一圈,从1号开始报数,报到k的人出圈,然后再从下一个人开始新一轮报数。问经过第m个出圈的人最开始的编号是多少。 题解经典约瑟夫问题,想必大家都知道递推式吧…… f(n,m) = (f(n-1,m-1) + k) % n 好了就是这样,至于具体证明貌似说刘汝佳的白书上有? 但是我们注意到此题数据范围真的是太大了,我们不能使用O(m)的做法了…… 不,并不是不能用,只是当m小于等于k的时候我们可以这么做(这时候m的范围只有2x106),但是如果是k小于等于m的时候我们就要另作讨论了。 首先如果k = 1,那我们直接输出m就好,因为题目保证n ≥ m; 但是如果k > 1……
继续阅读
icontofig | 发布于 2019-08-20 22:02:02 | 阅读量 317 | 思维题
发布于 2019-08-20 22:02:02 | 思维题
Codeforces Round 580div2  1025B Shortest Cycle 思维题
题目大意给n个数,两个数如果能取并运算不为0则又一条边相连,求长度至少为3的最小环的长度,若没有环,输出-1。 题解md这题我挂了7发,真是sb…… 首先我们先从大到小排序,把0去掉,因为0不会和任何数连边。 然后我们考虑二进制并运算,只有两个数某个二进制位相同时,两个数才会连边。 而如果有至少三个数二进制的第i位同时为1时,这些点互相之间都会连边,那么一定会形成环,最小环的长度为3。 所以我们可以对所有非0数进行二进制分解,记录每个二进制位上会出现多少次,如果其中有一个大于等于3,则说明最小环的长度为3。 那么如果没有以上的点就一定答案为-1吗?并不是。 那该怎么做? 如果我们仔细观察,所有
继续阅读
icontofig | 发布于 2019-08-13 00:35:49 | 阅读量 427 | 博弈论 贪心 思维题
发布于 2019-08-13 00:35:49 | 博弈论 贪心 思维题
2019 Multi-University Training Contest 7 1010 Just Repeat
题目大意先手有n张牌,后手有m张牌,如果某人打出了某种颜色的牌,那么另一个人就不能打这种颜色的牌,最后不能出牌的人输。求问是先手胜还是后手胜。 题解两人都是按最优策略取的博弈,不过和SG函数并没有什么关系。 两个人肯定每回合都是贪心的取对自己最有利的方案。 首先我们将两人都有的颜色的牌抽出来,剩下的就是两人各自独立的牌集,不会受对方出牌的影响。 然后我们考虑被抽出来的牌,怎样取能使得局面变得对自己有利。 如果对于某种颜色,两人共有的这种颜色的牌比较大,那么当前的出牌者选择出这种颜色的牌的优先级肯定就更高。 然后当前的人出一种颜色的牌,就可以看成是把自己原有的这种颜色的牌全部收回,把对方原有的这
继续阅读
icontofig | 发布于 2019-08-13 00:22:29 | 阅读量 423 | 思维题
发布于 2019-08-13 00:22:29 | 思维题
2019 Multi-University Training Contest 7 1006 Final Exam 思维题
题目大意一场考试有n个题目,总共为m分,如果要通过一个分值为x的题目,需要复习x+1小时。 现在目标为通过至少k个题目,求问至少要复习多长时间。 题解首先我们从出题老师的角度来看,怎么样才能让考生无法通过考试呢。 当然是让学生复习时间最少的n-k+1门科目不能通过考试,也就是要求让他们的复习时间恰好等于复习分数。 然后镜头转回学生,我们需要复习时间最少的n-k+1门复习时间最少的科目中有1门能通过就好了。 所以最后的答案是(m/(n-k+1)+1) *(k-1)+m+1. 代码#include <cstdio> #include <algorithm> typedef
继续阅读
icontofig | 发布于 2019-08-05 22:56:27 | 阅读量 337 | 思维题
发布于 2019-08-05 22:56:27 | 思维题
2019 Multi-University Training Contest 1004 equation 思维题
题目大意给出n个二元组(ai,bi),求出Σni=1|aix-bi| = c 的所有解,并用最简分数形式表示,若有无穷多解输出-1 题解这道题卡我常……比赛的时候被卡常卡到心态炸裂 赛后发现我被排序用的cmp函数给卡了,真TM没想到啊…… 首先我们不能直接求绝对值方程式的解,我们通常的想法是把绝对值号拿掉,然后再做。 但是这题一共有n个绝对值式,不是很好办。 我们想一下,每一个绝对值式都有一个对应的变号点,我们可以先把这些变号点求出来,然后根据变号点对每个式子排一遍序。 然后很明显的这些变号点把整个数轴分成了n+1个区间。每个区间对应了一个去掉绝对值后的方程式,也对应着一个合法的解区间。 然后
继续阅读
icontofig | 发布于 2019-07-23 13:46:23 | 阅读量 347 | 思维题 模拟
发布于 2019-07-23 13:46:23 | 思维题 模拟
2019 Multi-University Training Contest 1 1004 Vacation
题目大意Tom和Jerry开着0号车,前面依次有1……n号车,且不能超车。 给出每个车的长度、距离停车线的长度、最大行驶速度,求出0号车头部通过停车线的时间。 注意:车开过停车线后依旧不能超车。 题解正解实际上时用堆(优先队列)来维护各个车的追及时间以及距离什么的,时间复杂度时O(nlogn),而且非常难写。 听说他们有很多用二分做出来的,也不是很清楚怎么check的 这里有一个思维量稍大但代码简单的O(n)的做法。 首先我们要知道,每辆车开过停车线后依旧在走,不能超车,也就是即使此车开过停车线,也是可以堵住后面的车的。 第二点我们要知道的,就是如果前一辆车的尾部没有开过停车线,那么后面的车一
继续阅读
icontofig | 发布于 2019-07-23 13:22:47 | 阅读量 396 | 思维题
发布于 2019-07-23 13:22:47 | 思维题
Educational Codeforces Round 69 D Yet Another Subarray Problem  思维题
题目大意求出给定序列的一个连续子序列,使得这个子序列的值的和sum与k*(子序列长度len)/m(除法做上取整)的差值最小。 题解非常巧妙的一道思维题。 首先这个题用线段树维护最大子段和是错误的,我写线段树就一直WA on test 8. 听说还有写DP的,咱也不是很懂。 今天问的学长,学长说是把这些看成前缀和然后瞎搞就完事了。 然后……直到我看到榜单第3那个人写的东西的时候我才彻底搞清楚。 思路如下: 我们可以发现m很小,只有10,而当子段长度能整除以m的时候,再添加一个才会使得我们多去减一个k。 我们可以让所有位置对m取模,分成0——m-1这样的剩余系,我们枚举剩余系,以剩余系中的位置作为
继续阅读