当前位置: 首页 > article >正文

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

http://www.kler.cn/a/585698.html

相关文章:

  • Mybaties批量操作
  • SAP BC 记一次 DBCO 链接ORACLE DBCC 连接测试突然失败的问题
  • Python中将Markdown文件转换为Word
  • 【Linux】从互斥原理到C++ RAII封装实践
  • Web安全:保护您的网站免受网络威胁
  • Microsoft Outlook 2024 LTSC for Mac v16.95 电子邮件和日历 支持M、Intel芯片
  • Peach配置文件中<Agent>模块的作用及参数解析
  • SpringBoot调用华为云短信实现发短信功能
  • 如何把绿色可执行应用程序添加到Ubuntu的收藏夹Dock中
  • 【Azure 架构师学习笔记】- Azure Databricks (20) --Delta Live Table 建议
  • Markdown Poster – 免费Markdown转图片工具|优雅图文海报制作与社交媒体分享
  • Vue 中如何使用 slot 和 scoped slot?
  • OpenCV图像加权函数:addWeighted
  • 成功破解加密机制,研究人员解锁LinuxESXi Akira勒索软件
  • Redis的持久化-AOF
  • 【Qt】带参数的信号和槽函数
  • 计算机网络 网络层IP数据报首部格式、数据链路层帧格式综合练习
  • 神经网络微调技术解析
  • vue3实现星星打分组件
  • Java 集合框架大师课:集合框架的暗黑料理(六)