2021牛客OI赛前集训营-提高组（第六场）解题报告

比赛传送

得分：\(100 + 0 + 100 + 40 = 240pts\)

D 挂了 60 /ll

我感觉 B 挺好的，场上根本没想到怎么做/kk

A

观察一下他给的条件。

对于任意一个序列 \(a\)，如果所有的 \(a_i \to a_i + k\)，那么新的序列和原序列一样。

所以任意一个序列都有 \(m-1\) 个序列与之相同。

所以答案为总方案数除以 \(m\)，即 \(m^{n-1}\)。

int Pow(int x, int p) {
    int res = 1;
    while(p) {
        if(p & 1) res = res * x % mod;
        x = x * x % mod, p >>= 1;
    }
    return res;
}

signed main()
{
    T = read();
    while(T--) {
    	n = read(), m = read();
        printf("%lld\n", Pow(m, n) * Pow(m, mod - 2) % mod);
    }
    return 0;
}

B

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"< lim || w2 * d[2][i] > lim) continue;
            for(int b1 = 0; b1 <= b[1]; ++b1) {
                for(int b2 = 0; b2 <= b[2]; ++b2) {
                    if(!w1 && b2 >= c[2][i]) f[i][b1][b2] = min(f[i][b1][b2], max(f[i - 1][b1][b2 - c[2][i]], w2 * u[2][i]));
                    else if(!w2 && b1 >= c[1][i]) f[i][b1][b2] = min(f[i][b1][b2], max(f[i - 1][b1 - c[1][i]][b2], w1 * u[1][i]));
                    else if(b1 >= c[1][i] && b2 >= c[2][i]) f[i][b1][b2] = min(f[i][b1][b2], max(f[i - 1][b1 - c[1][i]][b2 - c[2][i]], max(w1 * u[1][i], w2 * u[2][i])));
                }
            }
        }
    }
    return f[n][b[1]][b[2]];
}

signed main()
{
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	b[1] = read(), b[2] = read();
	for(int i = 1; i <= n; ++i) c[1][i] = read();
	for(int i = 1; i <= n; ++i) c[2][i] = read();
	for(int i = 1; i <= n; ++i) d[1][i] = read();
	for(int i = 1; i <= n; ++i) d[2][i] = read();
	for(int i = 1; i <= n; ++i) u[1][i] = read();
	for(int i = 1; i <= n; ++i) u[2][i] = read();
	int lst = 0, ans = INF;
	while(lst < INF) {
	    int l = lst, r = INF, ansl = Calc(l), res;
	    ans = min(ans, l + ansl);
	    while(l <= r) {
	        int mid = (l + r) >> 1;
	        int ansmid = Calc(mid);
	        if(ansmid == ansl) l = mid + 1, res = mid, ansl = ansmid;
            else r = mid - 1;
        }
        lst = res + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

C

可以发现，如果中间存在一段连续的 \(0\)，我们可以直接算出其插入的位置，然后可插入的区间被分成了两段。

显然可以用 set 去维护所有区间的信息，这样插入操作就能被很好的解决了。

考虑删除操作，可以对每个点维护一个链表，指向它在序列前一个位置的点和后一个位置的点。

有几个特殊的位置，如果可填左端点为 \(1\) 就直接在 \(1\) 填，如果可填右端点是 \(n\) 就直接在 \(n\) 填。

其余的就是一些细节问题了。

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< b.len;
    }
    void Init() {
        int Len = r - l + 1;
        pos = l + Len / 2;
        if(Len % 2 == 0) pos--;
        len = pos - l + 1;
    }
};

struct Node {
    int pre, pos, nxt;
}a[MAXN];

int n, m;
int ans[MAXN];
bool vis[MAXN];
set S;
set::iterator it;
map Map;

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

int main()
{
//    freopen("C.in","r",stdin);
//    freopen("C.out","w",stdout);
    n = read(), m = read();
	S.insert((node){1, n, 1, n});
	it = S.begin();
	a[0].nxt = n + 1, a[m + 1].nxt = 0;
	a[0].pos = 0, a[m + 1].pos = n + 1;
	Map[0] = 0, Map[n + 1] = m + 1;
	for(int i = 1, x; i <= 2 * m; ++i) {
	    x = read();
	    if(!vis[x]) {
	        vis[x] = true;
	        node tmp = *S.begin();
	        S.erase(S.begin());
	        a[x].pos = tmp.pos;
            node res;
            res.l = tmp.l, res.r = a[x].pos - 1;
            if(res.l <= res.r) {
                if(res.l == 1) res.len = res.r, res.pos = 1;
                else res.Init();
                S.insert(res);
            }
            res.l = a[x].pos + 1, res.r = tmp.r;
            if(res.l <= res.r) {
                if(res.r == n) res.len = n - res.l + 1, res.pos = n;
                else res.Init();
                S.insert(res);
            }
            a[x].pre = Map[tmp.l - 1]; 
            a[x].nxt = Map[tmp.r + 1];
            a[a[x].pre].nxt = x;
            a[a[x].nxt].pre = x;
            Map[a[x].pos] = x;
            ans[x] = a[x].pos;
        } else {
            node tmp;
            tmp.l = a[a[x].pre].pos + 1;
            tmp.r = a[a[x].nxt].pos - 1;
            if(tmp.l == 1) {
                tmp.pos = 1;
                tmp.len = tmp.r;
            } else if(tmp.r == n) {
                tmp.pos = n;
                tmp.len = n - tmp.l + 1;
            } else {
                tmp.Init();
            }
            if(tmp.l <= a[x].pos - 1) {
                node res;
                res.l = tmp.l, res.r = a[x].pos - 1;
                res.Init();
                S.erase(*S.find(res));
            }
            if(a[x].pos + 1 <= tmp.r) {
                node res;
                res.l = a[x].pos + 1, res.r = tmp.r;
                res.Init();
                S.erase(*S.find(res));
            } 
            S.insert(tmp);
            a[a[x].pre].nxt = a[x].nxt;
            a[a[x].nxt].pre = a[x].pre;
            a[x].pos = a[x].nxt = a[x].pre = 0;
        }
    }
    for(int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

D

题目保证最小生成树唯一，建出最小生成树来，然后两个点之间的简单路径也是唯一的，所以维护一个树上前缀和，相邻两个点的距离就可以快速算出，经过了多少点也可以算出。实现方式比较多样，当然你不嫌麻烦可以写树剖+线段树。

原题卡了 long long，记得开 __int128

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define int __int128
#define orz cout<<"lkp AK IOI!"<> 1;
        Build(lson, l, mid), Build(rson, mid + 1, r);
        Push_up(i);
    }
    LL Query(LL i, LL l, LL r, LL L, LL R) {
        if(L <= l && r <= R) return sum[i];
        LL mid = (l + r) >> 1, ans = 0;
        if(mid >= L) ans = ans + Query(lson, l, mid, L, R);
        if(mid < R) ans = ans + Query(rson, mid + 1, r, L, R);
        return ans;
    }
}

namespace Cut {
    struct edge {
        LL to, w, nxt;
    }e[MAXN << 1];
    LL head[MAXN], num_edge = 1;
    LL dep[MAXN], siz[MAXN], son[MAXN], Cnt = 0, dfn[MAXN], fath[MAXN], top[MAXN];
    void add_edge(LL from, LL to, LL w) { e[++num_edge] = (edge){to, w, head[from]}, head[from] = num_edge; }
    void dfs(LL u, LL fa) {
        fath[u] = fa, dep[u] = dep[fa] + 1, siz[u] = 1;
        for(LL i = head[u]; i; i = e[i].nxt) {
            LL v = e[i].to;
            if(v == fa) continue;
            val[v] = e[i].w;
            dfs(v, u);
            siz[u] += siz[v];
            if(siz[son[u]] < siz[v]) son[u] = v;
        }
    }
    void dfs2(LL u, LL tp) {
        top[u] = tp, dfn[u] = ++Cnt, pre[Cnt] = u;
        if(son[u]) dfs2(son[u], tp);
        for(LL i = head[u]; i; i= e[i].nxt) {
            LL v = e[i].to;
            if(v == son[u] || v == fath[u]) continue;
            dfs2(v, v);
        }
    }
    LL Get_LCA(LL u, LL v) {
        while(top[u] != top[v]) dep[top[u]] < dep[top[v]] ? v = fath[top[v]] : u = fath[top[u]];
        return dep[u] < dep[v] ? u : v;
    }
    LL Query(LL u, LL v) {
        LL ans = 0;
        while(top[u] != top[v]) {
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            ans = ans + Seg::Query(1, 1, n, dfn[top[u]], dfn[u]);
            u = fath[top[u]];
        }
        if(dep[u] > dep[v]) swap(u, v);
        if(u != v) ans = ans + Seg::Query(1, 1, n, dfn[u] + 1, dfn[v]);
        return ans;
    }
}

LL find(LL x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void Print(int x){
    if(x > 9) Print(x / 10);
    putchar(x % 10 + '0');
}

signed main()
{
	n = read(), m = read();
	for(LL i = 1; i <= m; ++i) b[i].u = read(), b[i].v = read(), b[i].w = read();
    sort(b + 1, b + m + 1);
    for(LL i = 1; i <= n; ++i) fa[i] = i;
    for(LL i = 1, u, v, w; i <= m; ++i) {
        u = b[i].u, v = b[i].v, w = b[i].w;
        LL uf = find(u), vf = find(v);
        if(uf != vf) {
            fa[uf] = vf;
            Cut::add_edge(u, v, w), Cut::add_edge(v, u, w);
        }
    }
    Cut::dfs(1, 0), Cut::dfs2(1, 1), Seg::Build(1, 1, n);
    K = read(), t0 = read();
    for(LL i = 1; i <= K; ++i) a[i] = read();
    for(LL i = 2; i <= K; ++i) {
        LL u = a[i - 1], v = a[i];
        int Dis = Cut::Query(u, v);
        LL lca = Cut::Get_LCA(u, v);
        Dis = Dis + t0 * (Cut::dep[u] + Cut::dep[v] - 2 * Cut::dep[lca]);
        ans = ans + Dis;
    }
    Print(ans - t0);
    return 0;
}
各种比赛

相关

标签