T1

发现 $u\to v$ 的方案数是可以用 $u\to k\to v$ 算出来的，就类似 Floyd 枚举中心点。

然后就直接枚举 $gap$，$u\to u+gap$ 枚举中间点进行转移。

但是发现 $1\to 2\to 3\to 5$ 是会统计两次 $1\to {\color{red}2}\to 3\to 5$ 和 $1\to 2\to {\color{red}3}\to 5$ 的。

设 $g_{u,v}$ 表示是否存在 $u\to v$ 的直接连接路径即可顺利转移。

#include <bits/stdc++.h>
using namespace std;
int n;
char mp[1020][1020];
int f[1020][1020];
int g[1020][1020];
int ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
            mp[i][j] = '0';
        for (int j = i + 1; j <= n; j++)
            cin >> mp[i][j];
    }
    // for (int i = 1; i <= n; i++)
    //     for (int j = 1; j <= n; j++)
    //         cout << mp[i][j] << " \n"[j == n];
    for (int gap = 1; gap <= n; gap++)
    {
        for (int u = 1; u + gap <= n; u++)
        {
            int v = u + gap;
            // cout << u << " " << v << endl;
            for (int k = u + 1; k < v; k++)
                (f[u][v] += g[u][k] * f[k][v]) %= 2;
            // cout << f[u][v] << " " << mp[u][v] << endl;
            if ((f[u][v] & 1) != (mp[u][v] ^ '0'))
                (f[u][v] += 1) %= 2, g[u][v] = 1, ans++;
            // cout << f[u][v] << endl
            //      << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

T2

人类智慧

记忆化搜索，$g_u$ 表示 $u$ 出发的最长路，$f_u$ 表示 $u$ 出发最长路中字典序最小的收益。

然后发现字典序不是很好转移，考虑第一步一样取答案最小。喜提过了 19 个然后 WA on #20。

主播赛时到这里就跳了，然后发现

https://www.luogu.com.cn/blog/679936/au-t2-xian-xing-zuo-fa-post

我们记录两步就行了。

WA on #20

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
void read(T &x)
{
    x = 0;
    int f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            f = -f;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
    read(x);
    read(y...);
}
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
typedef pair<ll, ll> pii;
int n, m;
set<pii> e[200020];
ll f[200020];
ll g[200020];
ll len;
pii dfs(int u, int len)
{
    ll &t = f[u];
    ll &T = g[u];
    if (~t)
        return {t, T};
    if (e[u].empty())
        return {t = 0, T = 0};
    ll val = -1;
    for (pii i : e[u])
    {
        dfs(i.second, len + 1);
        ll res = i.first + f[i.second];
        if (g[i.second] + 1 > T)
            val = i.first, t = res, T = g[i.second] + 1;
        else if (g[i.second] + 1 == T && val == i.first)
            chkmn(t, res);
    }
    return {t, T};
}
int main()
{
    read(n, m);
    while (m--)
    {
        int x, y, z;
        read(x, y, z);
        e[x].insert({z, y});
    }
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= n; i++)
    {
        pii res = dfs(i, 0);
        cout << res.second << " " << res.first << '\n';
    }
    return 0;
}

别急，等发数据了再发。顺便去你谷加强一下。

正解

拓扑。

等我先学习一下。

T3

在线

发现按题目说的 $f(y)$ 就是个凹函数。

容易发现对于整数 $y$ 当 $a\neq b$ 时不存在非极值点的平台，只有在 $a=b$ 时存在平台，但此时函数是一条直线。

整数三分成立，贺板子。

然后考虑优化 $f(y)$ 的计算，稍微拆一下就知道记录前缀和后缀和即可，二分当前 $y$ 在 $x$ 序列中的位置即可单次 $f(y)$ 做到 $\log n$ 的效率，总过程是 $\log^2$ 的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q;
int x[200020];
ll pre[200020];
ll suf[200020];
ll a, b;
ll f(ll k)
{
    int pos = upper_bound(x + 1, x + n + 1, k) - x - 1;
    //[1,pos] [pos+1,n]
    return a * (k * pos - pre[pos]) + b * (suf[pos + 1] - k * (n - pos));
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    sort(x + 1, x + n + 1);
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + x[i];
    for (int i = n; i >= 1; i--)
        suf[i] = suf[i + 1] + x[i];
    cin >> q;
    while (q--)
    {
        cin >> a >> b;
        int l = 0, r = 1e6 + 1;
        while (l < r)
        {
            int ml = l + (r - l) / 3;
            int mr = r - (r - l) / 3;
            // cout << ml << " " << mr << " " << f(ml) << " " << f(mr) << endl;
            if (f(ml) > f(mr))
                l = ml + 1;
            else
                r = mr - 1;
        }
        cout << min(f(l), f(r)) << endl;
    }
    return 0;
}