LiaN

是一只废物捏

0%

【题解】模拟-枚举-排序

发表于 更新于 分类于 本文字数： 8.5k 阅读时长 ≈ 8 分钟
  • 主要内容
    • 一些题…

模拟

AcWing1210 连号区间数量

题意

1210. 连号区间数 - AcWing题库

概括：给定排列的数组 求连号区间的个数

思路

  • 首先，有个概念：排列，一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列。
  • 既然从a[L]到a[R]数组内的元素如果排序后严格逐个递增，那么必有max-min=R-L；题目已经说了是排列，所以不可能有相同的多个元素

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,a[N];
int main(){
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		int maxx=a[i],minn=a[i];
		for(int j=i;j<=n;j++){
			maxx = max(maxx,a[j]);
			minn = min(minn,a[j]);
			if(maxx-minn == j-i) ans++;
		}
	}
	printf("%d\n",ans);
}

AcWing1236 递增三元组

题意

1236. 递增三元组 - AcWing题库

思路

  • 首先考虑暴力求解，但至少三重循环，不太行，考虑如何优化：
  • 根据数据范围 1e5 反推，时间复杂度最多时nlogn的，并且至少会有一层遍历n，所有考虑logn的算法
  • 所以 可以循环遍历Bi，然后在A中找小于Bi的，在C中找大于Bi的；考虑用 前缀和 或者 二分的方法
    • 要求的是满足条件的三元组个数，则只需要 找到A中小于Bi个数，C中大于Bi的个数，相乘即可
  • 细节：

代码

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<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=1e5+5;
int n,a[N],b[N],c[N],sa[N],sc[N],s[N],cnt[N];
 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]++;	
	for(int i=1;i<=n;i++) scanf("%d",&b[i]),b[i]++;
	for(int i=1;i<=n;i++) scanf("%d",&c[i]),c[i]++;
	
	for(int i=1;i<=n;i++) cnt[a[i]]++;  //sa[i]: 数组a中值等于i的个数 
	for(int i=1;i<N;i++) s[i]=s[i-1]+cnt[i];  //s[i]:数组中的值 小于等于i 的个数
	for(int i=1;i<=n;i++) sa[i]=s[b[i]-1] ;//a[i]表示 小于b[i]的个数 
	
	memset(s,0,sizeof s);
	memset(cnt,0,sizeof cnt);
	for(int i=1;i<=n;i++) cnt[c[i]]++;
	for(int i=1;i<N;i++) s[i]=s[i-1]+cnt[i];
	for(int i=1;i<=n;i++) sc[i]=s[N-1]-s[b[i]];
	LL ans=0;
	for(int i=1;i<=n;i++)
		ans=ans+(LL)sa[i]*sc[i];
	cout<<ans<<endl;
	
}

AcWing1204 错误票据

题意

1204. 错误票据 - AcWing题库

思路

题目很简单，主要是复习一下输入流

getline（）的用法：接受一个字符串，可以接受空格并输出

1
2
3
string str; 
getline(cin,str); //输入：ss ss ss
cout<<str<<endl;  //输出：ss ss ss

当同时使用cin>>和getline(cin,str)的时候，在cin>>输入完成之后，getline(cin,str)(str是真正想要的串)之前，需要先getline(cin,str)（这个str是一个打算用来存储回车符的串）；将回车符从输入流缓存中清除

1
2
3
4
5
int n;
string line;
cin>>n;
getline(cin,line);
getline(cin,line);

stringstream的用法：主要用于将一个string串分割

1
2
3
4
5
6
7
8
string s;
stringstream ss;//先定义一个stringstream
int a b c;
getline(cin,s);
ss.clear();  //将ss清空
ss.str(s);   //传入一个string，将其按照空格分割,返回值是分割的串的个数
ss>>a>>b>>c;  //分割的内容输入到a b c 中
ss.fail(); //读完，返回值true；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int cnt,n;
int a[N*N];
int main(){
	ios::sync_with_stdio(false);
	cin>>cnt;
	string line;
	getline(cin,line);//因为之前有cin，这里要把换行符读走
	while(cnt--){
		getline(cin,line);//真正的一行
		stringstream ss;
		ss.str(line);  //13和14行可以合并成stringstream ss(line);
		while(ss>>a[n]) n++; // 
	} 
	sort(a,a+n);
	int res0,res1;
	for(int i=1;i<n;i++){
		if(a[i]==a[i-1]) res0=a[i];
		else if(a[i]==a[i-1]+2) res1=a[i-1]+1;
	}
	cout<<res1<<' '<<res0<<endl;
}

AcWing466 回文日期

题意

水题

思路

简单，但要复习一下之前忘记的东西

  • 从一个名为str的string中截取部分

    1
    2
    str.substr(起始下标，截取个数);
    //例如 str.substr(2,2) //从下标为2（第三个字符）开始，截取2个；即是第三个和第四个字符组成的串

  • string 转char[]

    1
    2
    string s
    a=s.c_str();

  • string类型转int

    1
    int a=atoi(str.c_str())；

  • 闰年（2月有29天）判断：非整百年份能被4整除，整百年份能被400整除

    1
    if((y%4==0&&y%100!=0 )|| (y%400==0)) return 1;

代码

自己直接模拟的，比较冗余；看了下y总的思路：因为只有8位数字，所以只需要枚举左半边一万个数，然后生成右半边对称的数，针对每个数判断是否合法以及是否在范围内即可

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;

struct D{
	int year,month,day;
};
D getDate(string a){
	int year=atoi(a.substr(0,4).c_str());
	int month=atoi(a.substr(4,2).c_str());
	int day = atoi(a.substr(6,2).c_str()); 
	D date={year,month,day};
	return date;
}
//闰年2月29天 
bool  isLeapYear(int y){
	if((y%4==0&&y%400!=0 )|| (y%400==0)) return 1;
	else return 0;
}
//判断日期的合法性 
int isValid(int y,int m,int d){
	if(m<=0||m>=13||d<=0||d>31) return 0;
	if(m==4||m==6||m==9||m==11){
		if(d>30) return 0;
	}
	if(m==2){
		if(isLeapYear(y)&&d>29) return 0;
		else if((!isLeapYear(y))&&(d>28)) return 0;
	}
	return 1;
}
int ans;
int main(){
	int ay,am,ad;
	int by,bm,bd;
	string a,b;
	cin>>a>>b;
	//判断开始日期和结束日期 
	ay=getDate(a).year;
	am=getDate(a).month;
	ad=getDate(a).day;
	
	by=getDate(b).year;
	bm=getDate(b).month;
	bd=getDate(b).day;
	
	int m=(ay%10)*10+(ay/10%10);
	int d=(ay/100%10)*10+ay/1000%10;
	if(isValid(ay,m,d)){
		if(m>am) ans++;
		else if(m==am&&d>=ad) ans++;
	}
	
	m=(by%10)*10+(by/10%10);
	d=(by/100%10)*10+by/1000%10;
	if(isValid(by,m,d)){
		if(m>bm) ans++;
		else if(m==bm&&d>=bd&&(a!=b)) ans++;
	}
	//判断中间日期 
	for(int year=ay+1;year<=by-1;year++){
		int month=(year%10)*10+(year/10%10);
		int day=(year/100%10)*10+year/1000%10;
		ans+=isValid(year,month,day);
	}
	cout<<ans<<endl;
}

AcWing1229 日期问题

题意

思路

直接暴力求解，对字符串处理判断，需要考虑重复和排序的问题

y总的思路很好：枚举从起始到终止，判断是否等于输入的日期，就可以避免排序和重复问题

水题，但是复习一下：

  • 日期的格式化输入输出 采用scanf printf比cin和cout方便
  • 数据输出最低两位，不足的高位补0输出
1
2
printf("%02d",3); //输出：03
printf("%2d",312312);//输出最低两位：12
  • 正确的日期格式判断

代码

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<bits/stdc++.h>
using namespace std;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int y,int m,int d){
	if(m==0||m>12) return 0;
	if(d==0) return 0;
	if(m!=2){
		if(d>days[m]) return 0;
	}else{
		int leap=(y%100!=0&&y%4==0)||(y%400==0);
		if(d>28+leap) return 0;
	}
	return 1;
} 
int main(){
	int a,b,c;
	scanf("%d/%d/%d",&a,&b,&c);
	for(int date=19600101;date<=20591231;date++){
		int y=date/10000,m=date%10000/100,d=date%100;
		if(check(y,m,d)){
			if(y%100==a&&m==b&&d==c||
				m==a&&d==b&&y%100==c||
				d==a&&m==b&&y%100==c
			)
			printf("%d-%02d-%02d\n",y,m,d);
		}
	}
}

AcWing1231 航班时间

  • string的back()和front()
1
2
3
4
5
6
7
8
9
10
11
12
13
string a="abcd";

1.获取字符串最后一个字符
auto b=a.back(); //结果为 b='d';

2.修改字符串最后一个字符
a.back()='!'; //结果为 a="abc!";

3.获取字符串第一个字符
auto b=a.front(); //结果为 b='a';

4.修改字符串第一个字符
a.front()='!'; //结果为 a="!bcd";

  • sscanf

    从一个字符串中读进于指定格式相符的数据。利用它可以从字符串中取出整数、浮点数和字符串。

    sscanf和scanf的区别：scanf是以键盘作为输入源，sscanf是以字符串作为输入源。

    1
    2
    3
    4
    5
    int sscanf(const char *str, const char *format,......);
    //将str按format格式读入到指定参数中；成功：返回参数个数，失败返回0

    //比如
    sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);

  • 去乘起飞时间+航行时间+时差=去乘降落时间
    回程起飞时间+航行时间-时差=回程降落时间
    航行时间 = (去乘降落时间-去乘起飞时间+回程降落时间-回程起飞时间)/2

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<bits/stdc++.h>
using namespace std;
//我焯 这个题的数据处理也太会搞了吧,学废了学废了 
int get_seconds(int h,int m,int s){
	return h*3600+m*60+s; 
}
int get_time(){
	string line;
	getline(cin,line);
	if(line.back()!=')') line+="(+0)";
	int h1,m1,s1,h2,m2,s2,d;
	sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
	return get_seconds(h2,m2,s2)-get_seconds(h1,m1,s1)+d*24*3600;
} 
int main(){
	int g;cin>>g;
	string line;
	getline(cin,line);//读去cin后的回车 
	while(g--){
		int time=(get_time()+get_time())>>1;
		int h=time/3600,m=time%3600/60,s=time%60;
		printf("%02d:%02d:%02d\n",h,m,s);
	}
	return 0;
}

AcWing446 字符串处理

题意

446. 统计单词数 - AcWing题库

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int main(){
	string a,b;
	getline(cin,a);getline(cin,b);
	transform(a.begin(),a.end(),a.begin(),::tolower);
	transform(b.begin(),b.end(),b.begin(),::tolower);
	a=" "+a+" "; //判别单词 
	b=" "+b+" "; //当a是第一个和最后一个 
	int pos=b.find(a);
	int idx=0,res=0;
	if(pos!=-1){
		idx=pos;
		while(pos!=-1){
			res++;
			pos=b.find(a,pos+1);
		}
	}else{
		cout<<-1<<endl;return 0;
	}
	cout<<res<<' '<<idx<<endl;
	return 0;
}

排序

快速排序

sort（）数据量大时采用快排,分段递归排序,一旦分段后的数据量小于某个门槛,为避免快排的递归调用带来过大的额外负荷,就改用插入排序。如果递归层次过深,还会改用堆排序，时间复杂度$nlog_{2}n$

基本思想

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[],int l,int r){
    //1、递归结束条件
	if(l>=r) return;
    //2、分治,将小于x的分到左边，大于x的分到右边
	int i=l-1,j=r+1,x=q[l+r>>1];
	while(i<j){
		do i++;while(q[i]<x);//while(q[++i]<x);
		do j--;while(q[j]>x);//while(q[--j]>x);
		if(i<j) swap(q[i],q[j]);
	}
    //3、递归处理左右两段
	quick_sort(q,l,j),quick_sort(q,j+1,r);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int q[N],tmp[N];
void merge_sort(int l,int r){
    //1、递归终止
	if(l>=r) return;
    //2、分解，归并排序左右两部分
	int mid=l+r>>1;
	merge_sort(l,mid),merge_sort(mid+1,r);
	//3、合并左右排好序的两部分
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<=q[j]) tmp[k++]=q[i++];
		else tmp[k++]=q[j++];
	}
	while(i<=mid) tmp[k++]=q[i++];
	while(j<=r) tmp[k++]=q[j++];
	for(int i=l,j=0;i<=r;i++,j++)
		q[i]=tmp[j];
}