第一种方法
暴力排序,超时了。
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
string s;
int q;
cin >> s >> q;
while(q --)
{
int a,b,c,d;
cin >> a >> b >> c >> d;
vector<char> AB, CD;
for(int i = a-1; i <= b-1; i ++)
AB.push_back(s[i]);
for(int i = c - 1; i <= d - 1; i ++)
CD.push_back(s[i]);
sort(AB.begin(), AB.end());
sort(CD.begin(), CD.end());
if(AB == CD)
cout << "DA" << endl;
else
cout << "NE" << endl;
}
return 0;
}
第二种方法
前缀和数组
#include<iostream>
#include<cstring>
using namespace std;
//这个题目字符串数组str[]就是已知差分数组,前缀和数组是A[][]
const int N = 50010;
int A[26][N];//这是26个字母的前缀和数组,A[i][j]表示A[i]这个字母从第一个字符到第j个字符出现的总次数
char str[N];
int main()
{
scanf("%s", str+1); //这里从下标1开始存,因为涉及到j-1
for(int i = 0; i < 26; i ++)
for(int j = 1; str[j]; j ++)
{
if(str[j] - 'a' == i) //如果字符相对应
A[i][j] = A[i][j-1] + 1; //前缀和公式
else
A[i][j] = A[i][j-1];
}
int m;
scanf("%d",&m);
while(m --)
{
int a, b, c, d;
scanf("%d%d%d%d",&a, &b, &c, &d);
bool status = true;
for(int i = 0; i < 26; i ++)
{//比较两个区间内每个字符出现的次数,类比[l,r]区间S[r] - S[l-1]
if(A[i][b] - A[i][a-1] == A[i][d] - A[i][c-1])
{
continue;
}
else
{
status = false;
break;
}
}
if(status == true)
printf("DA\n");
else
printf("NE\n");
}
return 0;
}
微总结
时间复杂度主要差在了main()
函数中循环内即while(m --)
,前缀和数组要是优化了每次循环的时间复杂度。