1.29 educational round 81

1.29 Educational Codeforces Round 81

A Display The Number

题目描述

数字屏上0-9数字点亮分别需要不同的段、给定一定段，问能够点亮的最大的数字是几

题解

对于偶数段，则最大数字的每一位都是1就可以，对于奇数段，令第一位数字是7，之后全都是1即可

B Infinite Prefixes

题目描述

有一个长度为n的01串，可以无限次叠加，定义一个前缀01差：前(i)项中0比1多的个数，问有多少个前缀01差等于(m)

题解

每一个串存在一个(u),即整串的前缀01差，无限前缀能组成的数字仅有前(n)项前缀01差及无限u的叠加

（注意考虑特殊条件） ~~不考虑就hack~~

C Obtain The String

题目描述

有两个小写字母字符串(s)和(t),定义操作：每次可将s的一个非连续子串取出，求最小的操作数(n),可使得(n)次得到的子串连续成为字符串(t)

题解

直接贪心，利用子序列自动机加速

将26个字母保存1个(nex)二维数组，(nex_{ij})表示第(s)在第(i)个位置后的字母$j $第一次出现的位置,我们在求解过程中：

首先查找t的第一个字母在s中第一次出现的位置，即(nex_{0,t_1}),找到第一个字母后，寻找t的第二个字母的过程就是在(s)中(t)的第一个字母的位置后继续寻找第一次出现第二个字母的位置，以此类推，若是找不到，则操作数++，重新寻找

#include<bits/stdc++.h>
using namespace std;
int T;
char s[100005],t[100005];
int nxt[100005][26];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        scanf("%s",t+1);
        int n=strlen(s+1),m=strlen(t+1);
        for(int j=0;j<26;++j)nxt[n][j]=0;
        for(int i=n-1;i>=0;--i)
        {
            for(int j=0;j<26;++j)nxt[i][j]=nxt[i+1][j];
            nxt[i][s[i+1]-'a']=i+1;
        }
        int now=0,ans=1;
        for(int i=1;i<=m;++i)
        {
            now=nxt[now][t[i]-'a'];
            if(!now)
            {
                ans++;
                now=nxt[now][t[i]-'a'];
                if(!now){ans=-1;break;}
            }
        }
        printf("%d
",ans);
    }
    return 0;
}

D Same GCDs

题目描述

给定(a,m),计算$sumlimits_{i = 0}^{m - 1} {[gcd (a,m) = = gcd (a + i,m)]} $

题解

(gcd (a,m) = d o gcd (frac{a}{d},frac{m}{d}) = 1)

则原式可化为

[{egin{array}{l}sumlimits_{i = 0}^{m - 1} {[gcd (a + i,m){ m{ = = }}d]} \ = sumlimits_{i = 0}^{m - 1} {[gcd (frac{{a + i}}{d},frac{m}{d}){ m{ = = }}1]} = sumlimits_{i = a}^{m - 1} {[gcd (frac{i}{d},frac{m}{d})]} + sumlimits_{i = m{ m{ + 1}}}^{m + a} {[gcd (frac{i}{d},frac{m}{d})]} = sumlimits_{i = { m{1}}}^m {[gcd (frac{i}{d},frac{m}{d})]} = varphi (frac{m}{d})end{array}} ]

直接求欧拉函数即可

E Permutation Separation

题目描述

给一个排列，每个排列中的第(i)个数字为(p_i),权值为(w_i).你可以选择一个位置切一刀把它分成左右两部分，然后你可以花费(w_i)把(p_i)移动到另一个部分。最终要保证左半部分的最大值小于右半部分的最小值。

题解

基础还是太弱，看了半天题解感觉终于明白了

首先暴力解法：就是枚举将左右集合分开的位置，然后枚举边界x,使得左边集合大于x的数与右边集合小于x的数花费和最小

线段树解法：

线段树是将枚举的边界x作为叶子节点的

如果能够确定切的位置左边集合与右边集合均已经确定，每一个叶子节点x保存的是当前集合下以x为边界所需花费，由于线段树维护的是最小值，全局最小值就是当前确定集合的最小花费。

如何更新：

当集合发生改变时，比如说左边集合中新增了右边集合的(y),权值为(w),则当前集合下的最优解法中的以比y小的边界均需要将y移动到右边,区间增加(w)，比y大的边界则会略去这一步骤，即区间减去(w)