Educational Codeforces Round 144 (Div. 2)

Prime Deletion

算法本质

思维

题目大意

给定长度9的排列数组，删除其中至多7个元素，剩下的元素按顺序以十进制拼接为一个新数，使得其为素数。

输出最后的素数。

思路推演

考虑是A题，应该具有简单的方法，其中一个想法就是，存在ab是素数且ba是素数，这样可以覆盖所有情况。
查阅100以内的素数表，发现79和97都是素数。

Two Binary Strings

算法本质

思维

题目大意

给定2个长度相等的01字符串a b，保证以0开头、以1结尾，接下来可以执行任意次操作：

• 选择a或b字符串，选择2个相等的字符，将其中间字符都修改为所选字符

检查a b最终是否可以相等。

思路推演

显然的一个找规律的题目，或者叫做洞察其本质。

观察样例，可行的情况稍微有点多，反过来观察不可行的情况——一定是存在某个下标p，a[p]和b[p]不同且无法通过操作来改变。
但是这样的情况有很多，继续找其特征。

因为操作无限制，且可以对两个字符串都使用，所以还有一个特征是：

• 若两者可行，一定可以变为000011111的形式

到此为止，只需要检查是否存在某个下标p，能作为01的分界线即可。分界线是否可行，判断十分简单，这里就不说了。

Queries for the Array

算法本质

模拟、思维

题目大意

初始存在一个空数组，接下来会有3种操作：

• 新添加一个随机数字放置末尾
• 移出末尾的数字
• 检查数组是否单调不减（需要返回0或1，0表示非，1表示满足）

现在Alice展示了她玩这个的指令，检查这个指令是否可能存在。

思路推演

这是一个典型的模拟题，其中0或1会告诉我们信息，重点在于用什么形式将这些信息完全捕获：

• 1的信息
  数字有序是一个连续的性质，所以仅需要一个下标存储就好了。
  当有新增元素时，下标不变，当元素减少时，若当前下标元素没了，下标后退一步即可
• 0的信息
  表示当前数组不有序，即至少存在某个元素不有序，其实也可以这样理解，假如现在有n个数字，被告知不有序，则我们可以假设存在一个p<n，前p个元素是有序的，但是这个p是不定的。

通过上面的分析，可以发现的是，对于数组来说，可以分成三段：

• 下标[1, l]的部分，是保证有序的
• 下标[1, r]的部分，是可能有序、可能无序的
• 下标[1, 末尾]的部分，是一定无序的

对于每个操作来说，维护l r值即可，若其有冲突，则不可行。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
void solve()
{
    string s;
    cin>>s;
    flag = 1;
    int siz=0, l=0, r=0;    // siz表示当前数组长度，l r同上含义
    for (char c:s)
    {
        if (c=='+')
        {
            siz++;
            if (r==siz-1)    // 新增元素时，l不需要移动，r需要判断是否移动
                r=siz;
        }
        else if (c=='-')    // 删除元素时，保证l r不越界
        {
            siz--;
            l = min(l, siz);
            r = min(r, siz);
        }
        else if (c=='1')
        {
            if (siz > r)        // siz>r表示一定是无序的，起了冲突，不可行
            {
                flag=0;
                break;
            }
            l = r = siz;        // 重新赋值l r
        }
        else if (c=='0')
        {
            if (siz<2 || siz==l)    // 一定有序的条件
            {
                flag=0;
                break;
            }
            if (r==siz)        
                r--;
        }
    }
    cout<<(flag ? "YES" : "NO")<<endl;
    return;
}

Sorting By Multiplication

算法本质

思维

题目大意

给定长度n的正整数数组，现在可以若干次执行操作：

• 选择l r x，使得a[l~r]都乘上x（x可以为任意值，包括零和负数）

使得操作后数组严格递增，输出最小化的操作次数。

思路推演

还是老样子，分析一下操作的本质：
如果x>0的话，因为只关心元素的相对大小，所以这个操作其实可以看作加法。那这个就非常简单了，只需要检查相邻元素之间非递增关系的个数即可。

但是这里存在x<=0的情况，继续思考。
稍加模拟可以发现：因为最后是升序情况，所以最终必然是前一部分为负数，后一部分为正数的情况。
而初始全正，前一部分的负数用一次操作统一处理，而且具体哪个负值没有意义，视作都用-1即可。

一个朴素的想法是，那检查正负分界线即可。
前面负数部分，操作数是：相邻元素之间非递减关系的个数+1
后面整数部分，操作数是：相邻元素之间非递增关系的个数

这里只需要用前缀和处理一下即可，注意考虑全正全负的情况。

这里还有一个小坑导致赛时wa了一发，就是假如前负数部分是[1, p]，正数部分是[p+1, n]，p和p+1之间的关系是不用考虑的，其必然严格递增。

ac核心代码

代码会稍微奇怪一点，构建了a[]，长度n-1，表示n个元素之间的关系：

• 1表示严格大于
• 0表示等于
• -1表示严格小于

头文件、宏定义、快读模板、常见变量、常见变量等略。
{
    cin>>n;
    n--;
    vector<int> a(n+5), pre0(n+5), pre1(n+5);
    int last=in();
    for (int i=1; i<=n; i++)
    {
        int now=in();
        if (now > last)
            a[i] = 1;
        else if (now < last)
            a[i] = -1;
        last = now;
    }
    for (int i=1; i<=n; i++)
    {
        pre0[i] = pre0[i-1];    // pre0[i]=x表示前i个关系中，有x个关系都是等于或大于
        pre1[i] = pre1[i-1];    // 类似pre0[]
        if (a[i]==0 || a[i]==1)
            pre0[i]++;
        if (a[i]==0 || a[i]==-1)
            pre1[i]++; 
    }
    int ans = pre1[n];        // 考虑全正的情况
    pre1[n+1] = pre1[n];    // 可能会越界，特殊处理
    for (int i=1; i<=n; i++)
    {
        int res = pre0[i] + pre1[n] - pre1[i+1] + 1;        // 考虑前i个关系为负数
        ans = min(ans, res);
    }
    cout<<ans<<endl;
    return;
}

Non-Intersecting Subpermutations

算法本质

思维、dp

题目大意

给定n k，表示合法合规数组长度n，元素范围1~k。

定义数组的美丽值：

• 将其任意划分，若某个部分为长度k的排列则贡献值+1，划分方案所能达到的最大贡献值

输出所有合法合规数组的美丽值之和。

k n <= 4e3

思路推演-初步思路

这种题通常有2个思考方向：

• 计算美丽值为x的合法数组个数，然后最后统一乘法求和
• 计算某个部分对整体的贡献值，统一相加

但是不管选择哪种方法，其最大的问题在于，用贪心思路去计算，会计算重复——这表明只能用dp去解决，通过巧妙的设计，解决重复计算的问题。

这里为了避免重复计算，设定一个规则，比如数组[3, 2, 1, 2, 3]对于k=3的情况来说，这个数组的美丽值为1，但是有2种分割方式，根据贪心可知，总是用靠前的分割方式是最优解，所以视作[3, 2, 1]和[2, 3]，为了方便叙述，我们称这个下标3的位置为奇点。

一个朴素的想法是，通过制造方向性来避免重复计算：假设f[i]表示填写[1~i]位且i是奇点的方案数。（注意，这里的每个方案数，其最后k位可以视作已经固定了的）
这样答案就可以表示为：$\sum_{i=1}^nf(i)*k^{n-i}$

转移方程的话，可以通过枚举上一个奇点位置来转移。
接下来研究两个奇点如何转移。

设靠前奇点位置是j，靠后奇点位置是i，首先因为题目规定，所以j <= i-k。
其次通过模拟可以发现，如果i是第一个奇点，情况会比较特殊，要特殊处理，这里先讨论i非第一个奇点的情况。

讨论1——i不是第一个奇点的情况

转移方程用文字描述是：（暂时没有考虑i是第一个奇点的情况）

• $f(i) = \sum_{j=k}^{i-k}f(j)*(已知ij是奇点、且ij之间不存在奇点、且已知j为奇点的排列方式的方案数)$

为了解决这个问题，通过模拟发现，贪心比较难，但是可以用dp来解决。
所以构建式子g[x]表示：存在某个下标p是奇点、已知p奇点的排列方式、p+x是下一个奇点（中间无其他奇点）的方案数。

这样的话可以优化f[]的求解为：$f(i) = \sum_{j=k}^{i-k}f(j)*g(i-j)$

接着完善g[]的维护方程，这里引入g[]的前缀和函数pre[]方便描述：

• i<k
  已知了p奇点的排列方式，要使得p+i为奇点，则所选的元素种类的固定的，可以改变的是其排列方式，再减去重复的方案即可（中间有奇点的情况）
  $g(i) = i!-pre(i-1)$
• i>=k
  则后k个元素一定是排列，还剩余的i-k个元素随意取，减去重复方案即可（中间奇点情况）
  $g(i) = k!*k^{i-k}-pre(i-1)$

讨论2——i是第一个奇点的情况

前面的讨论给了我们很大的启发，i是第一个奇点的情况显然也可以使用dp来维护。
设h[i]表示i是第一个奇点的方案数。

思考出转移方程：

• i<k
h[i]=0
• i>=k
  $h(i) = k!*k^{i-k}-\sum_{j=1}^{i-1}h(j)*g(i-j)$
  显然这里也可以用前缀和辅助优化

汇总

当预处理好了g[]和h[]就可以表示f[]：

• $f(i) = \sum_{j=k}^{i-k}f(j)*g(i-j) + h(i)$
• $ans = \sum_{i=1}^nf(i)*k^{n-i}$

第一个式子，前部分表示i是非第一个奇点的方案数，后部分表示i是第一个奇点的方案数。
注意f[<k]显然为0

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。