Educational Codeforces Round 129 (Rated for Div. 2)

A. Game with Cards

题目解析

直接判断Alice的最大卡片和Bob的最大的卡片的大小，如果相等，先手获胜，否则较大的获胜。

参考代码

int main() {
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n;
        vector<int> arr(n);
        for(auto& it: arr) cin >> it;
        cin >> m;
        vector<int> brr(m);
        for(auto& it: brr) cin >> it;
        sort(arr.begin(), arr.end());
        sort(brr.begin(), brr.end());
        int ra = arr.back(), rb  = brr.back();
        if(ra < rb){
            cout << "Bob\nBob\n";
        }else if(ra == rb){
            cout << "Alice\nBob\n";
        }else{
            cout << "Alice\nAlice\n";
        }
    }
    return 0;
}

B. Card Trick

题目解析

移动前 $b_j$ 张牌到末尾，意味着将牌顶指针向下移动 $b_j$ 。如果牌顶指针移到牌底之下，就将牌顶指针移回牌顶。

参考代码

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> arr(n);
        for(auto& it: arr) cin >> it;
        int top = 0;
        int m;
        cin >> m;
        for(int i = 0; i < m; ++i){
            int nex;
            cin >> nex;
            top = (top + nex) % n;
        }
        cout << arr[top] << endl;
    }
    return 0;
}

C. Double Sort

题目解析

先将 $a_i, b_i$ 合并起来排序，然后检查 $b_i$ 是不是非递减的。
如果不是非递增的，那么就不存在结果；
如果是非递增的，那么就可以通过交换，使它满足均非递减的状态；

然后根据初始位置和当前位置，设定一下交换关系。

参考代码

struct Node{
    int a, b;
    int idx;
    bool operator < (const Node& arg) const{
        if(a == arg.a){
            return b < arg.b;
        }
        return a < arg.a;
    }
};
int main() {
    fastIO();
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<Node> arr(n);
        for(int i = 0; i < n; ++i){
            arr[i].idx = i;
            cin >> arr[i].a;
        }
        for(int i = 0; i < n; ++i) cin >> arr[i].b;
        sort(itr(arr));
        bool ok = true;
        for(int i = 1; i < n; ++i){
            if(arr[i].b < arr[i - 1].b){
                ok = false;
                break;
            }
        }
        if(!ok){
            cout << "-1\n";
            continue;
        }
        vector<int> brr(n); //存放的是目标位置
        vector<int> rbrr(n);  //存放的是值对应的位置，brr的反向映射
        for(int i = 0; i < n; ++i) rbrr[i] = arr[i].idx;
        for(int i = 0; i < n; ++i){
            brr[rbrr[i]] = i;
        }
        vector<PII> ans;
        for(int i = 0; i < n; ++i){
            if(brr[i] != i){
                int x = i;
                int y = rbrr[i];
                ans.push_back({x, y});
                swap(brr[x], brr[y]);
                rbrr[brr[x]] = x;
                rbrr[brr[y]] = y;
            }
        }
        cout << ans.size() << "\n";
        for(auto& it: ans){
            cout << it.first + 1 << " " << it.second + 1 << "\n";
        }
    }
    return 0;
}

D. Required Length

题目解析

从 $x$ 开始，遍历它的每一位，然后找到它可以转移到的，大于 $x$ 的下个数字。通过BFS找到是否能转移到一个n位的数字。

开unsigned long long比较保险。

参考代码

typedef pair<ull, int> pui;
int main() {
    ull n, x;
    cin >> n >> x;
    ull ml = 1, mr = 10;
    while(--n){
        ml *= 10, mr *= 10;
    }
    pui st{x, 0};
    int ans = -1;
    queue<pui> q; //当前数字，操作次数
    q.push(st);
    set<ull> vis;
    vis.insert(st.first);
    while(!q.empty()){
        auto it = q.front();
        q.pop();
        if(it.first >= mr) continue;
        if(it.first >= ml and it.first < mr){
            ans = it.second;
            break;
        }
        ull flag = 0; //用来标记数字位是否已经访问过。
        ull tmpv = it.first;
        while(tmpv){
            int delta = tmpv % 10;
            tmpv /= 10;
            if(delta > 0 and !(flag & (1 << delta))){
                flag |= (1 << delta);
                ull nex = it.first * delta;
                if(!vis.count(nex)){
                    q.push({nex, it.second + 1});
                    vis.insert(nex);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

E. Labyrinth Adventures

题目解析

首先设定起始点 $(s_x, s_y)$ 的层序 $L_s$ 小于或者等于目标点 $(e_x, e_y)$ 的层序 $L_e$ ，如果不满足，就交换起始点和目标点。

如果起始点的层序和目标点的层序相同，起始点和目标点的曼哈顿距离就是结果，因为可以沿着当前层运动。

如果起始点层序小于目标点的层序。我们可以用线段树维护一下起始层的门旁位置到目标层的前一层门旁位置之间的最短距离（分别是 $d_{uu}, d_{ur}, d_{ru}, d_{rr}$）。门旁位置是代表当前位置的上方或者右方有一扇门。 然后计算起始点到起始层门旁位置的曼哈顿距离（分别是 $d_{su}, d_{sr}$ ）和目标层的前一层的门旁位置到目标点的曼哈顿距离（分别是 $d_{ue}, d_{re}$ ）。

那么起始点到目标点的最近距离就是：

$$d_{se} = \min(d_{su} + d_{uu} + d_{ue}, d_{su} + d_{ur} + d_{re}, d_{sr} + d_{ru} + d_{ue}, d_{sr} + d_{rr} + d_{re})$$

我们定义的线段树的节点如下所示：

struct SegNode{
    int stu, str; // stu: 起始层的上方门的y； str: 目标层的右方门的x
    int edu, edr; // stu: 目标层的上方门的y； str: 目标层的右方门的x
    int s, e; // s: 起始层序号； e: 目标层序号
    // uu: 起始层上方门旁位置到目标层上方门旁位置的最近距离； 
    // ur: 起始层上方门旁位置到目标层右方门旁位置的最近距离； 
    // ru: 起始层右方门旁位置到目标层上方门旁位置的最近距离； 
    // rr: 起始层右方门旁位置到目标层右方门旁位置的最近距离；
    ll uu, ur, ru, rr;  
    SegNode() = default;
    SegNode(int u, int r, int id): stu(u), str(r), edu(u), edr(r), uu(0), s(id), e(id), ur(abs(id - u) + abs(id - r)), ru(abs(id - u) + abs(id - r)), rr(0){ }
    SegNode operator + (const SegNode& arg) {
        SegNode ret;
        ret.stu = stu;
        ret.str = str;
        ret.s = s;
        ret.e = arg.e;
        ret.edu = arg.edu;
        ret.edr = arg.edr;
        ll tuu = abs(edu - arg.stu);
        ll trr = abs(edr - arg.str);
        ll tur = abs(edu - arg.s) + abs(arg.s - arg.str);
        ll tru = abs(edr - arg.s) + abs(arg.s - arg.stu);
        ret.uu = min(min(uu + arg.uu + tuu, ur + arg.ru + trr), min(uu + arg.ru + tur, ur + arg.uu + tru)) + 1;
        ret.ur = min(min(uu + arg.ur + tuu, ur + arg.rr + trr), min(uu + arg.rr + tur, ur + arg.ur + tru)) + 1;
        ret.ru = min(min(ru + arg.uu + tuu, rr + arg.ru + trr), min(ru + arg.ru + tur, rr + arg.uu + tru)) + 1;
        ret.rr = min(min(ru + arg.ur + tuu, rr + arg.rr + trr), min(ru + arg.rr + tur, rr + arg.ur + tru)) + 1;
        return ret;
    }
};

参考代码

struct Node{
    int x1, y1, x2, y2;
};
struct SegNode{
    int stu, str;
    int edu, edr;
    int s, e;
    ll uu, ur, ru, rr;
    SegNode() = default;
    SegNode(int u, int r, int id): stu(u), str(r), edu(u), edr(r), uu(0), s(id), e(id), ur(abs(id - u) + abs(id - r)), ru(abs(id - u) + abs(id - r)), rr(0){ }
    SegNode operator + (const SegNode& arg) {
        SegNode ret;
        ret.stu = stu;
        ret.str = str;
        ret.s = s;
        ret.e = arg.e;
        ret.edu = arg.edu;
        ret.edr = arg.edr;
        ll tuu = abs(edu - arg.stu);
        ll trr = abs(edr - arg.str);
        ll tur = abs(edu - arg.s) + abs(arg.s - arg.str);
        ll tru = abs(edr - arg.s) + abs(arg.s - arg.stu);
        ret.uu = min(min(uu + arg.uu + tuu, ur + arg.ru + trr), min(uu + arg.ru + tur, ur + arg.uu + tru)) + 1;
        ret.ur = min(min(uu + arg.ur + tuu, ur + arg.rr + trr), min(uu + arg.rr + tur, ur + arg.ur + tru)) + 1;
        ret.ru = min(min(ru + arg.uu + tuu, rr + arg.ru + trr), min(ru + arg.ru + tur, rr + arg.uu + tru)) + 1;
        ret.rr = min(min(ru + arg.ur + tuu, rr + arg.rr + trr), min(ru + arg.rr + tur, rr + arg.ur + tru)) + 1;
        return ret;
    }
};
#define LEFT (cur << 1)
#define RIGHT (LEFT | 1)
#define MID ((l + r) >> 1)
int dis(int x1, int y1, int x2, int y2){
    return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
    fastIO();
    int n;
    cin >> n;
    vector<Node> arr(n);
    for(int i = 1; i < n; ++i) {
        cin >> arr[i].x1 >> arr[i].y1 >> arr[i].x2 >> arr[i].y2;
    }
    vector<SegNode> seg((n + 5) << 2);
    auto&& build = [&](auto&& self, int cur, int l, int r) -> void{
        if(l == r){
            seg[cur] = SegNode(arr[l].y1, arr[l].x2, l);
            return;
        }
        self(self, LEFT, l, MID);
        self(self, RIGHT, MID + 1, r);
        seg[cur] = seg[LEFT] + seg[RIGHT];
    };
    build(build, 1, 1, n - 1);
    auto&& query = [&](auto&& self, int cur, int l, int r, int st, int ed) -> SegNode{
        if(ed < l or r < st) return SegNode(0, 0, -1);
        if(st <= l and r <= ed) return seg[cur];
        SegNode lv = self(self, LEFT, l, MID, st, ed);
        SegNode rv = self(self, RIGHT, MID + 1, r, st, ed);
        if(lv.s >= 0 and rv.s >= 0){
            return lv + rv;
        }else if(lv.s >= 0){
            return lv;
        }else if(rv.s >= 0){
            return rv;
        }else{
            return SegNode(0, 0, -1);
        }
    };
    int m;
    cin >> m;
    while(m--){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int m1 = max(x1, y1), m2 = max(x2, y2);
        if(m1 == m2){
            cout << abs(x1 - x2) + abs(y1 - y2) << "\n";
            continue;
        }
        if(m1 > m2){
            swap(m1, m2);
            swap(x1, x2);
            swap(y1, y2);
        }
        SegNode delta = query(query, 1, 1, n - 1, m1, m2 - 1);
        ll ssu = dis(x1, y1, delta.s, delta.stu);
        ll ssr = dis(x1, y1, delta.str, delta.s);
        ll ttu = dis(x2, y2, delta.e + 1, delta.edu);
        ll ttr = dis(x2, y2, delta.edr, delta.e + 1);
        ll ans = infl;
        ans = min(ssu + ttu + 1 + delta.uu, ans);
        ans = min(ssu + ttr + 1 + delta.ur, ans);
        ans = min(ssr + ttu + 1 + delta.ru, ans);
        ans = min(ssr + ttr + 1 + delta.rr, ans);
        cout << ans << "\n";
    }
    return 0;
}

F. Unique Occurrences

题目解析

首先将题意转化为求每条边对结果的贡献。对于边 $(u, v, c)$ 来讲，他的贡献就是在 $u \leftarrow v$ 方向的 $u$ 的子树中到 $u$ 的路径不包含边权为 $c$ 的节点总数 与 在 $u \rightarrow v$ 方向的 $v$ 的子树中到 $v$ 的路径不包含边权为 $c$ 的节点总数 的乘积。

以 $1$ 为根，遍历整棵树，找到每个节点的子树的节点总数 $cnt$。同时构建倍增数组 $fa$ ，倍增数组用来寻找祖先节点。

第二次遍历以 $1$ 为根的整棵树的时候，当前节点是 $cur_p$，子节点是 $nex_p$，边权是 $c_{(cur_p, nex_p)}$，判断可以判断之前遍历过的，具有相同边权 $c_{(cur_p, nex_p)}$ 的边所相连的两个点 $(cur_i, nex_i)$ 是否在当前子树之下， $nex_i$ 是 $cur_i$ 的相邻子节点。这里可以用倍增来判断是否是在相同子树上 $\operatorname{isSameTree}$。

$S^i_{down}$ 是从 $cur_i \rightarrow nex_i$ 方向的 $nex_i$ 的子树中到 $nex_i$ 的路径不包含边权为 $c_{(cur_i, nex_i)}$ 的节点总数。
$S^i_{up}$ 是从 $cur_i \leftarrow nex_i$ 方向的 $cur_i$ 的子树中到 $cur_i$ 的路径不包含边权为 $c_{(cur_i, nex_i)}$ 的节点总数。

那么当前边 $(cur_p, nex_p)$ 的 $cur_p \rightarrow nex_p$ 方向的 $nex_p$ 的子树中到 $nex_p$ 的路径不包含边权为 $c_{(cur_p, nex_p)}$ 的节点总数是

$$S^p_{down} = cnt_{nex} - \sum_{i = 1 \And \operatorname{isSameTree}(nex_p, nex_i)} cnt_{nex_i}$$

同时可以得到 $cur_i \leftarrow right_i$ 方向的 $cur_i$ 的子树中到 $cur_i$ 的路径不包含边权为 $c_{(cur_p, nex_p)}$ 的节点总数是

$$S^i_{up} = S^p_{down} (\operatorname{isSameTree}(nex_p, nex_i))$$

参考代码

struct Node{
    int s, e, v;
};
int main() {
    int n;
    cin >> n;
    vector<Node> arr(n - 1);
    vector<vector<PII>> g(n + 1); //建图
    for(int i = 0; i < n - 1; ++i){
        cin >> arr[i].s >> arr[i].e >> arr[i].v;
        g[arr[i].s].push_back({arr[i].e, i});
        g[arr[i].e].push_back({arr[i].s, i});
    }
    vector<vector<int>> fa(n + 1, vector<int>(20, 0));
    vector<int> dep(n + 1, 0);
    auto&& dfs = [&](auto&& self, int cur, int pre) -> void{
        fa[cur][0] = pre;
        dep[cur] = dep[pre] + 1;
        for(int i = 1; i < 20; ++i){
            fa[cur][i] = fa[fa[cur][i - 1]][i - 1];
        }
        for(auto& nex: g[cur]){
            if(nex.first == pre) continue;
            self(self, nex.first, cur);
        }
    };
    dfs(dfs, 1, 0);
    auto&& isSameTree = [&](int x, int y) -> int{
        if(dep[x] < dep[y]) swap(x, y);
        int delta = dep[x] - dep[y];
        for(int i = 0; i < 20; ++i){
            if(delta & (1 << i)){
                x = fa[x][i];
            }
        }
        return x == y;
    };
    vector<int> cnt(n + 1, 0);
    auto&& dfs1 = [&](auto&& self, int cur, int pre) -> int{
        int ret = 1;
        for(auto& [nex, idx]: g[cur]){
            if(nex == pre) continue;
            int res = self(self, nex, cur);
            ret += res;
        }
        cnt[cur] = ret;
        return ret;
    };
    dfs1(dfs1, 1, 0);
    map<int, stack<PII>> mp;
    vector<PLL> ans(n - 1, {0, 0});
    auto&& dfs2 = [&](auto&& self, int cur, int pre) -> void{
        for(auto& [nex, idx]: g[cur]){
            if(nex == pre) continue;
            self(self, nex, cur);
            int idv = arr[idx].v;
            int sum = 0;
            stack<int> st;
            while(mp.count(idv) and !mp[idv].empty() and isSameTree(mp[idv].top().first, nex)){
                sum += cnt[mp[idv].top().first];
                st.push(mp[idv].top().second);
                mp[idv].pop();
            }
            int sv = cnt[nex] - sum;
            ans[idx].first = sv;
            while(!st.empty()){
                ans[st.top()].second = sv;
                st.pop();
            }
            if(!mp.count(idv)) mp[idv] = stack<PII>();
            mp[idv].push({nex, idx});
        }
    };
    dfs2(dfs2, 1, 0);
    for(auto& [idv, tst]: mp){
        stack<int> st;
        int sum = 0;
        while(tst.size() > 0){
            sum += cnt[tst.top().first];
            st.push(tst.top().second);
            tst.pop();
        }
        int sv = n - sum;
        while(!st.empty()){
            ans[st.top()].second = sv;
            st.pop();
        }
    }
    ll res = 0;
    for(int i = 0; i < n - 1; ++i){
        res += ans[i].first * ans[i].second;
    }
    cout << res << endl;
    return 0;
}