A.9102（待补）

可以参考这篇博客戳我~

B.A Funny Bipartite Graph（状压dp）

题意：

给定一个二分图,左右均有个点，左边的点有个贡献。左边的每个点度数至少为至多为，且左边每个点只会连向右边编号大于等于它的点。现在你要选择一些边，限制如下：

• 右边的每一个点都要被覆盖到；
• 有一个矩阵 ，若则表示左边第个点和第个点不能同时被覆盖到；

对于左边的每一个点，如果它没被覆盖到则代价为，否则代价为，其中表示被它覆盖了多少次。满足上面两条的情况下要使得代价最小。求最小代价，或输出无解。
其中

题解：

观察到的数据范围，那么可以考虑用状压dp。又发现题目中给出左边每个点只会连向右边编号大于等于它的点。那么从左边第一个节点开始依次选择连边，当前选择点的时候，右边编号为的点肯定都被覆盖了，而左边编号为的点肯定都还没选择。那么这两个部分的二进制长度加起来刚好是。
所以从左边第一个节点开始依次选择连边进行状态转移，为选择连边时，的位代表前面选择的左边的点，位表示已经选择了的右边的点。然后枚举点连边情况进行转移即可。
因为下一个的节点状态只需要从上一次的节点状态转移，所以可以用滚动数组进行优化

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = (1 << 18) + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int dp[2][maxn];
int val[20], ban[20];
vector<int> G[20];
char s[20];
int n;
void solve()
{
    //初始化
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        G[i].clear();
        scanf("%s", s);
        for (int j = 0; j < n; j++)
            if (s[j] == '1')
                G[i].push_back(j);
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%s", s);
        ban[i] = 0;
        for (int j = 0; j < i; j++)
            if (s[j] == '1')
                ban[i] |= (1 << j);
    }
    for (int i = 0; i < n; i++)
        scanf("%d", &val[i]);

    //状态转移
    int cur = 0, nxt = 1; //用于滚动数组
    memset(dp, INF, sizeof(dp));
    dp[cur][0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int mask = 0; mask < (1 << n); mask++)
        {
            int lstate = mask & ((1 << i) - 1);        //代表选择的左边节点
            int rstate = mask & ((1 << n) - (1 << i)); //代表已选的右边节点
            if (dp[cur][mask] == INF)                  //如果右边节点的[1,i-1]未被覆盖着直接跳过
                continue;
            if ((rstate) >> i & 1) //如果右边节点i已选则考虑是否不用加入左边节点i
                dp[nxt][mask ^ (1 << i)] = min(dp[nxt][mask ^ (1 << i)], dp[cur][mask]);
            if (ban[i] & lstate) //如果i节点与已选的左边节点冲突则跳过
                continue;
            for (int t = 1; t < (1 << G[i].size()); t++) //依次枚举与左边节点相连的右边节点
            {
                int cost = 1;
                int tmp = 0;
                for (int j = 0; j < G[i].size(); j++)
                {
                    int v = G[i][j];
                    if ((t >> j) & 1)
                    {
                        cost *= val[i];
                        tmp |= (1 << v);
                    }
                }
                int nowstate = rstate | tmp;
                if (!((nowstate >> i) & 1)) //如果没有覆盖到右边节点i则这个选取不行
                    continue;
                dp[nxt][lstate | nowstate] = min(dp[nxt][lstate | nowstate], dp[cur][mask] + cost);
            }
        }
        swap(cur, nxt);
        memset(dp[nxt], INF, sizeof(dp[nxt]));
    }
    int ans = INF;
    for (int i = 0; i < (1 << n); i++)
        ans = min(ans, dp[cur][i]);
    if (ans == INF)
        puts("-1");
    else
        printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.And and Pair（组合数学）

题意：

给定一个二进制表示的n，让你找满足如下要求的数对的个数

题解：

遍历一遍,设从低位到最高位的之间有个，可选择的就是种（为的位置可以选，为的位置为），从低位向高位枚举每个数字，当遇到时，让他做最高位的，设这个的低位中有个和个，简单推导得到有种方案。
要注意这种方法只算了不为的情况，当时也成立，所以结果要加上

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
ll num2[maxn];
ll num3[maxn];
char a[maxn];

int main()
{
    ll t;
    scanf("%lld", &t);
    getchar();
    num2[0] = num3[0] = 1;
    for (int i = 1; i < maxn; i++)
    {
        num2[i] = (num2[i - 1] * 2) % mod;
        num3[i] = (num3[i - 1] * 3) % mod;
    }
    while (t--)
    {
        scanf("%s", a);
        ll len = strlen(a);
        ll y, x;
        y = x = 0;
        ll num = 0;
        for (ll i = len - 1; i >= 0; i--)
        {
            if (a[i] == '1')
            {
                num = (num + (num2[x] * num3[y]) % mod) % mod;
                y++;
            }
            else
                x++;
        }
        num = (num + 1) % mod; 
        printf("%lld\n", num);
    }
    return 0;
}

E.Bob's Problem（最大生成树）

题意：

一张包含个点和条边的图，边分为黑边和白边（为黑边，为白边），每条边有各自的权值，其中黑边任意选，白边只能选条，在保持整张图连通的情况下使得所选变的权值和最大，求最大的权值和

题解：

将所有的黑边都加入，白边按权值排序做一颗最大生成树即可，判断连完后是否是一整个连通块，如果连完仍有剩余则贪心加入权值较大的白边即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
int n, m, k, cnt, fa[maxn];
ll ans;
bool vis[maxn];
struct node
{
    int u, v, w;
    node(int u0 = 0, int v0 = 0, int w0 = 0) : u(u0), v(v0), w(w0) {}
    bool operator<(const node &C) const
    {
        return w > C.w;
    }
};
vector<node> v;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y)
{
    int a = find(x), b = find(y);
    if (a != b)
        fa[a] = b, cnt++;
}
void init()
{
    v.clear();
    ans = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    memset(vis, 0, sizeof(vis));
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d", &n, &m, &k);
        init();
        for (int i = 1; i <= m; i++)
        {
            int x, y, w, c;
            scanf("%d%d%d%d", &x, &y, &w, &c);
            if (!c)
                ans += w, merge(x, y);
            else
                v.push_back(node(x, y, w));
        }
        priority_queue<int> q;
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size() && k; i++)
        {
            int a = find(v[i].u), b = find(v[i].v);
            if (a != b)
            {
                vis[i] = 1;
                cnt++, k--;
                ans += v[i].w;
                fa[a] = b;
            }
        }
        if (cnt != n - 1)
        {
            printf("%d\n", -1);
            continue;
        }
        for (int i = 0; i < v.size() && k; i++)
            if (!vis[i])
                ans += v[i].w, k--;
        printf("%lld\n", ans);
    }
    return 0;
}

G.Eating Plan（思维）

题意：

给出个数和个查询，求最小的区间长度，使得

题解：

要求对每个数的阶乘取模，所以打表可以发现当后，阶乘就为。
那么我们只要求出前个数的阶乘即可，然后统计出每个区间长度所得的最大值与询问比较即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998857459;
ll jc[3005];
int len[maxn];
struct node
{
    int v, pos;
} a[maxn];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    jc[0] = jc[1] = 1;
    for (int i = 2; i <= 2802; i++)
        jc[i] = jc[i - 1] * i % mod;
    int cnt = 0;
    for (int i = 0, x; i < n; i++)
    {
        scanf("%d", &x);
        if (x <= 2802)
        {
            a[cnt].v = jc[x];
            a[cnt++].pos = i;
        }
    }
    for (int i = 0; i < cnt; i++)
    {
        int t = 0;
        for (int j = i; j < cnt; j++)
        {
            t = (t + a[j].v) % mod;
            len[a[j].pos - a[i].pos + 1] = max(len[a[j].pos - a[i].pos + 1], t);
        }
    }
    while (m--)
    {
        int x;
        scanf("%d", &x);
        int ans = -1;
        for (int i = 1; i < maxn; i++)
            if (len[i] >= x)
            {
                ans = i;
                break;
            }
        printf("%d\n", ans);
    }
    return 0;
}

J.Summon（polay定理+矩阵快速幂）

题意：

长度为的环，填四种颜色，有个要求，每个要求限制一个长度为的序列XXXX不许在环中出现，问有多少合法方案。（通过旋转可以变相同的算同一种方案）

题解：

首先根据polay定理：,为方案数，为置换数，为当前置换的循环数量。可以求出无限制的总方案数，但是这道题还有配色限制，所以单单用polay定理还无法解决
考虑置换群。我们知道对于一个置换，循环节数量为，而且第一个元素在第一个循环中，第二个元素在第二个循环中，...，第个元素在第个循环中，而且每个循环中的元素颜色相同。
我们可以用一个矩阵表示两色可以相邻，否则不行。
然后我们可以写一个dp方程，设表示处理到前位最后一位颜色是的答案，转移方程：
因为是一个环，所以还要保证最后一位的颜色和第一位的颜色满足条件，同时每个循环节内的颜色相同，所以我们可以取：
现在考虑四种颜色，对于一个四元组，如果第一位是且后面跟着，那么第二位就不能是且后面跟着。可以原先将中的都拓展为表示一种前三个颜色组成的和后三个颜色组成的方案能否可行。
可知，如果用矩阵表示无向图连通情况的话，次方代表的就是一个点经过次转移,后点到点的方案数
又由于我们要起始元素颜色和终止元素颜色相同，就是求次转移后矩阵对角线为的总和。
方案限制的问题解决以后，因为置换数有种，每个算复杂度太高，考虑到最终所求为，所以可以等价于求的所有约数，对于每个的个数就是

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 1e5 + 5;
int primes[maxn], cnt;
int phi[maxn];
bool v[maxn];
void init(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!v[i])
        {
            primes[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; primes[j] <= n / i; j++)
        {
            v[primes[j] * i] = 1;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            else
                phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}

struct mat
{
    ll a[67][67];
} base, pbase[25];

mat mul(mat a, mat b)
{
    mat res;
    memset(res.a, 0, sizeof res.a);
    for (int i = 0; i < 64; i++)
        for (int j = 0; j < 64; j++)
            for (int k = 0; k < 64; k++)
                res.a[i][j] = (res.a[i][j] % mod + a.a[i][k] % mod * b.a[k][j] % mod) % mod;
    return res;
}

ll ksm(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res % mod;
}

mat qmi(int b)
{
    mat res;
    memset(res.a, 0, sizeof res.a);
    for (int i = 0; i < 64; i++)
        res.a[i][i] = 1;
    int t = 0;
    while (b)
    {
        if (b & 1)
            res = mul(res, pbase[t]);
        b >>= 1;
        t++;
    }
    return res;
}

int main()
{
    init(maxn - 3);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < 64; i++)
        for (int k = 0; k < 4; k++)
        {
            int nxt = (i * 4 + k) % 64;
            base.a[i][nxt] = 1;
        }
    while (m--)
    {
        int x = 0, t;
        for (int i = 0; i < 4; i++)
        {
            scanf("%d", &t);
            x = x * 4 + t;
        }
        base.a[x / 4][x % 64] = 0;
    }
    pbase[0] = base;
    for (int i = 1; i < 20; i++)
        pbase[i] = mul(pbase[i - 1], pbase[i - 1]);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (n % i)
            continue;
        mat tt = qmi(i);
        ll t = 0;
        for (int j = 0; j < 64; j++)
            t = (t + tt.a[j][j]) % mod;
        t = t * phi[n / i] % mod;
        ans = (ans + t) % mod;
    }
    ans = ans % mod * ksm(n, mod - 2) % mod;
    cout << ans << endl;
    return 0;
}

K.Tree（dsu on tree + 权值线段树）

题意：

求有个点且以为根的有根树上，其中每个节点有一个权值，求满足下面条件的有序点对数目

1. 一个点不为另一个点的祖先
2. 
3. 到的路径长度小于等于给定的值

其中
和算两种方案

题解：

因为要满足一个点不为另一个点的祖先，那么可以想到如果将作为根节点的话，那么和恰好位于两棵不同的子树，且满足和。可以考虑用dsu on tree来实现，其中可以用一棵权值线段树来维护不同的，这样可以实现，到的路径长度小于等于给定的值就是找权值为那棵线段树中深度为的值，其中。
dsu on tree部分就是套板子，对dsu on tree不是很了解可以参考我这篇博客的E题，算是这题的弱化版。戳我~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll ans;
int n, k, a[maxn];
struct E
{
    int to, next;
} Edge[maxn << 1];
int tot, head[maxn];
void init()
{
    memset(head, -1, sizeof(head));
    tot = ans = 0;
}
void addedge(int u, int v)
{
    Edge[tot].to = v;
    Edge[tot].next = head[u];
    head[u] = tot++;
}
int siz[maxn], son[maxn], dep[maxn];
void dfs(int u)
{
    siz[u] = 1;
    son[u] = 0;
    for (int i = head[u]; ~i; i = Edge[i].next)
    {
        int v = Edge[i].to;
        dep[v] = dep[u] + 1;
        dfs(v);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]])
            son[u] = v;
    }
}
int T[maxn], lson[maxn * 200], rson[maxn * 200], idx = 0, sum[maxn * 200];
void update(int &rt, int l, int r, int pos, int val)
{
    if (!rt) rt = ++idx;
    sum[rt] += val;
    if (l == r) return;
    int mid = l + r >> 1;
    if (pos <= mid) update(lson[rt], l, mid, pos, val);
    else update(rson[rt], mid + 1, r, pos, val);
}
int query(int rt, int l, int r, int L, int R)
{
    if (!rt) return 0;
    if (L <= l && r <= R) return sum[rt];
    int res = 0;
    int mid = l + r >> 1;
    if (L <= mid) res += query(lson[rt], l, mid, L, R);
    if (R > mid) res += query(rson[rt], mid + 1, r, L, R);
    return res;
}
int flag; //flag用于标记重儿子
void cal(int u, int val)
{
    update(T[a[u]], 1, n, dep[u], val);
    for (int i = head[u]; ~i; i = Edge[i].next)
    {
        int v = Edge[i].to;
        cal(v, val);
    }
}
void query(int u, int lca)
{
    int d = k + dep[lca] * 2 - dep[u];
    d = min(d, n);
    int t = 2 * a[lca] - a[u];
    if (d >= 1 && t >= 0 && t <= n) ans += 2ll * query(T[t], 1, n, 1, d);
    for (int i = head[u]; ~i; i = Edge[i].next)
    {
        int v = Edge[i].to;
        query(v, lca);
    }
}
//dsu on tree板子
void dfs(int u, bool keep)
{
    //第一步，搞轻儿子及其子树算答案删贡献
    for (int i = head[u]; ~i; i = Edge[i].next)
    {
        int v = Edge[i].to;
        if (v == son[u]) continue;
        dfs(v, false);
    }
    //第二步，搞重儿子及其子树算答案不删贡献
    if (son[u])
    {
        dfs(son[u], true);
        flag = son[u];
    }
    //第三步，暴力统计u及其所有轻儿子的贡献合并道刚算出的重儿子信息里
    for (int i = head[u]; ~i; i = Edge[i].next)
    {
        int v = Edge[i].to;
        if (v == flag) continue;
        query(v, u);
        cal(v, 1);
    }
    update(T[a[u]], 1, n, dep[u], 1);
    flag = 0;
    //把需要删除贡献的删一删
    if (!keep) cal(u, -1);
}
int main()
{
    init();
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 2, u; i <= n; i++)
    {
        scanf("%d", &u);
        addedge(u, i);
    }
    dep[1] = 1;
    dfs(1);
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}

L.Who is the Champion（签到）

题意：

有个球队，给出的矩阵第行第列表示第个球队和第个球队踢球进球的个数。两个球队pk，赢的球队加分，输的球队不加分。平局各加分。规定分数最多的球队为冠军，如果有多个分数最多的，按每个队赢球数-失球数最高的，如果仍有多个，输出。否则输出第几个球队是冠军

题解：

按题意模拟即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 105;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n, a[maxn][maxn];
struct node
{
    int s, g, id;
    bool operator<(const node &C) const
    {
        if (s == C.s)
            return g > C.g;
        return s > C.s;
    }
} p[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    if (n == 1)
    {
        printf("%d\n", 1);
        return 0;
    }
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++)
    {
        p[i].id = i;
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            p[i].g += a[i][j];
            if (a[i][j] > a[j][i])
                p[i].s += 3;
            else if (a[i][j] == a[j][i])
                p[i].s += 1;
            p[i].g -= a[j][i];
        }
    }
    sort(p + 1, p + n + 1);
    if (p[1].s == p[2].s && p[1].g == p[2].g)
        puts("play-offs");
    else
        printf("%d\n", p[1].id);
    return 0;
}

终榜