2019 ICPC 上海区域赛总结

2019上海区域赛现场赛总结

补题情况（以下通过率为牛客提交）：

题号	标题	已通过代码	通过率	我的状态
A	Mr. Panda and Dominoes	点击查看	5/29	未通过
B	Prefix Code	点击查看	249/1019	通过
C	Maze	点击查看	8/110	未通过
D	Spanning Tree Removal	点击查看	88/211	通过
E	Cave Escape	点击查看	53/553	通过
F	A Simple Problem On A Tree	点击查看	66/290	通过
G	Play the game SET	点击查看	2/35	未通过
H	Tree Partition	点击查看	73/175	通过
I	Portal	点击查看	3/3	未通过
J	Bob's Poor Math	点击查看	15/105	通过
K	Color Graph	点击查看	154/344	通过
L	Light It Down	点击查看	1/3	未通过
M	Blood Pressure Game	点击查看	3/81	未通过

B

可以用字典树，但实际unordered_map就可以了，更好写一点

代码连接

D

这个题比较搞，但其实想出来的话特别好写（现场赛做崩了，298 1A）

题意是给一个 n (\(n\le 1000\)) 个点的完全图 , 每次删除一个n结点的生成树（在原图删除对应的边），问最多可以删除多少次。

容易想到 n 个点的完全图总边数是 \(n*(n-1) / 2\) ，而一个生成树的边数为 \((n-1)\) ，所以最多可以构造出\(n/2\) 棵生成树。

n 为偶数时，枚举\((x, y),x=2k-1,y=2k,k\in[1,n/2]\) , 将 \(x\) 与小于\(x\) 的偶数相连，与大于\(x\) 的奇数相连、将\(y\) 与小于 \(y\) 的奇数相连，与大于\(y\) 的偶数相连。

如此构造可以使得：

每个偶数都与比它大的偶数和比它小的奇数相连，都被比它小的偶数和比它大的奇数相连
每个奇数都与比它小的偶数和比它大的奇数相连，都被比它大的偶数和比它小的奇数相连

可以发现，每个点都只与其他\((n-1)\) 个点搭配了一次。

对于 n 为奇数的情况，先按照\((n-1)\) 为偶数的情况去处理，然后在第 \(i\) 个 \((n-1)\)结点的生成树中，将\((i,n)\)相连即可。

int T, n, cas;

void get(int s, int t, int n){

    for (int i = 2; i < s;i += 2)

        printf("%d %d\n", i, s);

    for (int i = s + 2; i <= n;i += 2)

        printf("%d %d\n", s, i);

    for (int i = 1; i < t; i += 2)

        printf("%d %d\n", i, t);

    for (int i = t + 2; i <= n;i+=2)

        printf("%d %d\n", t, i);

}

int main() {

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        printf("Case #%d: %d\n", ++cas, n / 2);

        for (int i = 1; i < n;i+=2){

            if(n & 1)

                printf("%d %d\n", i, n);

            get(i, i + 1, n - (n & 1));

        }

    }

    return 0;

}

关于怎么想到这么一种构造方法...首先只考虑n为偶数的情况，然后每次枚举两个点，做为整个树的“中心枢纽", 其他点各分一半与这两个点相连，按照规律去找。

E

比较裸的最大生成树，如果不是多组数据就可以裸着做了。

T = 10，点数1e6, 边数4e6级别。对边排序或者堆优化的prim都不太靠得住，但是注意下题目数据就会发现，边权最大只可能是10000，所以按照桶排的思想去处理边即可。然后kruskal。

const int N = 1000 + 5;

typedef pair<int, int> pii;

int T,n,m;

pii st, ed;

int val[N][N];

int x[1000010],A, B, C, P;

int id[N][N], vis[N][N], fa[N*N];

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

vector<pii> edge[10010];

int main()

{

    scanf("%d", &T);

    int cas = 0;

    while(T--){

        scanf("%d%d%d%d%d%d", &n, &m, &st.first, &st.second, &ed.first, &ed.second);

        scanf("%d%d%d%d%d%d", &x[1], &x[2], &A, &B, &C, &P);

        for (int i = 1; i <= n*m;i++)

            fa[i] = i;

        for (int i = 0; i <= 10000;i++)

            edge[i].clear();

        for (int i = 3; i <= n * m; i++)

        {

            x[i] = (A * x[i - 1] + B * x[i - 2] + C) % P;

        }

        int k = 0;

        for (int i = 1; i <= n;i++)

            for (int j = 1; j <= m;j++){

                id[i][j] = ++k;

                val[i][j] = x[k];

                if(i > 1)

                    edge[val[i][j] * val[i - 1][j]].push_back({ id[i][j], id[i - 1][j] });

                if(j > 1)

                    edge[val[i][j] * val[i][j - 1]].push_back({ id[i][j], id[i][j - 1] });

            }

        ll res = 0, cnt = 0;

        for (int i = 10000; i >= 0;i--){

            for (int j = 0; j < edge[i].size();j++){

                int x = edge[i][j].first, y = edge[i][j].second;

                if(find(x) == find(y))

                    continue;

                res += i;

                fa[find(x)] = find(y);

                cnt++;

                if(cnt == k-1)

                    break;

            }

            if(cnt == k-1)

                break;

        }

            printf("Case #%d: %lld\n", ++cas, res);

    }

    return 0;

}

F

显然是树剖，不过要维护的东西有那么一点恶心人。

维护\(\sum w^3\) ，从三个操作去分解它，得到线段树中需要存放的东西

区间赋值为 w
区间加 w
区间乘 w

为了简化线段树的操作，发现1号操作等价于先乘一个0，在加一个 w。所以这三个操作都可以转换为这个形式：区间先乘一个数 x，再加一个数 y

要维护 \(\sum w^3\) ，乘的操作看起来比较容易，所以先来看看加一个数如何维护

\((w+y)^3 = w^3 + y^3 + 3*w^2*y + 3*w*y^2\)

\(\Rightarrow \sum (x+y)^3 = \sum w^3 + \sum y^3 + 3*\sum w^2*y + 3*\sum w* y^2\)

发现线段树中需要维护三个值：\(\sum w^3, \sum w^2, \sum w\)

这三个值分别用 \(s3, s2, s\) 表示

对于乘法更新：

\[s3 = s3 * x^3\\
s2 = s2 * x ^2\\
s = s * x
\]

对于加法更新（注意变量更新顺序）：

\[s3 = s3 + \sum y^3 + 3*s2*y + 3*s*y^2\\
s2 = s2 + 2*s*y+\sum y*y\\
s = s + \sum y
\]

lazy_tag 更新：

\[mul = mul *x \\
add = add * x + y
\]

代码

由于绝大部分是板子，所以代码列出主要部分, 下面是线段树的操作代码：

#define ls (p*2)

#define rs (p*2+1)

struct SegTree{

    int l, r;

    ll len, s, s2, s3, mul, add;

} t[N << 2];

void pushup(int p){

    t[p].s = (t[ls].s + t[rs].s) % mod;

    t[p].s2 = (t[ls].s2 + t[rs].s2) % mod;

    t[p].s3 = (t[ls].s3 + t[rs].s3) % mod;

}

void build(int p,int l,int r){

    t[p].l = l, t[p].r = r;

    t[p].mul = 1;

    t[p].add = t[p].s = t[p].s2 = t[p].s3 = 0;

    t[p].len = r - l + 1;

    if(l == r){

        ll val = w[rnk[l]];

        t[p].s = val;

        t[p].s2 = val * val % mod;

        t[p].s3 = val * val % mod * val % mod;

        return;

    }

    int mid = l + r >> 1;

    build(p * 2, l, mid);

    build(p * 2 + 1, mid + 1, r);

    pushup(p);

}

ll S3(ll x) { return x * x % mod * x % mod; }

ll S2(ll x) { return x * x % mod; }

void calc(int p,ll x, ll y){ // 这里千万要细心

    //乘法更新

    t[p].s = t[p].s * x % mod;

    t[p].s2 = t[p].s2 * S2(x) % mod;

    t[p].s3 = t[p].s3 * S3(x) % mod;

    //加法更新，这里要按照s3,s2,s的顺序依次更新

    t[p].s3 = t[p].s3 + S3(y) * t[p].len % mod + 3ll * t[p].s2 * y % mod + 3ll * t[p].s * S2(y) % mod;

    t[p].s3 %= mod;

    t[p].s2 = (t[p].s2 + 2ll * t[p].s * y % mod + S2(y)*t[p].len) % mod;

    t[p].s = (t[p].s + y * t[p].len % mod) % mod;

    //最后也不能掉以轻心

    t[p].mul = t[p].mul * x % mod;

    t[p].add = (t[p].add * x % mod + y) % mod;

}

void pushdown(int p){

    if(t[p].mul != 1 || t[p].add){

        calc(ls, t[p].mul, t[p].add);

        calc(rs, t[p].mul, t[p].add);

        t[p].mul = 1, t[p].add = 0;

    }

}

void change(int p,int l,int r,ll x,ll y){

    if(t[p].l >= l && t[p].r <= r){

        calc(p, x, y);

        return;

    }

    pushdown(p);

    int mid = t[p].l + t[p].r >> 1;

    if(mid >= l)

        change(ls, l, r, x, y);

    if(mid < r)

        change(rs, l, r, x, y);

    pushup(p);

}

ll query(int p,int l,int r){

    if(t[p].l >= l && t[p].r <= r)

        return t[p].s3;

    pushdown(p);

    int mid = t[p].l + t[p].r >> 1;

    ll res = 0;

    if(mid >= l)

        res += query(ls, l, r);

    if(mid < r)

        res += query(rs, l, r);

    return res % mod;

}

H

二分+树形DP

枚举最小值mid，按照这个值对树进行分块。

对于 \(x\) 结点，递归处理它的子节点，并将所有子节点的剩余价值放到一个容器中，进行排序，优先考虑小的。不能装的时候，后面的要全部割掉。

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int N = 100000 + 5;

int n, k, cnt, head[N], ver[N<<1], nxt[N<<1], tot;

ll w[N], d[N], lim;

void add(int x,int y){

    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;

}

void dfs(int x,int fa){

    vector<ll> val;//放在内部还是外部需要仔细考虑，如果贪恋时间，可以放外面，不过要注意要先dfs所有子节点后，再扫一遍将他们加入到序列中，函数返回时要记得clear

    for (int i = head[x]; i;i=nxt[i]){

        int y = ver[i];

        if(y == fa)

            continue;

        dfs(y, x);

        val.push_back(d[y]);

    }

    sort(val.begin(), val.end());

    d[x] = w[x];

    for (int i = 0; i < val.size();i++){

        if(d[x] + val[i] > lim){

            cnt += val.size() - i;

            break;

        }

        d[x] += val[i];

    }

}

bool check(ll mid){

    lim = mid;

    cnt = 1;

    dfs(1, 0);

    return cnt <= k;

}

int main() {

    int T, cas = 0;

    scanf("%d", &T);

    while(T--){

        scanf("%d%d", &n, &k);

        tot = 0;

        for (int i = 1; i <= n;i++)

            head[i] = 0;

        for (int i = 1; i < n; i++) {

            int x, y;

            scanf("%d%d", &x, &y);

            add(x, y);

            add(y, x);

        }

        ll l = 1, r = 0;

        for (int i = 1; i <= n;i++){

            scanf("%lld", &w[i]);

            r += w[i];

            l = max(l, w[i]);

        }

        while(l < r){

            ll mid = l + r >> 1;

            if(check(mid))

                r = mid;

            else

                l = mid + 1;

        }

        printf("Case #%d: %lld\n", ++cas, l);

    }

    return 0;

}

J

字典树，类似线段树的操作，细节挺多

Add 操作，直接在字典树中加一个新的数字
Shift操作，new一个新的根，将原根接到新根的0号位置，并更新sum值，打tag标记
Query操作，每一层通过枚举找到一个最大可以组合成的数字
Sum 操作，类似线段树的区间求和

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int N = 200000 + 5;

int tr[N][10], n, m, rt, tot;

ll sum[N], tag[N], l, r, x, p[11];

char op[10];

void clear(){

    for (int i = 1; i <= tot;i++){

        memset(tr[i], 0, sizeof tr[i]);

        sum[i] = tag[i] = 0;

    }

    tot = rt = 1;

}

ll add_val(ll x, ll y){//按照题意的加法原则进行相加

    if(x == 0 || y == 0)

        return x | y;

    ll res = 0;

    for (int i = 0; i < 10;i++, x /= 10, y /= 10){

        res += (x % 10 + y % 10) % 10 * p[i];

    }

    return res;

}

void pushdown(int u){

    if(tag[u] == 0)

        return;

    for(int i = 0; i <= 9;i++){

        if(!tr[u][i])

            continue;

        int v = tr[u][i];

        if(tag[u] > 10)

            sum[v] = 0;

        else

            sum[v] /= p[tag[u]], tag[v] += tag[u];

    }

    tag[u] = 0;

}

void add(int u,int x){

    sum[u] = add_val(sum[u], x);

    for (int i = 9; i >= 0;i--){

        pushdown(u);

        int c = x / p[i] % 10;

        if(tr[u][c] == 0)

            tr[u][c] = ++tot;

        u = tr[u][c];

        sum[u] = add_val(sum[u], x);

    }

}

void shift(){

    tr[++tot][0] = rt;

    sum[tot] = sum[rt] / 10;

    tag[rt = tot]++;

}

ll query_sum(ll x){

    ll res = 0;

    int u = rt;

    for (int i = 9; i >= 0;i--){

        pushdown(u);

        int c = x / p[i] % 10, j = 9;

        //找到最大的可组合的 j

        while(tr[u][(j+10-c)%10] == 0)

            j--;

        res += j * p[i];

        u = tr[u][(j + 10 - c) % 10];

    }

    return res;

}

ll get(int dep, int u, ll l, ll r, ll x, ll y){

    if(y < l || x > r)

        return 0;

    if(l >= x && r <= y){

        return sum[u];

    }

    pushdown(u);

    ll res = 0;

    for (int i = 0; i <= 9;i++){

        if(!tr[u][i])

            continue;

        //注意这里的[nl,nr]的计算

        ll nl = l + p[dep] * i, nr = l + p[dep] * (i + 1) - 1;

        res = add_val(res, get(dep - 1, tr[u][i], nl, nr, x, y));

    }

    return res;

}

int main() {

    p[0] = 1;

    for (int i = 1; i <= 10;i++)

        p[i] = p[i - 1] * 10;

    int T, cas = 0;

    scanf("%d", &T);

    while(T--){

        scanf("%d%d", &n, &m);

        clear();

        for (int i = 1; i <= n;i++){

            scanf("%lld", &x);

            add(rt, x);

        }

        printf("Case #%d:\n", ++cas);

        while(m--){

            scanf("%s", op);

            if(op[0] == 'S' && op[1] == 'h')

                shift();

            else if(op[0] == 'A'){

                scanf("%lld", &x);

                add(rt, x);

            }else if(op[0] == 'Q'){

                scanf("%lld", &x);

                printf("%lld\n", query_sum(x));

            }else if(op[0] == 'S'){

                scanf("%lld%lld", &l, &r);

                printf("%lld\n", get(9, rt, 0, p[10] - 1, l, r));

            }

        }

    }

    return 0;

}

K

染边不存在奇环，那么染边与点构成一个二分图，枚举每个点在这个二分图中的所属，将所有边进行枚举，如果该边的两个点在二分图中所属不同，那么贡献++

const int N = 16 + 5;

int T, n, m, st[N];

int cas;

pair<int, int> e[N * N];

int main() {

    scanf("%d", &T);

    while(T--){

        scanf("%d%d", &n, &m);

        for (int i = 1; i <= m;i++){

            scanf("%d%d", &e[i].first, &e[i].second);

        }

        int res = 0;

        for (int i = 0; i < (1 << n);i++){

            for (int j = 0; j < n;j++){

                if(i >> j & 1)

                    st[j + 1] = 1;

                else

                    st[j + 1] = 0;

            }

            int cur = 0;

            for (int i = 1; i <= m;i++){

                if(st[e[i].first] != st[e[i].second]){

                    cur++;

                }

            }

            res = max(res, cur);

        }

        printf("Case #%d: %d\n", ++cas, res);

    }

    return 0;

}

巴特西

2019 ICPC 上海区域赛总结

2019上海区域赛现场赛总结

B

D

E

F

H

J

K

最新文章

热门文章