致60分
查看原帖
致60分
519605
Seven_tc楼主2025/1/7 03:07

按照题解的说法不论是s.compare还是重载的==,大概都是O(n)的时间复杂度,当T,n和q比较大时非常容易超时,而且我就改了一个字符,没必要把所有位置都再比较一次吧?

思路大概是第一次出现两个字符串时统计不相同位置的数量cnt,如果cnt为0那么相同,否则不相同。

其后每一次修改,需要判断四种情况(其实就两种)

改之前s[p-1]和t[p-1]相同,改之后s[p-1]和t[p-1]相同,那么cnt不变(忽略不写)

改之前s[p-1]和t[p-1]相同,改之后s[p-1]和t[p-1]不相同,那么cnt++(不相同位置的数量增加一个)

改之前s[p-1]和t[p-1]不相同,改之后s[p-1]和t[p-1]不相同,那么cnt不变(忽略不写)

改之前s[p-1]和t[p-1]不相同,改之后s[p-1]和t[p-1]相同,那么cnt--(不相同位置的数量减少一个)

之后再判断cnt就可以啦,不必要再判断n次,以下给出部分AC代码

#include<iostream>
#define endl '\n'
//#define int long long
using namespace std;
//const int N = 1e6 + 5;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
  
	return 0;
}


2025/1/7 03:07
加载中...