自学内容网 自学内容网

ABC375

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 S S
求字符串中下标三元组 i < j < k i<j<k i<j<k的个数,使得用这三个下标位置字符组成的字符串(长度3)为回文串


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

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

#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,现在需要移动一些元素,使得三部分的和相同,求最少移动几个?


由于 S ≤ 1500 S \leq 1500 S1500,可以用暴力的方法去做
f [ i ] [ a ] [ b ] f[i][a][b] f[i][a][b]代表当前取到第i个数 x x x,数组A里和为a,B和为b,需要最少移动的个数
边界 f [ 0 ] [ 0 ] [ 0 ] = 0 f[0][0][0]=0 f[0][0][0]=0
f [ i ] [ a ] [ b ] = min ⁡ ( f [ i − 1 ] [ a − x ] [ b ] + c o s t ( A , i ) , f [ i − 1 ] [ a ] [ b − x ] + c o s t ( B , i ) , f [ i − 1 ] [ a ] [ b ] + c o s t ( C , i ) ) f[i][a][b] = \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)) f[i][a][b]=min(f[i1][ax][b]+cost(A,i),f[i1][a][bx]+cost(B,i),f[i1][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的个数 ≤ 300 \leq 300 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 ) d(1,n) d(1,n)是否发生了变化


看边 ( u , v ) (u,v) (u,v)是否在最短路径上,只需要两边计算 d ( 1 , u ) d(1,u) d(1,u) d ( n , v ) d(n,v) d(n,v),看 d ( 1 , u ) + d ( n , v ) + w d(1,u)+d(n,v)+w d(1,u)+d(n,v)+w是否 = d ( 1 , n ) =d(1,n) =d(1,n)
但是v可能有多条最短路径通向1,如何判断边在关键路径上?
我们可以记录1到i最短路径的种数 f ( 1 , i ) f(1,i) f(1,i)
f ( 1 , u ) ∗ f ( n , v ) = f ( 1 , n ) f(1,u)*f(n,v)=f(1,n) 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)!