青春是萤火绚丽的流动银河，灿烂却也极致短暂

[POI 2005] PUN-Points

注意到是判断同构问题。

怎么换了个架子我就不会做了？？？

注意到就算是一堆点看同构，我们依然可以找到这些点的重心，也就是这一堆点的 $\overline x, \overline y$，把他们当作重心。

为了找到一个合理的顺序，考虑把所有点按照这个重心进行极角排序。

你会发现此时我们就不需要考虑平移和放缩的问题。

注意到数据范围比较小，可以直接暴力旋转和翻折。

代码不想写了，不会极角排序，但是重心面对同构真的是一把利器。

[ABC419G] Count Simple Paths 2

其实看到这种 $m-n$ 比较小的应该是有显然的串并联思维的。

可惜我不会。

注意到题解区有一个虚树的做法。

定义 $k=m-n+1$。

首先有一个暴力搜索所有路径的算法，注意到时间复杂度应该是 $\mathcal{O}(2^kn)$。

注意到如果你建出一颗搜索树，那么你在搜索中除开这 $2^k$ 种使用了非树边的路径，其实绝大部分都是在树上进行行走，而树的形态是确定的。

所以我们考虑用尽可能少的点来刻画这一搜索，注意到建出搜索树之后，我们把非树边对应的所有节点建一颗虚树，然后在树上插入两点距离作为边权，然后再加入非树边，再按照最开始的暴力搜索，时间复杂度就只有 $\mathcal{O}(2^kk)$ 了。

[ARC204A] Use Udon Coupon

考场上想半天啥也不会，这就是菜的力量。

首先考虑暴力 $\mathcal{O}(n^4)$ 的 DP，有 $dp_{i,j,k}$ 表示添加 $a$ 到了 $i$，从前往后删除到了 $j$，当前 $C=k$ 的方案数。

转移是显然的，这里不写了。

考虑一个小优化，注意到答案一定 $\ge \sum b_i-\sum a_i$。

故我们考虑把状态里的 $k$ 定义为 $k=c-\Big(\sum_{k=1}^j b_k-\sum_{k=1}^i a_i\Big )$。

发现从 $dp_{i,j}\to dp_{i,j+1}$ 的转移时，$k$ 的值不会变。

而从 $dp_{i,j}\to dp_{i+1,j}$ 时，稍微推一下式子，可以发现是 $k\to \max {k,\sum_{l=1}^i a_l-\sum_{l=1}^j b_j}$。

注意到 $k$ 的值一直再增加。

考虑对于原题的 $l,r$ 容斥变成 $\text{ans}_r-\text{ans}_{l-1}$，我们直接定义 $dp_{i,j}$ 表示满足 $k\le R$ 的答案。由于 $k$ 转移的单调性，我们可以得到如下转移：

dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
    for (int j = 0; j <= i; ++j)
    {
        if(j) dp[i][j] = dp[i][j - 1];
        if(sa[i] - sb[j] <= r) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
    }
}

可以看总代码方便理解：

#include <bits/stdc++.h>
using namespace std;
#define maxn 5005
const int mod = 998244353;
int dp[maxn][maxn];
int n, l, r;
int a[maxn], b[maxn];
int sa[maxn], sb[maxn];
int solve(int r)
{
    if(r < 0) return 0;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            if(j) dp[i][j] = dp[i][j - 1];
            if(sa[i] - sb[j] <= r) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
        }
    }
    return dp[n][n];
}
int main()
{
    // freopen("1.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> l >> r;
    for (int i = 1; i <= n; ++i) cin >> a[i], sa[i] = sa[i - 1] + a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i], sb[i] = sb[i - 1] + b[i];
    int all = sb[n] - sa[n], ans = 0;
    cout << (solve(max(r - all, -1)) - solve(max(l - 1 - all, -1)) + mod) % mod << endl;
    return 0;
}

GYM105789H Horrible Restaurants

考虑一个错误的贪心，从 $i\to i+1$ 时，新增一个代价最小的星星。

但是你会发现这个是错的，考虑一定程度上的反悔贪心，如下几种情况：

• $+1$
• $+2,-1$
• $+3,-2$
• $+2,+2,-3$
• $+3,-1,-1$

可以直接维护所有的情况，注意 $+,-$ 的时候不要操作同一家饭店即可。

代码看起来很重要：link。