月份:2017年8月

模拟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
模拟Day3

模拟Day3

题目:冲刺Noip2017模拟赛3.pdf
密码:haicaimimane

T1题解:
一道很迷的一眼就知道是找规律的题
然而一场考试也没找出来……
//显然30分暴力特别好写……
//60分不知道咋得?
//100分……
被告知了一个蜜汁规律:
对于B+A的B+(2^k+1)A的第k位相同
事实上是这样的,因为加上(2^k)
A对于后k位是没有影响的(等于在后面加了k个0)
然而这有什么用呢?
对于第k位的统计来说,
每[1,2^k]都构成一个循环,循环间第k位的1的个数和是相等的,所以直接处理[1,2^k]的k位个数即可
然后对于第k位为1,如果加上x变为0,那么我们就可以跳过x/A这一段了;同理0
那么我们的复杂度就降下来了啊!
O(TAlogB)
//可是这个规律这么难找!!!

AC代码:

T2题解:
显然:
对于30%的点,我们会想到复杂度无敌的dfs,当然我考试的时候也先写好了30分程序在那放着……
对于60%的点,无非是想想算法(显然dp),搞搞优化,就可以水过了
对于100%的点,考试的时候想不到呗……

30%:爆搜!记忆化一下就行了,特别好写,没啥好说的
60%:写完30%发现很多转移都是没用的,因为如果要保证最后最优,那么我们每次一点会从上一个美观度的点转移过来
那么我们就可以开一个vector记录有哪些美观度,并在下面挂一个桶,把该美观度的点扔进去再一层一层转移就好了
100%:最想不到的,就是100的优化,竟然是从曼哈顿距离的计算上优化……
对于两个点之间的曼哈顿距离|x2-x1|+|y2-y1|,我们共有4种展开方式
x1+y1-x2-y2
x1-y-1-x2+y2
-x1+y1+x2-y2
-x1-y1+x2+y2
然后对于每一个点1,我们可以处理出它的4种形式,同理处理出点2后,一一对应,选取4个中的最大值,即为真正的曼哈顿距离
如此一来,复杂度再次减小哦!
//吐槽时限……吐槽评测机……,虽然vijos是开了o2才和香港记者一样快的……

T3题解:
显然我们在求对于m步来说,多少种方案能回到原点时,很容易写出转移方程
dp[i][j]=dp[i-][j]+dp[i-][j+1]
dp[i][i]=1;
dpi][-i]=1;
//dp[i][j]表示i步走到j位置
然而考试的时候写完这个就接着想不到啥了……
然后,根据经验和数据范围等提示来说,我们(应该)会想到矩阵乘法
然后我们会找到这样一个转移矩阵

一个1 0 1顺序右移的矩阵(设为A)
把它作为转移矩阵的话,那么我们就可以用快速幂来处理A的n次方了
O(m^3logn)
//然而矩阵乘法不熟练啊,也不容易看出来是矩阵乘法的题啊!!!

0
模拟Day2

模拟Day2

题目:冲刺Noip2017模拟赛2
密码:di2cimoni

T1题解:
设斐波那契数列为f[],所求数列为g[]
设g[1]=x,则手推找规律得知g[a]=f[a]*x+f[a-1]
那么对于输入数据,我们对于已知的a和f[a]求一下x,再判断x是否满足题意(也就是说是否是整除),即可判断有解并直接求解或无解
唯一坑的地方就是要记得开long long
AC代码:

T2题解:
因为在题目的疯狂暗示下,我们很容易联想到归并排序求逆序对,然后再稍微打打表找找规律,就会发现:
当一个序列完成第一次翻转后,剩下的翻转只能在相邻的两个元素之间进行,所以这就很满足逆序对了啊!
那么答案就得出来了:第一次翻转次数+翻转后求逆序对的个数
//考试时被nb的ctrl+D删了代码……,导致我的100分程序啊……,算了……,谁让自己查不出来……
//奥对了,还要记得开long long
AC代码:

T3题解:
这道题是真的难啊……
//考试的时候只想到了第一步,二分答案,因为是让求max的min啊……
//但是菜还是菜,二分答案之后用贪心判断,事实上考虑不周……应该用dp判断
首先对于女友指数进行二分,然后dp检查是否可以
设f[i]为前i个人分班所得到的min欠扁值,那么我们轻松的得到转移方程:
f[i]=max(f[i],f[j]+max(hj,hj+1,…,hi));
可是这是n^2啊,肯定不行啊(虽然能过30~40的点)
所以我们就要考虑优化……
怎么优化呢?
//看了好久的题解也看不懂,云里雾里……打算今天问学姐,然后补上……
先附上部分分的代码吧……

//终于……终于在23点把题解搞懂了……
那么我们讨论dp的优化
//记欠扁值为g,女友指数为h
对于dp[i]来说,如果存在一个j,使g[j]<=g[i]且女友指数之和不会大于已二分的答案,那么他直接放到i的班级里就好了,所以事实上他不会对dp[i]的更新做出贡献,那么这个复杂度就是多余的。
所以怎么办?
我们发现对于转移到i来说的有用的j,是一个单调递减的g序列,那么我们就可以用一个单调序列来维护对于我要更新的dp[i]可以从哪里转移过来,那么时间复杂度就很小了
怎么维护?
对于我二分出来的答案,我可以知道我i所在的班级最前方可以到哪里,那么我们就把p~i中所有可以作为这个班中欠扁值最大的家伙加入队列(并且最后保证i也会加入这个队列),然后在队列中进行dp的转移即可
也就是说,check要做到:
1、找到我班级能到达的最前方的人的位置p
2、把p之前的候选人(队列中欠扁值……)去掉,因为他们不可能在这个班级
3、i要进入队列,把他之前的所有欠扁值小于i的出队
4、dp的转移
所以把n^2dp就优化了!是不是简直神奇?
还不懂怎么办?
看看代码吧:
AC代码:

0
模拟Day1

模拟Day1

题目:冲刺Noip2017模拟赛1
密码:zxg

T1 dry 题解:
水题……
然而做题经验太少,脑子迟钝,很久都没想出来是二分或者直接贪心就可以(或许是想的太麻烦?)
二分:
二分答案就行了,没啥好说的……
写跪的原因:ceil无法对整数出发进行向上取整,也就是ceil(10,4)还等于2,所以gg……
解决方案:改成很慢的while或者强制double应该都是可以的
贪心:
棵优先队列即可,每次取队首(最湿的)处理即可……
总之很水,但是本人很菜,所以……唉
AC代码:

T2 tahort 题解:
一道看了题解后,我更喜欢叫他dp的题……
对于dp[i]记录i为结束的最长的序列的首位,那么答案就是i-dp[i]
然后关于转移,从j开始倒序
因为如果a[i]>a[j],那么dp[i]所构成的序列与dp[j]所构成的序列就会是包含的关系(前提是能循环到j),所以可以直接把dp[i]的起点赋值为dp[j]
然后只要当a[j]>=a[i]时break就可以减少循环次数和方便判断了
//虽然最后优化成了一个while……但其实这样也能过

AC代码:

T3 circle 题解:
其实就是一道极其简单的二分……无疑让我感到了我的二分是有多么的菜……总是看不出来想不到可怎么办……
因为显然要找的距离是越接近于半个圆越好,而且又是要求1e5的数据,那么我们就处理一个前缀和然后直接来完成这件事就好了……
枚举每一个点作为起点,二分找到所能走的最大距离,然后总体取max即可
//因为是一个圆,所以化圆为链(把n的圆变成2×n的链即可)
AC代码:

今天考的是真的菜……唉……加油吧……

0
有向图强联通分量 Popular Cows

有向图强联通分量 Popular Cows

在yy就看了这道题,可是当时抄板子都没过,距离第一次尝试理解tarjan也很久了,今天写了两道题,怕是能写出来了……
poj The Popular Cows

0