#集训营日记#北京德闳营X02-2班笔记
2024-07-25 16:48:44
发布于：北京
本人学习笔记
枚举算法
枚举算法是一种将问题的所有可能结果一一列举，并用条件检验是否成立的解题思维。
埃氏筛法
把不大于根号n的所有素数的倍数全部剔除，剩下的自然数就都是素数。
线性
每个数都被它最小的质数筛掉。
T20333.输出素数个数2
#include<bits/stdc++.h>
using namespace std;
const int N=4000100;
bool vis[N];//vis[i]=false 表示是素数 vis[i]=true 表示不是素数
int main(){
int n;
cin>>n;//输入n
vis[1]=true;//1不是素数，标记成true
for(int i=2;i<=sqrt(n);i++){
//不大于sqrt(n) 的素数的倍数筛掉
if(vis[i]==false){//如果i是素数
//把i的倍数全部去掉
for(int j=2*i;j<=n;j+=i){
vis[j]=true;
}
}
}
int cnt=0;//计数器
for(int i=1;i<=n;i++)cnt+=(vis[i]==false);
cout<<cnt;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=100000000+100;
int prime[N],vis[N],cnt;
int main(){
vis[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i])prime[cnt++]=i;
for(int j=0;j<cnt && i*prime[j]<=n;j++){
vis[i=prime[j]]=1;
if(i%prime[j]==0)break;
}
}
int cnt=0;//计数器
for(int i=1;i<=n;i++)cnt+=(vis[i]==0);
cout<<cnt;
return 0;
}
vector的定义
vector<int>v;//定义一个类型为整型的动态数组
push_back()//函数插入元素
vector的访问，访问的下标范围0~v.size()-1,v.size()为动态数组v中的元素个数#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int>a;
a.push_back(3);
a.push_back(5);
a.push_back(1);
for(int i=0;i<a.size();i++){
cout<<a[i]<<"\n";
}
return 0;
}
vector初始化
vector<int>v(10,-1);
iota(v.begin(),v.end(),1); 输出 1~10的数字
sort(a.begin(),a.end()); 排序
结构体定义
#include<bits/stdc++.h>
using namespace std;
struct student{
int start;//开始时间
int end;//结束时间
}a[2000];
bool cmp(student x,student y){
return x.end<y.end;
}
二进制 B
八进制 O
十进制 D
十六进制 H
二进制转八进制：整数部分从右往左，小数部分从左往右
k进制转十进制
按权展开法：将各个数码与它的权值相乘
十进制转k进制
整数部分：除k取余 逆序排列
小数部分：乘k取整 顺序排列
符号位：0正，1负
反码:正数的反码和正数的原码一样，负数的反码是其原码符号位不变
其余各位取反所获得的码
补码：正数的补码和正数的原码一样，负数的补码是其反码加1
位运算：以二进制形式存储
常见位运算操作符：1.按位与& 2.按位或| 3.按位非~
4.按位异或^ 5按位左移<< 6.按位右移>>
按位与& 对两个数字进行比较，其余为零
1&1=1 其他为0
按位异或^
0^1=1
1^0=1
0^0=0
1^1=0
右移：n>>m相当于n/2m(整除)
左移：n<<m相当于n*2m
二进制转格雷码
1.二进制码的最高位作为格雷码最高位
2.格雷码的其余为位二进制码对应位于其上一位相异或
1字节=8bit
#include<bits/stdc++.h>
using namespace std;
int a[200];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
int x;
cin>>x;
int pos=lower_bound(a+1,a+n+1,x)-a;
cout<<pos<<"\n";
int pos2=upper_bound(a+1,a+n+1,x)-a;
cout<<pos2<<"\n"
return 0;
}
栈（stack） 先进后出
FILO
入栈（push） 出栈（pop）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int stk[N+10];
int top=0;
void push(int x){
top;
stk[top]=x;
}
void pop(){
top--;
}
bool empty(){
return top==0;
}
int size(){
return top;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i){
int x;
cin>>x;
push(x);
for(int j=1;j<=top;j++){
cout<<stk[j]<<" ";
cout<<endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int q[N];
int head=0;
int tail=0;
int main(){
return 0;
}
有帮助，赞一个