Skip to content

2020 牛客国庆集训派对 Day4

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J
7/10 O O O Ø - Ø - O - O
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

Problem A. Digits Are Not Just Characters

Solved By Dup4. 00:38(+)

题意

给出两个字符串，按特定规则比较大小。

规则就是一个字符串中，单个字符视为 letter item，连续的数字视为 digit item。

  • digit item 排在 letter item 前面。
  • letter item 之间按照字典序排序。
  • digit item 按照实际的值排序。

思路

  • 暴力模拟即可。
  • 但是我的代码也太长了。
  • 学习了一段代码，发现直接处理后，用 vector 去比较就行了，对于字符的处理要将它处理成一个较大的数字。
  • 然后发现题意中对于「排序」的定义，其实就是 PHP 中的 strnatcmp。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n;

vector<string> _get(string s) {
    vector<string> res;
    string t = "";
    for (auto &ch : s) {
        if (isdigit(ch))
            t += ch;
        else {
            if (!t.empty())
                res.push_back(t);
            t.clear();
            string _t = "";
            _t += ch;
            res.push_back(_t);
        }
    }
    if (!t.empty())
        res.push_back(t);
    //	for (auto &it : res) assert(SZ(it) > 0);
    return res;
}

int toInt(char ch) {
    return ch - '0';
}

char gao(string s, string t) {
    if (s == t)
        return '+';
    vector<string> _s(_get(s)), _t(_get(t));
    //	pt(_s, _t);
    //	return '+';
    for (int i = 0; i < min(SZ(_s), SZ(_t)); ++i) {
        string __s = _s[i];
        string __t = _t[i];
        //	dbg(__s, __t);
        int d_s = isdigit(__s[0]);
        int d_t = isdigit(__t[0]);
        if (d_s != d_t) {
            if (d_t)
                return '-';
            return '+';
        }
        if (__s != __t) {
            if (!d_s) {
                if (__s < __t)
                    return '+';
                else
                    return '-';
            } else {
                if (SZ(__s) != SZ(__t)) {
                    if (SZ(__s) < SZ(__t))
                        return '+';
                    else
                        return '-';
                }
                for (int j = 0; j < SZ(__s); ++j) {
                    int n_s = toInt(__s[j]);
                    int n_t = toInt(__t[j]);
                    if (n_s != n_t) {
                        if (n_s < n_t)
                            return '+';
                        else
                            return '-';
                    }
                }
            }
        }
    }
    if (SZ(s) > SZ(t))
        return '-';
    else
        return '+';
}

void run() {
    rd(n);
    string s;
    rd(s);
    for (int i = 1; i <= n; ++i) {
        string t;
        rd(t);
        //		cout << t << endl;
        pt(gao(s, t));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}
Code 
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int N = 1010;
vector<long long> v[N];

int main() {
    int n;
    cin >> n;
    string s;
    for (int k = 0; k <= n; k++) {
        cin >> s;
        long long x = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) {
                x = x * 10 + (s[i] ^ 0x30);
            } else {
                if (x)
                    v[k].push_back(x), x = 0;
                v[k].push_back(s[i] ^ (1ll << 32));
            }
        }
        if (x)
            v[k].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        cout << (v[i] < v[0] ? '-' : '+') << endl;
    }
    return 0;
}
Code 
<?php
$n = intval(fgets(STDIN));
$s0 = trim(fgets(STDIN));
for ($i = 0; $i < $n; $i++) {
$s = trim(fgets(STDIN));

if (strnatcmp($s0, $s) > 0) {
$result = '-';
} else {
$result = '+';
}

echo "$result\n";
}

Problem B. Arithmetic Progressions

Solved By Dup4. 00:45(+)

题意

给出 n 个数 a_i，找一个子序列，使得这个子序列排序后是一个「等差数列」。

思路

  • 先排序。
  • f_{i, j} 表示等差数列的最后一项为 a_j, 倒数第二项为 a_i 的最大长度是多少。
  • 因为倒数两个数确定了，差就确定了，然后枚举 i, j 找前驱的一个 k 进行转移即可。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 5e3 + 10;
int n, a[N], f[N][N];

unordered_map<int, int> mp;

void run() {
    rd(n);
    for (int i = 1; i <= n; ++i) rd(a[i]);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i) mp[a[i]] = i;
    int res = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (i == j)
                f[j][i] = 1;
            else {
                f[j][i] = 2;
                int pre = a[j] - (a[i] - a[j]);
                if (mp.count(pre)) {
                    chmax(f[j][i], f[mp[pre]][j] + 1);
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) chmax(res, f[i][j]);
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem C. Emergency Evacuation

Solved By groggy_. 01:40(+)

题意

有一辆公交车，有 n 行，m 列，并且两边是对称的。

每个位置上的人移动一个单位需要一个单位的时间，问所有人到达出口需要多少时间？

思路

  • 因为正着做会发生阻塞，我们将这个过程反过来，即刚开始大家都等在出口，然后需要到达自己的位置。
  • 我们让路程时间最长的先走，因为路程时间长的不会阻塞路程时间短的。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n;

void run() {}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem D. Shortest Common Non-Subsequence

Upsolved By Dup4.

题意

给出两个 01 串 s 和 t，现在要构造一个最短的 01 串，使得这个 01 串既不是 s 的子序列也不是 t 的子序列。 要求输出长度最小、其次字典序最小的答案。

思路

  • 假设答案为 n 位，那么答案的前 n - 1 位构成的 01 串肯定是 s 和子序列或者是 t 的子序列。
  • 那么我们倒着 dp，f_{i, j} 表示 s 串的后 i 位，t 串的后 j 位失配的最短长度。
  • 要求字典序最小，我们正着贪心即可。优先放 0。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 4e3 + 10;
constexpr int INF = 0x3f3f3f3f;
int n, lens, lent;
char s[N], t[N];
int h_s[N][2], h_t[N][2];
int g[N][N];

void gao1(char *s, int h[N][2]) {
    int len = strlen(s + 1);
    int nx[2] = {len + 1, len + 1};
    h[len + 1][0] = h[len + 1][1] = len + 1;
    for (int i = len; i >= 0; --i) {
        h[i][0] = nx[0];
        h[i][1] = nx[1];
        if (i < 1)
            break;
        nx[s[i] - '0'] = i;
    }
}

void run() {
    cin >> (s + 1) >> (t + 1);
    lens = strlen(s + 1);
    lent = strlen(t + 1);
    gao1(s, h_s);
    gao1(t, h_t);
    memset(g, 0x3f, sizeof g);
    g[lens + 1][lent + 1] = 0;
    for (int i = lens + 1; i >= 0; --i) {
        for (int j = lent + 1; j >= 0; --j) {
            for (int k = 0; k < 2; ++k) {
                chmin(g[i][j], g[h_s[i][k]][h_t[j][k]] + 1);
            }
        }
    }
    string res = "";
    int i = 0, j = 0;
    for (int o = 1; o <= g[0][0]; ++o) {
        for (int x = 0; x < 2; ++x) {
            int _i = h_s[i][x];
            int _j = h_t[j][x];
            if (g[i][j] == g[_i][_j] + 1) {
                i = _i;
                j = _j;
                res += x + '0';
                break;
            }
        }
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem E. Fair Chocolate-Cutting

Upsolved By -.

题意

思路

Problem F. What Goes Up Must Come Down

Upsolved By Dup4.

题意

给出 n 个数 a_i，现在每次只能交换相邻两个数，问将这个数列调整成只有一个山峰的形状最少需要多少次？

思路

  • 对于一个数来说，最终要么是它左边的数全都小于等于它，要么是它右边的数全都小于等于它。
  • 那么就是它左边比它大的数全都要跨过它到右边，或者右边比它大的数全都要跨过它到左边，我们取 Min 即可。

Problem G. Ranks

Upsolved By -.

题意

思路

Problem H. Colorful Tree

Solved By Dup4. 04:57(+10)

题意

给出一棵树，每个点有一个初始颜色 c_i，有两种操作：

  • U x y，将点 u 的颜色改成 y。
  • Q y, 询问所有颜色为 y 的点组成的虚数的周长。

思路

用 set 维护每种颜色虚树周长即可。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 2e5 + 10;
int n, q, c[N];
ll sum[N];

vector<vector<int>> G;
set<int> se[N];

int fa[N], deep[N], dis[N], sze[N], son[N], top[N], in[N], fin[N];

void dfs(int u) {
    sze[u] = 1;
    son[u] = 0;
    for (auto &v : G[u]) {
        if (v == fa[u])
            continue;
        fa[v] = u;
        deep[v] = deep[u] + 1;
        dis[v] = dis[u] + 1;
        dfs(v);
        sze[u] += sze[v];
        if (!son[u] || sze[v] > sze[son[u]])
            son[u] = v;
    }
}

void gettop(int u, int tp) {
    in[u] = ++*in;
    fin[*in] = u;
    top[u] = tp;
    if (son[u])
        gettop(son[u], tp);
    for (auto &v : G[u]) {
        if (v == fa[u] || v == son[u])
            continue;
        gettop(v, v);
    }
}

int querylca(int u, int v) {
    while (top[u] != top[v]) {
        if (deep[top[u]] < deep[top[v]]) {
            swap(u, v);
        }
        u = fa[top[u]];
    }
    if (deep[u] > deep[v])
        swap(u, v);
    return u;
}

int querydis(int u, int v) {
    return dis[u] + dis[v] - 2 * dis[querylca(u, v)];
}

void add(int col, int x) {
    if (SZ(se[col]) == 1) {
        auto pos = se[col].begin();
        sum[col] += querydis(x, fin[*pos]) * 2;
    } else if (SZ(se[col]) > 1) {
        auto nx = se[col].upper_bound(in[x]);
        if (nx == se[col].end())
            nx = se[col].begin();
        auto pre = prev(nx);
        if (nx == se[col].begin())
            pre = prev(se[col].end());
        sum[col] -= querydis(fin[*nx], fin[*pre]);
        sum[col] += querydis(x, fin[*nx]);
        sum[col] += querydis(x, fin[*pre]);
    }
    se[col].insert(in[x]);
}

void del(int col, int x) {
    if (SZ(se[col]) <= 2) {
        sum[col] = 0;
    } else {
        auto pos = se[col].lower_bound(in[x]);
        auto nx = next(pos);
        auto pre = prev(pos);
        if (pos == se[col].begin())
            pre = prev(se[col].end());
        if (nx == se[col].end())
            nx = se[col].begin();
        sum[col] -= querydis(x, fin[*nx]);
        sum[col] -= querydis(x, fin[*pre]);
        sum[col] += querydis(fin[*nx], fin[*pre]);
    }
    se[col].erase(in[x]);
}

void run() {
    rd(n);
    G.clear();
    G.resize(n + 1);
    for (int i = 1, u, v; i < n; ++i) {
        rd(u, v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    *in = 0;
    deep[1] = dis[1] = 0;
    fa[1] = 1;
    dfs(1);
    gettop(1, 1);
    memset(sum, 0, sizeof sum);
    for (int i = 1; i <= n; ++i) {
        rd(c[i]);
        add(c[i], i);
    }
    rd(q);
    char op[5];
    for (int i = 1, x, y; i <= q; ++i) {
        cin >> op;
        if (op[0] == 'U') {
            rd(x, y);
            if (c[x] == y)
                continue;
            del(c[x], x);
            c[x] = y;
            add(c[x], x);
        } else {
            rd(y);
            if (se[y].empty())
                pt(-1);
            else
                pt(sum[y] / 2);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem I. Sixth Sense

Upsolved By -.

题意

思路

Problem J. Jokewithpermutation

Solved By Dup4 & groggy_. 01:14(+)

题意

给出一个字符串，这个字符串是一个全排列中每个数字连接起来的。

现在要求将数字分开，还原成全排列序列。

思路

可以根据长度得到 n，然后暴力搜索就行了。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n, m, ok, use[110];
char s[N];

vector<int> res;

int toInt(char ch) {
    return ch - '0';
}

void dfs(vector<int> vec, int cur) {
    if (ok)
        return;
    if (cur == n + 1) {
        res = vec;
        ok = 1;
        return;
    }
    if (ok)
        return;
    int x = toInt(s[cur]);
    if (x >= 1 && x <= m && use[x] == 0) {
        use[x] = 1;
        vec.push_back(x);
        dfs(vec, cur + 1);
        vec.pop_back();
        use[x] = 0;
    }
    if (ok)
        return;
    if (cur < n && x >= 1) {
        x = x * 10 + toInt(s[cur + 1]);
        if (x <= m && use[x] == 0) {
            use[x] = 1;
            vec.push_back(x);
            dfs(vec, cur + 2);
            vec.pop_back();
            use[x] = 0;
        }
    }
}

void run() {
    cin >> (s + 1);
    //	cout << (s + 1) << endl;
    n = strlen(s + 1);
    if (n <= 9)
        m = 9;
    else {
        m = 9 + (n - 9) / 2;
    }
    //	dbg(m);
    ok = 0;
    memset(use, 0, sizeof use);
    dfs(vector<int>(), 1);
    //	dbg(ok);
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}
Last update: March 23, 2022
Created: March 23, 2022
Back to top