526互联

abc320

发布时间 2023-09-17 17:04:08作者: liuguanyi

A

题意

给你\(A\)和\(B\),输出\(pow(A,B)+pow(B,A)\)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define  len(x) ((int)((x).size()))
#define  inf 0x3f3f3f3f
#define mod 998244353
//#define  mod 1000000007

void solve() {
    ll A, B;
    cin >> A >> B;
    cout << pow(A, B) + pow(B, A) << endl;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B
给你一个字符串\(s\),找到最长回文字串的长度
由于\(len(s)<=100\)可以暴力\(n^3\)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define  len(x) ((int)((x).size()))
#define  inf 0x3f3f3f3f
#define mod 998244353
//#define  mod 1000000007

void solve() {
    string s;
    cin >> s;
    int ans = 1;
    auto cheak = [&](string str) -> bool {
        for (int i = 0; i < len(str) / 2; i++) {
            if (str[i] != str[len(str) - i - 1])return 0;
        }
        return 1;
    };
    for (int i = 0; i < len(s); i++) {
        for (int j = 1; j <= len(s) - i; j++) {
            if (cheak(s.substr(i, j))) {
                ans = max(ans, j);
            }
        }
    }
    cout << ans << endl;

}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

也可以进行动态规划,\(dp[i][j]\)表示在字符串\(i-j\)是否是回文字串,状态转移
\(dp[i][j]=dp[i+1][j-1]\&\&s[i]==s[j]\)时间复杂度\(O(n^2)\)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define  len(x) ((int)((x).size()))
#define  inf 0x3f3f3f3f
#define mod 998244353
//#define  mod 1000000007

void solve() {
    string s;
    cin >> s;
    int n = len(s);
    vector<vector<bool>> dp(n, vector<bool>(n));
    // 初始化dp数组
    dp[0][0]=1;
    for (int i = 1; i < n; i++) {
        dp[i][i]=1;
        if (s[i] == s[i - 1])dp[i - 1][i] = 1;
    }
    for (int i = n - 3; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (dp[i + 1][j - 1] && s[i] == s[j]) {
                dp[i][j] = 1;
            }
        }
    }
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (dp[i][j])
                ans = max(ans, j - i+1);
        }
    }
    cout << ans << endl;


}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

给你\(3\)个长度为\(M\)的字符串，你需要在\(T\)秒选择\(3\)个之一的字符串选择\(S[T\%M]\),选择\(3\)个字符使其相等,使其\(T\)最小

思路

如果\(3\)个字符都是在不同的位置,此时的\(ans=max(i,j,k)\)
如果\(3\)个字符都是在相同的位置，那么就要多跑\(2\)趟 \(ans=2*M+i\)
如果其中两个位置相同，那么我最多跑一趟，留下其中一个最小的最后一次收\(ans=M+min(min(i,j),k)\)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define  len(x) ((int)((x).size()))
#define  inf 0x3f3f3f3f
#define mod 998244353
//#define  mod 1000000007

void solve() {
    int M;
    cin >> M;
    vector<vector<vector<int>>> a(3, vector<vector<int>>(10));
    for (int i = 0; i < 3; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < M; j++) {
            a[i][s[j] - '0'].push_back(j);
        }
    }
    int ans = inf;
    for (int i = 0; i <= 9; i++) {
        vector<int> x = a[0][i];
        vector<int> y = a[1][i];
        vector<int> z = a[2][i];
        for (int u: x) {
            for (int o: y) {
                for (int p: z) {
                    if (u != o && o != p && u != p) {
                        ans = min(ans, max(o, max(u, p)));
                    } else {
                        if (u == o && u == p) {
                            ans = min(ans, 2 * M + u);
                        } else {
                           ans = min(ans, M + min(u, min(o, p)));
                        }
                    }
                }
            }
        }
    }
    if (ans == inf) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

在一个二维平面上，有\(N\)个点，同时有\(M\)个关系，再给你\(a,b,x,y\) 点\(b\)相等于\(x_b=x_a+x\) \(y_b=y_a+y\)
点\(1\)是在原点上，问你\(N\)个点的坐标，不能确定的点打印\(undecidable\)

建立反图，已知点\(a\)与点\(b\)之间的关系是\(X_a=X_b+X\)
\(Y_a=Y_b+Y\) 那么\(X_b=X_a-X\) \(Y_b=Y_a-Y\)

并且从点\(1\)开始\(dfs\)，所有能到的点都是能确定的点

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define  len(x) ((int)((x).size()))
#define  inf (ll)1e18
#define mod 998244353
//#define  mod 1000000007

void solve() {
    int N, M;
    cin >> N >> M;
    vector<vector<array<int, 3>>> g(N);
    for (int i = 0; i < M; i++) {
        int a, b, x, y;
        cin >> a >> b >> x >> y;
        a--;
        b--;
        g[a].push_back({b, x, y});
        //建立反图
        g[b].push_back({a, -x, -y});
    }
    vector<array<ll, 2>> ans(N, {inf, inf});
    ans[0] = {0, 0};
    vector<bool> vis(N);
    vis[0] = 1;
    auto dfs = [&](auto dfs, int u) -> void {
        for (auto[nx, x, y]: g[u]) {
            if (!vis[nx]) {
                ans[nx] = {ans[u][0] + x, ans[u][1] + y};
                vis[nx] = 1;
                dfs(dfs, nx);
            }
        }
    };
    dfs(dfs, 0);
    for (int i = 0; i < N; i++) {
        if (ans[i][0] == inf)cout << "undecidable" << endl;
        else cout << ans[i][0] << " " << ans[i][1] << endl;
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

有\(N\)个人，排成一列，有\(M\)碗面，在时间\(T_i\),数量为\(W_i\)，飞过来给排成一列的第一个人吃，并且吃完需要时间，需要\(S_i\)的消化时间，简而言之就是在\(T_i+S_i\)时间回到本身的位置(本身的位置就是，第\(i\)个人在\(i\)位置)
\(N\)个人吃的面的 数量

堆加平衡树，堆维护在消化的人，平衡树维护此时空闲的人们

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define  len(x) ((int)((x).size()))
#define  inf 0x3f3f3f3f
#define mod 998244353
//#define  mod 1000000007

void solve() {
    int N, M;
    cin >> N >> M;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    set<int> s;
    vector<ll> ans(N);
    for (int i = 0; i < N; i++) {
        s.insert(i);
    }
    for (int i = 0; i < M; i++) {
        int T, W, S;
        cin >> T >> W >> S;
        while (len(pq) && pq.top().first <= T) {
            s.insert(pq.top().second);
            pq.pop();
        }
        if (len(s) > 0) {
            ans[*s.begin()] += W;
            pq.push({T + S, *s.begin()});
            s.erase(s.begin());
        }
    }
    for (int i = 0; i < N; i++)cout << ans[i] << endl;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}