ABC 375
目录
C. Spiral Rotation
D. ABA
E. 3 Team Division
F. Road Blocked
C. Spiral Rotation
根据公式可以发现,第一次动全部,第二次动除了最外面一圈,第三次动除了最外面两圈。
也就是说第一圈的点会改变一次,第二圈的点会改变两次,以此类推。
把从(x,y)到(y,n + 1 - x)分成两步,先变到(n + 1 - x,y),再变到(y,n + 1 - x)
第一步实际上是关于水平平分线做对称,第二步是横纵坐标互换,关于 y = x 对称
这种多步对称的,一定存在一个循环节,对称 n 次后会回到原点,此处是 4 次。也就是说对于一个点只要走(所在圈层 % 4)次,优化到 4 * n^2
注意要重新开一个图去复制
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3 + 5, INF = 1e18;
int T, n, cnt, ans;
char in[N][N], ot[N][N];
string s;
signed main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> s;
for (int j = 1; j <= n; j ++)
in[i][j] = s[j - 1];
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
int id = min(min(i, n - i + 1), min(j, n - j + 1));
int ti = id % 4;
int tx = i, ty = j;
for (int k = 1; k <= ti; k ++)
{
int nx = n + 1 - tx, ny = ty;
swap(nx, ny);
tx = nx, ty = ny;
}
ot[tx][ty] = in[i][j];
}
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
cout << ot[i][j];
cout << '\n';
}
return 0;
}
D. ABA
暴力的做法:设当前枚举到 i,第 i 个字符为 Cn(第 n 次出现),ans += ( i - C1 - 1 )+( i - C2 - 1 )+ …… +( i - Cn-1 - 1 )。
看到这是一个求和公式,应该把它拆开来,变成( i - 1 )*( n - 1 )+( C1 + C2 + …… + Cn-1 )。后者就是在 i 之前出现过的所有和第 i 个字符相等的字符的下标求和。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;
int T, n, res, d[30], cnt[30], ans;
string s;
map<char, int> mp;
signed main()
{
cin >> s;
int len = s.length();
s = ' ' + s;
for (int i = 1; i <= len; i ++)
{
int num = s[i] - 'A';
ans += (i - 1) * cnt[num] - d[num];
cnt[num] ++, d[num] += i;
}
cout << ans;
return 0;
}
E. 3 Team Division
三个队伍,每个队伍的力量值相等且都为总和的三分之一,这是很明显的背包特征,每个队伍的力量值就相当于是体积,且必须装满,只是背三个包。
定义 dp [ i ] [ a ] [ b ] [ c ] :前 i 个人,一队的力量值为 a,而队的力量值为 b,三队的力量值为 c。但第四维是可以省略掉的,只需要求一个到 i 个人为止的力量总和,减掉 a 减掉 b 就是 c。
尤其要注意枚举 a 和 b 的时候一定要从 0 开始,不能是 1。比如说会更新 dp [ 1 ] [ a ] [ 0 ]。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e9;
int T, n, tot, ans, g[105], w[1505], d[105], dp[105][505][505];
signed main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> g[i] >> w[i];
tot += w[i];
d[i] = d[i - 1] + w[i];
}
if (tot % 3 != 0)
{
cout << "-1";
return 0;
}
tot /= 3;
for (int i = 0; i <= n; i ++)
for (int a = 0; a <= tot; a ++)
for (int b = 0; b <= tot; b ++)
dp[i][a][b] = INF;
dp[0][0][0] = 0;
for (int i = 1; i <= n; i ++)
for (int a = 0; a <= tot; a ++)
for (int b = 0; b <= tot; b ++)
{
int x = INF, y = INF;
if (a - w[i] >= 0)
x = dp[i - 1][a - w[i]][b] + (g[i] != 1);
if (b - w[i] >= 0)
y = dp[i - 1][a][b - w[i]] + (g[i] != 2);
if (d[i] - a - b >= 0)
dp[i][a][b] = dp[i - 1][a][b] + (g[i] != 3);
dp[i][a][b] = min(min(x, y), dp[i][a][b]);
}
int ans = dp[n][tot][tot];
if (ans != INF)
cout << ans;
else
cout << "-1";
return 0;
}
F. Road Blocked
整体思路:把所有询问离线下来,然后倒过来做,把删边变成加边。
具体做法:
(1)把读入的边都先加上,vis 标记为 1 表示这条边存在
(2)每个询问按顺序存下来,如果是操作一就把对应边的编号的 vis 置为 0,表示这条边不存在
(3)初始化 f,自己到自己可达,其余均为 INF。然后存在边的两点修改 f。
(4)倒序遍历所有离线下来的操作,如果是第二种询问那答案也是存下来
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;
struct node
{
int u, v, w;
}e[N];
struct qnode
{
int opt, id, x, y;
}que[N];
int T, n, m, q, cnt, ans[N], vis[N], f[305][305];
string s;
signed main()
{
cin >> n >> m >> q;
for (int i = 1; i <= m; i ++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
vis[i] = 1;
}
for (int i = 1; i <= q; i ++)
{
cin >> que[i].opt;
if (que[i].opt == 1)
{
cin >> que[i].id;
vis[que[i].id] = 0;
}
else
cin >> que[i].x >> que[i].y;
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if (i == j)
f[i][j] = 0;
else
f[i][j] = INF;
for (int i = 1; i <= m; i ++)
{
if (vis[i] == 0)
continue;
f[e[i].u][e[i].v] = e[i].w;
f[e[i].v][e[i].u] = e[i].w;
}
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
for (int i = 1; i <= q; i ++)
ans[i] = -1;
for (int i = q; i > 0; i --)
{
if (que[i].opt == 1)
{
int u = e[que[i].id].u, v = e[que[i].id].v, w = e[que[i].id].w;
f[u][v] = min(f[u][v], w), f[v][u] = min(f[v][u], w);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
f[i][j] = min(min(f[i][j], f[i][u] + w + f[v][j]), f[i][v] + w + f[u][j]);
}
else
{
int x = que[i].x, y = que[i].y;
cnt ++;
if (f[x][y] != INF)
ans[cnt] = f[x][y];
}
}
for (int i = cnt; i > 0; i --)
cout << ans[i] << '\n';
return 0;
}