ABC375

🕗 发布于 2024-10-15 19:25 算法图论

C

c题第一次看到400分。需要分情况讨论，但不难。
需要注意到旋转是按照由外向内分层次旋转的，第一层顺时针转1次，第二层转2次，第三层转3次。。以此类推。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int n;
char s[3003][3003];
char b[3003][3003];

void rep(int x, int y, int k) {
    if (k == 1) {
        b[y][n + 1 - x] = s[x][y];
    }
    else if (k == 2) {
        b[n + 1 - x][n + 1 - y] = s[x][y];
    }
    else if (k == 3) {
        b[n + 1 - y][x] = s[x][y];
    }
    else {
        b[x][y] = s[x][y];
    }
}


int main(){
   // freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s[i] + 1);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int lev = min(min(i, n + 1 - i), min(j, n + 1 - j));
            rep(i, j, lev % 4);
        }
    }
    for (int i = 1; i <= n; ++i) {
        printf("%s\n", b[i] + 1);
    }
    return 0;
}

D

给出一个字符串 $S$
求字符串中下标三元组 $i < j < k$ 的个数，使得用这三个下标位置字符组成的字符串（长度3）为回文串

对于每个 $S_k$ ，要从 $[1, k - 2]$ 位置中寻找相同的字符 $c h$ 作为 $i$ 。 $[i + 1, k - 1]$ 的所有下标都可以作为 $j$ ，对答案贡献为k-i-1。

因此在 $k$ 位置上的和为 $\sum(k-pos_{ch}-1)$ ，其中k可以提出，剩下需要知道有几个 $c h$ ，以及 $c h$ 前面的位置和。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int n;
string s;
ll f[200020][26];
ll l[200020][26];


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> s;
    n = s.length();
    s = "#" + s;
    ll cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int t = s[i] - 'A';
        if (i >= 2) {
            ll temp = l[i - 2][t] * i - f[i - 2][t] - l[i - 2][t];
            cnt += temp;
        }
        for (int j = 0; j < 26; ++j) {
            if (t == j) {
                f[i][j] = f[i - 1][j] + i;
                l[i][j] = l[i - 1][j] + 1;
            }
            else {
                f[i][j] = f[i - 1][j];
                l[i][j] = l[i - 1][j];
            }
        }
    }
    printf("%lld\n", cnt);
    return 0;
}

E

将数组分为三个数组ABC，现在需要移动一些元素，使得三部分的和相同，求最少移动几个？

由于 $\leq 1500$ ，可以用暴力的方法去做
设 $f [i] [a] [b]$ 代表当前取到第i个数 $x$ ，数组A里和为a，B和为b，需要最少移动的个数
边界 $f [0] [0] [0] = 0$
$\min(f[i-1][a-x][b]+cost(A,i),f[i-1][a][b-x]+cost(B,i),f[i-1][a][b]+cost(C,i))$

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
  

int f[101][501][501];
int n;
int w[101], g[101];


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n;
    int s = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> g[i] >> w[i];
        s += w[i];
    }
    if (s % 3) {
        printf("-1\n");
        return 0;
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int a = 0; a <= s / 3; ++a) {
            for (int b = 0; b <= s / 3; ++b) {
                if (a >= w[i]) {
                    f[i][a][b] = min(f[i][a][b], f[i - 1][a - w[i]][b] + (g[i] == 1 ? 0 : 1));
                }
                if (b >= w[i]) {
                    f[i][a][b] = min(f[i][a][b], f[i - 1][a][b - w[i]] + (g[i] == 2 ? 0 : 1));
                }
                f[i][a][b] = min(f[i][a][b], f[i - 1][a][b] + (g[i] == 3 ? 0 : 1));
            }
        }
    }
    if (f[n][s / 3][s / 3] > 1 << 20) {
        printf("-1\n");
    }
    else {
        printf("%d\n", f[n][s / 3][s / 3]);
    }
    return 0;
}

F

无向图中有N个点M条边，每条边有一权值
Q个操作
操作1：将第i条边删去
操作2：求u,v间最短路径
其中操作1的个数 $\leq 300$

最短路的第一题。因为反过来加边是可以用类似prim算法的松弛操作来做最短路，所以考虑离线操作，倒序，
一开始先用prim求出两点间的最短路，然后对每一条加回去的边进行松弛操作。
最后把答案填回去。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

struct Edge {
    int u, v;
    ll w;
};
Edge e[90009];

struct Query {
    int op, u, v;
}qr[200002];

ll g[303][303];
ll ans[200002];
bool use[90009];
int n, m, q;


int main() {
    //freopen("in.txt", "r", stdin);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        e[i] = { u, v, w };
        use[i] = 1;
    }
    for (int i = 1; i <= q; ++i) {
        int op, u = 0, v = 0;
        cin >> op;
        if (op == 1) {
            cin >> u;
            use[u] = 0;
        }
        else {
            cin >> u >> v;
        }
        qr[i] = { op, u, v };
    }
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= n; ++i) g[i][i] = 0;
    for (int i = 1; i <= m; ++i) {
        auto [u, v, w] = e[i];
        if (use[i])
            g[u][v] = g[v][u] = w;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                g[j][k] = min(g[j][k], g[j][i] + g[i][k]);
            }
        }
    }
    for (int i = q; i >= 1; --i) {
        auto [op, u, v] = qr[i];
        if (op == 1) {
            int idx = u;
            auto [u, v, w] = e[idx];
            g[u][v] = g[v][u] = min(g[u][v], w);
            for (int j = 1; j <= n; ++j) {
                if (g[j][u] + w < g[j][v]) {
                    g[j][v] = g[v][j] = g[j][u] + w;
                }
                if (g[j][v] + w < g[j][u]) {
                    g[j][u] = g[u][j] = g[j][v] + w;
                }
            }
            for (int j = 1; j <= n; ++j) {
                for (int k = 1; k <= n; ++k) {
                    if (g[j][u] + w + g[v][k] < g[j][k]) {
                        g[j][k] = g[k][j] = g[j][u] + w + g[v][k];
                    }
                    if (g[j][v] + w + g[u][k] < g[j][k]) {
                        g[j][k] = g[k][j] = g[j][v] + w + g[u][k];
                    }
                }
            }
        }
        else {
            ans[i] = g[u][v];
        }
    }
    for (int i = 1; i <= q; ++i) {
        if (qr[i].op == 2) {
            if (ans[i] >= 1ll << 60)
                ans[i] = -1;
            printf("%lld\n", ans[i]);
        }
    }
    return 0;
}

G

N个点M条边的带权值无向图
只删除每条边后，看从1到n的最短路距离 $d (1, n)$ 是否发生了变化

看边 $(u, v)$ 是否在最短路径上，只需要两边计算 $d (1, u)$ 和 $d (n, v)$ ，看 $d (1, u) + d (n, v) + w$ 是否 $= d (1, n)$
但是v可能有多条最短路径通向1，如何判断边在关键路径上？
我们可以记录1到i最短路径的种数 $f (1, i)$
当 $f (1, u) * f (n, v) = f (1, n)$ 时，即为关键路径
由于数太大，需要给一个大质数，记录f%m。这里一个质数往往不够，需要使用两个质数，bloom filter的思路。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int n, m;
vector<pair<int, ll>> g[200020];
ll dist1[200020];                   // from 1
ll f1[200020];   // different number of path
ll dist2[200020], f2[200020];       // from n
ll x1[200020], x2[200020];
bool vis[200020];
ll m1 = ll(1e9 + 7);
ll m2 = ll(99999989);

struct Node {
    int u;
    ll d;
    bool operator < (const Node& r) const {
        return d > r.d;
    }
};
struct Edge {
    int u, v;
    ll w;
} e[200020];

priority_queue<Node> qu;


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
        e[i] = { u, v, w };
    }
    memset(dist1, 0x3f, sizeof(dist1));
    memset(dist2, 0x3f, sizeof(dist2));
    memset(vis, 0, sizeof(vis));
    dist1[1] = 0;
    f1[1] = 1;
    qu.push(Node({ 1, 0 }));
    while (qu.size()) {
        auto [u, d] = qu.top();
        qu.pop();
        if (u == n) {
            break;
        }
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w] : g[u]) {
            if (dist1[v] > dist1[u] + w) {
                dist1[v] = dist1[u] + w;
                f1[v] = f1[u];
                x1[v] = x1[u];
                qu.push(Node({ v, dist1[v] }));
            }
            else if (dist1[v] == dist1[u] + w) {
                f1[v] = (f1[v] + f1[u]) % m1;
                x1[v] = (x1[v] + x1[u]) % m2;
            }
        }
    }

    while (qu.size()) qu.pop();
    memset(vis, 0, sizeof(vis));
    dist2[n] = 0;
    f2[n] = 1;
    qu.push(Node({ n, 0 }));
    while (qu.size()) {
        auto [u, d] = qu.top();
        qu.pop();
        if (u == 1) break;
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w] : g[u]) {
            if (dist2[v] > dist2[u] + w) {
                dist2[v] = dist2[u] + w;
                f2[v] = f2[u];
                x2[v] = x2[u];
                qu.push(Node({ v, dist2[v] }));
            }
            else if (dist2[v] == dist2[u] + w) {
                f2[v] = (f2[v] + f2[u]) % m1;
                x2[v] = (x2[v] + x2[u]) % m2;
            }
        }
    }
    
    for (int i = 1; i <= m; ++i) {
        auto [u, v, w] = e[i];
        if (dist1[u] + dist2[v] + w == dist1[n] && f1[u] * f2[v] % m1 == f1[n] && 
            x1[u] * x2[v] % m2 == x1[n]) {
            printf("Yes\n");
        }
        else if (dist1[v] + dist2[u] + w == dist1[n] && f1[v] * f2[u] % m1 == f1[n] &&
            x1[v] * x2[v] % m2 == x1[n]) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    return 0;
}

原文地址：https://blog.csdn.net/acrux1985/article/details/142957056

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：送交CNKI/CPCI收录，2024经济管理与智能社会国际会议（EMIS2024）
下一篇：氧化钆Gd2O3纳米颗粒50nm|DM-Gd2O3纳米粒子

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

ABC375

C

D

E

F

G

相关文章