累死自己卷死室友


私信TA

用户名:52hertz

访问量:11214

签 名:

刷题好!

等  级
排  名 1676
经  验 2651
参赛次数 2
文章发表 3
年  龄 0
在职情况 学生
学  校 吉林大学
专  业 软件工程

  自我简介:

解题思路:

        中心思想:s[l] > s[r]则满足条件,答案的个数+1。

        详细解释:考虑s的所有子串[l,r], l即left,是子串的起始下标,r即right是子串的末尾下标,判断s[l] 和 s[r]的大小关系:

                若s[l] > s[r]则该子串反转后,新串<原串,满足条件,答案数+1;

                若s[l] = s[r]则将子串区间[l,r]缩小为[l+1,r-1],再判断s[l+1]和s[r-1]的大小关系;

                若s[l] < s[r]则该子串反转后,新串>原串,不满足条件。


注意事项:

         注意l和r的取值范围(详见代码注释)。

参考代码:

#include<iostream>
#include<string>
using namespace std;
string s;
int F(int l, int r) {
	while (l < r) {
		if (s[l] > s[r])return 1;//如果s[l] > s[r],反转后满足条件 新字符串<原字符串。
		else if (s[l] == s[r]) { l++;r--; }//如果s[l] == s[r],两边同时缩小区间。
		else break;//如果s[l] < s[r],不用继续考虑,反转后一定不满足条件,直接退出循环
	}
	return 0;
}
int main(){
	cin >> s;
	int n = s.length();//n是字符串长度
	int ans = 0;//记录答案
	for (int l = 0;l <= n - 2;l++) {//l即left是子串的起始下标,从0开始到n-2(子串长度至少为2,最右侧的最小子串下标为[n-2,n-1],故l最多到n-2)
		for (int r = n - 1;r > l;r--) {//r即right是子串的末尾下标,从s的最末下标n-1到l+1。
			if(F(l,r))ans++;
		}
	}
	cout << ans;
	return 0;
}


 

0.0分

41 人评分

  评论区

这样写时间不是O(n^3)了吗,为什么时间能过呢?
2024-03-28 19:40:03
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int ans=0;
	string num;
	cin>>num;
	for(int l=0;l<=num.length()-2;l++)
		for(int r=l+1;r<=num.length()-1;r++)
		{
			int i=l;
			int j=r;
			while(i<j)
			{
				if(num[i]<num[j])	break;
				if(num[i]>num[j]){
					ans++;
					break;
				}
				if(num[i]=num[j]){
					++i;
					--j;
				}
			}
		}
		cout<<ans<<endl;
		return 0;
}
2024-03-12 20:16:42
为什么不是小于的时候也一样再缩减范围呢,缩减之后的范围有可能满足条件啊
2024-03-04 14:20:59
题解有问题吧,主函数里内层循环r的循环条件是错的
2024-02-17 11:12:46
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
string s;

int compare(int i, int j) {
	while (i < j) {
		if (s[i] < s[j]) return 0;
		if (s[j] < s[i]) return 1;
		else {
			i++;
			j--;
		}
	}
}
int main() {
	getline(cin, s);
	int n = s.length(), count = 0;
	for (int i = 0; i < n - 1; i++)
		for (int j = i + 1; j < n; j++) {
			if (compare(i, j) == 1) {
				count++;
			}
		}
	cout << count;
	return 0;
}
2024-01-23 21:24:10
6
2023-11-19 22:41:25
我请想问一下,当两个数相同l++,r--,如果s[l] > s[r]成立ans++,但这种情况在主函数里循环到这个l和r的时候ans不会再加一次么?
2023-10-29 20:59:00
#include<iostream>
#include<cstring>
#include<sstream>
using namespace std;
string s;
int F(int r, int l)
{
    while (l < r)
    {
        if (s[l] < s[r])return 0;
        else if (s[l] > s[r])return 1;
        else
        {
            l ++;
            r --;
        }
    }
}
int main()
{
    getline(cin, s);
    int n = s.length(),count=0;
    for (int l = 0; l <= n - 2; l++)
    {
        for (int r = n - 1; r > l; r--)
        {
            if (F(r, l))count++;
        }
    }
    cout << count;
}
2023-09-26 00:59:27
  • «
  • 1
  • »