AtCoder Beginner Contest 375（A，B，C，D，E，F）（大模拟，前缀和，dp，离线处理，Floyd）

比赛链接

AtCoder Beginner Contest 375

A题

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
char s[N];
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> s[i];}int ans = 0;for (int i = 1; i <= n - 2; i++){if (s[i] == '#' && s[i + 1] == '.' && s[i + 2] == '#')ans++;}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

B题

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
struct Point
{ // 点double x, y;Point() {}Point(double x, double y) : x(x), y(y) {}Point operator+(Point B) { return Point(x + B.x, y + B.y); }Point operator-(Point B) { return Point(x - B.x, y - B.y); }
} p[N];
double Distance(Point A, Point B)
{ // 两点之间的欧氏距离return sqrtl((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
void solve()
{cin >> n;p[0] = {0, 0};for (int i = 1; i <= n; i++){cin >> p[i].x >> p[i].y;}double ans = 0;n++;for (int i = 0; i < n; i++){int j = (i + 1) % n;ans += Distance(p[i], p[j]);}cout << fixed << setprecision(8) << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

C题

思路

其实就是从外圈到内圈的局部旋转，注意取模，每个圈最多旋转3次。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e3 + 5, M = 1e6 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
char a[N][N], b[N][N];
void solve()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> a[i][j];}}for (int k = 1; k <= n / 2; k++){int num = k % 4;vector<char> v[4];for (int j = k + 1; j <= n - k; j++){v[0].push_back(a[k][j]);}for (int i = k + 1; i <= n - k; i++){v[1].push_back(a[i][n - k + 1]);}for (int j = n - k; j >= k + 1; j--){v[2].push_back(a[n - k + 1][j]);}for (int i = n - k; i >= k + 1; i--){v[3].push_back(a[i][k]);}vector<char> op[4];for (int i = 0; i < 4; i++){op[(i + num) % 4] = v[i];}int idx = 0;for (int j = k + 1; j <= n - k; j++){b[k][j] = op[0][idx++];}idx = 0;for (int i = k + 1; i <= n - k; i++){b[i][n - k + 1] = op[1][idx++];}idx = 0;for (int j = n - k; j >= k + 1; j--){b[n - k + 1][j] = op[2][idx++];}idx = 0;for (int i = n - k; i >= k + 1; i--){b[i][k] = op[3][idx++];}vector<int> ji;ji.push_back(a[k][k]);ji.push_back(a[k][n - k + 1]);ji.push_back(a[n - k + 1][n - k + 1]);ji.push_back(a[n - k + 1][k]);vector<int> kk(4);for (int i = 0; i < 4; i++){kk[(i + num) % 4] = ji[i];}b[k][k] = kk[0];b[k][n - k + 1] = kk[1];b[n - k + 1][n - k + 1] = kk[2];b[n - k + 1][k] = kk[3];}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cout << b[i][j];}cout << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

D题

思路

预处理出每一个字符的前缀和与后缀和，最后遍历一遍直接计算即可。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
int pre[N][26], nxt[N][26];
string s;
void solve()
{cin >> s;n = s.size();s = "#" + s;for (int i = 1, j = n; i <= n; i++, j--){int op1 = s[i] - 'A';int op2 = s[j] - 'A';for (int k = 0; k < 26; k++){pre[i][k] = pre[i - 1][k];nxt[j][k] = nxt[j + 1][k];}pre[i][op1]++, nxt[j][op2]++;}int ans = 0;for (int i = 2; i < n; i++){for (int k = 0; k < 26; k++){int low = pre[i - 1][k];int high = nxt[i + 1][k];ans += (low * high);}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

E题

思路

注意到，$n$最大为100，强度的和最大值为1500。因为有三组，所以每一组强度的和最大值为500。

我们令$dp[i][j][k]$表示前$i$个已经分配完成，第$1$组的强度为$j$，第$2$组的强度为$k$时需要执行换队操作的最小数量。

状态转移方程为：

$dp[i+1][j+b[i+1]][k]=min(dp[i+1][j+b[i+1]][k],dp[i][j][k]+(a[i+1]!=1))$

$dp[i+1][j][k+b[i+1]]=min(dp[i+1][j][k+b[i+1]],dp[i][j][k]+(a[i+1]!=2))$

$dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]+(a[i+1]!=3))$

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 5, M = 5e2 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[N], b[N], dp[N][M][M];
void solve()
{cin >> n;int sum = 0;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i];sum += b[i];}if (sum % 3 != 0){cout << -1 << endl;return;}memset(dp, inf, sizeof dp);dp[0][0][0] = 0, sum /= 3;for (int i = 0; i < n; i++){for (int j = 0; j <= sum; j++){for (int k = 0; k <= sum; k++){if (dp[i][j][k] == inf)continue;if (j + b[i + 1] <= sum)dp[i + 1][j + b[i + 1]][k] = min(dp[i + 1][j + b[i + 1]][k], dp[i][j][k] + (a[i + 1] != 1));if (k + b[i + 1] <= sum)dp[i + 1][j][k + b[i + 1]] = min(dp[i + 1][j][k + b[i + 1]], dp[i][j][k] + (a[i + 1] != 2));dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k] + (a[i + 1] != 3));}}}if (dp[n][sum][sum] == inf){cout << -1 << endl;}elsecout << dp[n][sum][sum] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

F题

思路

对于所有的查询，我们考虑倒着进行离线操作。先用$Floyd$进行一次预处理求出所有的$dist[x][y]$，即点到点$y$的最短距离。

之后根据查询的条件，不断将新的边加到图中，并根据新边用$Floyd$进行$n^2$的更新操作。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e2 + 5, M = 1e6 + 5;
const int inf = 1e14;
int n, m, q;
int g[N][N];
struct edge
{int a, b, c;
};
vector<edge> v;
struct query
{int id, x, y;
};
vector<query> op;
void solve()
{cin >> n >> m >> q;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){g[i][j] = inf;}}for (int i = 1, a, b, c; i <= m; i++){cin >> a >> b >> c;g[a][b] = c;g[b][a] = c;v.push_back({a, b, c});}for (int i = 1, id, x, y; i <= q; i++){cin >> id >> x;if (id == 1){int a = v[x - 1].a;int b = v[x - 1].b;int c = v[x - 1].c;g[a][b] = inf;g[b][a] = inf;}y = 0;if (id == 2)cin >> y;op.push_back({id, x, y});}for (int k = 1; k <= n; k++){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){g[i][j] = min(g[i][j], g[i][k] + g[k][j]);}}}vector<int> ans;for (int num = q - 1; num >= 0; num--){if (op[num].id == 1){int x = op[num].x;int a = v[x - 1].a;int b = v[x - 1].b;int c = v[x - 1].c;g[a][b] = min(g[a][b], c);g[b][a] = min(g[b][a], c);for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){g[i][j] = min(g[i][j], g[i][a] + g[a][j]);}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){g[i][j] = min(g[i][j], g[i][b] + g[b][j]);}}}else{int x = op[num].x;int y = op[num].y;if (g[x][y] >= inf / 2)ans.push_back(-1);elseans.push_back(g[x][y]);}}reverse(ans.begin(), ans.end());for (int val : ans){cout << val << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}