首页 > 编程语言 >石家庄铁道大学第五届程序设计竞赛

石家庄铁道大学第五届程序设计竞赛

时间：2024-08-14 18:55:15浏览次数：13  
标签：cur int 石家庄 i64 -- 铁道 程序设计 void size

链接: https://ac.nowcoder.com/acm/contest/66307#question
\(\\\)

An A-SOUL Ellien Fan F

指定每一位的进制，求 \(A+B\) 的值，直接模拟即可，复杂度 \(O(max(n, \ m))\)，\(n,m\)为字符串的长度。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

void solve() {
    string base;
    cin >> base;

    string A, B;
    cin >> A >> B;

    deque<char> a, b;
    for (int i = 0; i < A.size(); i++) {
        a.push_back(A[i]);
    }
    for (int i = 0; i < B.size(); i++) {
        b.push_back(B[i]);
    }

    while (a.size() < base.size()) {
        a.push_front('0');
    }
    while (b.size() < base.size()) {
        b.push_front('0');
    }

    deque<int> ans;

    int S = 0;
    for (int i = b.size() - 1; i >= 0; i--) {
        int cur = a[i - b.size() + a.size()] - '0' + b[i] - '0' + S;
        int B = base[i - b.size() + base.size()] - '0';
        B = B ? B : 10;
        ans.push_front(cur % B);
        S = cur / B;
    }

    for (int i = a.size() - b.size() - 1; i >= 0; i--) {
        int cur = a[i] - '0' + S;
        int B = base[i] - '0';
        B = B ? B : 10;
        ans.push_front(cur % B);
        S = cur / B;
    }

    assert(S < 10);

    if (S) {
        ans.push_front(S);
    }

    while (ans.size() && !ans[0]) {
        ans.pop_front();
    }

    if (!ans.size()) {
        cout << 0 << endl;
        return;
    }

    for (auto c: ans) {
        cout << c;
    }
    cout << endl;

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

    init();

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

\(\\\)

B 打牌

贪心，降序排序后，每次选择收益最大的一项，复杂度 \(O(n \ logn)\)。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

void solve() {
    cin >> n;

    multiset<i64> p, q;

    for (int i = 0; i < n; i++) {
        cin >> k;
        if (k & 1) {
            p.insert(k);
        } else {
            q.insert(k);
        }
    }

    i64 x = 0, y = 0;

    int check = 1;
    while (p.size() || q.size()) {
        if (check) {
            if (p.size() && q.size()) {
                if (*p.rbegin() <= *q.rbegin()) {
                    x += *q.rbegin();
                    q.extract(*q.rbegin());
                } else {
                    p.extract(*p.rbegin());
                }

            } else if (p.size()) {
                p.extract(*p.rbegin());

            } else {
                x += *q.rbegin();
                q.extract(*q.rbegin());
            }

        } else {
            if (p.size() && q.size()) {
                if (*p.rbegin() >= *q.rbegin()) {
                    y += *p.rbegin();
                    p.extract(*p.rbegin());
                } else {
                    q.extract(*q.rbegin());
                }

            } else if (p.size()) {
                y += *p.rbegin();
                p.extract(*p.rbegin());

            } else {
                q.extract(*q.rbegin());
            }
        }
        check ^= 1;
    }

    if (x > y) {
        cout << "T" << endl;
    } else if (x < y) {
        cout << "X" << endl;
    } else {
        cout << "Tie" << endl;
    }

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

    init();

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

\(\\\)

C BJS and HT

暴力哈希，逆天卡常题。双模和动态都不行，必须单模+静态模，复杂度 \(O(max(N*strlen^2, \ 1e8))\)。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

constexpr i64 mod = 998244353, P = 131;

template<const long long N>
struct StringHash {
    using i64 = long long;
    array<i64, N> a;
    array<i64, N> Phs;
    StringHash() {
        init(N - 1);
    }
    void work(const char *s) {  
        i64 n = strlen(s);
        for (int i = 0; i < n; ++i) {
            Phs[i + 1] = (Phs[i] * P + s[i]) % mod;
        }
    }
    i64 PreHash(int l, int r) {
        if (l > r) {
            return -1;
        }
        i64 res = (Phs[r] - Phs[l - 1] * a[r - l + 1] % mod + mod) % mod;
        return res;
    };
    void init(int n) {
        a[0] = 1;
        for (int i = 0; i < n; ++i) {
            a[i + 1] = a[i] * P % mod;
        }
    }
};

constexpr int N = 5e5 + 5;
char b[N], h[N];
StringHash<N> p, q;

void solve() {
    cin >> n;
    int ans = 0;

    auto check = [&](i64 x, i64 y) -> bool {
        if (x == -1 || y == -1) {
            return true;
        }
        return x == y;
    };

    while (n--) {
        cin >> b >> h >> k;
        
        if (strlen(b) != strlen(h) || k > strlen(b)) {
            continue;
        }
        
        p.work(b);
        q.work(h);

        for (int i = 0; i < strlen(b) - k + 1; i++) {
            if (b[i] != h[0]) {
                continue;
            }
            if (!check(p.PreHash(i + 1, i + k), q.PreHash(1, k))) {
                continue;
            }
            if (!check(p.PreHash(1, i), q.PreHash(k + 1, k + i))) {
                continue;
            }
            if (!check(p.PreHash(i + k + 1, strlen(b)), q.PreHash(i + k + 1, strlen(h)))) {
                continue;
            }
            ans++;
            break;
        }
    }

    cout << ans << endl;

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

    init();

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

\(\\\)

D F爱玩炉石传说

判断若干个给定的数能够构成一个 \([1,\ ranges::max\{a\}]\) 的排列，用 \(map\) 枚举。复杂度 \(O(n \ logn)\)。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

void solve() {
    cin >> n;

    vector<int> p(n);
    map<int, bool> mp;
    int mx = -1;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        mx = max(mx, p[i]);
        mp[p[i]] = true;
    }

    for (int i = 1; i < mx; i++) {
        if (mp.find(i) == mp.end()) {
            cout << "Nevermind, just use the Twisting Nether." << endl;
            return;
        }
    }

    cout << "This is a textbook-like blasphemy!" << endl;

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

    init();

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

\(\\\)

E A+B Problem

非常浪费时间的高精度浮点数模拟，复杂度 \(O(max(n, \ m))\)，\(n,m\)为字符串的长度。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

void solve() {
    string a, b;
    while (cin >> a >> b && a != "-1") {
        int p = -1, q = -1;
        for (int i = 0; i < a.size(); i++) {
            if (a[i] == '.') {
                p = i;
                break;
            }
        }
        for (int i = 0; i < b.size(); i++) {
            if (b[i] == '.') {
                q = i;
                break;
            }
        }

        if (p != -1 && q != -1) {
            deque<int> in, on;
            int l = a.size() - p - 1, r = b.size() - q - 1;
            if (l < r) {
                swap(a, b);
                swap(l, r);
                swap(p, q);
            }

            for (int i = a.size() - 1; i > a.size() - l + r - 1; i--) {
                on.push_front(a[i] - '0');
            }

            int S = 0;

            for (int i = a.size() - l + r - 1; i > p; i--) {
                int j = b.size() + i - a.size() + l - r;
                int cur = a[i] - '0' + b[j] - '0' + S;
                on.push_front(cur % 10);
                S = cur / 10;
            }

            if (p < q) {
                swap(a, b);
                swap(p, q);
            }

            for (int i = p - 1; i > p - 1 - q; i--) {
                int j = q - 1 + i - p + 1;
                int cur = a[i] - '0' + b[j] - '0' + S;
                in.push_front(cur % 10);
                S = cur / 10;
            }

            for (int i = p - 1 - q; i >= 0; i--) {
                int cur = a[i] - '0' + S;
                in.push_front(cur % 10);
                S = cur / 10;
            }

            if (S) {
                in.push_front(S);
            }

            for (auto c: in) {
                cout << c;
            }

            int mx = 0;
            for (auto c: on) {
                mx = max(mx, c);
            }

            if (!on.size() || !mx) {
                cout << endl;
                continue;
            }

            deque<int> on2;
            for (int i = on.size() - 1; i >= 0; i--) {
                if (on[i]) {
                    for (int j = i; j >= 0; j--) {
                        on2.push_front(on[j]);
                    }
                    break;
                }
            }

            cout << ".";
            for (auto c: on2) {
                cout << c;
            }
            cout << endl;

        } else if (q != -1) {
            deque<int> in, on;
            for (int i = q + 1; i < b.size(); i++) {
                on.push_back(b[i] - '0');
            }

            int mx = 0;
            for (auto c: on) {
                mx = max(mx, c);
            }

            while (b.size() > q) {
                b.pop_back();
            }

            if (a.size() < b.size()) {
                swap(a, b);
            }

            int S = 0;
            for (int i = b.size() - 1; i >= 0; i--) {
                int j = a.size() + i - b.size();
                int cur = a[j] - '0' + b[i] - '0' + S;
                in.push_front(cur % 10);
                S = cur / 10;
            }

            for (int i = a.size() - b.size() - 1; i >= 0; i--) {
                int cur = a[i] - '0' + S;
                in.push_front(cur % 10);
                S = cur / 10;
            }

            if (S) {
                in.push_front(S);
            }

            for (auto c: in) {
                cout << c;
            }

            if (!on.size() || !mx) {
                cout << endl;
                continue;
            }

            deque<int> on2;
            for (int i = on.size() - 1; i >= 0; i--) {
                if (on[i]) {
                    for (int j = i; j >= 0; j--) {
                        on2.push_front(on[j]);
                    }
                    break;
                }
            }

            cout << ".";
            for (auto c: on2) {
                cout << c;
            }
            cout << endl;

        } else if (p != -1) {
            deque<int> in, on;
            for (int i = p + 1; i < a.size(); i++) {
                on.push_back(a[i] - '0');
            }

            int mx = 0;
            for (auto c: on) {
                mx = max(mx, c);
            }

            while (a.size() > p) {
                a.pop_back();
            }

            if (a.size() < b.size()) {
                swap(a, b);
            }

            int S = 0;
            for (int i = b.size() - 1; i >= 0; i--) {
                int j = a.size() + i - b.size();
                int cur = a[j] - '0' + b[i] - '0' + S;
                in.push_front(cur % 10);
                S = cur / 10;
            }

            for (int i = a.size() - b.size() - 1; i >= 0; i--) {
                int cur = a[i] - '0' + S;
                in.push_front(cur % 10);
                S = cur / 10;
            }

            if (S) {
                in.push_front(S);
            }

            for (auto c: in) {
                cout << c;
            }

            if (!on.size() || !mx) {
                cout << endl;
                continue;
            }

            deque<int> on2;
            for (int i = on.size() - 1; i >= 0; i--) {
                if (on[i]) {
                    for (int j = i; j >= 0; j--) {
                        on2.push_front(on[j]);
                    }
                    break;
                }
            }

            cout << ".";
            for (auto c: on2) {
                cout << c;
            }
            cout << endl;
 
        } else {
            deque<int> in;
            if (a.size() < b.size()) {
                swap(a, b);
            }

            int S = 0;
            for (int i = b.size() - 1; i >= 0; i--) {
                int j = a.size() + i - b.size();
                int cur = a[j] - '0' + b[i] - '0' + S;
                in.push_front(cur % 10);
                S = cur / 10;
            }

            for (int i = a.size() - b.size() - 1; i >= 0; i--) {
                int cur = a[i] - '0' + S;
                in.push_front(cur % 10);
                S = cur / 10;
            }

            if (S) {
                in.push_front(S);
            }

            for (auto c: in) {
                cout << c;
            }
            cout << endl;

        }
    }

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

    init();

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

\(\\\)

F 懒虫读诗

树形 \(dp\)，原题为无根树，会形成森林，做起来比较困难，考虑新增一个结点权值为 \(0\) 的零结点作为树的根，可视为有根树中每个结点最多有一个父亲结点。

考虑 \(dp(i, \ j, \ k)\) 表示在以 \(i\) 为根的子树中，遍历了 \(u\) 个结点，选择了 \(k\) 个结点的最优解，并设以 \(x\) 为根的子树的大小为 \(size_x\)，任一点 \(y\) 的儿子结点个数 \(s_y\)，其状态转移过程是不难的，

\[dp(i, \ j, \ k)=max_{u<size_v} \ dp(i, \ j - 1, \ k - u) + dp(i, \ s_v, \ u) \]

不过开三维空间会爆内存，需要滚动数组来省略掉第二维。时间复杂度不确定，应该是 \(O(nm)\)。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

void solve() {
    cin >> m >> n;
 
    vector<vector<int>> adj(m + 1);
    vector<int> p(m + 1);
 
    int x, y;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        adj[x].emplace_back(i);
        p[i] = y;
    }
 
    vector<vector<int>> dp(m + 1, vector<int> (m + 1, 0));
 
    auto dfs = [&](auto &&self, int u, int cur) -> void {
        if (!cur) {
            return;
        }
        for (auto c: adj[u]) {
            for (int i = 0; i < cur; i++) {
                dp[c][i] = dp[u][i] + p[c];
            }
            self(self, c, cur - 1);
            for (int i = 1; i <= cur; i++) {
                dp[u][i] = max(dp[u][i], dp[c][i - 1]);
            }
        }
    };
 
    dfs(dfs, 0, n);
 
    cout << dp[0][n] << endl;

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

    init();

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

\(\\\)

G A Hard Calculation Problem

签到，复杂度 \(O(T)\)。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

void solve() {
    cin >> n;

    cout << 2016 + n << endl;

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

    init();

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

\(\\\)

Ｈ 水果蛋糕

题面有点绕，建议编故事别跑题了。简单说就是把一个矩形分成若干个三角形或者梯形或者矩形，求第几个图形内的给定点的数量最多。

这题也是卡常卡的很死，射线法判断 \(InPolygon\) 寄了，为什么 \(O(4m \ logn)\) 寄了，感觉完全够用啊。

改成矢量叉积之后对了，常数变成射线法的 \(\frac{1}{4}\)，变成 \(O(m \ logn)\)。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}
 
typedef struct Point {
    i64 x, y;
    Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
};

void solve() {
    i64 x, y;
    cin >> n >> m >> x >> y;

    Point p[n + 2][2];

    p[0][0].x = 0, p[0][0].y = 0;
    p[0][1].x = 0, p[0][1].y = y;
    p[n + 1][0].x = x, p[n + 1][0].y = 0;
    p[n + 1][1].x = x, p[n + 1][1].y = y;
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        p[i][0].x = p[i - 1][0].x + l, p[i][0].y = p[i - 1][0].y;
        p[i][1].x = p[i - 1][1].x + r, p[i][1].y = p[i - 1][1].y;
    }

    vector<i64> L(n + 1), R(n + 1);
    L[0] = 0, R[0] = max(p[1][0].x, p[1][1].x);

    for (int i = 1; i <= n; i++) {
        L[i] = min(p[i][0].x, p[i][1].x);
        R[i] = max(p[i][0].x, p[i][1].x);
    }
    
    vector<int> cnt(n + 2);
    vector<i64> S(n + 2);

    for (int i = 1; i <= n + 1; i++) {
        S[i] = p[i][0].x - p[i - 1][0].x + p[i][1].x - p[i - 1][1].x;
    }

    for (int i = 0; i < m; i++) {
        i64 u, v;
        cin >> u >> v;

        auto prod = [&](i64 a, i64 b, i64 c, i64 d) -> i64 {
            return a * d - b * c;
        };

        auto calc = [&](Point p[2]) -> i64 {
            return prod(p[1].x - p[0].x, -y, u - p[0].x, v - y);
        };

        auto get = [&]() -> int {
            int l = 1, r = n + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (calc(p[mid]) > 0) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            return l;
        };
        
        int idx = get();

        cnt[idx]++;
    }

    int cur = 0, ans = 0;
    i64 area = 0;
    for (int i = 0; i <= n + 1; i++) {
        if (cnt[i] > cur || (cnt[i] == cur && S[i] > area)) {
            cur = cnt[i];
            area = S[i];
            ans = i;
        }
    }

    cout << ans << endl;

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

    init();

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

\(\\\)

I Digital Logic and Bit Operation

给定 \(n, m\)，在区间 \([n,m]\) 内找两个数，使其或运算后结果最大。分类讨论一下，分为 \(n\) 和 \(m\) 的二进制位数相等和不相等两种情况。

容易发现，当二进制位数不相等时，答案为 \(2^{bitwidth(m)}-1\)。否则，从高逐位枚举，找到异或为 \(1\) 的位置，之后全部置 \(1\) 即可。复杂度 \(O(logm)\) 或 \(O(log^2m)\)。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

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

    if (n == m) {
        cout << n << endl;
        return;
    }

    auto u = (n > 1LL && (n & (n - 1) == 0) ? __lg(n) : __lg(n) + 1);
    u = n ? u : 1;
    auto v = (m > 1LL && (m & (m - 1) == 0) ? __lg(m) : __lg(m) + 1);
    v = v ? v : 1;

    i64 ans = 0;

    if (u != v || !(n * m)) {
        ans += (1LL << v) - 1;
        cout << ans << endl;
        return;
    }

    for (int i = u - 1; i >= 0; i--) {
        if (n & (1LL << i) && m & (1LL << i)) {
            ans += 1LL << i;
        } else if (n & (1LL << i) || m & (1LL << i)) {
            ans += 1LL << i;
            for (int j = i - 1; j >= 0; j--) {
                ans += 1LL << j;
            }
            break;
        }
    }

    cout << ans << endl;


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

    init();

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

\(\\\)

J 蛋糕惨案

欧拉筛之后枚举一下就可以了。复杂度 \(O(nlog(\frac{n}{lnn})+nlogn)\)，可以用 \(minp\) 和桶排序做到 \(O(n)\)，不过无所谓，而且内存可能会爆。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

vector<int> Sieve(int n) {
    vector<int> minp;
    minp.assign(n + 1, 0);
    vector<int> res;
    for(int i = 2; i <= n; i++) {
        if(!minp[i]) {
            minp[i] = i;
            res.emplace_back(i);
        }
 
        for(auto p: res) {
            if(i * p > n) {
                break;
            }
            minp[i * p] = p;
            if(p == minp[i]) {
                break;
            }
        }
    }
    return res;
}

auto primes = Sieve(10000000);

void solve() {
    cin >> n;
    int kk;
    vector<int> ans;
    
    for (int i = 0; i < n; i++) {
        cin >> kk;
        int q = lower_bound(primes.begin(), primes.end(), kk) - primes.begin();
        if (q != primes.size() && primes[q] == kk) {
            ans.emplace_back(kk);
        }
    }

    sort(ans.begin(), ans.end());

    if (!ans.size()) {
        cout << 0 << endl << -1 << endl;
        return;
    }

    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }

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

    init();

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

\(\\\)

K Equation

求给定函数的最值，套个模拟退火就过了，看了下题解是求导二分，不是很懂。复杂度为常数。

点击查看代码 
import math
import random

t = int(input())
for i in range(0, t):

    n = int(input());
     
    def aimFunction(x):
        y = 6 * (x ** 7) + 8 * (x ** 6) + 7 * (x ** 3) + 5 * (x ** 2) - n * x
        return y
     
    start = 0
    end = 100
     
    X = random.uniform(start,end)
    Y = aimFunction(X)
     
    T = 100000000000
    rate = 0.9974
    while T > 1:
        x = random.uniform(start,end)
        y = aimFunction(x)
        if y < Y:
            Y = y
            X = x
        else:
            p = math.exp((Y - y) / T)
            q = random.random();
            if p > q:
                Y = y
                X = x
        T *= rate
    print(round(Y, 4))

\(\\\)

L 树上宝藏

因为边的数量很少，直接暴力 \(dfs\)，复杂度不会算。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

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

    vector<i64> p(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    vector<vector<int>> adj;
    adj.assign(n + 1, {});
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }

    for (int i = 0; i < m; i++) {
        int x, y;
        i64 z;
        cin >> x >> y >> z;

        bool check = false;
        auto dfs = [&](auto &&self, int u, int bef) -> void {
            p[u] += z;
            if (u == y) {
                check = true;
                return;
            }
            for (auto c: adj[u]) {
                if (c == bef) {
                    continue;
                }
                if (check) {
                    return;
                }
                self(self, c, u);
            }
            if (check) {
                return;
            }
            p[u] -= z;
        };

        dfs(dfs, x, -1);
    }

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;

        i64 ans = 0, cur = 0;
        bool check = false;
        auto dfs = [&](auto &&self, int u, int bef) -> void {
            if (u == y) {
                cur += p[u];
                ans = cur;
                return;
            }
            cur += p[u];
            for (auto c: adj[u]) {
                if (c == bef) {
                    continue;
                }
                self(self, c, u);
            }
            cur -= p[u];
        };

        dfs(dfs, x, -1);

        cout << ans << endl;
    }

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

    init();

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

\(\\\)

M Rescue Hostage

这个题的测试数据有问题，\(assert\) 之后会发现存在无 \(F\) 或者无 \(X\) 的数据。做法是从 \(F\) 点和 \(X\) 点开始各做一次 \(bfs\)，然后暴力枚举所有的 \(H\) 求最小的和。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

struct g {
    int x, y;
    g (int x_, int y_): x(x_), y(y_) {}
};

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

    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    static const int M = 250;

    int dis[M][M][2];
    memset(dis, 0, sizeof dis);

    vector<vector<int>> dir{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    auto check = [&](int x, int y) -> bool {
        if (x < 0 || y < 0 || x > n - 1 || y > m - 1) {
            return false;
        }
        return true;
    };

    int sx = 0, sy = 0, ux = 0, uy = 0;

    auto bfs = [&](int x, int y, int P) -> void {
        queue<g> q;
        g st(x, y);
        q.push(st);
        while (!q.empty()) {
            auto c = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                g nxt(c.x + dir[i][0], c.y + dir[i][1]);
                if (!check(nxt.x, nxt.y)) {
                    continue;
                }
                if (dis[nxt.x][nxt.y][P]) {
                    continue;
                }
                if (s[nxt.x][nxt.y] == '#') {
                    continue;
                }
                dis[nxt.x][nxt.y][P] = dis[c.x][c.y][P] + 1;
                q.push(nxt);
            }   
        }
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'F') {
                sx = i, sy = j;
            }
            if (s[i][j] == 'X') {
                ux = i, uy = j;
            }
        }
    }

    int ans = 10010;

    bfs(sx, sy, 0);
    bfs(ux, uy, 1);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'H' && dis[i][j][0] && dis[i][j][1]) {
                // assert(dis[i][j][0] && dis[i][j][1]);
                ans = min(ans, dis[i][j][0] + dis[i][j][1]);
            }
        }
    }

    cout << ans << endl;

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

    init();

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

\(\\\)

N 嘉然的问题

签到，复杂度 \(O(strlen^2)\)。

点击查看代码 
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

void init() {}

template<const long long N>
struct StringHash {
    using i64 = long long;
    using PII = std::pair<i64, i64>;
    const i64 mod1 = 1e9 + 97, mod2 = 998244853, p1 = 131, p2 = 233;
    std::array<i64, N> a1, a2;
    std::array<i64, N> Phs1, Phs2;
    std::array<i64, N> Shs1, Shs2;
    StringHash() {
        init(N - 1);
    }
    StringHash(const std::string& S) {
        init(N - 1);
        work(S);
    }
    void work(const std::string& s) {  
        i64 n = s.size();
        assert(n + 1 <= N);
        for (int i = 0; i < n; ++i) {
            i64 t = n - i - 1;
            Phs1[i + 1] = ((i64)Phs1[i] * p1 + s[i]) % mod1;
            Phs2[i + 1] = ((i64)Phs2[i] * p2 + s[i]) % mod2;
            Shs1[t + 1] = ((i64)Shs1[t + 2] * p1 + s[t]) % mod1;
            Shs2[t + 1] = ((i64)Shs2[t + 2] * p2 + s[t]) % mod2;
        }
    }
    PII PreHash(i64 l, i64 r) {
        assert(l <= r);
        i64 P1 = (Phs1[r] - (i64)Phs1[l - 1] * a1[r - l + 1] % mod1 + mod1) % mod1;
        i64 P2 = (Phs2[r] - (i64)Phs2[l - 1] * a2[r - l + 1] % mod2 + mod2) % mod2;
        return PII(P1, P2);
    };
    PII SufHash(i64 l, i64 r) {
        assert(l <= r);
        i64 S1 = (Shs1[l] - (i64)Shs1[r + 1] * a1[r - l + 1] % mod1 + mod1) % mod1;
        i64 S2 = (Shs2[l] - (i64)Shs2[r + 1] * a2[r - l + 1] % mod2 + mod2) % mod2;
        return PII(S1, S2);
    }
    bool isPlalindrome(i64 l, i64 r) {
        auto [P1, P2] = PreHash(l, r);
        auto [S1, S2] = SufHash(l, r);
        return P1 == S1 && P2 == S2;
    }
    void init(i64 n) {
        a1[0] = a2[0] = 1;
        for (int i = 0; i < n; ++i) {
            a1[i + 1] = (i64)a1[i] * p1 % mod1;
            a2[i + 1] = (i64)a2[i] * p2 % mod2;
        }
    }
};

constexpr int N = 1500;
StringHash<N> S;

void solve() {
    string s;
    getline(cin, s);

    vector<pair<string, int>> ans;

    S.work(s);

    for (int i = 1; i <= s.size(); i++) {
        for (int j = i + 1; j <= s.size(); j++) {
            if (S.isPlalindrome(i, j)) {
                ans.emplace_back(s.substr(i - 1, j - i + 1), i);
            }
        }
    }

    sort(ans.begin(), ans.end(), [](pair<string, int> x, pair<string, int> y) {
        if (x.first.size() < y.first.size()) {
            return true;
        }
        if (x.first.size() > y.first.size()) {
            return false;
        }
        return x.second < y.second;
    });

    for (auto [x, y]: ans) {
        cout << x << endl;
    }

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

    init();

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

标签：cur,int,石家庄,i64,--,铁道,程序设计,void,size
From： https://www.cnblogs.com/h-rm/p/18359592

相关文章

  • 《python语言程序设计》2018版第6章第47题编写显示两个棋盘，我没有按要求写定义
    一、我的奇幻结果大小棋盘的def的函数代码问题分析：原来的坐标加入了总坐标作为参考坐标配合使用drawChessboard(-6,-6,sizeGird=3)drawChessboard(16,16,sizeGird=10)大小棋盘的def的函数代码defdrawChessboard(startX,startY,sizeGird):turtle.spee......
  • 《python语言程序设计》2018第7章第1题 第2次刷题 创建一个Rectangle类，包括长、宽数据
    uml类图到现在不会弄。此处为main的位置，不是rectangle类的代码。importmathdefmain():width_int=eval(input("EnterRectangle#1width:"))height_int=eval(input("EnterRectangle#1height:"))a=exCode07.Rectangle(width_int,height......
  • Python之程序设计策略
    这是《Python入门经典以解决计算问题为导向的Python编程实践》106-109页的内容程序设计策略问题的实质是什么让问题真实化编程之前先思考。简化（分治）停下来思考放松一下：让自己休息一下坚持有助于解决问题，所以不要轻易放弃。同时解决多任务有时候容易分心。找不......
  • 选择结构程序设计（2/3）
    目录​编辑条件运算符1.条件运算符的一般形式2.作用条件运算符首先来用if语句实现对两个数中最大值的求解，代码如下：if(a>b){ max=a;}else{ max=b;}上面的代码可以用条件运算符“？：”来简化：max=(a>b)?a:b;1.条件运算符的一般形式表达式1？表达式2：......
  • 【C语言(谭浩强)】程序设计与 C 语言
    博客主页：小蜗系列专栏：C语言（谭浩强）版关注博主，后期持续更新系列文章如果有错误请大家批评指出，我会及时修改感谢大家点赞......
  • [米联客-安路飞龙DR1-FPSOC] UDP通信篇连载-09 ICMP层程序设计
    软件版本：Anlogic-TD5.9.1-DR1_ES1.1操作系统：WIN1064bit硬件平台：适用安路(Anlogic)FPGA实验平台：米联客-MLK-L1-CZ06-DR1M90G开发板板卡获取平台：https://milianke.tmall.com/登录"米联客"FPGA社区http://www.uisrc.com视频课程、答疑解惑！ 5上板调试5.1硬件连接本次......
  • [米联客-安路飞龙DR1-FPSOC] UDP通信篇连载-04 IP层程序设计
    软件版本：Anlogic-TD5.9.1-DR1_ES1.1操作系统：WIN1064bit硬件平台：适用安路(Anlogic)FPGA实验平台：米联客-MLK-L1-CZ06-DR1M90G开发板板卡获取平台：https://milianke.tmall.com/登录"米联客"FPGA社区http://www.uisrc.com视频课程、答疑解惑！ 3.3IP层ICMP层数据和UDP层数......
  • [米联客-安路飞龙DR1-FPSOC] UDP通信篇连载-05 ARP层程序设计
    软件版本：Anlogic-TD5.9.1-DR1_ES1.1操作系统：WIN1064bit硬件平台：适用安路(Anlogic)FPGA实验平台：米联客-MLK-L1-CZ06-DR1M90G开发板板卡获取平台：https://milianke.tmall.com/登录"米联客"FPGA社区http://www.uisrc.com视频课程、答疑解惑 3.4ARP层该层具有接收ARP请求......
  • [米联客-安路飞龙DR1-FPSOC] UDP通信篇连载-06 UDP层程序设计
    软件版本：Anlogic-TD5.9.1-DR1_ES1.1操作系统：WIN1064bit硬件平台：适用安路(Anlogic)FPGA实验平台：米联客-MLK-L1-CZ06-DR1M90G开发板板卡获取平台：https://milianke.tmall.com/登录"米联客"FPGA社区http://www.uisrc.com视频课程、答疑解惑！ 3.5UDP层该层实现用户数据和U......
  • 消灭星星游戏程序设计【连载十】——小星星的残影轨迹
    消灭星星游戏程序设计【连载十】——小星星的残影轨迹大家每次都可以在页面中下载本节内容的实现代码，一步一步从简单开始，逐步完成游戏的各种功能，如果大家有任何问题也欢迎留言交流。游戏整体效果展示：1、本节要达到的效果这一节课，我们需要添加小星星的残影轨迹效果，也......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99