Codeforces Round 833 (Div. 2)

A.The Ultimate Square

算法本质

思维

题目大意

给n块木板，第i块木板的规格是1 * (i+1)/2。

请问可以拼成的最大正方形边长。

思路推演

第一时间想不到解法，但是思考其A题，应该相对简单，就打表n块木板的最大面积：1 2 4 6 9 12 16 20 ...。
可以看到的是，对于n为奇数的情况，其总面积是平方数。

然后拿个奇数n来手动拼一下，验证一下是否可行：
可以分为(n+1)/2个1 * (n+1)/2的矩形：(n+1)/2 (n+1)/2-1和1 (n+1)/2-1和1 (n+1)/2-2和2 ...

说明是可行的，而且偶数n情况也不会大于下一个平方数。
所以答案输出(n+1)/2即可。

B.Diverse Substrings

算法本质

思维

题目大意

给定由0~9组成的字符串S。
对于其中的一个子串，称其为美丽：

• 某字符的数目 <= 字符种类

请问美丽的非空字串数目。

s.length <= 1e5

思路推演

普通的想法是，看看某字符的数目和字符种类有没有单调性，可以前缀+二分搞定。
手动模拟了一下，发现没有。

但是发现了一个忽略的条件：字符串只由0~9组成，说明字符种类最多也就10个，当某字符数目>10时，就一定不能是美丽的。

所以直接暴力搜就好，写个条件剪枝。

C.Zero-Sum Prefixes

算法本质

思维

题目大意

给定长度为n的数组a[]，其中值为0的元素可以修改为任意值。

对于数组a[]，其魅力值的计算如下：

• 设其前缀和数组为pre[]，魅力值为pre[]元素为0的数目

最大化a[]的魅力值并输出。

n <= 2e5

思路推演

对于下标为i的0值来说，其整体改变会影响其pre[i~n]的值。

所以实际上，0值之间的pre[]元素会上下移动，让其最多的元素值移动到0值即可。

D.ConstructOR

算法本质

思维

题目大意

给定3个整数a b d。

输出是否存在整数x，使得：

• a|x % d == 0
• b|x % d == 0

a,b,d <= 2**30
x <= 2**60

思路推演

要同时满足a b两个数，比较难。
因为是or运算，所以考虑，x对于a b都满足x|a == x和x|b == x。
即把a b都看作同一个数：a|b。

这里看成同一个数，只是单纯地为了简化思考难度。
如果后面发现不能，我们也完成了对单个数的思考，从而进一步思考两个数情况。

设：c = a|b

目前存在2个式子（要求）

• x|c == x（二进制下，c的某位为1，x的这位必须为1）
  同时需要lowbit(x) == lowbit(c)
• x%d == 0

思维推演-1

回忆一下，通常对于多个要求的情况，都是先满足一个相对简单、有规律的要求，然后去靠近另外的要求。
所以我们这里先满足x%d==0的要求。

下面结论得出有些跳跃，实际做的时候是不断尝试+经验得到的结论

假设目前x=0
随后找到c为1但是x为0的二进制位，现在需要用左移的d对这些位填充。

假设c的二进制为：0000000011010100（左高右低，从右往左下标1开始）
则x的第1、2位只能为0，现在3、5、7、8位必须要填充为1。

• 整体填充
  没有找到合适方法
• 从左往右填充
  在填充位置更小的1时，d的值可能改变前面位置更大的需要填充的1
• 从右往左填充
  合理

ac核心代码-1

头文件、宏定义、快读模板、常见变量、常见变量等略。
int er[100];        //solve_init()预处理了
int wei(int x, int c)        //找到最低的一位：c为1，x为0的位
{
    for (int i=0; i<=60; i++)
    {
        if ((c&er[i])>0 && (x&er[i])==0)
            return i;
    }
    return -1;        //说明已经合格了
}
inline void solve()
{
    //init
    int a, b, c, d;
    cin>>a>>b>>d;
    c = a|b;
    if (lowbit(d) > lowbit(c))
    {
        cout<<-1<<endl;
        return;
    }
    //cal
    int x=0, p0=0, tmp=d;        //p0表示d的前缀0个数
    while ((tmp&1)==0)
    {
        p0++;
        tmp/=2;
    }
    while (1)
    {
        int w = wei(x, c);        //找到最低的一位：c为1，x为0的位
        if (w==-1)    break;        //如果没找到，就说明填充完了，直接退出
        x += d*er[w-p0];        //填充
    }
    cout<<x<<endl;
    return;
}

https://zhuanlan.zhihu.com/p/582922871

https://zhuanlan.zhihu.com/p/583789192

https://zhuanlan.zhihu.com/p/583087619

https://zhuanlan.zhihu.com/p/582927038

E.Yet Another Array Counting Problem

算法本质

思维、树形dp

题目大意

给定长度为n的数组a[]，其元素值在1~m之间。
对于长度为n数组b[]，其是美丽的如果满足下列条件：

• 元素值在1~m之间
• 对于所有的区间[l r]，b[]在区间内的最左端的最大值的下标同a[]的一样，下面用函数f(l,r)表示

找出美丽b[]的数目。（mod 1e9+7）

n,m <= 2e5
n*m <= 1e6

思路推演

手动模拟一下，如果对于a[]，f(1,n)=i。
则当l<=i && r>=i的时候，其f(l,r)=i。

这一下子解决了许多区间！

继续思考左右两边是不是独立的，手动模拟（题目样例），发现确实是独立的。
不过左区间需要保证值<b[i]而右区间的值<=b[i]。

这是相当典型的二叉树结构。
思考，能否log级别找到区间最大值下标——ok的，只需要稍微改动一下st表。

ac核心代码-1

头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
vector<int> cnt[maxn];            //cnt[pos][val]：b[pos]值为val的方案数（只算树下部分）
vector<int> pre[maxn];            //cnt的前缀和


pair<int,int> st[maxn][20];        //st板子
void init_st()
{
    for (int i=1; i<=n; i++)        //st[]初始化
        st[i][0]={a[i], n-i};     //值大、位置小优先
    for (int len=1; len<=20; len++)
        for (int pos=1; pos+(1<<len)-1<=n; pos++)    
            st[pos][len] = max(st[pos][len-1], st[ pos+(1<<(len-1)) ][len-1]);
}

int find_st(int l, int r)    //返回的是最左边的最大值的下标
{
    int len=log2(r-l+1);        
    pair<int, int> u=max(  st[l][len]    ,     st[r-(1<<len)+1][len]);
    return n-u.second;
}

int sonl[maxn], sonr[maxn];
int dfs(int l=1, int r=n, int fr=0, int val=m)        //开始造树结构
{
    int pos = find_st(l, r);        //找到最左边的最大值
    if (pos>l)
        sonl[pos] = dfs(l, pos-1, pos, val-1);
    if (pos<r)
        sonr[pos] = dfs(pos+1, r, pos, val);

    if (sonl[pos]==0 && sonr[pos]==0)        // 如果左右都没有儿子，那就把所有可以取到的值设为1
    {
        for (int i=1; i<=val; i++)
        {
            cnt[pos][i] = 1;
            cnt[pos][i] %= mod;
            pre[pos][i] = pre[pos][i-1] + cnt[pos][i];
            pre[pos][i] %= mod;
        }
    }
    else if (sonl[pos]==0)        
    {
        for (int i=1; i<=val; i++)
        {
            cnt[pos][i] = pre[sonr[pos]][i];        //右区间的值不降
            cnt[pos][i] %= mod;
            pre[pos][i] = pre[pos][i-1] + cnt[pos][i];
            pre[pos][i] %= mod;
        }
    }
    else if (sonr[pos]==0)
    {
        for (int i=1; i<=val; i++)
        {
            cnt[pos][i] = pre[sonl[pos]][i-1];        //左区间的值降1
            cnt[pos][i] %= mod;
            pre[pos][i] = pre[pos][i-1] + cnt[pos][i];
            pre[pos][i] %= mod;
        }
    }
    else
    {
        for (int i=1; i<=val; i++)
        {
            cnt[pos][i] = pre[sonl[pos]][i-1] * pre[sonr[pos]][i];
            cnt[pos][i] %= mod;
            pre[pos][i] = pre[pos][i-1] + cnt[pos][i];
            pre[pos][i] %= mod;
        }
    }
    return pos;
}
inline void solve()
{
    //init
    cin>>n>>m;
    rep(i,1,n)    cin>>a[i];
    rep(i,1,n)
    {
        cnt[i].clear();        //cnt[]和pre[]可以不用赋初始值
        cnt[i].resize(m+5);
        pre[i].clear();
        pre[i].resize(m+5);
        sonl[i]=0;        //因为dfs()中需要判断是否为空，所以要赋初值0
        sonr[i]=0;
    }
    init_st();        //稍作改动的st表
    //cal
    int root=dfs();
    int ans = pre[root][m];
    cout<<ans<<endl;
    return;
}