B.Prefix Code(字典树)

题意：给出一系列数字，长度均小于，问是否有一个数是其他数的前缀？

题解：Trie树模板题。记录单词的终末，前缀包含的单词个数即可。若一个点是单词终末且前缀包含单词个数，则输出No。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int T[maxn][12];
int num[maxn];
int isend[maxn];
int tot=1;
void init()
{
    for(int i=0;i<=tot;i++)
    {
        memset(T[i],0,sizeof(T[i]));
        num[i]=isend[i]=0;
    }
    tot=1;
}
void add(char * s)
{
    int l=strlen(s+1);
    int rt=1;
    for(int i=1;i<=l;i++)
    {
        if(T[rt][s[i]-'0']==0)
        {
            T[rt][s[i]-'0']=++tot;
            rt=tot;
        }
        else 
            rt=T[rt][s[i]-'0'];
        num[rt]++;
    }
    isend[rt]=1;
}
char s[15];
int main()
{
    int t;
    int caseN=0;
    scanf("%d",&t);
    while(t--)
    {
        init();
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s+1);
            add(s);
        }
        int flag=1;
        for(int i=1;i<=tot;i++)
        {
            if(isend[i]&&num[i]>1)
            {
                flag=0;
                break;
            }
        }
        if(flag)printf("Case #%d: Yes\n",++caseN);
        else printf("Case #%d: No\n",++caseN);
    }
}

D.Spanning Tree Removal（构造）

题意：给定一个阶的完全图，每次操作是从图中移除一棵生成树的所有边，问最多能进行多少次这样的操作？输出操作次数和每次移除的生成树的边。

题解：阶完全图共有条边，一棵生成树有条边，很容易猜到能进行次操作，接下来就是如何构造的问题。类似于双指针，一个在，另一个为，连接连接

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    int caseN=0;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int k=n/2;
        printf("Case #%d: %d\n",++caseN,k);
        for (int i = 1; i <= k; ++i){
            for (int j = i+1; j <= i + k; ++j) printf("%d %d\n",i,j);
            for (int j = 1; j <= n-k-1; ++j) printf("%d %d\n",i+k,(i+k+j) % n == 0 ? n : (i + k + j) % n );
        }
    }
    return 0;
}

E.Cave Escape（生成树）

题意：给定一个的格子矩阵，其中有一个格子是起点，一个格子是终点。从起点开始移动，每次能移动到有相邻边的格子中，每个格子都有一个权值,若从点移动到点，且点未被访问过，则可以获得的收益，若移动到终点，可以选择先不出去，继续在图上乱走，问如何可以使得走出终点后获得得收益最大？(只需要输出最大收益即可)

题解：不管起点在哪里，因为权值都为正数，我们要让收益最大，肯定尽量每个点都访问一遍，然后才是最大的值，所以我们可以直接建图，然后跑一遍生成树(最大),因为要让每个点访问一次。正解的话存图是把权值作为索引，然后从大到小一次枚举；一般的做法可以卡过去。

正解（运行时间： 893 ms 占用内存：186444K）：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> pii;
int val[maxn][maxn], fa[maxn * maxn], x[maxn * maxn];
int cnt, n, m;
struct Edge
{
    int u, v, w;
    bool operator<(const Edge &C) const
    {
        return w > C.w;
    }
} E[2 * maxn * maxn];
int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
ll kruskal()
{
    ll ans = 0;
    int tot = 0;
    for (int i = 0; i < cnt; i++)
    {
        int u = E[i].u;
        int v = E[i].v;
        int w = E[i].w;
        int a = find(u);
        int b = find(v);
        if (a != b)
        {
            fa[b] = a;
            ans += w;
            tot++;
        }
        if (tot == n * m - 1)
            break;
    }
    return ans;
}
int main()
{
    int t;
    int caseN = 0;
    scanf("%d", &t);
    while (t--)
    {
        int s, a, b, c, p;
        scanf("%d%d%d%d%d%d", &n, &m, &s, &s, &s, &s);
        scanf("%d%d%d%d%d%d", &x[1], &x[2], &a, &b, &c, &p);
        fa[1] = 1;
        fa[2] = 2;
        for (int i = 3; i <= n * m; i++)
        {
            fa[i] = i;
            x[i] = (a * x[i - 1] + b * x[i - 2] + c) % p;
        }
        cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                val[i][j] = x[(i - 1) * m + j];
                if (!val[i][j])
                    continue;
                if (i > 1 && val[i - 1][j])
                    E[cnt++] = Edge{(i - 1) * m + j, (i - 2) * m + j, val[i][j] * val[i - 1][j]};
                if (j > 1 && val[i][j - 1])
                    E[cnt++] = Edge{(i - 1) * m + j, (i - 1) * m + j - 1, val[i][j] * val[i][j - 1]};
            }
        }
        sort(E, E + cnt);
        printf("Case #%d: %lld\n", ++caseN, kruskal());
    }
    return 0;
}

一般做法（运行时间： 1731 ms 占用内存：36156K）：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> pii;
int val[maxn][maxn], fa[maxn * maxn], x[maxn * maxn];
vector<pair<int, int>> V[10005];
int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main()
{
    int t;
    int caseN = 0;
    scanf("%d", &t);
    while (t--)
    {
        for (int i = 0; i <= 10000; i++)
            V[i].clear();
        int n, m, s, a, b, c, p;
        scanf("%d%d%d%d%d%d", &n, &m, &s, &s, &s, &s);
        scanf("%d%d%d%d%d%d", &x[1], &x[2], &a, &b, &c, &p);
        fa[1] = 1;
        fa[2] = 2;
        for (int i = 3; i <= n * m; i++)
        {
            fa[i] = i;
            x[i] = (a * x[i - 1] + b * x[i - 2] + c) % p;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                val[i][j] = x[(i - 1) * m + j];
                if (!val[i][j])
                    continue;
                if (i > 1 && val[i - 1][j])
                    V[val[i][j] * val[i - 1][j]].push_back(make_pair((i - 1) * m + j, (i - 2) * m + j));
                if (j > 1 && val[i][j - 1])
                    V[val[i][j] * val[i][j - 1]].push_back(make_pair((i - 1) * m + j, (i - 1) * m + j - 1));
            }
        }
        ll res = 0;
        int tot = 0;
        for (int i = 10000; i >= 0; i--)
        {
            for (auto j : V[i])
            {
                int u = j.first;
                int v = j.second;
                int a = find(u);
                int b = find(v);
                if (a != b)
                {
                    fa[b] = a;
                    res += 1ll * i;
                    tot++;
                }
                if (tot == n * m - 1)
                    break;
            }
            if (tot == n * m - 1)
                break;
        }
        printf("Case #%d: %lld\n", ++caseN, res);
    }
    return 0;
}

F.A Simple Problem On A Tree（树剖）

可以参考这一篇博客地址

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, a[maxn];
vector<int> g[maxn];
int f[maxn], dep[maxn], son[maxn], sz[maxn];
int top[maxn], id[maxn];
ll w[maxn];
ll mul[maxn << 2], add[maxn << 2];
ll sum1[maxn << 2], sum2[maxn << 2], sum3[maxn << 2];
int dfn;
void init()
{
    dfn = 0;
    for (int i = 0; i <= n; i++)
    {
        son[i] = 0;
        g[i].clear();
    }
}
void dfs1(int u, int fa)
{
    f[u] = fa;
    dep[u] = dep[fa] + 1;
    sz[u] = 1;
    for (auto v : g[u])
    {
        if (v == fa)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v])
            son[u] = v;
    }
}
void dfs2(int u, int tp)
{
    top[u] = tp;
    id[u] = ++dfn;
    w[dfn] = a[u];
    if (son[u])
        dfs2(son[u], tp);
    for (auto v : g[u])
    {
        if (v == f[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}
void solve(int rt, ll x, ll y, int len)
{
    if (x != 1)
    {
        ll x2 = x * x % mod;
        ll x3 = x2 * x % mod;

        sum1[rt] = sum1[rt] * x % mod;
        sum2[rt] = sum2[rt] * x2 % mod;
        sum3[rt] = sum3[rt] * x3 % mod;

        mul[rt] = mul[rt] * x % mod;
        add[rt] = add[rt] * x % mod;
    }
    if (y != 0)
    {
        ll y2 = y * y % mod;
        ll y3 = y2 * y % mod;

        sum3[rt] = (sum3[rt] + 1ll * len * y3 % mod) % mod;
        sum3[rt] = (sum3[rt] + 3ll * y * sum2[rt] % mod) % mod;
        sum3[rt] = (sum3[rt] + 3ll * y2 * sum1[rt] % mod) % mod;

        sum2[rt] = (sum2[rt] + 1ll * len * y2 % mod) % mod;
        sum2[rt] = (sum2[rt] + 2ll * y * sum1[rt] % mod) % mod;

        sum1[rt] = (sum1[rt] + 1ll * len * y % mod) % mod;

        add[rt] = (add[rt] + y) % mod;
    }
}
void pushup(int rt)
{
    sum1[rt] = (sum1[rt << 1] + sum1[rt << 1 | 1]) % mod;
    sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % mod;
    sum3[rt] = (sum3[rt << 1] + sum3[rt << 1 | 1]) % mod;
}
void pushdown(int rt, int len)
{
    solve(rt << 1, mul[rt], add[rt], len - (len >> 1));
    solve(rt << 1 | 1, mul[rt], add[rt], len >> 1);
    mul[rt] = 1;
    add[rt] = 0;
}
void build(int l, int r, int rt)
{
    mul[rt] = 1;
    add[rt] = 0;
    if (l == r)
    {
        sum1[rt] = w[l] % mod;
        sum2[rt] = w[l] * w[l] % mod;
        sum3[rt] = w[l] * w[l] % mod * w[l] % mod;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update(int rt, int L, int R, int l, int r, int x, int y)
{
    if (L <= l && r <= R)
    {
        solve(rt, x, y, r - l + 1);
        return;
    }
    pushdown(rt, r - l + 1);
    int mid = l + r >> 1;
    if (L <= mid)
        update(rt << 1, L, R, l, mid, x, y);
    if (mid < R)
        update(rt << 1 | 1, L, R, mid + 1, r, x, y);
    pushup(rt);
}
ll query(int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
        return sum3[rt] % mod;
    pushdown(rt, r - l + 1);
    int mid = l + r >> 1;
    ll res = 0;
    if (L <= mid)
        res = (res + query(rt << 1, l, mid, L, R)) % mod;
    if (mid < R)
        res = (res + query(rt << 1 | 1, mid + 1, r, L, R)) % mod;
    pushup(rt);
    return res;
}
void updRange(int u, int v, int x, int y)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        update(1, id[top[u]], id[u], 1, n, x, y);
        u = f[top[u]];
    }
    if (dep[u] > dep[v])
        swap(u, v);
    update(1, id[u], id[v], 1, n, x, y);
}
ll qRange(int u, int v)
{
    ll res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        res = (res + query(1, 1, n, id[top[u]], id[u])) % mod;
        u = f[top[u]];
    }
    if (dep[u] > dep[v])
        swap(u, v);
    res = (res + query(1, 1, n, id[u], id[v])) % mod;
    return res;
}
int main()
{
    int t;
    int caseN = 0;
    scanf("%d", &t);
    while (t--)
    {
        printf("Case #%d:\n", ++caseN);
        scanf("%d", &n);
        init();
        for (int i = 1; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        dfs1(1, 0);
        dfs2(1, 1);
        build(1, n, 1);
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
        {
            int op, u, v, w;
            scanf("%d%d%d", &op, &u, &v);
            if (op == 1)
            {
                scanf("%d", &w);
                updRange(u, v, 0, w);
            }
            else if (op == 2)
            {
                scanf("%d", &w);
                updRange(u, v, 1, w);
            }
            else if (op == 3)
            {
                scanf("%d", &w);
                updRange(u, v, w, 0);
            }
            else if (op == 4)
                printf("%lld\n", qRange(u, v));
        }
    }
    return 0;
}

H.Tree Partition（二分+贪心）

题意：给出一棵点权树，一个树的大小定义为所有点的权值和。问将一棵树切次分为棵子树，如何分割才能使所有树的大小的最大值最小，求出最小值？

题解：首先权值最大的块，最小。我们可以想到二分。然后看是否能够满足。我们对于每个点，假设子树都是小于当前二分的值mid，对于当前点，如果把全部子树加上都是合法的，那么肯定直接加上即可。如果全部加上不合法，肯定就需要丢弃一些子树。肯定贪心丢掉最大的子树，直到合法。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
typedef long long ll;
typedef pair<int, int> pii;
struct Edge
{
    int v, next;
} E[maxn];
int head[maxn], tot;
int n, k, flag, cnt;
ll w[maxn], sum[maxn];
void addedge(int u, int v)
{
    E[tot].v = v;
    E[tot].next = head[u];
    head[u] = tot++;
}
void init()
{
    fill(head, head + n + 1, -1);
    fill(sum, sum + n + 1, 0);
    tot = 0;
}
void dfs(int u, int fa, ll x)
{
    sum[u] = w[u];
    if (sum[u] > x || flag == 0)
    {
        flag = 0;
        return;
    }
    for (int i = head[u]; ~i; i = E[i].next)
    {
        int v = E[i].v;
        if (v == fa)
            continue;
        dfs(v, u, x);
        sum[u] += sum[v];
    }
    if (sum[u] > x)
    {
        vector<ll> V;
        for (int i = head[u]; ~i; i = E[i].next)
        {
            int v = E[i].v;
            if (v == fa)
                continue;
            V.push_back(sum[v]);
        }
        sort(V.begin(), V.end());
        while (sum[u] > x)
        {
            cnt++;
            sum[u] -= V.back();
            V.pop_back();
        }
    }
    if (cnt > k - 1)
    {
        flag = 0;
        return;
    }
}
bool check(ll x)
{
    flag = 1;
    cnt = 0;
    dfs(1, 0, x);
    return flag;
}
int main()
{
    int t;
    int caseN = 0;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &k);
        init();
        for (int i = 1; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }
        for (int i = 1; i <= n; i++)
            scanf("%lld", &w[i]);
        ll l = 0, r = 1e14 + 5ll;
        while (l < r)
        {
            ll mid = (l + r) >> 1ll;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        printf("Case #%d: %lld\n", ++caseN, l);
    }
    return 0;
}

K.Color Graph（二分图+枚举）

题意：给定一个简单图，点个数，删去部分边后，使得该图中无边数为奇数得环，问剩下的边数最大为多少？

题解：如果一个图中无奇数边的环，那么这个图一定是个二分图。只要枚举二分图的左部，统计所有从左部到右部的边个数，答案就是枚举出的所有边数的最大值。(因为最优解一定也是一个二分图，所以一定会被枚举到)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef pair<int,int> edge;
vector<edge>G;
bool flag[20];
int main()
{
    int t;
    int caseN=0;
    scanf("%d",&t);
    while(t--)
    {
        G.clear();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G.push_back({u,v});
        }
        int ans=0;
        for(int i=0;i<(1<<n);i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i&1<<j-1)
                    flag[j]=1;
                else flag[j]=0;
            }
            int tmp=0;
            for(auto i:G)
                if(flag[i.first]^flag[i.second])
                    tmp++;
            ans=max(ans,tmp);
        }
        printf("Case #%d: %d\n",++caseN,ans);
    }
}

终榜