月份:2017年9月

七校模拟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