小公司做网站需要什么条件,东莞网站建设seo推广,淮安j经济开发区建设局网站,最新新闻热点事件2021年7月题目来源#xff1a;
蓝桥杯 2023 省 A]更小的数 - 洛谷
这题只需要用到双指针就OK~
思路1#xff1a;
翻转数组的子数组#xff0c;然后进行比较大小将翻转后的数组存储在字符串 k k k中#xff0c;然后将字符串 k k k与字符串 a a a进行逐一元素比较#xff08;因为…题目来源
蓝桥杯 2023 省 A]更小的数 - 洛谷
这题只需要用到双指针就OK~
思路1
翻转数组的子数组然后进行比较大小将翻转后的数组存储在字符串 k k k中然后将字符串 k k k与字符串 a a a进行逐一元素比较因为只是进行了部分元素的翻转看成整数的话位数是一一对应的且不需要考虑首项是 0 0 0的情况如果某一元素小的话就返回 t r u e , r e s 1 true,res1 true,res1这里还要说一下本题暴力求解将字符串转换为数值哪怕是开 l o n g l o n g long long longlong 也是装不下的。因为前20%的数据都有 100 100 100位
暴力40’过了前四个样例
#includebits/stdc.h
typedef long long ll;
using namespace std;
const int N5010;string a;string fan(string b,int start,int end)
{for(int istart,jend;ij;i,j--){char tb[i];b[i]b[j];b[j]t;}return b;
}bool check(string a,string b)
{int lena.size();for(int i0;ilen;i){if(a[i]b[i]) return true;else if(a[i]b[i]) return false;}return false;
}signed main()
{ll res0;cina;int la.size();string ma;for(int i0;il;i){for(int ji1;jl;j){string kfan(m,i,j);if(check(k,a)) {//coutii jjendl;res; } }}coutres;return 0;
}思路2双指针
顺着思路 1 1 1的想法发现多比较了一些区间这里进行优化。我们枚举翻转区间的左端点和右端点然后判断翻转的这个区间中的几个数字的大小就好了。如何判断因为要比较 n u m num num和 n u m n e w num_{new} numnew所以可以用两个指针 i , j i,j i,j。若字符 a i a j a_ia_j aiaj表明 n u m n e w n u m num_{new}num numnewnum若字符 a i a j a_ia_j aiaj表明 n u m n e w n u m num_{new}num numnewnum否则 a i a j a_ia_j aiaj令 i 1 j − 1 i1j-1 i1j−1直到 i j ij ij。
AC代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
const int N5010;string a;bool check(int l,int r)
{for(int il,jr;ij;i,j--){if(a[i]a[j]) return true;else if(a[i]a[j]) return false;}return false;
}signed main()
{ll res0;cina;int la.size();for(int i0;il;i){for(int ji1;jl;j){if(check(i,j)) res;}}coutres;return 0;
}
