A.Portal

题意：

给定一个 $n$ 个点 $m$ 条边的带权图。一开始在 $1$ 号点，要按顺序完成 $k$ 个任务，第 $i$ 个任务是先去 $a_i$ 再走到 $b_i$ 。当走到一个点上的时候，可以在这个点创建一个传送门。当同时存在两个传送门的时候，可以在传送门之间不耗代价地传送。如果已经存在了两个传送门，想再创建一个，就必须选择之前的一个传送门关掉（关掉这个操作不耗时间，并且是远程操作，不需要走过去）。问完成所有任务的最短总行走距离。

题解：

设 $f[i][p]$ 表示当前已经完成了前 $i$ 个任务，当前正在 $c[i]$ 上，传送门的位置在 $p$ 。
可以证明，只需要3种转移，就可以覆盖所有情况：

直接从 $c[i]$ 走到 $c[i+1]$
枚举走到 $c[i+1]$ 之后，传送门的位置变为了哪个节点，设这个节点是 $q$ 。从 $c[i]$ 走到 $q$ ，在 $q$ 设置传送门，从 $q$ 传送到 $p$ ，再从 $p$ 走到 $c[i+1]$
从 $c[i]$ 传送到 $p$ ，从 $p$ 走到 $q$ ，在 $q$ 设置传送门，最后从 $q$ 走到 $c[i+1]$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 305;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
ll f[maxn * 2][maxn], d[maxn][maxn];
int a[maxn * 2];
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    memset(d, 0x3f, sizeof(d));
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++)
        d[i][i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        ll w;
        scanf("%d%d%lld", &u, &v, &w);
        d[u][v] = d[v][u] = min(d[u][v], w);
    }
    a[1] = 1;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[2 * i], &a[2 * i + 1]);
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++)
        f[1][i] = d[1][i];
    for (int i = 2; i <= 2 * k + 1; i++)
        for (int p = 1; p <= n; p++)
        {
            f[i][p] = min(f[i][p], f[i - 1][p] + d[a[i]][a[i - 1]]);
            for (int q = 1; q <= n; q++)
            {
                f[i][q] = min(f[i][q], f[i - 1][p] + d[a[i - 1]][q] + d[p][a[i]]);
                f[i][q] = min(f[i][q], f[i - 1][p] + d[p][q] + d[q][a[i]]);
            }
        }
    ll ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, f[2 * k + 1][i]);
    printf("%lld\n", ans);
}

B.Graph

题意：

给一棵 $n$ 个节点的树，每条边有边权。可以任意加边和删边，但要满足任何时刻图连通，而且任何一个环的边权异或和为 $0$ 。求操作后最小权值和。

题解：

可以发现任意两个点之间连边的权值都是固定的。由于图始终联通，所以两点间始终存在至少一条路径，如果存在多条，根据环的异或和为0，两点间的路径的异或和应该相等，且始终是固定的。可以通过给定一个根节点权值为 $0$ ，其余点通过和边权异或得到一个点权，任意两个点的边权就是两个点权异或的值。因此问题就转化为已知一个 $n$ 个节点的完全图，要求一棵权值之和最小的树。就是求最小生成树，或者叫异或最小生成树，考虑到是完全图，可以想到是 $boruvka$ 算法。根据 $boruvka$ 的思想找最小生成树，很自然得想到把所有点分为最高位为 $0$ 和 $1$ 的堆，其中找一条权值最小的边连接两堆，其余的点都在同一堆内找一条边连接，这个可以用字典树来维护

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int maxp = maxn * 32;
int head[maxn], tot = 1;
int a[maxn];
ll ans;
struct Edge
{
    int to, nxt, w;
} e[maxn << 1];
void add(int u, int v, int w)
{
    e[++tot].to = v;
    e[tot].nxt = head[u];
    e[tot].w = w;
    head[u] = tot;
}
struct trie
{
    int son[maxp][2];
    int root, tot;
    void init()
    {
        for (int i = 0; i <= tot; i++)
            son[i][0] = son[i][1] = 0;
        root = tot = 1;
    }
    void insert(int w)
    {
        int x = root;
        for (int i = 29; i >= 0; i--)
        {
            int &y = son[x][w >> i & 1];
            if (!y)
                y = ++tot;
            x = y;
        }
    }
    int findx(int w)
    {
        int x = root, ec = 0;
        for (int j = 29; j >= 0; j--)
        {
            int k = w >> j & 1;
            if (son[x][k])
                x = son[x][k];
            else
                x = son[x][!k], ec |= 1 << j;
        }
        return ec;
    }
} tr;
void dfs(int id, int l, int r)
{

    if (id < 0)
        return;
    int mid = l - 1;
    for (int i = l; i <= r; i++)
        if (((a[i] >> id) & 1) == 0)
            mid = i;
    if (l <= mid)
        dfs(id - 1, l, mid);
    if (mid + 1 <= r)
        dfs(id - 1, mid + 1, r);
    if (l <= mid && mid + 1 <= r)
    {
        for (int i = l; i <= mid; i++)
            tr.insert(a[i]);
        int mi = 2e9;
        for (int i = mid + 1; i <= r; i++)
            mi = min(mi, tr.findx(a[i]));
        ans += mi;
    }
    tr.init();
}
void dfs(int x, int fat)
{
    for (int i = head[x]; i; i = e[i].nxt)
    {
        int y = e[i].to, w = e[i].w;
        if (y == fat)
            continue;
        a[y] = a[x] ^ w;
        dfs(y, x);
    }
}
int main()
{
    int n, u, v, w;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        u++;
        v++;
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1, 0);
    sort(a + 1, a + 1 + n);
    dfs(29, 1, n);
    printf("%lld\n", ans);
    return 0;
}

C.Easy

题意：

有两个长度为 $k$ 的正整数序列 $A$ ， $B$ 满足 $\sum_{i=1}^{k}{a_i}=N,\sum_{i=1}^{k}{b_i}=M$
求 $P=\sum_{i=1}^{k}{min(a_i,b_i)}$ 的数量

题解：

这题看题解也没看懂，找了一篇现在也没搞懂，先贴出来把戳我~

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e6+5;
const ll mod = 998244353;
ll qpow(ll a, ll b){
    ll res = 1;
    a %= mod;
    while(b) {
        if(b & 1) {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}
ll fac[maxn], inv[maxn];
void init() {
    fac[0] = 1;
    for(int i = 1; i < maxn; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
    for(int i = maxn - 2; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll c(ll n, ll m) {
    if(m > n) {
        return 0;
    }
    if(m == 0) return 1;
    if(n < maxn) return fac[n] * inv[m] % mod * inv[n - m] % mod;
    ll res = inv[m];
    for(int i = n - m + 1; i <= n; i++) {
        res = res * i % mod;
    }
    return res;
}
int main()
{
    init();
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        if (n > m)
            swap(n, m);
        ll res = 0;
        for (int i = 0; i <= n - k; i++)
            res = ((ll)res + c(k + i - 1, i) * c(k + n - k - i - 1, n - k - i) % mod * c(k + m - k - i - 1, m - k - i) % mod) % mod;
        printf("%lld\n", res);
    }
}

D.Drop Voicing

题意：

给定一个 $1 \sim n$ 的排列，有两种操作

可以将倒数第二个数放到开头
可以将开头的第一个数放到最后

续若干次操作 $1$ （包括1次）称为一段。现在要将排列变成 $1 \sim n$ ，要使得段数尽可能少，输出这个最小值。

题解：

相当于看成一个环，连续若干次操作 $1$ 等价为改变指针指向的数所处的位置，连续若干次操作 $2$ 等价为改变指针的位置。因此可以在环上找到一个最长上升序列，这个序列的数不需要改变，其余的改变，可以发现这个是最优的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 505;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int a[maxn << 1], d[maxn];
int LIS(int *a, int n)
{
    for (int i = 1; i <= n; i++)
        d[i] = 0;
    int lis = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > d[lis])
            d[++lis] = a[i];
        else
            *lower_bound(d, d + lis, a[i]) = a[i];
    }
    return lis;
}
int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), a[i + n] = a[i];
    for (int i = 0; i < n; i++)
    {
        int len = LIS(a + i, n);
        ans = max(len, ans);
    }
    printf("%d\n", n - ans);
    return 0;
}

E.Bogo Sort

题意：

给定置换，求有多少排列可以通过这个置换变成顺序。

题解：

首先可以确定整个给定的排列可以组成若干个独立的环。观察可以发现答案就为这些环长度的 $lcm$

from math import gcd
n=int(input())
p=[]
p=list(map(int,input().split()))
p.insert(0,0)
vis=[(False) for i in range(n+10)]
v=[]
for i in range(1,n+1):
    if vis[i]==True:
        continue
    vis[i]=True
    tmp=p[i]
    ans=1
    while tmp!=i:
        vis[tmp]=True
        tmp=p[tmp]
        ans+=1
    v.append(ans)
v.sort(reverse=True)
res=v[0]
for i in v[1:]:
    res=res*i//gcd(res,i)
res%=10**n
print(res)

F.DPS

题意：

模拟显示游戏中的伤害数据。

题解：

签到题，模拟即可

#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
int a[maxn];
typedef long long ll;
int main(){
    int n;
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mx=max(a[i],mx);
    }
    for(int i=1;i<=n;i++){
        ll ans=(1ll*50*a[i]+mx-1)/mx;
        cout<<"+";
        for(int j=1;j<=ans;j++)cout<<"-";
        cout<<"+\n";
        cout<<"|";
        for(int j=1;j<ans;j++)cout<<" ";
        if(mx==a[i])cout<<"*";
        else if(a[i]!=0)cout<<" ";
        cout<<"|"<<a[i]<<"\n";
        cout<<"+";
        for(int j=1;j<=ans;j++)cout<<"-";
        cout<<"+\n";
    }
    return 0;
}

H.Interval

题意：

给定 $n$ 个数 $A_i$ ，定义 $F(l,r)=A_{l} \& A_{l+1} \& \dots \& A_{r}$
$S(l,r) = {F(a,b) | min(l,r) \leq a \leq b \leq max(l,r)}$ 。
给定 $q$ 个询问，每个询问包含一个 $L'$ 和 $R'$ ， $L=(L' \oplus last) \% N +1,R=(R' \oplus last) \% N +1$ ，其中 $last$ 为上一次询问的结果,要求求出对应的 $S(L,R)$ 的集合个数

题解：

考虑到答案异或，并且 $0 \leq A_{i} \leq 2^{30}$ ，因此对应每个固定的右端点，他的 $F$ 值至多为 $30$ 个，因此可以固定右端点来统计左端点即可，二维偏序，对每个右端点的结果用主席树来维护，对于左端点的就是 $[L,R]$ 的区间的结果。要注意的是因为用主席树每次会继承上一棵树的结果，所以对于同一个值可能会重复，因此只需要每次记录每个值出现的最新的坐标记录下来，每次更新都令最近位置的坐标 $-1$ ，当前位置的值 $+1$ 即可，具体实现见代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
typedef pair<int, int> pii;

struct Node
{
    int l, r, val;
} T[maxn << 5];
int tot, rt[maxn];

void update(int &p, int l, int r, int pos, int val)
{
    T[++tot] = T[p], p = tot, T[p].val += val;
    if (l == r)
        return;
    int mid = l + r >> 1;
    if (pos <= mid)
        update(T[p].l, l, mid, pos, val);
    else
        update(T[p].r, mid + 1, r, pos, val);
}
int query(int p, int l, int r, int L, int R)
{
    if (l > R || L > r)
        return 0;
    if (L <= l && r <= R)
        return T[p].val;
    int mid = l + r >> 1;
    return query(T[p].l, l, mid, L, R) + query(T[p].r, mid + 1, r, L, R);
}

int main()
{
    map<int, int> now, mp;
    int n;
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++)
    {
        map<int, int> tmp;
        scanf("%d", &x);
        now[(1 << 30) - 1] = i;
        for (auto p : now)
        {
            int k = p.first & x;
            tmp[k] = max(tmp[k], p.second);
        }
        rt[i] = rt[i - 1];
        for (auto p : tmp)
        {
            if (mp.count(p.first))
                update(rt[i], 1, n, mp[p.first], -1);
            mp[p.first] = p.second;
            update(rt[i], 1, n, p.second, 1);
        }
        swap(tmp, now);
    }
    int q, last = 0, l, r;
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d", &l, &r);
        l = (l ^ last) % n + 1;
        r = (r ^ last) % n + 1;
        if (l > r)
            swap(l, r);
        last = query(rt[r], 1, n, l, r);
        printf("%d\n", last);
    }
    return 0;
}

I.Hard Math Problem

题意：

有一个无穷大的二维网格，每个格子可以是 $1、2、3$ ，每个 $1$ 旁边要有一个 $2和$ 3$，要使机器的占比最大。

题解：

发现 $(i+j) \%3 =0$ 交错 $2$ 和 $3$ 是最优的，此时答案为 $\frac{2}{3}$

#include <bits/stdc++.h>
using namespace  std;
const int maxn=1e7+10;
bool prime[maxn];
int mp[maxn],res[maxn][3];
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int main()
{
    printf("%.6lf\n",2.0/3);
    return 0;
}

2020牛客暑期多校训练营（第五场）