2021.4.5

Ⅰ.pta-谷歌的招聘

素数的遍历条件可以缩减为：（最后一个测试点）

for(int i=2;i*i<a;i++)

截取字符串中连续子串 substrate()

#include<bits/stdc++.h>
using namespace std;

int main(){
	string s="12345789",s1;
	int k;
	cin>>k;
	for(int i=0;i<9-k;i++){
	s1=s.substr(i,k);
	cout<<s1<<endl;
	}
	
	return 0;
}
/*
3
123
234
345
457
578
789
*/

将int类型的数字转化为字符串

#include<bits/stdc++.h>
using namespace std;

int main(){
/* 
char *itoa( int value, char *string,int radix);
原型说明：
value：欲转换的数据。
string：目标字符串的地址。
radix：转换后的进制数，可以是10进制、16进制等。
返回指向string这个字符串的指针
*/ 
	
	
	int a=99;
	cout<<"a:"<<a<<endl;
	char c1[10];
	itoa(a,c1,2);
	cout<<"二进制："<<c1<<endl;
	char c2[10];
	itoa(a,c2,8);
	cout<<"八进制："<<c2<<endl;
	char c3[10];
	itoa(a,c3,10);
	cout<<"十进制："<<c3<<endl;
	char c4[10];
	itoa(a,c4,16);
	cout<<"十六进制："<<c4<<endl;
	
	return 0;
} 
/*
a:99
二进制：1100011
八进制：143
十进制：99
十六进制：63
*/ 

字符串转化为任意类型

 

2021.4.30

Ⅰ.2019，有几个PAT

简单dp，用四个变量分别存储2，20，201，2019的数量，用三个变量分别存储p，pa，pat的数量

//2019
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e9+7;

signed main(){
    string s;
    while(cin>>s){
    int a=0,b=0,c=0,d=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='2')
            a++;
        else if(s[i]=='0')
            b=(a+b)%N;
        else if(s[i]=='1')
            c=(c+b)%N;
        else
            d=(c+d)%N;
    }
    cout<<d%N<<endl;
    }
    return 0;
}

//PAT
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000000007;
signed main()
{
	string s;
	cin>>s;
	int a=0,b=0,c=0;
	for(int i=0;i<s.size();i++){
        if(s[i]=='P')
            a++;
        else if(s[i]=='A')
            b=(b+a)%N;
        else
            c=(b+c)%N;
	}
	cout<<c%N;
	return 0;
}

 

Ⅱ.奇妙养乐多

暴力寻找每一次的最大值并减去k——O(n)

使用优先队列——O(1)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int main()
{
	int n,m,k;
	while(cin>>n>>m>>k)
	{
		priority_queue<int>heap;
		memset(a,0,sizeof(a));
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
			heap.push(a[i]);
		}
		while(m>0&&heap.size()&&heap.top()>0)
		{
			int tops=heap.top();
			heap.pop();
			tops=tops-k;
			m--;
			heap.push(tops);
		}
		int tops=heap.top();
		if(tops<0)
		{
			tops=0;
		}
		cout<<tops+1<<endl;
	}
	return 0;
}

 

优先队列——priority_queue 

O(log n) 

大顶堆:

队头元素为最大值

//构造一个空的优先队列（此优先队列默认为大顶堆）
priority_queue<int> big_heap;   

//另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2;   

小顶堆：

队头元素为最小值

//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;   

operator<

 

 

Ⅲ.a+b

int，long的范围：

4byte=32bit

signed范围：2^31-1 ~ -2^31即：2147483647 ~ -2147483648

unsigned范围：2^32-1 ~ 0即：4294967295 ~ 0

double的范围：

 8 byte = 64 bit

范围：1.79769e+308 ~ 2.22507e-308

double是8字节共64位，其中小数位占52位，float型只能保证6位有效数字，而double型至少可以保证15位有效数字（小数点后的数位），2-^52=2.2204460492503130808472633361816e-16，量级为10^-16，故能够保证2^-15的所有精度。

long long的范围：

最大值：9223372036854775807（>10^18）
最小值：-9223372036854775808