首页 > 其他分享 >ABC 286 C - Rotate and Palindrome

ABC 286 C - Rotate and Palindrome

时间:2024-04-20 19:11:06浏览次数:23  
标签:ABC int res long i64 Palindrome ans rm Rotate

题目链接:

注意到“您可以按任意顺序执行以下两种运算零次或多次”。

因此,解决这个问题的一个重要观察点是,你可以假设 \(A\) 操作执行了几次,然后 \(B\) 操作执行了几次。你也可以假设 \(A\) 操作最多被执行 \(N\) 次(因为执行 \(N\) 次就会使它处于原始状态)

有了这个观察结果,你就会意识到,小约束条件允许我们检查所有可能的 $A $ 操作次数。执行 \(B\) 操作所需的最小次数就是应该匹配但目前不匹配的字符对数。

时间复杂度为 \(O(n^2)\)。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 5010;
i64 ans;

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n, A, B;
	string s;
	cin >> n >> A >> B >> s;
	
	i64 ans = 1e18;
	for (int i = 0; i < n; i++) {
		i64 res = 1LL * A * i;//1LL可以将后面的临时数据扩容成long long
		for (int j = 0; j < n / 2; j++) {
			res += (s[j] != s[n - 1 - j]) * B;//在固定A操作的次数下考虑B操作需要执行多少次。
		}
		ans = min(ans, res);
		rotate(s.begin(), s.begin()+1, s.end());//左旋转
	}
	cout << ans;
	return 0;
}

另一种不使用 \(\rm std::rotate\) 的思路是,把字符串 \(s\) 复制一份连接上去,每次截取一个从 \(S_i\) 开始,长度为 \(n\) 的子串,就相当于进行了 \(i\) 次操作 \(A\),然后再看这个子串是否回文进行操作 \(B\),与之前思路一致。
image

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 5010;
i64 ans;

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n, A, B;
	string s;
	cin >> n >> A >> B >> s;
	
	s = s + s;
	i64 ans = 1e18;
	for (int i = 0; i < n; i++) {
		int l = i, r = i + n - 1;
		i64 res = 1LL * A * i;
		while (l < r) {
			res += (s[l] != s[r]) * B;
			l++, r--;
		}
		ans = min(ans, res);
	}
	cout << ans;
	return 0;
}

注:std::rotate 的函数原型为

template <class ForwardIterator>  void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last);

具体而言。\(\sf std::rotate\) 交换范围 \(\rm [first,last)\) 中的元素,方式满足元素 \(\rm middle\) 成为新范围内的首个元素,而 \(\rm middle-1\) 成为最后元素。

此函数的前提条件是 \(\rm [first,middle)\) 和 \(\rm [middle,last)\) 为合法范围。
示例程序:

#include <bits/stdc++.h>

int main()
{
	std::vector<int> v;
	for (int i = 1; i <= 9; i++) v.push_back(i);//1 2 3 4 5 6 7 8 9
	std::rotate(v.begin(), v.begin()+3, v.end());
	for (auto i : v) std::cout << i << " ";//4 5 6 7 8 9 1 2 3
	return 0;
}

旋转过程可以按下图来理解:
image

image

标签:ABC,int,res,long,i64,Palindrome,ans,rm,Rotate
From: https://www.cnblogs.com/pangyou3s/p/18148018

相关文章

  • [题解]ABC209F Deforestation
    ABC209FDeforestation首先我们可以思考\(a_i\)和\(a_{i+1}\)先砍哪棵花费少。可以看出,当\(a[i]<a[i+1]\)时,先砍\(a[i+1]\),反之亦然。所以这个题转化成了:给定\(n-1\)个关系,分别表示\(n\)个值中相邻两个的大小关系,问满足这些关系的序列个数。与AtcoderEducationalDPContest......
  • ABC349F题解
    思想看到LCM想到质因数分解。首先,我们先把\(M\)质因数分解了,根号复杂度刚好1e8级别。然后我们发现一个很显然的性质:如果一个数不是\(M\)的因数那他肯定没用。所以此处我们就把不是因数地踢掉。我们惊奇地发现因为\(M\)的质因数分解最多\(13\)个不同的质数,然后我......
  • [ABC232G] Modulo Shortest Path (优化建图)
    链接:https://www.luogu.com.cn/problem/AT_abc232_g暴力的做法肯定不行,这道题要用到一个比较经典的拆点操作:把一个点拆成内点和外点。在接下来的分析中会慢慢介绍。由于题目每次连的边都是单向边,那要考虑的问题是:比如说现在要从1走到3,怎么走才能与暴力建边等价。先不考虑取模这......
  • 「杂题乱刷」AT_abc230_e
    链接(luogu)链接(at)典题。整除分块。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?*/#include<bits/stdc++.h>usingnamespacestd;#definemapunordered_map#defineforl(i,a,b)for(registerlong......
  • [题解]ABC282E Choose Two and Eat One
    ABC282EChooseTwoandEatOne又一个图论的回顾——Kruskal最小(最大)生成树算法。看到\(n\)的范围只有\(500\),应该没有什么特别的算法。那么我们考虑建一个*\(n\)个顶点的完全图,节点\(x\)到节点\(y\)的边权值就是\(x^y+y^x\)。然后跑一遍最大生成树,得到的和就是最大结果了。如......
  • [ABC240E] Ranges on Tree 题解
    [ABC240E]RangesonTree题解思路解析由题意可知,只要一个点的所有儿子节点都被确定了,那么当前节点也就被确定了。也就是说,只要确定了所有叶子节点,也就能一层层地确定所有节点,而叶子节点没有儿子节点不受此条件的约束,同时我们希望\(\max\limits^N_{i=1}R_i\)最小,所以我们把所......
  • ABC240 复盘
    ABC240复盘[ABC240C]JumpingTakahashi思路解析显而易见,求是否可能,用可能性dp即可。code#include<bits/stdc++.h>usingnamespacestd;constintN=1e2+10,M=1e4+10;intn,x,a[N],b[N];boolf[N][M];intmain(){ cin>>n>>x; for(inti=1;i......
  • ABC191 复盘
    ABC191复盘[ABC191C]DigitalGraffiti思路解析求不规则图形的边数,根据题目可知多边形的内角只有\(90^\circ\)和\(270^\circ\),所以只需要从四个方向扫描一遍,求出每个方向上分别有几条边即可。code#include<bits/stdc++.h>usingnamespacestd;intn,m;charch[15][15......
  • ABC349
    不用考试了/kx/kx/kx/kx/kx/kx/kxABCD一眼。E发现状态不多,可以直接搜,状态之间的转移关系很容易让人想到minimax搜索,直接做即可。注意细节。F题面没有废话,数据范围良心,做法巧妙,好评。link一看到lcm,不难想到要分解质因数,试除法可以通过,不过我们更喜欢Pollard-Rho。将\(......
  • AT_abc211_d [ABC211D] Number of Shortest paths 题解
    题目简述给定一张$n$个点$m$条边的无向无权图,问从$1$到$n$的最短路有多少条。题目分析设$cnt_i$表示从$1$到$i$的最短路条数,$dis_i$表示最短路。这道题可以考虑使用BFS做,对于一个点$v$,设第一次更新它的点为$u$,则它的转移应为$cnt_v\leftarrowcnt_u$并......