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⋅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$个整数$a_1\sim a_n$，$m$个整数$b_1\sim b_n$（均不超过$10^7$），令$A=\sum_ia_i,B=\sum_ib_i$.
要求输出$p,q$，再分别输出$p$个整数$c_1\sim c_n$，$q$个整数$d_1\sim d_n$（均不超过$10^7$），令$C=∑_ic_i,D=∑_id_i$.
要求：$p,q≤10^5，\frac{A}{B}=\frac{C}{D}，gcd(C,D)=1$.

[Solution]

直接上107的质因数分解。计算出上下两部分要除去哪些质因数并记录数量，并分别把原来数里的这些质因数正好除掉，最后得到一个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)⋅min(n−i+1,n−j+1)$，首先我们得到一个$O(n^2)$的算法。
考虑优化，对于所有$i≤j$，都有$ans+=i⋅(n−j+1)$，否则$ans+=j⋅(n−i+1)$，用前缀和优化就可以$O(n)$求解了。