首页 > 其他分享 >题解:AT_abc370_c [ABC370C] Word Ladder

题解:AT_abc370_c [ABC370C] Word Ladder

时间:2024-09-07 23:03:47浏览次数:9  
标签:ch int 题解 ABC370C texttt top 先改 越改越 Ladder

说句闲话

并不会有更好的阅读体验。

这题是一个比较奇葩的贪心、构造。也可以认为是一个数据结构略有难度的练习题。

理论部分

?> 注:使用 \(N\) 表示字符串长度。

段话题意:三个字符串 \(S\)、\(T\)、\(X\),其中 \(S\) 和 \(T\) 仅包含小写字母且等长,\(X\) 为空。每一个操作可以把对应的 \(S_i\) 修改为 \(T_i\),但需要把改完后的整个 \(S\) 加进 \(X\) 里,求最少步数及方案,要求方案最后得到的 \(X\) 字典序最小。

这咱办呢?首先是等长的,所以只需要修改一定能达成——每次把不对应的修改成对应的不就可以了?因此步数很好求:不匹配的位置的个数。

现在问题就是怎样最小?

首先能够明确的是:既然等长,那么开头最小字符串最小,正常不都是这么比较的吗(

比如说,字符串 \(S = \texttt{abc}\) 和 \(T = \texttt{abd}\),前面 \(\texttt{ab}\) 相同,\(\texttt{b} < \texttt{c}\),因此 \(S < T\)。

这样子就好办了:目标最小,那么就把它改的尽量小嘛。

如何尽量小?兜圈子呢。

首先肯定是越改越小好,不然你越改越大在小还不如先改小的呢是吧~

如果想要尽量小,那么肯定是要先改前面的且是改小的;后面往大了改的同理,先改后面的在改前面的。

这句话比较绕,也是这个思路的核心。总结一下其实就是把这 \(N\) 个位置分成三类,如下:

  1. \(S_i = T_i\),完全一致,不用管
  2. \(S_i > T_i\),越改越小,优先改,越早出现的越优先改
  3. \(S_i < T_i\),越改越大,最后改,而且越晚出现的越后改。

以上的规则基于题目规则,\(S_i\) 表示 \(S\) 中某字符,\(T_i\) 同理。两条更改的规则是因为越往前的越需要把它停留在小的状态,因此越改越小优先改,越改越大则先改后面的。

还是举个例子。

\(S = \texttt{xay}, T = \texttt{abe}\),我们想要尽量小,那么按照这个逻辑,先筛出最往小了改的,就是第一个和最后一个位置。它们当中第一个位置最前,因此先改它,\(S\) 变为 \(\texttt{aay}\),然后是第三个位置,变成 \(\texttt{aae}\),最后在去改第二个位置,变成 \(\texttt{abe}\)。


时间复杂度分析

这个算法是 \(O(N ^ 2)\) 的,而且本题最优解的最坏时间复杂度也是这个值。

为什么?因为最坏情况下我们需要对每一个位置进行更改,而每次输出这个长度,因此输出就是这个复杂度,没法优化了。

我才不会告诉你这是我冒充这是个 \(O(N)\) 算法结果被学长发现了才写这一段的。


ACCode with 注释:

/*Code by Leo2011*/
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define EPS 1e-8
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define log printf
#define IOS                      \
	ios::sync_with_stdio(false); \
	cin.tie(nullptr);            \
	cout.tie(nullptr);

using namespace std;

typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;

int ret, len;
deque<int> a, b;
string s, t;

template <typename T>

inline T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>

inline void write(T x) {
	if (x < 0) {
		putchar('-'), write<T>(-x);
		return;
	}
	static T sta[35];
	int top = 0;
	do { sta[top++] = x % 10, x /= 10; } while (x);
	while (top) putchar(sta[--top] + 48);
}

int main() {
	IOS;
	cin >> s >> t;
	len = s.size();
	for (int i = 0; i < len; ++i)
	if (s[i] != t[i]) {
		++ret;
		if (s[i] < t[i]) b.push_front(i);  /* 考场留下的写法,这一行是说要往大了改的放到 b 里,而且越后出现的越先改*/
		else a.push_back(i);  /*同上,反过来*/
    /*这里之所以用 deque 主要是因为统一:下面可以统一使用 front 而不用在倒腾 front 和 back*/
	}
	cout << ret << endl;
	while (!a.empty()) {  /*先处理 a 改小*/
		s[a.front()] = t[a.front()];
		cout << s << endl;
		a.pop_front();  /*一定要pop*/
	}
	while (!b.empty()) {  /*再处理 b 改大*/
		s[b.front()] = t[b.front()];
		cout << s << endl;
		b.pop_front();
	}
	return 0;
}

AC 记录~

理解万岁!

标签:ch,int,题解,ABC370C,texttt,top,先改,越改越,Ladder
From: https://www.cnblogs.com/leo2011/p/18402291

相关文章

  • CF2002D2 DFS Checker (Hard Version) 题解
    https://codeforces.com/problemset/problem/2002/D2考虑找一个容易维护的必要条件,再证明充分性。最容易想到的是每个子树对应一个区间,子树根位于左端点sol1相邻的结点\(p_{i-1},p_i\)有两种情况:\(fa[p_i]=p_{i-1}\);叶子\(p_{i-1}\)在子树\(fa[p_i]\)中,回溯到\(fa[......
  • abc370 A-E题解 (AtCoder Beginner Contest 370)
     A这类简单题,看清楚:OutputPrint Yes, No,or Invalid accordingtotheinstructionsintheproblemstatement. B Cstd,这样写(0->n-1,n-1->0),可以少写一个vector1#include<bits/stdc++.h>2usingnamespacestd;34intmain(){5strings,......
  • 题解:Toyota Programming Contest 2024#9(AtCoder Beginner Contest 370)
    总体情况这次手速够快:ABCin10min,ABCDEin30min。A-RaiseBothHands思路分类讨论很简单的。注意一定要判断\(0,0\)这种情况。Code//Problem:A-RaiseBothHands//Contest:AtCoder-ToyotaProgrammingContest2024#9(AtCoderBeginnerContest370)//URL:......
  • 天翼云存储SpinTires问题解析:d3dx9_43.dll文件丢失应对指南
    在使用天翼云存储或运行SpinTires等游戏时,有时会遇到系统提示“d3dx9_43.dll文件丢失”的错误。这个问题通常是由于DirectX组件中的d3dx9_43.dll文件未正确安装、损坏或丢失所导致的。以下是一些应对指南,帮助您解决这一问题:一、了解d3dx9_43.dll文件的重要性d3dx9_43.dll是D......
  • 东方博宜oj题解1161-1165(c++)
    各位读者们,抱歉,因为最近的时间原因,所以更新频率比较低。1161:1161-元素插入有序数组-东方博宜OJ#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn,s,c; cin>>c>>n; inta[n];//定义数组 for(inti=0;i<n;i++){ cin>>a[i]; } s=n;//设c是最大的......
  • 洛谷 P4829 kry loves 2048——题解
    洛谷P4829题解传送锚点摸鱼环节kryloves2048题目背景kls是一个人赢。题目描述kls最近在玩一款类似2048的游戏,规则是这样的:一开始,有\(n\)个方块,每个方块上有一个\(1\)到\(m\)的整数。kls可以进行两种操作:选择两个数字相同的方块(不一定要相邻),将它们合并成一个数字为......
  • 【题解】【动态规划】—— [NOIP2001 普及组] 装箱问题
    【题解】【动态规划】——[NOIP2001普及组]装箱问题[NOIP2001普及组]装箱问题题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.题意解析2.AC代码2.1.二维d......
  • 【题解】—— [NOIP2005 普及组] 陶陶摘苹果
    【题解】——[NOIP2005普及组]陶陶摘苹果[NOIP2005普及组]陶陶摘苹果题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.题意解析2.AC代码[NOIP2005普及组]陶陶摘苹果通往洛谷的传送门题目描述陶陶家的院子里有一棵苹果树,每到秋天树上就会结出......
  • 【题解】【结构体排序】——[NOIP2007 普及组] 奖学金
    【题解】【结构体排序】——[NOIP2007普及组]奖学金[NOIP2007普及组]奖学金题目背景题目描述输入格式输出格式输入输出样例输入#1输出#1输入#2输出#21.题意解析2.AC代码[NOIP2007普及组]奖学金通往洛谷的传送门题目背景NOIP2007普及组T1题目描述某......
  • [ABC328G] Cut and Reorder 题解
    [ABC328G]CutandReorder题解题目不难,思维难度尚可。首先需要发现的性质是\(1\)操作的次数最多只需要使用一次,使用多少次其实都是等价的。\(n\le22\)显然考虑状压dp。平凡的想法是设\(dp_{i,j}\)表示填数的状态为\(i\),最后一个填的是\(j\)位置的数的最小代价。这......