备赛蓝桥杯时做的一些题目,记录一下
next_permutation()
在C++中,std::next_permutation
是一个标准库函数,用于生成序列的下一个排列。这个函数定义在头文件
<algorithm>
中,可以用于遍历一个序列的所有可能的排列。
std::next_permutation
函数的基本用法如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 #include <algorithm> #include <iostream> #include <string> int main () { std::string s = "ABC" ; if (std::next_permutation (s.begin (), s.end ())) { std::cout << "The next permutation is: " << s << std::endl; } else { std::cout << "There are no more permutations." << std::endl; } return 0 ; }
在这个例子中,std::next_permutation
函数尝试为字符串
s
生成下一个排列。如果成功,函数返回
true
,并且 s
会被更新为下一个排列。如果已经是最后一个排列,函数返回
false
,s
保持不变。
函数的参数是序列的开始和结束迭代器。对于数组,可以使用数组的指针或数组的引用作为参数。例如:
1 2 int arr[] = {1 , 2 , 3 }; std::next_permutation (arr, arr + sizeof (arr) / sizeof (arr[0 ]));
在使用 std::next_permutation
时,通常将其放在一个循环中,以便遍历序列的所有排列。例如:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <algorithm> #include <iostream> #include <vector> int main () { std::vector<int > v = {1 , 2 , 3 }; do { for (int i : v) { std::cout << i << ' ' ; } std::cout << '\n' ; } while (std::next_permutation (v.begin (), v.end ())); return 0 ; }
在这个例子中,do-while
循环确保了即使在最后一次调用
std::next_permutation
后,循环体内的代码也会执行,从而打印出最后一个排列。然后,std::next_permutation
被调用,尝试生成下一个排列。循环会一直继续,直到所有的排列都被遍历完毕。
无重复字符的最长子串
给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。
希哈表+快慢指针 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int lengthOfLongestSubstring (char * s) { int result = 0 , i = 0 , j = 0 ; int length = strlen (s); int cnt[128 ] = { 0 }; for (j = 0 ; j < length; j++) { cnt[s[j]]++; if (cnt[s[j]] > 1 ) { result = result < j - i ? j - i : result; for (int k = i; k < j; k++) { cnt[s[k]]--; if (s[k] == s[j]) { i = k; break ; } } i++; } } result = result < j - i ? j - i : result; return result; }
对一列数排序(火星人)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iostream> #include <bits/stdc++.h> using namespace std;int main () { int n,m; int a[10110 ]; cin>>n; cin>>m; for (int i=1 ;i<=n;i++) { cin>>a[i]; } while (m--) { next_permutation (a+1 ,a+1 +n); } for (int i=1 ;i<=n;i++) { cout<<a[i]<<" " ; } return 0 ; }
排列序数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream> #include <bits/stdc++.h> using namespace std;int main () { string s,o; cin>>s; o=s; sort (s.begin (),s.end ()); if (s==o) cout<<0 ; int cnt=0 ; while (next_permutation (s.begin (),s.end ())) { cnt++; if (s==o) cout<<cnt; } return 0 ; }
第几个幸运数字
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> using namespace std;int main () { long long n=59084709587505 ; int cnt=0 ; for (int i=0 ;pow (3 ,i)<n;i++) { for (int j=0 ;pow (5 ,j)<n;j++) { for (int k=0 ;pow (7 ,k)<n;k++) { if (pow (3 ,i)*pow (5 ,j)*pow (7 ,k)<=n) cnt++; } } } printf ("%d" ,cnt-1 ); return 0 ; }
1 2 3 4 5 6 7 8 9 10 import os import sys cnt=0 for i in range (50 ): for j in range (50 ): for k in range (50 ): a=3 **i;b=5 **j;c=7 **k if a*b*c<=59084709587505 : cnt+=1 print (cnt-1 )
奖学金
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <iostream> #include <bits/stdc++.h> using namespace std;struct stu { int id; int c,m,e; int sum; }st[305 ]; bool cmp (stu a,stu b) { if (a.sum>b.sum) return true ; else if (a.sum<b.sum) return false ; else { if (a.c>b.c) return true ; else if (a.c<b.c) return false ; else { if (a.id>b.id) return true ; else return false ; } } }int main () { int n; cin>>n; for (int i=0 ;i<n;i++) { st[i].id=i+1 ; cin>>st[i].c>>st[i].m>>st[i].e; st[i].sum=st[i].c+st[i].m+st[i].e; } sort (st,st+n,cmp); for (int i=0 ;i<5 ;i++) { cout<<st[i].id<<" " <<st[i].sum<<"\n" ; } return 0 ; }
双向排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <iostream> #include <bits/stdc++.h> using namespace std;const int N =1e5 +10 ;int a[N];bool cmp (int a ,int b) { return a>b; }int main () { int n,m; cin>>n>>m; for (int i=1 ;i<=n;i++) a[i]=i; while (m--) { int p,q; cin>>p>>q; if (p==1 ) sort (a+q,a+n+1 ); if (p==0 ) sort (a+1 ,a+q+1 ,cmp); } for (int i =1 ;i<=n;i++) { cout<<a[i]<<' ' ; } return 0 ; }
错误票据
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream> #include <bits/stdc++.h> using namespace std;const int N=1e4 +10 ;int m[N];int main () { int n; cin>>n; int cnt=0 ; while (scanf ("%d" ,&m[cnt])!=EOF) cnt++; sort (m,m+cnt); int ans1,ans2; for (int i=0 ;i<cnt-1 ;i++) { if (m[i+1 ]-m[i]>1 ) ans1=m[i]+1 ; if (m[i]==m[i+1 ]) ans2=m[i]; } cout<<ans1<<' ' <<ans2; return 0 ; }
统计数字
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include <iostream> #include <bits/stdc++.h> using namespace std;int m[200010 ];int main () { int n; scanf ("%d" ,&n); for (int i=0 ;i<n;i++) { scanf ("%d" ,&m[i]); } sort (m,m+n); int cnt=0 ; for (int i=0 ;i<n;i++) { cnt++; if (m[i]!=m[i+1 ]) { printf ("%d %d\n" ,m[i],cnt); cnt=0 ; } } return 0 ; }
求和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream> using namespace std;int main () { long long n; cin>>n; int a[200005 ]; long long sum=0 ; long long temp=0 ; for (int i=0 ;i<n;i++) { scanf ("%d" ,&a[i]); temp +=a[i]; } for (int i=0 ;i<n;i++) { temp-=a[i]; sum += a[i]*temp; } printf ("%lld" ,sum); return 0 ; }
782 拼数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <bits/stdc++.h> using namespace std;bool cmp (string a,string b) { return a+b>b+a; }int main () { int n; cin>>n; string a[n]; for (int i=0 ;i<n;i++) cin>>a[i]; sort (a,a+n,cmp); for (int i=0 ;i<n;i++) cout<<a[i]; return 0 ; }
208 带分数
这题我不是很会,参考了题解,懂了一点,感觉好复杂啊啊啊啊啊
仔细看还是很好理解的,就是不太好想到欸,还是自己太菜了。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <bits/stdc++.h> using namespace std;int num[9 ]={1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 };int cnt;int func (int a,int b) { int sum=0 ; for (int i=a;i<=b;i++) { sum=sum*10 +num[i]; } return sum; }int main () { int n; cin>>n; while (next_permutation (num,num+9 )) { for (int i=0 ;i<7 ;i++) { for (int j=i+1 ;j<8 ;j++) { int a=func (0 ,i); int b=func (i+1 ,j); int c=func (j+1 ,8 ); if (n*c==a*c+b) { cnt++; } } } } cout<<cnt; return 0 ; }
回文判定(双指针/反向扫描)
实现一 for循环 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <bits/stdc++.h> using namespace std;int main () { string s; cin>>s; int n=s.size (); int cnt=0 ; for (int i=0 ;i<n/2 ;i++) if (s[i]!=s[n-i-1 ]) cnt++; if (cnt!=0 ) cout<<'N' ; else cout<<'Y' ; return 0 ; }
实现二 for循环加改进 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <bits/stdc++.h> using namespace std;int main () { string s; cin>>s; int n=s.size (); int cnt=0 ; for (int i=0 ;i<n/2 ;i++) if (s[i]!=s[n-i-1 ]) { cout<<'N' ; return 0 ; } cout<<'Y' ; return 0 ; }
实现三 使用while循环 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std;int main () { string s; cin>>s; int n=s.size (); int i=0 ,j=n-1 ; while (i<j) { if (s[i]!=s[j]) { cout<<'N' ; return 0 ; } i++,j--; } cout<<'Y' ; return 0 ; }