Codeforces Round 863 (Div. 3)

A.Insert Digit

算法本质

思维

题目大意

给定正整数a和小于10的正整数b，可以选择将b插入a的任意位置。

输出最大化a

思路推演

显然来说（稍微模拟一下），规律即从高位数向低位，找到第一个小于b的数字位置。

注意，最坏的情况b也需要插入a的末尾。

B.Conveyor Belts

算法本质

思维

题目大意

对于n*n（偶数n）的矩阵来说，其由n/2条口型传送带组成（如图）：

• 传送带不停顺时针循环，移动到相邻传送带需要花费1元

现在Alice想从位置s移动到位置t，输出最小化成本。

思路推演

显然，我们只需要计算出s和t所处的传送带层级，然后相减即可得到正解。

如何通过位置得到传送带层级呢：
观察图像，发现整体非常对称，我们可以将传送带上的位置，都转移到左上方位。
然后继续观察，当位置处于左上方位，我们可以用min(x,y)来表示传送带的层级。

C.Restore the Array

算法本质

思维

题目大意

对于长度n的a[]，存在长度n-1的b[]：b[i]=max(a[i], a[i+1])。

现在给定长度n-1的b[]，找出一种可能的a[]。（保证有解）

思路推演

对于b[i]来说，相关联的只有a[i]和a[i+1]，反之对于a[i]来说，关联的只有b[i-1]和b[i]。（可以画个图更直观）

假设对于当前的a[i]来说，取值范围为0 ~ min(b[i-1], b[i])，同时可以理解的是，尽量取大是最优解。
既然题目自己保证有解，我们只需要找最优解即可。

再考虑边缘情况，a[1]=b[1]和a[n]=b[n-1]为最优解。

D.Umka and a Long Fligh

算法本质

思维

题目大意

设f()是下标从0开始的斐波那契数列。

现在给定一个f(n) * f(n+1)的矩形，和特殊位置(x,y)，询问是否可以切割矩形并满足以下条件：

• 切割为n+1个正方形
• 所有正方形边长必须为斐波那契数
• 最多存在一对正方形的边长相等
• 其中(x,y)必须切割为一个1*1的正方形

思路推演

这些条件，一看有些懵，还是来看看样例吧。
可以发现，样例切割的n+1个正方形的边长为：f(n)、f(n-1)、......、f(1)、f(0)
这也恰好符合所谓的最多存在一对正方形的边长相等。

同时有闲心还可以证明一下：f(n)*f(n+1) = f(n)^2 + f(n-1)^2 + ... + f(1)^2 + f(0)^2（递归证明）

随后只有最后一个条件需要满足了：其中(x,y)必须切割为一个1*1的正方形

总体来说，矩形还是先切大正方形好切，我们在切大正方形的同时，就需要考虑如何避免切到(x,y)，以此尽可能留其到最后。
比如当前矩形长>高，我们固定切正方形切最左边部分， 则通过水平翻转，让(x,y)尽可能靠右，然后再切割。
这是贪心最优解，如果无可避免会切割到(x,y)的话，说明不可行。

随后旋转剩下的矩形，继续切割，递归写法。

E.Living Sequence

算法本质

思维

题目大意

Alice有一个1~1e12数字顺序排列的数组a[]，因为她不喜欢数字4，删去了所有有4的数字。

现在给定n，返回a[n]的值。

思路推演

显然的是，我们通过x计算1~x中不含4的数字个数，比反推容易许多。
同时其存在单调性，可以用二分协助。

如何计算1~x中不含4的数字个数：

• 九进制
  其实这本质就是九进制嘛

其实还有数位dp的方式，但是实际上是九进制的复杂版本

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
string to_s(int x)    // 将x转移到string[]中，同时处理掉4
{
    bool lim=1;        // 没有遇到4前存在限制
    string res = to_string(x);        // 高位在前（方便处理4）
    for (int i=0; i<res.length(); i++)
    {
        if (lim)
        {
            if (res[i]=='4')
            {
                res[i]='3';
                lim=0;
            }
        }
        else
            res[i] = '9';
    }
    return res;
}
int jin_9(string x)        // 九进制处理
{
    int res=0;
    reverse(x.begin(), x.end());
    for (int i=0; i<x.length(); i++)
    {
        int num = x[i] - '0' - (x[i]>'4');
        res += num * qpow(9, i, 1e18);
    }
    return res;
}
inline void solve()
{
    //init
    cin>>n;
    int l=1, r=1e13+5;        // r要多开大10倍才够
    int ans=r;
    while (l<=r)
    {
        int mid=(l+r)/2;
        int num=jin_9(to_s(mid));
        if (num>=n)
        {
            ans=mid;    // 可能好几个答案相同，找那个最小的（因为只有最小的才不含4）
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<ans<<endl;
    return;
}

F.Is It Flower?

算法本质

思维、模拟

题目大意

对于一个无向图，恰好满足以下条件称之为美丽：

• 初始有k个点形成简单环
• 这k个点各自又与k-1个点形成简单环，这部分的简单环之间不相交

对于给定的无向图，是否能找到某个k使其满足美丽输出YES，反之输出NO。

思路推演

对于一个美丽图显然存在：

• 边数：k*k+k
• 点数：k*k
• k个度数为4的点、k*k-k个度数为2的点

这部分条件肯定不足以判断美丽，主要是用于规范一下数据范围。

题目需要我们判断简单环，经过思考，对于n点为简单环的充要条件为：（这里的度概念仅限n点之间的边）

• 每点度数为2
• 连通性

对于题目的第一个要求：初始有k个点形成简单环
相对好解决，因为这k个点即度数为4的点，其边、点都很容易取出来，然后判断。

随后对于其第二个要求：这k个点各自又与k-1个点形成简单环，这部分的简单环之间不相交
发现只需要删除中心k点的边，即保证剩下的图会形成k个k点组成的简单环。我们只需要：

• 度数都为2——都是简单环
• 每个连通块的元素个数为k——k个长度k的简单环
• 中心点所属的连通块不同——每个简单环有一个中心点

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
// 省略了并查集板子
inline void solve()
{
    //init
    vector<pair<int,int>> g;            // 边
    map<int, int> d, d1, d2;            // 度、中心度、边缘度
    cin>>n>>m;
    int k=m-n;
    rep(i,1,m)
    {
        int u, v;
        cin>>u>>v;
        if (u > v)    swap(u, v);
        g.push_back({u, v});
        d[u]++, d[v]++;
    }
    // 规范数据范围
    map<int, int>cnt_du;
    for (auto i : d)    cnt_du[i.second]++;
    if (n==k*k && m==k*k+k && cnt_du[2]==k*k-k && cnt_du[4]==k);
    else
    {
        cout<<"NO"<<endl;
        return;
    }
    // 中心k个点成环
    init_set();
    vector<int> center;
    for (auto i:d)        // 中心点
        if (i.second==4)    center.push_back(i.first);
    for (auto i:g)        // 中心边
    {
        if (d[i.first]==4 && d[i.second]==4)        
        {
            d1[i.first]++, d1[i.second]++;
            union_set(i.first, i.second);
        }
    }
    for (int u:center)        // 判断是否为简单环
    {
        if (d1[u]==2 && find_set(u)==find_set(*center.begin()));    // 度数为2，且联通
        else
        {
            cout<<"NO"<<endl;
            return;
        }    
    }
    // 边缘k个环
    init_set();
    for (auto i:g)
    {
        if (d[i.first]==2 || d[i.second]==2)        // 边缘边
        {
            d2[i.first]++, d2[i.second]++;
            union_set(i.first, i.second);
        }
    }
    for (int i=1; i<=n; i++)    // 说明有k个k点环互不相交
    {
        if (d2[i]==2 && len[find_set(i)]==k);        // 保证有k个长度k的简单环
        else
        {
            cout<<"NO"<<endl;
            return;
        }
    }    
    set<int> st;
    for (int u:center)
        st.insert(find_set(u));
    if (st.size()==k);        // 保证每个环中都有1个中心点
    else
    {
        cout<<"NO"<<endl;
        return;
    }
    //out
    cout<<"YES"<<endl;
    return;
}

G2.Vlad and the Nice Paths (hard version)

算法本质

思维、dp

题目大意

给定长度n的a[]和k，满足下列条件的a[]子序列称之为美丽：

• 长度为k*x
• 子序列按序分成x组（每组有k个元素），每组元素相等

找到美丽且最长的子序列数目。（%mod）

注：空数组记作长度为0的一种情况。

思路推演

显然，如果对于这样的一个子序列，当想往里加元素，只与最后一个元素的值有关，十分适合dp性质。
同时我们对个数有要求，需要表示已选个数的信息，值作为方案数即可。

创建一个dp[i][j]表示已选了i个元素，最后一个元素的值为j。

随后推理转移方程式子：

• 不选择当前a[i]
  那就不用转移

• 选择当前a[i]

  • 新组第一个元素（j%k==1）
    dp[j][val] += dp[j-1][1~n]（这里显然需要优化处理）
  • 其他元素
    dp[j][val] += dp[j-1][val]

对于dp[j-1][1~n]的优化，我们设dp[][0]表示dp[][1~n]的值，每次更新时也向dp[][0]同步更新一下即可。

同时因为最后要输出最长的，所以我们还建立了一个vis[][]与dp[][]同步，表示可以抵达的地方。

其实可以使用dp值是否为0判断是否可达，但是因为取模的问题，0值也可能表达是mod。

当然还可以继续用魔法对抗，在取模中先-1后+1，这样mod值不会被模成0，此题可用。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
int dp[maxn][maxn];            // 已选j个元素、最后一个元素的值
bool vis[maxn][maxn];
int val[maxn];
void cls()
{
    for (int i=0; i<=n; i++)
    {
        for (int j=0; j<=n; j++)
            dp[i][j] = vis[i][j] = 0;
    }
}
inline void solve()
{
    //init
    int k;
    cin>>n>>k;
    cls();
    rep(i,1,n)    cin>>val[i];
    //cal
    dp[0][0] = 1;        // 空列表的方案数为1
    vis[0][0] = 1;        // 空列表默认可行
    for (int i=1; i<=n; i++)
    {
        for (int j=i; j>=1; j--)        // 从大往小数，避免干扰当前轮次
        {
            if (j%k == 1)        // 开新组
            {
                vis[j][val[i]] |= vis[j-1][0];
                dp[j][val[i]] += dp[j-1][0];
                dp[j][val[i]] %= mod;

                vis[j][0] |= vis[j-1][0];
                dp[j][0] += dp[j-1][0];
                dp[j][0] %= mod;
            }
            else
            {
                vis[j][val[i]] |= vis[j-1][val[i]];
                dp[j][val[i]] += dp[j-1][val[i]];
                dp[j][val[i]] %= mod;

                vis[j][0] |= vis[j-1][val[i]];
                dp[j][0] += dp[j-1][val[i]];
                dp[j][0] %= mod;
            }
        }
    }
    int ans;
    for (int i=n/k*k; i>=0; i-=k)
    {
        if (vis[i][0])
        {
            ans = dp[i][0];
            break;
        }
    }
    cout<<ans<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

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