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

发表评论

电子邮件地址不会被公开。 必填项已用*标注