NOIP2015 - 模拟考试Ⅹ

闲扯

我轻轻地跳过了Ⅸ…
er。

Day 1

又一个绝佳的AC机会被我玩掉了hhh

Permutations

[Description]

给出长度为n的两个排列a,b,每次可以将a的最后一个元素拿出放到任意位置。问至少几次操作才能将a变成b.

[Hint]

$n≤10^5$.

[Solution]

考虑将a变成全排列,最少操作次数为n-排列开始最长连续子串的长度,然后把原题看做”关于b”的一个全排列即可。

[Summary]

感觉先考虑全排列这个思路比直接想优很多(其实是一开始我看错了题,然后发现原题就变简单了!)。

Stone

[Description]

n堆石子,每堆个数为ai。每次操作(i,j),为把第i堆石子并到第j堆,代价为ai。
q个询问,每个询问为一个整数k,表示每堆石子最多能合并多少堆石子(超过就只能合并到别的去),最后将n堆石子合为一堆的最小代价。

[Hint]

$n,q≤10^5,1≤k≤10^5$.

[Solution]

可以将合并的过程看做一棵k叉树,第i层的代价为权值和*(i-1),然后按大小排序并$log$计算就好了!

[Summary]

坑点此时就出现了…询问中竟然很多k等于1!然后我就丧心病狂地TLE了…
随便加个记忆化或者预处理出1就好了qwq

Rock

[Description]

n个红绿灯,颜色再任意时刻相同,第0秒所有灯变为绿灯,绿灯持续g秒,红灯持续r秒,轮流交换。到达某个等时正好从红变绿需要停下,从绿变红可以直行。给出n+1个整数,依次代表起点到第一个灯,第i个灯到第i+1个灯(1 ≤ i < n),第i个灯到终点的路程时间。给出q个询问,询问在第t秒出发会在什么时候到达。

[Hint]

$q,n≤5\cdot 10^4$

[Solution]

模拟70分。加个当前灯停下到终点要多久的预处理即可AC.

Day 2

Hello

Hello-3Q-3Q-very-much!

[Description]

统计区间[l,r]有多少个整数首位等于末位。

[Hint]

$1≤l≤r≤10^{18}$.

[Solution]

按位数分块统计下。

Fraction

[Description]

输入$n,m(n,m≤10^5)$,再分别输入n个整数a1~an,m个整数b1~bn(均不超过$10^7$),令$A=\sum ai$,$B=\sum bi$.
要求输出$p,q$,再分别输出p个整数c1~cn,q个整数d1~dn(均不超过$10^7$),令$C=\sum ci$,$D=\sum di$.
要求:$p,q≤10^5$,$\frac{A}{B}=\frac{C}{D}$,$gcd(C,D)=1$.

[Solution]

直接上$10^7$的质因数分解。计算出上下两部分要除去哪些质因数并记录数量,并分别把原来数里的这些质因数正好除掉,最后得到一个p=n,q=m的方案。

Match

[Description]

给定两个长度为n的大写字母串a,b,求函数$f(i,j,k)$(1≤i,j≤n且i+k,j+k≤n)的期望值。
$$f(i,j,k)=\sum_{t=0}^{k-1}a[i+k]=b[j+k]$$

[Solution]

我们发现,若a[i]=b[j],那么这两个字符对答案的贡献为$min(i,j)\cdot min(n-i+1,n-j+1)$,首先我们得到一个$O(n^2)$的算法。
考虑优化,对于所有i≤j,都有$ans+=i\cdot (n-j+1)$,否则$ans+=j\cdot (n-i+1)$,用前缀和优化就可以$O(n)$求解了。