T1

预处理出任意两点的最短路，找出每个点最远的3个点
枚举第2，3两点，枚举3个最大值即可，注意点判重

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node
{
    int Next, y;
} Pth[10005];
int cnt, head[3005], INF = 0x3f3f3f3f, dis[3005][3005];
bool vis[3005][3005];
ll ans = 0;
vector<pair<int, int>> v1[3005], v2[3005];

void add(int x, int y)
{
    cnt++;
    Pth[cnt].Next = head[x];
    Pth[cnt].y = y;
    head[x] = cnt;
}
int n, m;

void spfa(int s)
{
    queue<int> q;
    dis[s][s] = 0;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[s][x] = 0;
        for (int i = head[x]; i; i = Pth[i].Next)
        {
            int y = Pth[i].y;
            if (dis[s][y] > dis[s][x] + 1)
            {
                dis[s][y] = dis[s][x] + 1;
                if (!vis[s][y])
                    q.push(y);
            }
        }
    }
}

int main()
{
    // freopen("task.in", "r", stdin);
    // freopen("task.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i)
    {
        spfa(i);
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i == j)
                continue;
            if (dis[i][j] != INF)
                v1[i].push_back(make_pair(dis[i][j], j));
            if (dis[j][i] != INF)
                v2[i].push_back(make_pair(dis[j][i], j));
        }
        sort(v1[i].begin(), v1[i].end());
        sort(v2[i].begin(), v2[i].end());
        reverse(v1[i].begin(), v1[i].end());
        reverse(v2[i].begin(), v2[i].end());
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (dis[i][j] == INF || i == j)
                continue;
            for (int l = 0; l < v1[j].size() && l < 3; ++l)
            {
                if (i == v1[j][l].second)
                    continue;
                if (j == v1[j][l].second)
                    continue;
                for (int k = 0; k < v2[i].size() && k < 3; ++k)
                {
                    if (i == v2[i][k].second)
                        continue;
                    if (j == v2[i][k].second)
                        continue;
                    ans = max(ans, (ll)dis[i][j] + v1[j][l].first + v2[i][k].first);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

T2

dp
$dp[i][j][k]$表示前i个中左括号比右括号多j个，匹配到A串的第k位
预处理出KMP的Next数组即可
CF 1015F - Bracket Substring TODO

T3

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-14/