Educational Codeforces Round 81


A. Display The Number

题意

用灯点亮来表示数字。现在要求最多使用 \(n\) 盏灯,求能表示的最大数。

分析

首先肯定是要位数尽可能的多。

显然数字 \(1\) 只是用两盏灯,用 \(1\) 点亮一定能获得尽可能多的位数。

于是如果灯的数量如果是偶数,那么就是全 \(1\) 的数。

否则是奇数的话,可以用三盏灯来表示 \(7\) ,显然把 \(7\) 放最前面是最优的。

B. Infinite Prefixes

题意

找一个无穷串 \(T=ssss\cdots \) 有多少前缀满足 \(0\) 的个数 \(-\) \(1\) 的个数为 \(x\) 。

分析

假设一个串 \(s\) 整体 \(0\) 的个数 \(-\) \(1\) 的个数为 \(y\) ,每一个位置本身的前缀 \(0\) 的个数 \(-\) \(1\) 的个数为 \(_i\) 。则重复的第 \(n\) 串中,每一个位置 \(0\) 的个数 \(-\) \(1\) 的个数为 \(a_i+y(n-1)\) 。

又因为 \(a_i\) 的跨度最大为 \(n\) ,可以直接枚举。

于是我们只需要将 \(x\) 调节到上下限附近,然后直接枚举每个数出现的次数统计即可。

C. Obtain The String

题意

通过不断获得 \(s\) 的子序列来构成字符串 \(t\) 。询问至少需要几个 \(s\) 的子序列。

分析

我们肯定会尽可能多的去获得 \(s\) 的子序列来和 \(t\) 当前的前缀匹配。

于是我们预处理 \(s\) 每一位之后能够到达最近某个字母的位置(从后往前遍历一遍即可)。

每次都从当前位置开始跳到之后的第一个字母出现的位置,一旦没有了,则从头开始,显然此时开始了一个新的子序列。

D. Same GCDs

题意

求在 \(x\in [0,m)\) 中有多少 \(x\) 满足 \(gcd(n,m)=gcd(n+x,m)\) 。

分析

题目要求的其实就是 \(\sum _{i=0}^{m-1}[gcd(n,m)=gcd(n+i,m)]\)

根据辗转相除法 :\(\sum _{i=0}^{m-1}[gcd(n,m)=gcd(n+i,m)]\Leftrightarrow \sum _{i=0}^{m-1}[gcd(n,m)=gcd((n+i)\; mod\; m,m)]\)

因为 \(0\le i < m\) ,显然 \((n+i)\; mod\; m \in [0,m)\) 。

也就是 \(\sum _{i=0}^{m-1}[gcd(n,m)=gcd((n+x)\; mod\; m,m)]\Leftrightarrow \sum _{i=0}^{m-1}[gcd(n,m)=gcd(i,m)]\) 。

而其中 \(gcd(n,m)\) 是常数,令 \(gcd(n,m)=k\) ,则有 \(\sum _{i=0}^{m-1}[gcd(i,m)=k]\Leftrightarrow \sum _{0\le i < m}^{k|i}[gcd(\frac{i}{k},\frac{m}{k})=1]\)

可以发现 \(\sum _{0\le i < m}^{k|i}[gcd(\frac{i}{k},\frac{m}{k})=1]=\phi (\frac{m}{k})\) 。

E. Permutation Separation

题意

给出一个排列,要先将排列从中间分开成两个非空的数列,然后需要移动两个数列中的元素,每个元素移动的代价给出,需要最后满足前一个排列中的元素均小于第二个数列中的元素,求最小代价。

分析

首先考虑把其中一个排列移空的情况,因为 \(a[i]\ge 1\) ,显然,分开的时候留一个头或者留一个尾,然后将这个元素并入另一个数列,则代价显然是 \(min\{a[1],a[n]\}\) 。

其余的情况,我们考虑用 \(f[i]\) 表示第一个数列的结尾为第 \(i\) 个元素所需要的代价。

考虑如果位于位置 \(i\) 的元素在所有操作完成后应该属于第二个数列,则 \(f[j](i\le j\le n)\) 需要加上 \(a[i]\) (因为这些情况下分成两个数列以后,第 \(i\) 个元素属于第一个数列);同样地,如果位于位置 \(i\) 的元素在所有操作完成后应该属于第一个数列,则 \(f[j](1\le j < i)\) 需要加上 \(a[i]\) 。

于是我们考虑枚举,所有操作完成以后,第二个数列的数下限,用线段树维护操作,每次只需要修改一个数所造成的影响即可。

F. Good Contest

题意

每个数有一个可供选择的范围,现在要求这个数列不上升的概率。

分析

如果不考虑数的范围的话,很容易想到一个 dp 。用 \(f[i][j]\) 表示处理了前 \(i\) 个数,且最后一个数为 \(j\) 的方案数。

但是数的范围太大了,现在不能这么做。

我们考虑把所涉及到的左右端点离散,于是可以变成一个区间的问题。考虑用状态 \(f[i][j][k]\) 来表示,处理了前 \(i\) 个数,且最后有 \(k\) 个数属于区间 \(j\)  的方案数,为了方便描述,我们令 \(j\) 区间的长度为 \(|j|\) ,要在区间 \(j\) 中选出 \(k\) 个数,且满足不增的关系,显然方案数为 \(C_{|j|+k-1}^k\)。

于是考虑转移:

  • 在当前的状态下,继续在区间 \(j\) 中加入一个数,则 \(f[i+1][j][k+1]+=f[i][j][k]\div \frac{C_{|j|+k-1}^k}{|j|^k}\times \frac{C_{|j|+k}^{k+1}}{|j|^{k+1}}\times \frac{|j|}{r_{i+1}-l_{i+1}+1}\) ,其中 \(\frac{|j|}{r_{i+1}-l_{i+1}+1}\) 表示的是当前这个数落在这个区间的概率,其余的方式是除去选择 \(k\) 的概率在乘上 选择 \(k+1\) 的概率。
  • 选择一个新的区间加入,但是要满足不增的关系,所以要在 \(k(k < j)\) 区间加入,则 \(f[i+1][k][1]+=f[i][j][k]\times \frac{|j|}{r_{i+1}-l_{i+1}+1}\) ,只有一个数则不需要考虑不增的选择方式。

对于上面的第二个转移方程,可以使用后缀和的方式来优化时间复杂度。

总的时间复杂度为 \(O(2n^4)\) 。

这道题目是分数,有逆元无法手算,就给调试带来了很大的不便利。

 

You may also like

LEAVE A COMMENT

Statistics

  • 1
  • 67,592

Categories

Archive

Comments