Codeforces Global Round 21 （C构造贪心，D分治ST表，E组合数学）

比赛链接

Dashboard - Codeforces Global Round 21 - Codeforces
上次状态不好，小号随便打了两题就走，前两题太水就不说了

C-Fishingprince Plays With Array（构造+贪心） 1400

题意

给你一个长度为n的数组a以及正整数m。你有两个操作
- 如果一个$a_i$数是$m$的倍数，你可以将$m$分成连续的$\frac{a_i}{m}$
- 如果有$m$个连续的$\frac{a_i}{m}$，可以合成一个数$a_i$

问能否最后得到一个长度为$k$的数组$b$

例如：

5 2
1 2 2 4 2
4
1 4 4 2

可以将a数组的第二位和第三位的两个2合成一个4，使得a数组变成b数组。

思路

这种两个操作都是逆操作的，可以把它们都转化成最长的，也就是分解到都不能分解为止。因为如果最底层的都是一样的，那么最后合成也是可以的。例如：

n=5 m=4
a: 16,12,20,12,12

我可以转化成

4,4,4,4,3,3,3,3,5,5,5,5,3,3,3,3,3,3,3,3

但是这样太长，我们到时候保存的时候就拿pair<int,int>保存
变成{4,4},{3,4},{5,4},{3,8}，第一个存值，第二个存个数。
将a,b两个数组都变成这样，然后再去比较两个是不是一样，注意：vector可以直接用==比较

代码

vector<PII> p(N),q(N);
inline PII divide(int x)
{
    int res = 1;
    while (x%m==0)
    {
        x/=m;
        res *= m;
    }
    return {x,res};
}
inline void Case_Test()
{
    cin>>n>>m;
    p.clear();q.clear();
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        PII res = divide(x);
        if (p.size()&&p[p.size()-1].first==res.first)
            p[p.size()-1].second += res.second;
        else
            p.push_back(res);
    }
    cin>>k;
    for (int i=1;i<=k;i++)
    {
        cin>>x;
        PII res = divide(x);
        if (q.size()&&q[q.size()-1].first==res.first)
            q[q.size()-1].second += res.second;
        else
            q.push_back(res);
    }
    if (p!=q) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

D. Permutation Graph（ST表+分治） 1900

题意

给你一个长度为$n$的排列$a$，如果有$l_i,r_i$满足$a[l_i],a[r_i]$是区间$a[l_i],a[l_i+1],...,a[r_i-1],a[r_i]$中的最小值或者最大值，那么就在$l_i$到$r_i$建一条边，边权为$1$。问从$1$到$n$的最短距离是多少。注意，给出的数组是排列，没有相同的时候。
例如：

10
7 4 8 1 6 10 3 5 2 9

为如下图片

思路

我们对于上面那个样例来分析，一开始我在1...n中找到最小的最大的位置，分别是4,6，那么我不用管4和6之间了。为什么？因为哪怕中间有再多路径都不如走从4->6这一条，因为4和6已经是当前最小和最大的了。

假如有人问，能不能绕过4呢？比如从结点3到结点5——不可能，因为4是最小的。

所以这个最小和最大，完全将整个数列分割开来，只需要不断这样寻求最优解分治下去即可。

具体操作：
对于当前的dfs(int l,int r)中寻找最小值和最大值两个分界点L和R（不满足L<R则交换），然后往下继续分治找dfs(l,L),dfs(R,r)，知道只有一个和两个的时候特判，一个点肯定是不足构成一个边的，如果是两个点那么就return 1。

寻找区间最小值和最大值用的是ST表，

代码

inline int MIN(int l,int r)
{
    w=lg2[r-l+1];
    return Min(f[l][w],f[r-(1<<w)+1][w]);
}
inline int MAX(int l,int r)
{
    w=lg2[r-l+1];
    return Max(g[l][w],g[r-(1<<w)+1][w]);
}
inline void init()
{
    for (int i=1;i<=n;i++)
        f[i][0] = g[i][0] = a[i];
    for (int i=2;i<=n;i++)
        lg2[i]=lg2[i>>1]+1;
    for (int i=n;i>=1;i--)
        for (int j=1;i+(1<<j)-1<=n;j++)
            f[i][j]=Min(f[i][j-1],f[i+(1<<j-1)][j-1]),
            g[i][j]=Max(g[i][j-1],g[i+(1<<j-1)][j-1]);
}
inline int dfs(int l,int r)
{
    if (l==r) return 0;
    if (l+1==r) return 1;
    int mi = MIN(l,r), ma = MAX(l,r);
    int L = pos[mi], R = pos[ma];
    if (L>R) swap(L,R);
    return dfs(l,L)+dfs(R,r)+1;
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        pos[ a[i] ] = i;
    }
    init();
    cout<<dfs(1,n)<<endl;
}

E. Placing Jinas（数学/组合数学） 2000

题意

有一个无限大的网络，给定一个长度为n+1的数组a[0]到a[n]，保证a是非递增的，对于所有点$(x,y)$满足$y<a[x]$的点都是白色点，其他都是黑色点。
以题目中

10
12 11 8 8 6 6 6 5 3 2 1

为例。

其实就是在说第$i$列有$a[i]$个白色格子

在初始有一个小球在(0,0)，你可以执行以下操作，选择一个位置在(x,y)上的小球，把它删除，并且在(x+1,y),(x,y+1)上的地方继续添加一个小球，也就是

问最少多少次操作，使得白色格子上没有小球了。

思路

先分析一下，小球在(0,0)开始往外扩散的时候能得出什么样的数据？当小球在(x,y)的时候，个数与(x-1,y)与(x,y-1)有关，也就是
f[x][y] = f[x-1][y]+f[x][y-1],f[0][0]=1
也就是杨辉三角

杨辉三角这个题教给我一个结论，一个矩阵和的结论：

一个矩阵的和（从左上(0,0)开始到(x,y)）的值为f[x][y]-1
例如上面的$35-1=1+1+1+1+1+2+3+4+1+3+6+10$.

所以我们能得到从(0,0)到(x,y)的矩阵和：

int cal(int x,int y)
{
    x++;y++;
    return (C(x+y,x)-1+mod)%mod;
}

那对于每一列我们可以优化一下，优化成一个个的矩形，如严格鸽这图：

可以用map<int,vector<int>>mp处理

    for (int i=0;i<=n;i++)
        mp[a[i]].push_back(i);

这样对于矩形两边只需要取v.begin()和v.back()即可。

然后我们对于每个矩形求和就好。
类似于前缀和。

inline int calc(int L,int R,int k)
{
    return (cal(R,k) - cal(L-1,k) + mod) % mod;
}

这里对于组合数进行预处理：

int fac[N],invfac[N],n,a[N];
inline void init()
{
    fac[0] = invfac[0] = 1;
    for (int i=1;i<N;i++)
        fac[i] = fac[i-1]*i%mod;
    invfac[N-1] = qpow(fac[N-1],mod-2,mod);
    for (int i=N-2;i>=0;i--)
        invfac[i] = invfac[i+1]*(i+1)%mod;
}
inline int C(int a,int b)
{
    if (a<b) return 0;
    return fac[a]*invfac[b]%mod*invfac[a-b]%mod;
}

代码

代码都在上面呢
主函数写一下：

map<int,vector<int>> mp;
inline void Case_Test()
{
    init();
    cin>>n;
    for (int i=0;i<=n;i++)
        cin>>a[i],a[i]--;
    for (int i=0;i<=n;i++)
        mp[a[i]].push_back(i);
    int ans = 0;
    for (auto t:mp)
    {
        int k = t.first, L =  t.second.front(), R = t.second.back();
        ans = (ans + calc(L,R,k)) % mod;
    }
    cout<<ans<<endl;
}