作者:Mrha

七校模拟WEEK1 0916&0917

七校模拟WEEK1 0916&0917

DAY1
T1 count
一道数学题……
我们考虑一个x序列,那么他的累乘可以得到的无非是小于n^m,等于n^m,和大于n^m三种,我们要求的是前两种。
对于一个序列x:x1,x2,x3,…,xn,把每一位都被n除,变成新的序列x:n/x1,n/x2,n/x3,…,n/xn。当x的累乘小于n^m时,x的累乘等于n^m/x的累乘,肯定大于n^m。
所以如果有s1个小于,s2个等于,s3个大于,那么s1=s3,所求答案就是(s1+s2+s3+s2)/2,而s1+s2+s3显然就是能组合出来的所有排列数,也就是n的约数的个数的m次方,那么问题就转化成了求s2的个数
对于s2的个数,我们dp来求:
将n分解质因数得到每一个质因数的幂是多少,然后对每一个因数进行dp(选取数字得到该质因数幂等于n中该质因数的幂时的方案数),然后根据乘法原理累乘即可。
(dp[i][j]表示前i个取出j个该质因数的方案数)
//还是……思维含量挺高的啊……

AC代码:

T2:
直接nlogn删500次最长上升或下降即可,只要在nlogn的同时记录一下他进来时的前一个是什么就行……
大概是代码能力gg?或者数学不好?

T3:
一眼看出来矩阵乘法可求根号五前系数和常数,然后考虑了两个小时的逆元,然后滚粗
事实上显而易见根号五前系数是由斐波那契数列组成的,然后&……%¥##通过打表找规律可以发现ans=f[i]/2-(i&1)^1(奇数不变,偶数减一)
这规律……
难以理解……

DAY2:
T1:
暴力找到一个假装可行的可行解,然后n^2判断是否可行……
真蠢……找到可行解还不可行……
AC代码:

T2:
只有我觉得复杂度是nlogn,然后真被我说对了?
只是!!!短路运算符!!!
并且注意奇数不能拆成两个字符串,要return 0……
100->60->30
AC代码;

T3:
数位dp……
状压一个数拥有的0~9的个数作为状态,然后dp即可……
dp[i][j]表示i状态,j枚举0~9进行转移即可
//看标称才能研究懂?
AC代码:

0
0912模拟

0912模拟

T1题解:
对于一个已有的n的单峰排列,n+1只能放在n两边,所以就是ans[n-1]*2,所以就是ksm(2,n-1)

AC代码:

T2题解:
贪心搞最小生成树,很显然啊……

AC代码:

T3题解:
考试的时候写的贪心……
事实上我们会发现这是对于一个无向图中访问每一条边并只访问一次,也就是欧拉回路
然后我就学习了一下欧拉回路……

AC代码:

T4题解:
//对于每个点,我们有一个约数和,但会有很多对应的值,所以会想到是一颗树,其约数和是父亲
通过手动打表等我们会发现,所有素数被连向1
而其余符合条件的数的约数和被连向小于他的素数或另一个符合条件的数,也就是最终都回到了1
所以这构成了一棵树,而答案就是树的直径(边权为1) ,且一定经过根结点1

对于符合条件的数来说,sum[i]等价于其树中的父亲
简单的说,树的直径是其最长边和次长边的合,而一个节点的子树均又比他大的数组成,所以降序处理即可

AC代码:

0
0910模拟

0910模拟

T1题解:
身为熟悉的括号匹配……,基本上都只写了个暴力拿了60分……
主要还是考虑的太局限了,可能是因为只记得括号匹配是用栈吧……
如果直接分析题意而不是带有主观思想来说,那么我们肯定会处理当前区间里有多少个合法的括号匹配,也就是我们所说的n^2暴力,怎么继续转变呢
对于[l,r]来说,我们就是[1,r]-[1,l-1]的已经合法的括号数,所以这在我们求[1,n]的过程中就已经分步实现了,那么我们只要在考虑问题的时候再全面变通一些,就会发现离线树状数组处理即可完成目标,然而如果想不到离线就会很糟糕
思维还是太窄了,可能是见得题太少?
还要多多熟悉树状数组啊

AC代码:

T2题解:
本来以为非常简单的贪心……然后因为一些细节的失误gg了……
首先,我们肯定知道先贪心出来人数cnt,那么现在的最优方案一定是用最便宜的cnt个数去复活cnt个人,对于要复活的人来说,肯定是在能用这个方法中奖励金最多的人来复活(考试的时候想得太简单,觉得肯定是用最便宜的cnt个人复活k最多的3个人……),那么我们只要造一个大根堆来维护就行了
对细节的掌握不是很好,很容易就觉得自己想得很对然后没有更深一步,这很关键……
对数据结构的灵活应用也不怎么滴

AC代码:

T3题解:
一度认为自己写的是巨对的正解……
错误解法(其实删的过程没说错……只是……):
首先我们优先删除1个p中间夹杂的其他字母,这样ans就会慢慢增加,然后再删除相邻两个p之间隔着的字母,这时ans保持最大值不变,然后再依次删去每一个p,但是这样的话每一个p的分解太过清晰,回导致ababa找aba这种字符串无法辨识,那么这个想法就被否了
所以我们其实应该很容易就想到这是一道dp,因为当举出ababa这种反例之后,我们就会考虑对于每一个字母,删还是不删对于答案的影响,所以dp转移方程应运而生:
//dp[i][j]表示前i个字符删j个的最多p
如果不删:
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
如果删了:
dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
这显然不能满足所有情况,所以我们要处理一个对于位置i来说,往后删j个字符可以多出来一个p的这样一个w[i],所以
dp[i+w[i]][j+w[i]-lp]=max(dp[i][j]+1,dp[i+w[i]][j+w[i]-lp]);
这样一来考虑就周到了
//思维幼稚,考虑问题不周全,dp思想不贯彻

AC代码:

0
0907模拟

0907模拟

T1题解:
多了一段记忆的题,然而都写跪了……
考试的时候想到正解,hahs表连边跑最长路,写着写着觉得太麻烦然后莫名退化n^2……
添加与删除是等价的,修改与两个都删除是等价的,然后先处理一遍删除(也就是把原串扔进hash表,再枚举每个字符串删每个字母来连边),再跑一遍修改(枚举删每一位,把字符串扔进去并同时比较连边即可)。
所以说其实没有那么难吧……虽然代码写起来巨麻烦

AC代码:

T2题解:
最水的一道题,打表或者四队列都可以水过,没啥好说的……

AC代码:

T3题解:
乍一看就是一道左偏树!
可是事实上在考试之后重做的时候发现暴力就可以ac啊……是不是如果我们没听过左偏树这个名词,大家就都100了呢……

AC代码:

0
模拟0829

模拟0829

T1题解:
简单的三道题的代码
考试的时候只想到了& 和 一个假的|(虽然数据一个都没卡,莫名得了20分)然后加上暴力分就是正常成绩55了
至于三个运算符的正解:
&:高位开始贪心,每次通过从当前位向后找该位有>1个数为1缩小搜索范围,直到只剩两个数
|:先标记哪一个数出现过,再对出现的数进行删1操作,因为对于|来说,某一位不是1的数也相当于是出现过的,然后枚举每个数进行判断
//简直难以置信的方法啊!
^:建一棵字典树,每次走最优即可(11和小迪都觉得这很简单!!然而我却没想到?)
AC代码:

T2题解:

之前在51nod上做过一道蚂蚁,题目类似,然后满脑子都是骚操作……
事实上,从蚂蚁来看,我们可以知道,对于这些孩子,如果不去区分它们的个体,那么他们的最终位置就是初始位置和t,然后我们再考虑他们的相对位置是不变的(每个孩子不可能穿过其他孩子)
然后部分分就可以把末位置求出来然后sort即可
因为复杂度过不了所以我们就考虑优化:把他分为方向向左和向右,然后分别处理单调,再二分查找判断即可……

0
模拟0828

模拟0828

密码:12345

T1题解:
记搜或者dp(听说不记忆化也能过)
然后简单的博弈论,如果搜到必败那么必胜,同理必败……

然后被卡读入优化??!!!

AC代码:

T2题解:
没有算法……
找规律……写暴力程序打表……
然后暴力写跪……
//因为没有特判每一层的第一个和每一层的最后一个的特殊情况!!

AC代码的来源(打表代码):

T3题解:
求前缀和,然后再求一个%k后的前缀和,对于每一个[1,k)的数i来说,原前缀和里i的个数-%后前缀和里i的个数就为区间和等于k的个数

AC代码:

0
2-SAT !

2-SAT !

想知道2-SAT是什么一定要先知道SAT问题是什么:
适定性问题 Satisfiability
适,就是合适,定,就是确定,适定性问题通俗的说就是确定是否可以满足所有的条件?或者说就是确定一个满足所有条件的方案。
取英文前三个字母,即SAT问题
通俗的sat问题表述一般是这样的:有很多个集合,每个集合里面有若干元素,现给出一些取元素的规则,要你判断是否可行,可行则给出一个可行方案。如果所有集合中,元素个数最多的集合有k个,那么我们就说这是一个k-sat问题,同理,2-sat问题就是k=2时的情况。

我们从一个例题说起:
HDU 1814

题目大意:一国有n个党派,每个党派在议会中都有2个代表,现要组建和平委员会,要从每个党派在议会的代表中选出1人,一共n人组成和平委员会。已知有一些代表之间存在仇恨,也就是说他们不能同时被选为和平委员会的成员,现要你判断满足要求的和平委员会能否创立?如果能,请任意给出一种方案。

样例输入:
3 2
1 3
2 4
输出:
1
4
5

这个问题可以被简化为:有n个组,第i个组里有两个节点Ai, Ai’。需要从每个组中选出一个。而某些点不可以同时选出(称之为不相容)。任务是保证选出的n个点都能两两相容。
我们可以初步构图:
如果Ai与Aj不相容,那么如果选择了Ai,必须选择Aj’;
同样,如果选择了Aj,就必须选择Ai’。
Ai -> Aj’
Aj -> Ai’
这样的两条边对称

我们在这里不喵的拿样例引题:

根据我们构图的定义来说,在这样一个图内,我们选择1就一定要选择4,选择2就一定要选择3,而5和6可以任意选择
那么我们如果按字典序来查找选择,就可以得到1-4-5这个答案了

至此,我们得到了第一种解法
枚举每一对尚未确定的Ai, Ai’,任选1个,推导出相关的组,若不矛盾,则可选择;否则选另1个,同样推导。若矛盾,问题必定无解。
这个解法已经可以解决例题了!

但是我们还有一些更喵的优化
如果我们再仔细认识这个图,就会发现,对于一个强连通分量里的点,它们的是否选择是一样的,所以就可以进行强连通分量缩点,对新图(得到的DAG)再判断。
判断可行性:
枚举每一对Ai和Ai’,如果它们在一个强连通分量里即不可行
接下来我们要做的就是在新图中进行选择:对新图做一个拓扑排序,按自底向上的顺序,标记选择和不选择,把不选择的标记逆向传递即可。
为什么呢?

对于原图来说,我们的连边是具有对称性的,所以对于缩点后的新图也是一样的。
1、假设新图中两个点S1、S2,分别包含A1和A1’,那么S1和S2就是对称的点,里面包含的点也是对称的。
2、对于对称的S1和S2,S1的后继节点和S2的前驱节点是对称的。
对于新图中的点,记录一下每个点的矛盾点(含有Ai的点的矛盾点是含有Ai’的点)
考虑若按拓扑序从前往后选择,然后标记选择和不选择,这看起来是合理的,那么让我们来看这个例子(为原图):

首先找到A标记选择,A’不选择,然后B选择,B’选择,这矛盾了,可是原图是有解得啊!因为A是否选择对图的影响太大了,所以我们假如倒拓扑序,先选对原图影响小的A’,A标为不选再选择B,B’标为不选即可啊
所以我们就会选择倒着存图然后正着拓扑呗~

至此,我们得到了第二种算法,它是在第一个算法的基础上进行了缩点优化,并提前判断了是否无解
它的步骤是:
1、构图
2、求强连通分量、缩点
3、判断是否有解(无解直接退出即可)
4、对新图topo(新图存边时反着存,便于传递不选择标记)
5、进行选择

紧接着,不知道有没有人能发现,我们在对缩点后的图进行topo后,最终是倒着选择的,那么我们只要对于每一对Ai,Ai’选择topo序在后面的即可
然后听说:Tarjan 算法所求的强连通分量就是按拓扑序的逆序得出的
所以我们连建图和topo都省了,直接判断:
对于每个变量x ,让x 所在的强连通分量的拓扑序在x’ 所在的强连通分量之后,那么 x 为真

最终,我们得到了时间复杂度无敌的算法3
构图后缩点即可完成全部任务!

微暴力代码:
hdu 1814

带Tarjan代码(解法3):

1+
模拟DAY6

模拟DAY6

题目:NOIP模拟测试题(day2).pdf
无密码

T1题解:
集训的时候松爷讲过……(然而一开始并没有想起来正解)
先用埃拉托斯特尼筛法筛出0~sqrt(2147483647)的素数表,然后用这个素数表筛l~r的区间,O(nloglogn)完成任务
//所以说是棵题?

AC代码:

T2题解:
显然的找规律题,可是计算过程爆int就跪了……
对于一个数n,我们显然要考虑他的每一位对答案的贡献,也可能会把它分类为个位十位百味来考虑,去找由个位到十位(也就是n和10n之间有什么联系)
举一个2和20的例子:
2的答案是3,20的答案是102
对于20来说,我们可以把它看做00~19~20,也就是在十位数字为0~2-1时,他的个位数字循环了2次,所以个位数字的贡献就是452;再考虑十位数字,0~2-1时,每一个数字都连续出现10次,所以去掉20这个数本身(因为他并没有循环个位数字),十位数字对答案的贡献就是10(0+1);在考虑这个数本身,也就是没有参与个位数循环的20,只要单独把它的贡献算出来加到答案里即可(因为计算单个数的贡献的O(位数))
类比下来,我们就可以找到这个规律了:
对于一个数n,设它的答案为S[n]
假如他%10等于0,我们去掉它的末位0得到x,那么S[n]=45x+10S[x-1]+n的贡献;
假如他%10不等于0,就可以枚举得到的整数到n的剩余几个数直接计算他的贡献(如通过12得到了120,121、122、123通过枚举加入答案即可),这样的复杂度依然是很小的。
//一定不要天真的以为答案看long long 就可以了,过程爆int你可就gg了哦!(像我一样?)

AC代码:

T3题解:
正常的人来说(比如我),会想到dfs传一个数组,数组中记录当前没堆该拿第几张牌,这没什么问题,而且也能AC,但是……
但是这会TLE啊!而且显然我们需要记忆化啊!像我开的结构体数组就没法记忆化啊(因为map是用红黑树储存,需要定义小于号,也正是因此它的复杂度才是log)
那怎么办呢?
我们都会想到状压啊!我们可以想象这是一个五进制数,那么用int就可以记录了(最多为444444444(5),也就是5^9-1)然后开vis什么的也炒鸡方便(状压天下第一!)
虽然我被五进制搞得一脸蒙蔽……:
要取某一位的数:如对x取第i位,return x%ksm[i+1]/ksm[i]即可(类比10进制)
要把某一位+1,:return x+ksm[i]
所以其实还是很简单的!

//考试的时候被存图卡死……,因为身为一个字符串,它的后面有一个\0,这是需要一个位置的……

AC代码:

0
模拟DAY5

模拟DAY5

题目:noin2017模拟测试(day1).pdf
密码:233

T1题解:
长久以来少有的一眼秒的题啊!简单的递推
dp[i][j]表示i长度的基因第i位放j的方案数
显然:
dp[i][0]=dp[i-1][0]+dp[i-1][1];
dp[i][1]=dp[i-1][0];
那么就AC了呗!
//吐槽电脑慢……,std啥的也都被卡……,虽然最后都是AC

AC代码:

T2题解:
题面很长,但是题并不难……虽然……
对于我们现在所在的鱼,我们要找到他往下走要最优的点,那么什么是最优的点?
考试的时候我想的是他能到的点中度最大的,然而事实不是这样的,eg:

如果右面是一条链,那么显然我应该先走右边……所以不能用度啊!gg哦
那是什么?
应该是找到花费时间最长的内个点先走,既然我们在dfs,那么我们就这样找他的所有儿子要花费的时间return上来,然后放在一个数组里
在这个数组里,我们要更新的所在的点的时间就是sort后的a[i]+i+1(如果从0开始存),为啥加i+1呢,因为我要一个一个通知,所以其他的点会有延时
所以dfs就可以解决这道题了啊!
//正解的名字好像是树形dp,据说实际上是一样的……

AC代码:

T3题解:
一道很迷的题,第一个想法就是写一个spfa按速度最优跑一跑,事实上是可以做出样例的(讲个笑话)
然而物理学的好的人(不是我)就会发现按速度判断是不对的,所以我们要做一些变化……
对于一个我们做出来的ans的话,如果要更新它,那么我们一定要满足条件:
(P1+P2+……+Pk)/(T1+T2+……+Tk)>Ans
对这个式子进行变化,移项,就得到了:
P1–T1Ans+P2–T2Ans+……+Pk–TkAns>0
所以我们二分答案,然后check()
怎么check?
我们用一个数组记录P-T
Ans,把他当做边权跑spfa,如果我们正权到了n,也就是最后答案大于0,那么显然是满足条件的
但是我们做过样例的人都会发现,这个人会绕着圈跑啊跑啊跑啊跑,只为了有最大速度……(chun)
所以遇到环怎么办,不就TLE了吗!
这时候我们就想起了spfa的特性,可以判环,简单的来说,如果一个点入队列太多次,那么它一定在环上,所以在这个式子中,如果遇到了正权的环,那么这个式子最后一定满足>0,所以直接return 1即可
//听说如果学过01分数规划,会很简单?
//为什么会想到二份答案呢?

AC代码:

0
模拟DAY4

模拟DAY4

题目:冲刺Noip2016模拟赛4
密码:monisai4

T1题解:
纯粹数学题!
首先,我们会发现,对于每个点,都有作为式子中减数和被减数的机会。
但是,对于终点来说,它只能作为被减数,不能作为减数,而其他点均可。
那么我们知道总次数是n!,而一个点作为终点的概率是1/n,也就是说他作为被减数的次数是(n-1)!,那么不是终点的概率就是n!-(n-1)!
然后我们再对式子进行一定的展开:
对于|a-b|,显然有两种展开,a-b和b-a,然后对这里的这个式子进行分类讨论。
对于一个排好序的序列中的一个点,他到所有他前面的点的距离绝对值展开,它是不用变号的,同理对于他后面的点是要变号的,也就是说对于第i个点,他的dis有i个是正的,n-i个是负的。
然后再将得到的这个规律放到刚刚的式子中,即为:
减数:(n!-(n-1)!)(ia[i]+(n-i)(-a[i]))
被减数:(n-1)!
(i(-a[i])+(n-i)a[i])
所以加起来合并后得到式子:
ans=sigma(i=1,i<=n)(a[i](4i-2*n-1))/n
所以计算出sigma后,求与n的gcd然后输出即可
//完全考验数学啊!!吐槽!!

AC代码:

T2题解:
听说正常人的想法都是:
由3个类比两个,对于每一个元素枚举第三个后去找他之前是否有两个元素的和满足这个条件。
也就是说,维护一个数据结构,里面存有到目前为止,我之前有的两个元素的和有哪些。
所以,出题人想到了hash表,并且是链表的hash表。
为什么呢?
因为hash表查找判断的复杂度很低,而且通过每一个hash值下面连一个链表会使值都是精确的,不会出现误差,所以其实这是一个很好的数据结构(不,他不是一个数据结构)
//顺便说一下这个模数……按照标称来看,我们能用的模数只有三个,不然不是TLE就是MLE,真滴坑……

AC代码:

T3题解:
当我们无尽的把问题想的简单化的时候,问题就真的简单了……?
对于这道题来说,乍一看,分类讨论 n和m的位置有很多种,那么怎么办啊!
事实上,如果全面的来看,所有的情况下,我们的棋盘都可以被分为三个部分
<图待补>
那么我们就可以在每一部分内分别处理前i行放了j个城堡的方案数,也就是一个很简单的dp
再通过将这三块的合并:
dp[h][i][j][k]表示到第h行,第1块i个城堡,第2块j个城堡,第3块k个城堡
然后再压缩掉一维空间即可……

说着容易?
明明代码实现很简单的题,怎么可能这么出给你?!
所以啊,记得看数据范围,要写高进度啊!!!
要写好多好多高精度啊!
慢慢写,加油哈!

AC代码:

0