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;
}