2022年沈阳理工大学-“理工杯”程序设计竞赛个人题解

A 这是一个特别难的题目

直接输出答案，复杂度 $O(1)$

let's go

B 相识

贪心的考虑每一位都为 $1$ ，即枚举所有的 $2^n-1$ ，然后判断结果是否合法即可，复杂度 $log(n)$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    i64 n;
    cin >> n;

    int ans = 0;
    static const i64 inf = 1e18;

    for (int i = 1; i < 64; i++) {
        i64 b = (1LL << i) - 1;
        i64 x = n + b, y = n - b;
        if (x > 0 && x <= inf || y > 0 && y <= inf) {
            ans = max(ans, i);
        }
    }

    cout << ans << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

C 散步

暴力 DFS 一下即可，复杂度不超过 $O((n+m) \cdot log(n+m))$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

class Z {
    using i64 = long long;
    static const i64 Mod = 20130744;
public:
    i64 num;
    Z() = default;
    Z(i64 _num) : num((_num % Mod + Mod) % Mod) {}
    i64 val() const {
        return num;
    }
    Z &operator = (i64 b) {
        return *this = Z(b);
    }
    friend bool operator < (Z a, Z b) {
        return a.num < b.num;
    }
    friend bool operator >(Z a, Z b) {
        return a.num > b.num;
    }
    friend bool operator <=(Z a, Z b) {
        return a.num <= b.num;
    }
    friend bool operator>=(Z a, Z b) {
        return a.num >= b.num;
    }
    friend bool operator==(Z a, Z b) {
        return a.num == b.num;
    }
    friend Z operator + (Z a, Z b) {
        return Z((a.num + b.num) % Mod);
    }
    friend Z &operator += (Z &a,Z b) {
        return a = a + b;
    }
    friend Z operator + (Z a, i64 b) {
        return a + Z(b);
    }
    friend Z &operator += (Z &a, i64 b) {
        return a = a + b;
    }
    friend Z &operator ++ (Z &a) {
        return a += 1;
    }
    friend Z operator ++ (Z &a, int) {
        Z copy(a);
        a += 1;
        return copy;
    }
    friend Z operator - (Z a, Z b) {
        return Z(((a.num - b.num) % Mod + Mod) % Mod);
    }
    friend Z &operator -= (Z &a, Z b) {
        return a = a - b;
    }
    friend Z operator - (Z a, i64 b) {
        return a - Z(b);
    }
    friend Z &operator -= (Z &a, i64 b) {
        return a = a - b;
    }
    friend Z &operator -- (Z &a) {
        return a -= 1;
    }
    friend Z operator -- (Z &a, int) {
        Z copy(a);
        a -= 1;
        return copy;
    }
    friend Z operator * (Z a, Z b) {
        return Z((long long)a.num * b.num % Mod);
    }
    friend Z &operator *= (Z &a, Z b) {
        return a = a * b;
    }
    friend Z operator * (Z a, i64 b) {
        return a * Z(b);
    }
    friend Z &operator *= (Z &a, i64 b) {
        return a = a * b;
    }
    Z inv() {
        i64 ans = 1;
        i64 a = num;
        i64 b = Mod - 2; 
        while (b) {
            if (b & 1) ans = ans * a % Mod;
            a = a * a % Mod;
            b >>= 1;
        }
        return Z(ans);
    }
    friend Z operator / (Z a, Z b) {
        return a * b.inv();
    }
    friend Z &operator /= (Z &a, Z b) {
        return a = a / b;
    }
    friend Z operator / (Z a, i64 b) {
        return a / Z(b);
    }
    friend Z &operator /= (Z &a, i64 b) {
        return a = a / b;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        int v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    map<pair<int, int>, int> mp;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        mp[{x, y}] += z;
        mp[{y, x}] += z;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }

    Z ans = 0;
    auto dfs = [&](auto &&self, int u, int v, Z add) -> void {
        if (u == n) {
            ans += add;
            return;
        }
        for (auto c: adj[u]) {
            if (c == v || c < u) {
                continue;
            }
            self(self, c, u, add * mp[{c, u}]);
        }
    };

    dfs(dfs, 1, -1, Z(1));

    cout << ans << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

D 看书

暴力计算锐角和非锐角的个数，每个锐角三角形对锐角的贡献数量为 $3$ ，直角三角形和钝角三角形对锐角的贡献数量为 $2$ 。设锐角的数量为 $u$ ，钝角的数量为 $v$ ，答案即为 $\frac{u-2v}{3}$ 。

对每个点做极角排序，然后用 Two Pointers 的经典方法，即可做到 $O(n^2 \ log(n))$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n;
    cin >> n;
    vector<double> x(n + 1), y(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    static const double pi = acos(-1.0);
    vector<double> ang(n * 2 + 1);

    i64 u = 0, v = 0;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;

        for (int j = 1; j <= n; j++) {
            if (i == j) {
                continue;
            }

            ang[++cnt] = atan2(y[i] - y[j], x[i] - x[j]);

            if (ang[cnt] < 0) {
                ang[cnt] += 2. * pi;
            }
        }

        sort(ang.begin() + 1, ang.begin() + cnt + 1);

        for (int j = 1; j <= cnt; j++) {
            ang[j + cnt] = ang[j] + 2. * pi;
        }

        i64 l = 1, r = 1;
        i64 len = 1;
        for (int j = 1; j <= cnt; j++) {
            while (r < 2LL * cnt && ang[r] - ang[j] < pi) {
                r++;
            }
            while (l < 2LL * cnt && ang[l] - ang[j] < 0.5 * pi) {
                l++;
            }
            while (len < 2LL * cnt && ang[j] == ang[len]) {
                len++;
            }
            
            u += l - len;
            v += r - l;
        }
    }
    
    i64 ans = (u - 2LL * v) / 3;
    cout << ans << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

E 赏月

结论题，答案为 $\frac{1}{\frac{n}{100} \cdot (1-\frac{p}{100})(1-\frac{q}{100})}$ ，推断不难。复杂度 $O(1)$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    double n, p, q;
    cin >> n >> p >> q;

    n /= 100;
    p /= 100;
    q /= 100;
    p = 1. - p;
    q = 1. - q;

    double ans = 1. / (n * p * q);

    cout << fixed << setprecision(10);

    cout << ans << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

F 礼物

暴力枚举所有的选购礼物的情况，然后判断合法性即可，复杂度 $O(2^n)$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> v(n), w(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    auto check = [&](int u) -> bool {
        while (u) {
            int x = u % 10;
            if (x != 0 && x != 1 && x != 3 && x != 7 && x != 9) {
                return false;
            }
            u /= 10;
        }
        return true;
    };

    int ans = 0;
    auto dfs = [&](auto &&self, int u, int cur, int V) -> void {
        if (check(cur) && V <= m){
            ans = max(ans, cur);
        }
        if (u == n) {
            return;
        }
        self(self, u + 1, cur + w[u], V + v[u]);
        self(self, u + 1, cur, V);
    };

    dfs(dfs, 0, 0, 0);

    cout << ans << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

G 开心度

二分开心度，用 Segment tree 维护区间加减法，然后判断是否存在连续的长度至少为 $2$ 的和为非负数的区间即可，变成了一个简单的 DP 问题。复杂度 $O(n \ log^2(n))$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class Info, class Tag>
struct LazySegmentTree {
    const int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree(int n) : n(n), info(4 << std::__lg(n)), tag(4 << std::__lg(n)) {}
    LazySegmentTree(std::vector<Info> init) : LazySegmentTree(init.size()) {
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, {-(info[p].min + 1) / 2});
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m, r);
        pull(p);
    }
    void half() {
        half(1, 0, n);
    }
};
 
struct Tag {
    double add = 0;
    void apply(Tag t) {
        add += t.add;
    }
};
 
struct Info {
    double Act = 1;
    double Sum = 0;
    void apply(Tag t) {
        Sum += 1. * Act * t.add;
    }
};
 
Info operator+(Info a, Info b) {
    Info c;
    c.Sum = a.Sum + b.Sum;
    c.Act = a.Act + b.Act;
    return c;
}

void solve() {
    int n;
    cin >> n;

    vector<Info> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].Sum;
    }

    LazySegmentTree<Info, Tag> seg(a);
    static const double eps = 1e-4;

    auto check = [&](double u) -> bool {
        seg.rangeApply(0, n, Tag{-u});

        vector<array<double, 2>> dp;
        dp.assign(n, {});

        dp[0][0] = seg.rangeQuery(0, 1).Sum;
        dp[0][1] = -1e9;
        for (int i = 1; i < n; i++) {
            dp[i][0] = seg.rangeQuery(i, i + 1).Sum;
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + seg.rangeQuery(i, i + 1).Sum;
        }

        seg.rangeApply(0, n, Tag{u});

        for (int i = 1; i < n; i++) {
            if (dp[i][1] >= eps) {
                return true;
            }
        }
        return false;
    };

    double l = 0, r = 10001.0;
    while (l <= r) {
        double mid = (l + r) / 2;

        if (check(mid)) {
            l = mid + 0.01;
        } else {
            r = mid - 0.01;
        }
    }

    cout << fixed << setprecision(1);

    cout << l << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

H 旅行

根据要求自定义快排即可，复杂度 $O(n \ logn)$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct g {
    int x, y;
    int z;
    int id;
    int vis;
};

void solve() {
    int n, m;
    cin >> n >> m;

    vector<g> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].x;
    }
    for (int i = 0; i < n; i++) {
        cin >> v[i].y;
    }

    for (int i = 0; i < n; i++) {
        v[i].z = v[i].x + v[i].y;
        v[i].id = i + 1;
        v[i].vis = v[i].x != 0 && v[i].y != 0;
    }

    auto cmp = [&](struct g a, struct g b) -> bool {
        if (a.vis != b.vis) {
            return a.vis > b.vis;
        }

        if (a.z == b.z) {
            return a.id < b.id;

        } else {
            return a.z > b.z;
        }

        return true;
    };

    sort(v.begin(), v.end(), cmp);

    i64 ans = 0;
    for (int i = 0; i < m; i++) {
        ans += v[i].id;
    }

    cout << ans << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

I 奇妙的缘分

暴力统计即可，复杂度不超过 $O(max(n \ log(n), m \ log(m)))$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n, m;
    cin >> n >> m;

    map<int, int> x, y;
    for (int i = 0; i < n; i++) {
        int a = 0, b = 0;
        string s;
        cin >> s;

        int pos = -1;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == '/') {
                pos = j;
                break;
            }
        }
        for (int j = 0; j < pos; j++) {
            a = a * 10 + s[j] - '0';
        }
        for (int j = pos + 1; j < s.size(); j++) {
            b = b * 10 + s[j] - '0';
        }

        if (a == 1 || a == 3 || a == 5 || a == 7 || a == 8 || a == 10 || a == 12) {
            if (b < 0 || b > 31) {
                continue;
            }
        } else if (a == 2) {
            if (b < 0 || b > 29) {
                continue;
            }
        } else if (a == 4 || a == 6 || a == 9 || a == 11) {
            if (b < 0 || b > 30) {
                continue;
            }
        } else {
            continue;
        }
        
        int u = to_string(b).size();
        x[a * pow(10, u) + b]++;
    }

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        y[a]++;
    }

    int ans = 0;

    for (auto &[l, r]: x) {
        if (y.contains(l)) {
            ans += min(r, y[l]);
            y[l] -= min(r, y[l]);
        }
    }

    cout << ans << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

J 爵士

将 $[L,R]$ 转换成 $[0, L-1]$ 和 $[0,R]$ ，设 $DP_{i,j}$ 表示长度为 $i$ ，异或和为 $j$ 的数的个数，分别预处理出不考虑前导 $0$ 和考虑前导 $0$ 的情况下的 $DP_{i,j}$ 数组。

然后考虑计算 $[0,R]$ 上的问题，设 $R$ 的长度为 $K$ ，那么对于所有的 $DP_{i,j} \ \ ( i \in [1,K-1] \ , j \in [0,9] \ )$ ，其贡献都是完整的，直接累加即可。

只需考虑长度为 $K$ 的情况，从高位到低位枚举，设此前已经枚举了 $x$ 位数，这些数的异或和为 $y$ ，分两种情况讨论：

1. 当前位选择的数 $z$ 小于 $R$ 上的对应数位的数，那么对答案的贡献为 $DP_{K-x-1, \ y \ \oplus \ z}$ ，计算结束

2. 否则，置 $y=y \ \oplus \ z$ ，继续往下枚举

上述操作可以通过一次 DFS 计算，此外还注意一些细节问题。

复杂度应该不超过 $O(log^2(n))$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    i64 a, b;
    cin >> a >> b;

    vector<vector<i64>> dp(20, vector<i64> (1 << 4, 0));
    vector<vector<i64>> ndp(20, vector<i64> (1 << 4, 0));

    for (int i = 0; i < 10; i++) {
        dp[1][i] = 1;
    }

    for (int i = 0; i < 10; i++) {
        ndp[1][i] = 1;
    }

    for (int i = 2; i < 20; i++) {
        for (int j = 0; j < (1 << 4); j++) {
            for (int k = 0; k < 10; k++) {
                dp[i][j ^ k] += dp[i - 1][j];
            }
        }
    }

    for (int i = 2; i < 20; i++) {
        for (int j = 0; j < (1 << 4); j++) {
            for (int k = 1; k < 10; k++) {
                ndp[i][j ^ k] += dp[i - 1][j];
            }
        }
    }

    i64 ans = 0;
    vector<int> sep;

    auto dfs = [&](auto &&self, int u, int cur) -> void {
        if (u >= sep.size()) {
            return;
        }

        if (u == sep.size() - 1) {
            for (int i = 0; i <= sep[u]; i++) {
                ans += (cur ^ i) == 0;
            }
            return;
        }

        if (!u) {
            for (int i = 1; i < sep[u]; i++) {
                ans += dp[sep.size() - u - 1][cur ^ i];
            }
            self(self, u + 1, cur ^ sep[u]);

        } else {
            for (int i = 0; i < sep[u]; i++) {
                ans += dp[sep.size() - u - 1][cur ^ i];
            }
            self(self, u + 1, cur ^ sep[u]);
        }
    };

    if (a) {
        a--;
        for (int i = 1; i < to_string(a).size(); i++) {
            ans += ndp[i][0];
        }
        while (a) {
            sep.emplace_back(a % 10);
            a /= 10;
        }
        reverse(sep.begin(), sep.end());

        dfs(dfs, 0, 0);
        ans *= -1;

        sep.clear();
    } 

    for (int i = 1; i < to_string(b).size(); i++) {
        ans += ndp[i][0];
    }
    while (b) {
        sep.emplace_back(b % 10);
        b /= 10;
    }
    reverse(sep.begin(), sep.end());

    dfs(dfs, 0, 0);

    cout << ans << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

K 慢慢来

暴力枚举选择 $a$ 天的次数即可，复杂度 $O(\frac{n}{a})$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int a, b;
    cin >> a >> b;

    int n;
    cin >> n;

    for (int i = 0; i * (a + 1) <= n; i++) {
        int x = n - (i * (a + 1));
        if (x % (b + 1) == 0) {
            cout << "YES" << endl;
            return;
        }
    }

    cout << "NO" << endl;

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}

L 来日方长

按照题意输出图形，复杂度 $O(n^2)$

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'

constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n;
    cin >> n;

    int m = (n * 2 + 1) * 2;

    cout << "be happy" << endl;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n - i + 1; j++) {
            cout << ' ';
        }
        for (int j = 1; j <= 2 * i - 1; j++) {
            cout << "*";
        }
        for (int j = m - 2 * (n + i); j >= 1; j--) {
            cout << ' ';
        }
        for (int j = 1; j <= 2 * i - 1; j++) {
            cout << "*";
        }
        cout << endl;
    }

    for (int i = 1; i <= 2 * n + 1; i++) {
        for (int j = 1; j <= i - 1; j++) {
            cout << ' ';
        }
        for (int j = m - 2 * (i - 1); j >= 1; j--) {
            cout << '*';
        }
        cout << endl;
    }

}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0; 
}