考试的状态和平时做题的状态天壤之别

qwq

A

我也不知道为啥我写了这么长

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MAXN (100 + 5)
#define INF (0X7FFFFFFF)
using namespace std;
bool cmp(string& x, string& y)
{
    if (x.length() != y.length())
        return x.length() < y.length();
    else
        return x < y;
}
int pd(string x, string y)
{
    int re = 0;
    for (int i = 0; i < x.length(); i++)
        if (x[i] != y[i])
            ++re;
    return re;
}
int main()
{
    string s[MAXN], t[MAXN];
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> s[i];
    for (int i = 1; i <= n; i++)    cin >> t[i];
    sort(s + 1, s + n + 1, cmp);
    sort(t + 1, t + n + 1, cmp);
    bool viss[MAXN], vist[MAXN];
    memset(viss, false, sizeof(viss));
    memset(vist, false, sizeof(vist));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (viss[i])
                break;
            if (vist[j])
                continue;
            if (s[i] == t[j])
                viss[i] = vist[j] = true;
        }
    for (int i = 1; i <= n; i++)
    {
        if (viss[i])
            continue;
        int dqans = INF, ansi = 0;
        for (int j = 1; j <= n; j++)
            if (!vist[j] && t[j].length() == s[i].length())
            {
                if (pd(s[i], t[j]) < dqans)
                    dqans = pd(s[i], t[j]), ansi = j;
            }
        vist[ansi] = true;
        ans += dqans;
    }
    cout << ans;
    return 0;
}

B

贪心找翻转的最大收益就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXM (1000000000 + 5)
#define INF (0x7fffffff)
#define LL long long
using namespace std;
int n, m, a[MAXN];
void solve()
{
    int fa[MAXN];
    for (int i = 1; i <= n; i++)
        if (i & 1)
            fa[i] = fa[i - 1] + a[i] - a[i - 1];
        else
            fa[i] = fa[i - 1];

    int frdark = 0, frlight = 0, ansi = n, maxc = -INF, ans = 0;
    for (int i = n; i >= 1; i--)
    {
        if (i & 1)
            frdark += a[i + 1] - a[i];
        else
            frlight += a[i + 1] - a[i];
        if (maxc < frdark - frlight)
            maxc = frdark - frlight, ansi = i, ans = frdark;
    }
    printf("%d\n", max(fa[n], fa[ansi] + ans - 1));    
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    if (n %2 == 0)
        a[++n] = m;
    a[n + 1] = m;
    solve();
    return 0;
}

C

离散化前缀和随便做, 听说他们都打了线段树Orz

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define LL long long
#define pii pair<LL, LL>
using namespace std;
int n, f[MAXN << 1], a[MAXN << 1];
LL sora[MAXN << 1];
pii s[MAXN];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &s[i].first, &s[i].second), ++s[i].second, sora[++sora[0]] = s[i].first, sora[++sora[0]] = s[i].second;
    sort(sora + 1, sora + sora[0] + 1);
    sora[0] = unique(sora + 1, sora + sora[0] + 1) - sora - 1;
    for (int i = 1; i <= n; i++)
    {
        LL le = lower_bound(sora + 1, sora + sora[0] + 1, s[i].first) - sora, ri = lower_bound(sora + 1, sora + sora[0] + 1, s[i].second) - sora;
        ++f[le], --f[ri];
    }
    LL cnt[MAXN];
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= sora[0] + 1; i++)
        f[i] += f[i - 1];
    for (int i = 1; i <= sora[0] + 1; i++)
        cnt[f[i]] += sora[i + 1] - sora[i];
    for (int i = 1; i <= n; i++)
        printf("%lld ", cnt[i]);
    return 0;
}

D

考场上想的dp状态非常鬼畜…要不然是记录了能分成几个好数组, 要不然是记录了左右端点, 然后就一直$n ^ 3$凉了

后来翻$Claris$爷爷代码, 发现根本不用记录这玩意23333

f[i]以为第i位为第一个好数组的第一个数, 到n能凑出的好子序列的数量

转移的时候

  • 初始为$f_i = \mathrm C_{n - i}^{a_i}$
  • 转移的时候$f_i += \sum{f_{j + 1} \cdot \mathrm C_{j - i}^{a_i}} \,\,\,\, j \in [i + a_i, n)$, $j$就代表我们枚举的分界限, $f_{j + 1}$代表后面的部分, $\mathrm C_{j - i}^{a_i}$代表在界限之前可以新加入的好子数组, 乘法代表我们可以和后面的任意一个好子序列组成新的好子序列(而且乘法也有去重的作用, 如果$f_{j + 1} =0$的话也不会重复记录$\mathrm C_{j - i}^{a_i}$)

$Claris$ Orz

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define LL long long
#define Refun (998244353ll)
using namespace std;
int n, a[MAXN];
LL f[MAXN], c[MAXN][MAXN];
int main()
{
    c[0][0] = 1;
    for (int i = 1; i < MAXN; i++)
        for (int j = 0; j <= i; j++)
            c[i][j] = (c[i - 1][j] + (j > 0 ? c[i - 1][j - 1] : 0)) % Refun;

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = n - 1; i >= 1; i--)
    {
        if (a[i] <= 0)    continue;
        if (a[i] <= n - i)
            f[i] = c[n - i][a[i]];
        for (int j = i + a[i]; j < n; j++)
            if (a[i] <= j - i)
                f[i] = (f[i] + (f[j + 1] * c[j - i][a[i]]) % Refun) % Refun;
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + f[i]) % Refun;
    printf("%lld", ans);
    return 0;
}

E

简单题, 只要把所有的联通块缩点(或者说只保留桥), 然后跑直径就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <set>
#define MAXN (300000 + 5)
using namespace std;
struct edg
{
    int from, to, next;
}b[MAXN << 1], bn[MAXN << 1];
int g[MAXN], cntb, gn[MAXN], cntn, n, m, belong[MAXN], dfn[MAXN], low[MAXN], cntdfn, f[MAXN];
stack<int> gary;
void tarjan(int dq, int fa)
{
    dfn[dq] = low[dq] = ++cntdfn;
    gary.push(dq);
    for (int i = g[dq]; i; i = b[i].next)
        if (!dfn[b[i].to])
        {
            tarjan(b[i].to, dq);
            low[dq] = min(low[dq], low[b[i].to]);
        }
        else if (b[i].to != fa)
            low[dq] = min(low[dq], dfn[b[i].to]);
    if (low[dq] == dfn[dq])
    {
        while (!gary.empty() && gary.top() != dq)
            belong[gary.top()] = dq, gary.pop();
        if (!gary.empty())
            gary.pop();
        belong[dq] = dq;
    }
}
void adn(edg* bx, int* gx, int& cntx, int from, int to)
{
    bx[++cntx].next = gx[from];
    bx[cntx].from = from, bx[cntx].to = to;
    gx[from] = cntx;
}
void dfs(int dq, int fa)
{
    for (int i = gn[dq]; i; i = bn[i].next)
        if (bn[i].to != fa)
        {
            f[bn[i].to] = f[dq] + 1;
            dfs(bn[i].to, dq);
        }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, srx, sry; i <= m; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(b, g, cntb, srx, sry);
        adn(b, g, cntb, sry, srx);
    }
    tarjan(1, 1);
    set<int> te[MAXN];
    for (int i = 1; i <= n; i++)
        for (int j = g[i]; j; j = b[j].next)
            if (belong[i] != belong[b[j].to] && te[belong[i]].find(belong[b[j].to]) == te[belong[i]].end())
            {
                te[belong[i]].insert(belong[b[j].to]);
                te[belong[b[j].to]].insert(belong[i]);
                adn(bn, gn, cntn, belong[i], belong[b[j].to]);
                adn(bn, gn, cntn, belong[b[j].to], belong[i]);
            }
    dfs(belong[1], belong[1]);
    int ans = 0, ansi;
    for (int i = 1; i <= n; i++)
        if (ans < f[belong[i]])
            ans = f[belong[i]], ansi = belong[i];
    memset(f, 0, sizeof(f));
    dfs(ansi, ansi);
    ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, f[belong[i]]);
    printf("%d", ans);
    return 0;
}

F

要口胡了qwq

我们搞一个nex数组, 把询问按照左端点排序, 然后从左到右扫描

遇到一个数, 我们把他的nex[i]nex[nex[i]]用标记永久化置为a[i], 如果已经有数了, 就撤销后调整边界重新赋值, 让左边界靠左的右边界也靠左, 然后查询的时候就直接在线段树上单点查询就行了

我猜这样是对的23333333

By 沙茶 Cansult