@Dmaxiya 2018-08-17T10:13:50.000000Z 字数 7405 阅读 975

Codeforces Round #457 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #457 (Div. 2)
过题数：2
排名：447/6352

A. Jamie and Alarm Snooze

题意

$Jamie$ 想睡懒觉，但是他必须要在 $hh:mm$ 时刻起床，于是他需要提前定一个含有 $lucky$ 数字 $7$ 的时刻作为第一次闹钟响起的时刻，已经知道他每隔 $x$ 分钟就会按下闹钟的“贪睡”按钮，问他第一次闹钟的时间是多少。

数据范围

$1\leq x\leq60\\00\leq hh\leq23,00\leq mm\leq59$

题解

按照给定时刻每次往前跑 $x$ 分钟，判断该时间是否含有数字 $7$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int x, h, m;
int ans;
void cut_x(int &h, int &m, int x) {
    m -= x;
    if(m < 0) {
        m += 60;
        h -= 1;
        if(h < 0) {
            h += 24;
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &x, &h, &m) != EOF) {
        int ans = 0;
        while(h % 10 != 7 && m % 10 != 7) {
            cut_x(h, m, x);
            ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Jamie and Binary Sequence

题意

将 $n$ 分成 $k$ 个 $2^{a_i}$ 相加，若不能拆分，则输出 $No$ ，否则找到 $\min(\max(a_i)),i\in[1,k]$ ，且字典序最大的满足条件的序列，题目保证答案的范围在 $[-10^{18},10^{18}]$ 之间。

数据范围

$1\leq n\leq10^{18},1\leq k\leq10^5$

题解

先判断是否可以用 $k$ 个数字来表示 $n$ ，若可行，用大顶堆将最大值弹出，拆成两个小的进入堆，直到堆的大小为 $k$ ，以此确定 $\min(\max(a_i))$ ，然后根据这个值贪心构造数列。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 63;
const int maxm = 100000 + 100;
int cnt, k;
LL n;
LL two[maxn];
int ans[maxm];
priority_queue<int> que;
void Pull(int Max, LL n) {
    cnt = 0;
    while(n != 0) {
        LL *it = upper_bound(two, two + maxn, n);
        --it;
        n -= *it;
        if(Max < it - two) {
            for(int i = 0; i < two[it - two - Max]; ++i) {
                ans[cnt++] = Max;
            }
        } else {
            ans[cnt++] = it - two;
        }
    }
    while(cnt != k) {
        ans[cnt - 1] = ans[cnt - 1] - 1;
        ans[cnt] = ans[cnt - 1];
        ++cnt;
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    two[0] = 1;
    for(int i = 1; i < maxn; ++i) {
        two[i] = two[i - 1] << 1;
    }
    while(scanf("%I64d%d", &n, &k) != EOF) {
        while(!que.empty()) {
            que.pop();
        }
        LL nn = n;
        while(n != 0) {
            LL *it = upper_bound(two, two + maxn, n);
            --it;
            que.push(it - two);
            n -= *it;
            if((int)que.size() == k) {
                break;
            }
        }
        if(n != 0) {
            printf("No\n");
            continue;
        }
        printf("Yes\n");
        while((int)que.size() < k) {
            int tmp = que.top();
            que.pop();
            --tmp;
            que.push(tmp);
            que.push(tmp);
        }
        int Max = que.top();
        Pull(Max, nn);
        for(int i = 0; i < cnt; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

C. Jamie and Interesting Graph

题意

如果一张带权无向图满足以下条件，它就是一张有趣的图：

图是连通的，含有 $n$ 个顶点与 $m$ 条边；

边权是整数且在 $[1, 10^9]$ 内；

从点 $1$ 到点 $n$ 的最短路径长度是一个质数；

最小生成树的路径长度和为质数；

图上没有自环和重边。

给定 $n$ 和 $m$ ，请构造出这样的图。

数据范围

$2\leq n\leq10^5\\n-1\leq m\leq\min(\frac{n\times(n-1)}{2},10^5)$

题解

按照 $n\rightarrow1\rightarrow2\rightarrow3\rightarrow\cdots\rightarrow n-2\rightarrow n-1$ 的顺序连边，除了 $n\rightarrow1$ 的权为 $2$ ，其他边权都为 $1$ ，边 $n-2\rightarrow n-1$ 的程度根据总长度来凑出一个质数，这条链就是最小生成树。其他边只要边权大于这个最小生成树的最大边权，就随便加。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
struct Node {
    int v, u;
    LL dis;
    Node() {}
    Node(int uu, int vv, LL d) {
        u = uu;
        v = vv;
        dis = d;
    }
};
int cnt, n, m;
LL mst;
LL maxlen;
Node ans[maxn];
int id[maxn];
void add(int u, int v, int d) {
    ans[cnt].u = u;
    ans[cnt].v = v;
    ans[cnt++].dis = d;
}
bool isPrime(LL x) {
    for(LL i = 2; i * i <= x; ++i) {
        if(x % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        maxlen = 2;
        id[1] = n;
        for(int i = 2; i <= n; ++i) {
            id[i] = i - 1;
        }
        cnt = 0;
        add(1, n, 2);
        for(int i = 2; i < n; ++i) {
            add(id[i], id[i + 1], 1);
        }
        mst = n;
        while(!isPrime(mst)) {
            ++ans[cnt - 1].dis;
            ++mst;
            maxlen = max(maxlen, ans[cnt - 1].dis);
        }
        ++maxlen;
        for(int i = 1; i < n - 1; ++i) {
            for(int j = i + 2; j <= n; ++j) {
                if(cnt < m) {
                    add(id[i], id[j], maxlen);
                } else {
                    break;
                }
            }
            if(cnt >= m) {
                break;
            }
        }
        printf("%d %I64d\n", 2, mst);
        for(int i = 0; i < cnt; ++i) {
            printf("%d %d %I64d\n", ans[i].u, ans[i].v, ans[i].dis);
        }
    }
    return 0;
}

E. Jamie and Tree

题意

题给一棵 $n$ 个节点的树，每个节点上有一个权值 $a_i$ ，接下来有 $q$ 次操作，按照以下输入进行相应操作：

$1\quad v$ : 将 $v$ 作为树根；

$2\quad u\quad v\quad x$ : — 将包含有节点 $u$ 和 $v$ 的最小子树上的所有节点加上 $x$ ；

$3\quad v$ : 询问以 $v$ 为根的子树的所有节点的和。

对于每次询问，输出结果。

数据范围

$1\leq n\leq10^5,1\leq q\leq10^5\\ -10^8\leq a_i\leq10^8,1\leq u_i,v_i\leq n,-10^8\leq x\leq10^8,$

题解

对于第 $2$ 和第 $3$ 种操作，就是裸的线段树构图 $+$ $LCA$ ，现在要考虑的是，根改变之后，节点 $u$ $v$ 的根节点会如何改变。
如果记当前的根节点为 $root$ ，多画几组样例可以发现，对 $u$ $v$ $root$ 两两求 $LCA$ ， $dfs$ 序最大的，就是 $u$ 和 $v$ 在 $root$ 为根时的子树的根，记为 $root\_uv$ ，对于 $root$ 不在 $root\_uv$ 的子树下的情况（以 $1$ 为根节点），操作 $2$ 和 $3$ 直接对 $root\_uv$ 对应的子树进行操作即可；如果 $root$ 在 $root\_uv$ 对应的子树下，就先对整棵树进行操作 $2$ $2$ ，再减去 $root$ 所在的 $root\_uv$ 的子树的贡献即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
const int Log = 25;
int root;
int n, q, cnt, u, v, command;
LL tmp, ans;
LL num[maxn];
int id[maxn], ide[maxn], rid[maxn];
int fa[Log][maxn];
vector<int> G[maxn];
LL lazy[maxn << 2], sum[maxn << 2];
void push_up(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void push_down(int rt, int len) {
    if(lazy[rt]) {
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        sum[rt << 1] += (len - (len >> 1)) * lazy[rt];
        sum[rt << 1 | 1] += (len >> 1) * lazy[rt];
        lazy[rt] = 0;
    }
}
void build(int l, int r, int rt) {
    lazy[rt] = 0;
    if(l == r) {
        sum[rt] = num[rid[l]];
        return ;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    push_up(rt);
}
void add(int L, int R, LL tmp, int l, int r, int rt) {
    if(L <= l && r <= R) {
        lazy[rt] += tmp;
        sum[rt] += (r - l + 1) * tmp;
        return ;
    }
    push_down(rt, r - l + 1);
    int m = (r + l) >> 1;
    if(L <= m) {
        add(L, R, tmp, l, m, rt << 1);
    }
    if(R > m) {
        add(L, R, tmp, m + 1, r, rt << 1 | 1);
    }
    push_up(rt);
}
LL query(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) {
        return sum[rt];
    }
    push_down(rt, r - l + 1);
    int m = (l + r) >> 1;
    LL ret = 0;
    if(L <= m) {
        ret += query(L, R, l, m, rt << 1);
    }
    if(R > m) {
        ret += query(L, R, m + 1, r, rt << 1 | 1);
    }
    return ret;
}
void dfs(int f, int x) {
    id[x] = ++cnt;
    rid[cnt] = x;
    int len = G[x].size();
    for(int i = 0; i < len; ++i) {
        int pos = G[x][i];
        if(pos != f) {
            fa[0][pos] = x;
            dfs(x, pos);
        }
    }
    ide[x] = cnt;
}
void prepare_skip_table() {
    cnt = 0;
    fa[0][1] = 1;
    dfs(1, 1);
    for(int j = 1; j < Log; ++j) {
        for(int i = 1; i <= n; ++i) {
            fa[j][i] = fa[j - 1][fa[j - 1][i]];
        }
    }
}
int Find(int x, int y, bool flag) {
    if(x == y) {
        return x;
    }
    if(id[x] > id[y]) {
        swap(x, y);
    }
    for(int i = Log - 1; i >= 0; --i) {
        if(id[fa[i][y]] > id[x]) {
            y = fa[i][y];
        }
    }
    if(flag) {
        return fa[0][y];
    } else {
        return y;
    }
}
int Find_real_root(int a, int b, int c) {
    int ret;
    int ab = Find(a, b, true);
    int ac = Find(a, c, true);
    if(id[ab] > id[ac]) {
        ret = ab;
    } else {
        ret = ac;
    }
    int bc = Find(b, c, true);
    if(id[ret] < id[bc]) {
        ret = bc;
    }
    return ret;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i) {
        scanf("%I64d", &num[i]);
    }
    for(int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    prepare_skip_table();
    build(1, n, 1);
    for(int i = 0; i < q; ++i) {
        scanf("%d", &command);
        if(command == 1) {
            scanf("%d", &u);
            root = u;
        } else if(command == 2) {
            scanf("%d%d%I64d", &u, &v, &tmp);
            int real_root = Find_real_root(u, v, root);
            if(real_root == root) {
                add(1, n, tmp, 1, n, 1);
            } else {
                if(id[real_root] < id[root] && ide[real_root] >= id[root]) {
                    add(1, n, tmp, 1, n, 1);
                    int rr = Find(real_root, root, false);
                    add(id[rr], ide[rr], -tmp, 1, n, 1);
                } else {
                    add(id[real_root], ide[real_root], tmp, 1, n, 1);
                }
            }
        } else {
            scanf("%d", &u);
            if(u == root) {
                printf("%I64d\n", query(1, n, 1, n, 1));
            } else {
                if(id[u] < id[root] && ide[u] >= id[root]) {
                    ans = query(1, n, 1, n, 1);
                    int rr = Find(u, root, false);
                    ans -= query(id[rr], ide[rr], 1, n, 1);
                } else {
                    ans = query(id[u], ide[u], 1, n, 1);
                }
                printf("%I64d\n", ans);
            }
        }
    }
    return 0;
}

Codeforces Round #457 (Div. 2)

A. Jamie and Alarm Snooze

题意

数据范围

题解

过题代码

B. Jamie and Binary Sequence

题意

数据范围

题解

过题代码

C. Jamie and Interesting Graph

题意

数据范围

题解

过题代码

E. Jamie and Tree

题意

数据范围

题解

过题代码

内容目录