Skip to content

第十七届中国计量大学程序设计竞赛

Contents

Contest Info

Practice Link

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

Solutions

Problem A

Solved By Dup4. 01:49(+)

题意

抽象一下，就是树上的 DFS序 上区间更新，单点查询。

思路

随便搞个数据结构维护一下。

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, in[N], out[N];
vector<vector<int>> G;

struct BIT {
    ll a[N];
    void init() {
        memset(a, 0, sizeof a);
    }
    void update(int x, ll v) {
        for (; x < N; x += x & -x) a[x] += v;
    }
    ll query(int x) {
        ll res = 0;
        for (; x; x -= x & -x) res += a[x];
        return res;
    }
    void update(int l, int r, ll v) {
        //	dbg(l, r, v);
        if (l > r)
            return;
        update(l, v);
        update(r + 1, -v);
    }
} bit;

void dfs(int u) {
    in[u] = ++*in;
    for (auto &v : G[u]) {
        dfs(v);
    }
    out[u] = *in;
}

void run() {
    rd(n, m);
    G.clear();
    G.resize(n + 1);
    bit.init();
    int rt = -1;
    for (int i = 1, fa; i <= n; ++i) {
        rd(fa);
        if (fa)
            G[fa].push_back(i);
        else
            rt = i;
    }
    *in = 0;
    //	dbg(rt);
    dfs(rt);
    //	for (int i = 1; i <= n; ++i) dbg(i, in[i], out[i]);
    for (int i = 1, u, x, v; i <= m; ++i) {
        rd(u, x, v);
        pt(bit.query(in[v]));
        bit.update(in[u], out[u], x);
    }
}

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 B

Solved By Dup4. 01:16(+)

题意

给出两个 01 串 A 和 B，每次可以执行的操作有：

  • 将所有位都变成 0。
  • 翻转一个后缀的状态。

问将 A 变成 B 最少的操作步骤。

思路

如果需要执行第一种操作，显然肯定是第一次执行。

根据这个讨论两种情况，发现只用第二种操作，最少步数是固定的，肯定是从前往后去翻转，因为一次翻转只会影响后缀，前面的位是不会变的。

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;
string a, b;

vector<int> gao() {
    int f = 0;
    vector<int> res;
    for (int i = 0; i < SZ(a); ++i) {
        int _a = a[i] - '0';
        int _b = b[i] - '0';
        if (_a != (_b ^ f)) {
            f ^= 1;
            res.push_back(i + 1);
        }
    }
    return res;
}

vector<int> gao1() {
    int f = 0;
    vector<int> res;
    res.push_back(0);
    for (int i = 0; i < SZ(a); ++i) {
        int _a = a[i] - '0';
        int _b = 0;
        if (_a != (_b ^ f)) {
            f ^= 1;
            res.push_back(i + 1);
        }
    }
    return res;
}

void run() {
    cin >> a >> b;
    swap(a, b);
    vector<vector<int>> vec(2);
    vec[0] = gao();
    vec[1] = gao1();
    if (SZ(vec[0]) > SZ(vec[1]))
        vec[0] = vec[1];
    pt(vec[0]);
}

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 C

Solved By Dup4. 01:03(+)

题意

要烤牛排，有 n 个步骤，需要在每个步骤烤制一分钟。

第 i 个步骤有温度要求 [l_i, r_i]，当烤肉机的温度在这个范围内才能烤制一分钟并且到下一个步骤。

每分钟可以将烤肉机的温度升高或者降低 1 度。

刚开始的温度是 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 = 1e5 + 10;
int n;
pII a[N];

void run() {
    rd(n);
    for (int i = 1; i <= n; ++i) rd(a[i].fi, a[i].se);
    ll res = 0;
    ll t = 0;
    for (int i = 1; i <= n; ++i) {
        if (t < a[i].fi) {
            res += a[i].fi - t;
            t = a[i].fi;
        } else if (t > a[i].se) {
            res += t - a[i].se;
            t = a[i].se;
        }
        ++res;
    }
    pt(res);
}

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

Solved By ltslts. 02:55(+)

题意

取石子，每次只能选择一堆，选取不少于上次拿的数。然后最后如果有剩余的石子，最后一个人必须取完。取完的人输，问先手第一次取多少个才能必赢，如果不能输出 -1.

思路

  • 如果最大数量的堆有奇数个，那么先手取最大的数量即必胜策略，以此类推，降序的石堆中如果有某个数量是奇数，那么先手的即取该数量的石子。
  • 特殊的，如果所有数量的石堆都是偶数个，那么先手必胜，如果先手取的是最小数量的石堆，并且最小数量的石堆个数为奇数，那么先手必败。
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, a[N];

void run() {
    rd(n);
    for (int i = 1; i <= n; ++i) rd(a[i]);
    sort(a + 1, a + 1 + n);
    reverse(a + 1, a + 1 + n);
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == 1 || a[i] == a[i - 1])
            ++cnt;
        else {
            if (cnt & 1)
                return pt(a[i - 1]);
            cnt = 1;
        }
    }
    if (cnt & 1)
        return pt(-1);
    pt(a[n]);
}

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 E

Solved By groggy_. 03:53(+)

题意

一条链，每个节点数字表示节点附属的子节点，末尾节点一定包含一个子节点。 两个人轮流从末尾节点的子节点取若干个，当末尾节点无子节点时，末尾节点的父亲节点成为新的末尾节点。 最后拿完的人输，求先手者能否胜利。

思路

根据子节点是否唯一可以判断是否改变先后手，递推即可。

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, a[N];

void run() {
    rd(n);
    for (int i = 1; i <= n; ++i) {
        a[i] = nextInt() + 1;
    }
    int f = 1;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 1)
            f ^= 1;
        else
            f = 1;
    }
    if (f)
        pt("these are sweet grapes");
    else
        pt("these are sour grapes");
}

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 F

Solved By Dup4. 00:13(+)

题意

签到。

思路

Code 
print('e')

Problem G

Upsolved By Dup4.

题意

给出一张 n 个点 m 条边的无向图，每个点有一种颜色 a_i，有 q 次操作：

  • 1 u x, 将点 u 的颜色染成 x。
  • 2 u，询问如果将点 u 重新染色，并且不和点 u 相邻的任意一点的颜色一样，那么可染色的颜色中，编号最小的是多少？

思路

  • 根据度数分成大点和小点。
  • 显然小点的答案很好算，复杂度 \mathcal{O}(\sqrt{n})。
  • 对于大点，只有 \sqrt{n} 个大点，对于每个大点都维护一个 BitSet，然后对于每次更新颜色都修改一下大点的 BitSet 中的对应位置。
    • 我不知道 C++ 中的 BitSet 怎么实现的，也不知道修改单点信息的复杂度是多少，但是如果自己写一个 BitSet，修改单点信息是能够做到 \mathcal{O}(1) 的。
    • 对于大点答案的查询，复杂度是 \mathcal{O}(\frac{n}{w})。
  • 所以最优情况下，能够做到 \displaystyle \mathcal{O} (\frac{n^2}{w} + n \cdot \sqrt{n})。
  • 其实也可以用树状数组来维护，查询的时候二分即可，这样复杂度是 \mathcal{\log^2 n}，如果用线段树的话，查询复杂度能够做到 \mathcal{o}(\log n)。但是更新的时候线段树常数大，树状数组常数小。感觉没什么差别。这样的话，复杂度能够做到 \mathcal{O}(n \cdot \sqrt{n} \cdot \log n + n \cdot \log^2 n)。
  • 我感觉题意有点问题： > * Type 1:1 u x(0 \leq x \leq 10^9)–Change the colour of area u to x. > * Type 2:2 u–At this time, the little beauty wants to draw area u, YHH will pass a brush according to the above rules, which number is what you should print.
    • 说实话，从这两句话我看不出第 2 种操作后也需要将 u 的颜色更改为询问的答案，但是实际上是要这么做的，但是这好像给「强制在线」提供了一种比较好的思路。
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;
constexpr int S = 450;
int n, m, q, a[N], f[N], id[N], fid[N], sze[N];
bool isBig[N];
vector<vector<int>> G, T, H;
bitset<N> b[2 * (N / S) + 10];

void run() {
    rd(n, m);
    memset(isBig, 0, sizeof isBig);
    G.clear();
    G.resize(n + 1);
    T.clear();
    T.resize(n + 1);
    for (int i = 1; i <= n; ++i) rd(a[i]);
    for (int i = 1, u, v; i <= m; ++i) {
        rd(u, v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    *id = 0;
    H.clear();
    H.resize(1);
    for (int i = 1; i <= n; ++i) {
        if (SZ(G[i]) > S) {
            isBig[i] = 1;
            id[i] = ++*id;
            fid[*id] = i;
            sze[*id] = SZ(G[i]) + 5;
            b[*id].set();
            H.push_back(vector<int>(sze[*id], 0));
        }
    }
    for (int u = 1; u <= n; ++u) {
        for (auto &v : G[u]) {
            if (isBig[v]) {
                int _v = id[v];
                T[u].push_back(_v);
                int x = a[u];
                if (x < sze[_v]) {
                    ++H[_v][x];
                    if (H[_v][x] == 1)
                        b[_v][x] = 0;
                }
            }
        }
    }
    rd(q);
    for (int i = 1, op, u, x; i <= q; ++i) {
        rd(op, u);
        if (op == 1) {
            rd(x);
        } else {
            if (isBig[u]) {
                x = b[id[u]]._Find_first();
            } else {
                int _sze = SZ(G[u]) + 5;
                for (int i = 0; i <= _sze; ++i) f[i] = 0;
                for (auto &v : G[u]) {
                    if (a[v] < _sze) {
                        f[a[v]] = 1;
                    }
                }
                for (int i = 0; i <= _sze; ++i)
                    if (!f[i]) {
                        x = i;
                        break;
                    }
            }
            pt(x);
        }
        int pre = a[u];
        a[u] = x;
        for (auto &it : T[u]) {
            if (pre < sze[it]) {
                --H[it][pre];
                if (H[it][pre] == 0)
                    b[it][pre] = 1;
            }
            if (x < sze[it]) {
                ++H[it][x];
                if (H[it][x] == 1)
                    b[it][x] = 0;
            }
        }
    }
}

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 H

Solved By Dup4. 01:27(+)

题意

思路

线段树区间更新，全局查询。

可能有更简短的做法。

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;
constexpr int INF = 0x3f3f3f3f;
int n, m;
int a[N];

struct SEG {
    struct node {
        int Max, lazy;
        node() {
            Max = 0, lazy = INF;
        }
        void up() {
            Max = 0;
            lazy = 0;
        }
        node operator+(const node &other) const {
            node res = node();
            res.Max = max(Max, other.Max);
            return res;
        }
    } t[N << 2];
    void down(int id) {
        int lazy = t[id].lazy;
        if (lazy != INF) {
            t[id << 1].up();
            t[id << 1 | 1].up();
        }
    }
    void build(int id, int l, int r) {
        t[id] = node();
        if (l == r) {
            t[id].Max = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    void update(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) {
            t[id].Max = t[id].lazy = 0;
            return;
        }
        int mid = (l + r) >> 1;
        down(id);
        if (ql <= mid)
            update(id << 1, l, mid, ql, qr);
        if (qr > mid)
            update(id << 1 | 1, mid + 1, r, ql, qr);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
} seg;

void run() {
    rd(n, m);
    for (int i = 1; i <= n; ++i) rd(a[i]);
    seg.build(1, 1, n);
    for (int i = 1, l, r; i <= m; ++i) {
        rd(l, r);
        seg.update(1, 1, n, l, r);
        pt(seg.t[1].Max);
    }
}

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 I

Solved By all. 01:56(+6)

题意

给出 n 个点，问你是否有一种方案，使得这 n 个点不重叠，并且任意两点的中垂线之间都至少有一个点。

思路

$ n geq 3 $ 时答案为 Yes。

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() {
    rd(n);
    if (n >= 3)
        pt("Yes");
    else
        pt("No");
    //	if (n == 1) return pt("No");
    //	if (n % 2 || n == 4 || n == 6) pt("Yes");
    //	else pt("No");
    //	if (n != 1 && (n < 3 || n > 7)) pt("No");
    //	else pt("Yes");
}

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 J

Solved By Dup4. 03:22(+1)

题意

给出 n 个人，要求组成不超过两支队伍，并且每个人都要在一支队伍中。现在给出 m 条关系 (a_i, b_i, t_i)，表示 a_i 和 b_i 要想在一支队伍的话，至少需要 t_i 的时间去磨合。

如果对于一对 a_j, b_j 没有在 m 条关系中给出，可以理解为这两个人不需要时间磨合。

一支队伍的磨合时间为队伍中任意两人所需磨合时间的最大值。

现在问所有人都有队伍并且磨合完毕的最少时间是多少。

思路

二分答案 x，然后考虑补图，即保留所有边权大于 x 的边，在补图中连边等价于这两个人不能在一个队伍里，那么二分图染色判断是否是二分图就可以了。

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, col[N];
vector<vector<int>> G;

struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
} e[N];

int res;
void dfs(int u) {
    for (auto &v : G[u]) {
        if (col[v] != -1) {
            if (col[u] == col[v])
                res = 0;
        } else {
            col[v] = col[u] ^ 1;
            dfs(v);
        }
    }
}

bool ok(int x) {
    G.clear();
    G.resize(n + 1);
    memset(col, -1, sizeof col);
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if (w > x) {
            G[u].push_back(v);
            G[v].push_back(u);
        }
    }
    res = 1;
    for (int i = 1; i <= n; ++i)
        if (col[i] == -1)
            dfs(i);
    return res;
}

void run() {
    rd(n, m);
    for (int i = 1; i <= m; ++i) {
        rd(e[i].u, e[i].v, e[i].w);
    }
    int l = 0, r = 1e9, res = r;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (ok(mid)) {
            r = mid - 1;
            res = mid;
        } else {
            l = mid + 1;
        }
    }
    pt(res);
}

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 K

Solved By ltslts and Dup4. 01:33(+2)

题意

给出若干个身份证号，判断有多少个子串是合法的回文日期。

思路

暴力。

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;
string s;

bool isYEAP(int year) {
    if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
        return true;
    return false;
}

int Mon[2][13] = {
        0,
        31,
        28,
        31,
        30,
        31,
        30,
        31,
        31,
        30,
        31,
        30,
        31,
        0,
        31,
        29,
        31,
        30,
        31,
        30,
        31,
        31,
        30,
        31,
        30,
        31,
};

int ok(string t) {
    string _t = t;
    reverse(all(_t));
    if (t != _t)
        return false;
    int year = atoi(t.substr(0, 4).c_str());
    int month = atoi(t.substr(4, 2).c_str());
    int day = atoi(t.substr(6, 2).c_str());
    if (year < 1 || month < 1 || day < 1)
        return false;
    if (month > 12)
        return false;
    if (day > Mon[isYEAP(year)][month])
        return false;
    return true;
}

void run() {
    if (s == "#")
        return;
    stringstream ss;
    ss.clear();
    ss.str("");
    ss << s;
    int res = 0;
    while (ss >> s) {
        for (int i = 0; i + 8 <= SZ(s); ++i) {
            //	cout << s.substr(i, 8) << endl;
            res += ok(s.substr(i, 8));
        }
    }
    pt(res);
}

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

Problem L

Solved By Dup4. 04:29(+1)

题意

给出若干个身份证号，判断有多少个子序列是合法的回文日期。

思路

在题意限定日期范围内，合法回文日期只有 12 个，那么直接转化成给出两个字符串 S 和 T，问 S 中有多少个子序列是 T，直接 DP 即可，时间复杂度 \mathcal{O}(|S||T|)。

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> obj;
string s, t;
int f[N][10];

bool isYEAP(int year) {
    if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
        return true;
    return false;
}

int Mon[2][13] = {
        0,
        31,
        28,
        31,
        30,
        31,
        30,
        31,
        31,
        30,
        31,
        30,
        31,
        0,
        31,
        29,
        31,
        30,
        31,
        30,
        31,
        31,
        30,
        31,
        30,
        31,
};

int ok(string t) {
    string _t = t;
    reverse(all(_t));
    if (t != _t)
        return false;
    int year = atoi(t.substr(0, 4).c_str());
    int month = atoi(t.substr(4, 2).c_str());
    int day = atoi(t.substr(6, 2).c_str());
    if (year < 1 || month < 1 || day < 1)
        return false;
    if (month > 12)
        return false;
    if (day > Mon[isYEAP(year)][month])
        return false;
    return true;
}

inline int calc(string s, string t) {
    int lens = SZ(s), lent = SZ(t);
    for (int i = 0; i <= lens; ++i) f[i][0] = 1;
    for (int i = 1; i <= lens; ++i) {
        for (int j = 1; j <= lent; ++j) {
            f[i][j] = f[i - 1][j];
            if (s[i - 1] == t[j - 1]) {
                chadd(f[i][j], f[i - 1][j - 1]);
            }
        }
    }
    return f[lens][lent];
}

void run() {
    if (s == "#")
        return;
    string _s = "";
    for (auto &ch : s)
        if (ch != ' ')
            _s += ch;
    int res = 0;
    for (auto &it : obj) chadd(res, calc(_s, it));
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    for (int i = 2000; i <= 2099; ++i) {
        for (int j = 1; j <= 12; ++j) {
            for (int k = 1; k <= 31; ++k) {
                char t[10];
                sprintf(t, "%04d%02d%02d", i, j, k);
                //	string _t = string(t);
                //	cout << _t << endl;
                if (ok(string(t))) {
                    obj.push_back(string(t));
                }
            }
        }
    }
    while (getline(cin, s)) run();
    return 0;
}

Problem M

Solved By . 0:00(+)

题意

思路

Problem N

Solved By . 0:00(+)

题意

思路

Last update: March 24, 2022
Created: March 23, 2022
Back to top