A Floor Tiles in a Park

题意：给定 h×wh \times w 的矩形，将其分为 kk 个子矩形的方案数。h,w≤1×109h,w \leq 1\times 10^9，1≤k≤51 \leq k \leq 5。

解法：kk 很小可以考虑分类讨论，但是不建议此做法。最好的分类方案是以子矩形在大矩形内部分割产生的点的位置进行分类讨论。小于等于 44 的情况可以简单分类讨论出来。

对于 k=5k=5 有以下四大类：

  1. 全竖线分割、全横线分割（无新产生分割点）。(h−14)+(w−14)\displaystyle {h-1 \choose 4}+{w-1 \choose 4}。
  2. 产生三个在一条线上的分割点：大体可以认为是四个竖条子矩形再从中选择若干个相邻的竖条合并后拆分出一个长的横矩形alt

如上。这种情况有 2626 种：26((h−13)(w−12)+(h−12)(w−13))\displaystyle 26\left({h-1 \choose 3}{w-1 \choose 2}+{h-1 \choose 2}{w-1 \choose 3}\right)。 3. 分割点只有两个：这种情况下中间的alt

77 条分割线只需要随便擦除一根即可：7((h−12)(w−11)+(h−11)(w−12))\displaystyle 7\left({h-1 \choose 2}{w-1 \choose 1}+{h-1 \choose 1}{w-1 \choose 2}\right)。 4. 产生了 3,43,4 个不共线分割点，可以围成一个矩形：alt

这种情况最为复杂，其中有四个分割点的有 1616 种，右侧三个点的有 4848 种情况，总共有 6464 种情况：64((h−12)(w−12)+(h−12)(w−12))\displaystyle 64\left({h-1 \choose 2}{w-1 \choose 2}+{h-1 \choose 2}{w-1 \choose 2}\right)。

因而此题真诚的建议使用拉格朗日插值。注意到分割方案数 f(h,w)f(h,w) 是关于 h,wh,w 的最高五次多项式函数，因而大胆暴力打表然后插值即可：f(h,w)=∑i=15∑j=15yi,jlh,i(h)lk,j(w)\displaystyle f(h,w)=\sum_{i=1}^5\sum_{j=1}^5 y_{i,j}l_{h,i}(h)l_{k,j}(w)，其中 li(x)=∏j=1,j≠ix−ij−i\displaystyle l_i(x)=\prod_{j=1,j \neq i}\dfrac{x-i}{j-i}。暴力打表可以暴力枚举 kk 个子矩形的位置。具体代码实现可以参考其他题解。

C Constructive Problems Never Die

题意：构造一个长度为 nn 的排列，使得第 ii 位不是 aia_i。n≤5×105n \leq 5\times 10^5。

解法：依次记录每个值 ii 最早在什么时候被 ban，然后顺次从前到后的填数字，依照最早被 ban 的位置从后到前的填即可，这样可以保证后面的位置永远可以腾出来给前面的。若某个数字被 nn 个位置 ban 则无解。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        vector<int> a(n), nolim, ban, vis(n + 1, 0), ans(n);
        for (int i = 0; i < n;i++)
        {
            scanf("%d", &a[i]);
            if(!vis[a[i]])
            {
                vis[a[i]] = 1;
                ban.push_back(a[i]);
            }
        }
        if (ban.size() == 1)
        {
            printf("NO\n");
            continue;
        }
        for (int i = 1; i <= n;i++)
            if(!vis[i])
                nolim.push_back(i);
        for (int i = 0; i < n;i++)
        {
            int used = 1;
            if (!ban.empty() && a[i] == ban.back())
            {
                used = 0;
                ban.pop_back();
            }
            if (!ban.empty())
            {
                ans[i] = ban.back();
                ban.pop_back();
            }
            else if(!nolim.empty())
            {
                ans[i] = nolim.back();
                nolim.pop_back();
            }
            if (!used)
                ban.push_back(a[i]);
        }
        printf("YES\n");
        for (auto i : ans)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}

F Candies

题意：给定长度为 nn 的环形序列，若相邻两个数字和为 xx 或相等则可删除，删除后序列填补空隙，问删除次数。n≤5×105n \leq 5\times 10^5。

解法：显然消除顺序与最终结果无关。将大于等于 x2\dfrac{x}{2} 的数字 aia_i 一律当作 x−aix-a_i，则只有相等条件才能删除。首先不考虑环形则就是简单的栈删除，再考虑栈首尾消除即可。时间复杂度 O(n)\mathcal O(n)。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
vector<int> st;
int main()
{
    int n, x, ans = 0;
    scanf("%d%d", &n, &x);
    for (int i = 1, y; i <= n; i++)
    {
        scanf("%d", &y);
        if (!st.empty() && (st.back() + y == x || st.back() == y))
        {
            st.pop_back();
            ans++;
        }
        else
            st.push_back(y);
    }
    int posa = 0, posb = st.size() - 1;
    while(posa < posb)
        if(st[posa] == st[posb] || st[posa] + st[posb] == x)
        {
            posa++;
            posb--;
            ans++;
        }
        else
            break;
    printf("%d", ans);
    return 0;
}

G Regular Expression

题意：给定字符串 SS，问最短能接受 SS 的正则表达式长度和在这个长度下的正则表达式个数。

解法：考虑以下几种情况：

  1. S=aS=a。可以的正则表达式：a，.。
  2. S=aaS=aa。可以的正则表达式：a.，.a，a*，aa，.*，..，.+，a+。
  3. S=abS=ab。可以的正则表达式：a.，.b，ab，.*，..，.+。
  4. SS 为全 aa 串。可以的正则表达式：.*，.+，a+，a*。
  5. 其余情况。可以的正则表达式：.*，.+。