coding_note

备赛蓝桥杯时做的一些题目，记录一下

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>  //cpp实现
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  # python实现
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];  //n<=300
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];
//60%的解法 算法的复杂度为mnlogn
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;   //先生成数组包含数1-n
  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
//排列题，9！共有362880种情况，全排列即可，不会超时
#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); //9个数索引是0到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;   //这里通过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;
}

CPP
coding_note
http://jrhu0048.github.io/2024/03/20/cpp/codingnote/
作者
JR.HU
发布于
2024年3月20日
更新于
2024年10月26日
许可协议