笔记
Fractsidus · · 个人记录
头文件
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e8+10;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
return 0;
}求质数
普通质数求法
#include<bits/stdc++.h>
using namespace std;
bool s(int a){
if(a<2){
return false;
}
for(int i=2;i*i<=a;i++){
if(a%i==0){
return false;
}
}
return true;
}
int main(){
}质数筛
vis[1]=1;
for(int i=1;i<=n;i++){
if(vis[i]==1) continue;
for(int j=2*i;j<=n;j+=i){
vis[j]=1;
}
}字符串
大小写转换
string f1(string a){
for(int i=0;i<a.size;i++){
if(a[i]>='a'&&a[i]<='z'){
a[i]-='a'-'A';
}
else if(a[i]>='A'&&a[i]<='Z'){
a[i]+='a'-'A';
}
}
return a;
}反转字符串
string f2(string a){
string f="";
for(int i=a.size()-1;i>=0;i--){
f+=a[i];
}
return f;
}map
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int n;
int main(){
cin>>n;
for(int i=0;i<n;i++){
int t;
cin>>t;
mp[t]++;
}
for(auto t:mp){
cout<<t.first<<' '<<t.second<<endl;
}
return 0;
}
sort 排序
bool cmp(no x,no y){
if(x.fe != y.fe) return x.fe > y.fe;
return x.mi < y.mi;
}进制
10 进制转 x 进制
#include<bits/stdc++.h>
using namespace std;
long long n;
long long i1;
long long x;
long long a[111111111];
int main(){
cin>>n>>x;
if(n==0||n==1){
cout<<n;
return 0;
}
long long c=n;
while(c){
i1++;
a[i1]=c%x;
c/=x;
}
for(int i=i1;i>=1;i--){
if(a[i]<=9) cout<<a[i];
else cout<<char(a[i]-10+'A');
}
}x 进制转 10 进制
#include <bits/stdc++.h>
using namespace std;
int x, a[10555];
string s;
int c(char c) {
if('0'<=c&&c<='9') return c-'0';
return c-'A'+10;
}
int main() {
cin>>x>>s;
int len=s.size();
for(int i=len-1;i>=0;i--)
a[len-1-i]=c(s[i]);
int ans=0,a1=1;
for(int i=0;i<len+1;i++){
ans+=a1*a[i];
a1*=x;
}
cout<<ans;
return 0;
}队列
初始状态：
haed=tail=0队尾插入：
q[tail]=x;
弹出队首：
head++；使用队首：
cout<<q[head];使用队尾：
cout<<q[tail-1];查找元素：
tail-head;pair
在 C++ 中，pair 是一个模板类，用于将两个不同类型的数据组合成一个单元。以下是其主要用法和特点：
- 基本定义与头文件 pair 定义在<utility>头文件中，使用时需包含该头文件。 类模板声明形式为：template\<class T1, class T2> struct pair;，其中 T1 和 T2 分别为两个成员的数据类型。
- 成员变量 first：存储第一个数据，类型为 T1。 second：存储第二个数据，类型为 T2。
- 初始化方式 默认构造：pair \<T1, T2> p;（成员值未初始化）。 直接初始化：pair \<T1, T2> p (val1, val2);。 拷贝构造：pair \<T1, T2> p2 (p1);。 使用 make_pair：auto p = make_pair (val1, val2);（自动推导类型）。
- 常用操作 访问成员：通过 p.first 和 p.second 直接访问。 赋值操作：支持 = 赋值，如 p1 = p2; 或 p1 = make_pair (val1, val2);。 比较操作：按字典序比较（先比较 first，再比较 second）。
- 典型应用场景 STL 容器：如 map、unordered_map 的键值对存储。 函数多返回值：通过 pair 返回两个值。 排序与优先队列：可作为 priority_queue 的元素，自定义排序规则。 示例代码
#include <iostream>
#include <utility>
using namespace std;
int main() {
// 初始化
pair<int, string> p1(1, "apple");
auto p2 = make_pair(2.5, "banana");
// 访问成员
cout << p1.first << ", " << p1.second << endl; // 输出: 1, apple
// 比较
pair<int, int> a(1, 2), b(1, 3);
cout << (a < b) << endl; // 输出: 1 (true)
return 0;
}
- 扩展说明 与 tuple 的区别：pair 仅支持两个元素，而 tuple 支持多个元素。 性能：因底层为结构体，直接访问成员变量效率较高。
通过灵活使用 pair，可以简化需要组合数据的场景，提升代码可读性和维护性。
二分
普通二分
int l=1-1,r=n+1;
while(l+1<r){
int mid=(l+r)/2;
if(x==a[mid]) {
cout<<mid;
return 0;
}
else if(x<a[mid]) r=mid;
else l=mid;
} 二分查找右侧边界
int l=1-1,r=n+1;
while(l+1<r){
int mid=(l+r)/2;
if(a[mid]<=x) l=mid;
else r=mid;
}
if(a[l]==x) cout<<l<<' ';
else cout<<"-1"<<' ';二分查找左边界
int l=1-1,r=n+1;
while(l+1<r){
int mid=(l+r)/2;
if(a[mid]>=x) r=mid;
else l=mid;
}
if(a[r]==x) cout<<r<<' ';
else cout<<"-1"<<' ';
函数二分
质数筛
vis[1]=1;
for(int i=1;i<=n;i++){
if(vis[i]==1) continue;sum++;
for(int j=2*i;j<=n;j+=i){
vis[j]=1;
}
}
cout<<sum;位运算
cout<<(a&b)<<endl;
cout<<(a|b)<<endl;
cout<<(a^b)<<endl;
cout<<(~a)<<endl;
cout<<(a<<k)<<endl;
cout<<(a>>k);DFS
迷宫搜索（判断是否能到）
bool vis[2005][2005];
int f=0;
void dfs(int x,int y){
if(x>n||y>n||x<1||y<1||a[x][y]==1||vis[x][y]==1) return;
vis[x][y]=1;
if(x==ex&&y==ey){
f=1;
return;
}
dfs(x,y+1);
dfs(x+1,y);
dfs(x,y-1);
dfs(x-1,y);
}全排列（第 k 种）
#include<bits/stdc++.h>
using namespace std;
int n,k;
int box[100005],vis[100005];
int sum;
void dfs(int x){
if(x>n){
sum++;
if(sum==k){
for(int i=1;i<=n;i++){
cout<<box[i]<<' ';
}
exit(0);
}
return ;
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
vis[i]=1;
box[x]=i;
dfs(x+1);
vis[i]=0;
}
}
int main(){
cin>>n;
cin>>k;
dfs(1);
}全排列
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e5+10;
int n,k;
int a[15],ans;
int box[15];
bool vis[15];
void dfs(int x,int last){
if(x>k){
for(int i=1;i<=k;i++){
cout<<box[i]<<' ';
}
cout<<endl;
return;
}
for(int i=last+1;i<=n;i++){
if(vis[i]==1) continue;
vis[i]=1;
box[x]=i;
dfs(x+1,i);
vis[i]=0;
}
return;
}
int main(){
cin>>n>>k;
dfs(1,0);
}高精度
加法
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e8+10;
vector<int> stov(string a) {//字符串转换为vector
vector<int> res;//逆序存储
for(int i=a.size()-1;i>=0;i--){
res.push_back(a[i]-'0');//字母转换为数字
}
return res;
}
vector<int> add(vector<int> a1,vector<int>a2){
//传入的vector默认是逆序存储
vector<int> res;//存储最终结果
int t=0;//辅助计算/存储进位
int len=max(a1.size(),a2.size());//更大的数
for(int i=0;i<len;i++){
if(i<a1.size()) t+=a1[i];
if(i<a2.size()) t+=a2[i];
//防止越界
res.push_back(t%10);//算这一次的结果
t/=10;//计算下一次的进位
}
if(t>0){
res.push_back(t);//考虑最高位是否进位
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string a,b;
cin>>a>>b;
vector<int> res=add(stov(a),stov(b));
for(int i=res.size()-1;i>=0;i--){//和字符串一样从0开始长度-1结束
cout<<res[i];//逆序存储所以逆序输出
}
return 0;
}减法
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e8+10;
bool f;
vector<int> stov(string a) {//字符串转换为vector
vector<int> res;//逆序存储
for(int i=a.size()-1;i>=0;i--){
res.push_back(a[i]-'0');//字母转换为数字
}
return res;
}
bool cmp(string a,string b){//判断a是否<b,如果是的返回true
if(a.size()!=b.size()) return a.size()<b.size();//数位比较
return a<b; //按位比较
}
vector<int> sub(vector<int> a1,vector<int> a2){
//默认a1>=a2
vector<int> res;//最后结果存储
int t=0;//辅助计算
for(int i=0;i<a1.size();i++){
t=a1[i]-t;
if(i<a2.size()){//判断a2[i]是否越界
t-=a2[i]; //等同于a1[i]-a2[i]-t;
}
if(t<0){//这一次的结果<0说明要借位
res.push_back(t+10);
t=1;
}
else {//没有越界则正常处理
res.push_back(t);
t=0;
}
}
while(res.size()>1&&res.back()==0){
res.pop_back();
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string a,b;
cin>>a>>b;
if(cmp(a,b)){//若a<b
swap(a,b);
f=1;//标记是否是负数
}
if(f==1){
cout<<'-';
}
vector<int>res;
res=sub(stov(a),stov(b));
for(int i=res.size()-1;i>=0;i--){
cout<<res[i];
}
return 0;
}高精度乘低精度
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e8+10;
vector<int> stov(string a) {//字符串转换为vector
vector<int> res;//逆序存储
for(int i=a.size()-1;i>=0;i--){
res.push_back(a[i]-'0');//字母转换为数字
}
return res;
}
vector<int> mul(vector<int>a,int b){//vector用来存储高精度，int存储低精度
vector<int>res;//逆序存储结果
int t=0; //存储进位
for(int i=0;i<a.size();i++){
t=a[i]*b+t;
res.push_back(t%10);
t/=10;
}
while(t>0){//处理最高位的进位
res.push_back(t%10);
t/=10;
}
while(res.size()>1&&res.back()==0){
res.pop_back();
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string a;
int b;
cin>>a>>b;
vector<int>res=mul(stov(a),b);
for(int i=res.size()-1;i>=0;i--){
cout<<res[i];
}
return 0;
}高精度除低精度
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e8+10;
vector<int>stov(string a){
vector<int>res;//转换为int类型
for(int i=a.size()-1;i>=0;i--){//逆序存储
res.push_back(a[i]-'0');
}
return res;
}
ll r=0;//余数
vector<int> div(vector<int>a,int b){//vector用来存储高精度，int存储低精度
vector<int>res;
r=0;
for(int i=a.size();i>=0;i--){
int t=r*10+a[i];
res.push_back(t/b);
r=t%b;
}
reverse(res.begin(),res.end());//反转数组
while(res.size()>1&&res.back()==0){
res.pop_back();
}
return res;//反转后依然是反的
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string a;
int b;
cin>>a>>b;
vector<int>res=div(stov(a),b);
for(int i=res.size()-1;i>=0;i--){
cout<<res[i];
}
return 0;
}同余
ll c(ll a,ll b,ll m){
return ((a%m+m)+(b%m+m))%m;
}
//加法
ll j(ll a,ll b,ll m){
return ((a%m+m)-(b%m+m)+2*m)%m;
}
//减法
ll c(ll a,ll b,ll m){
return ((a%m+m)*(b%m+m))%m;
}
//乘法函数去重
pow()
cin.ignore()
快读板子
void read(int &x)
{
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}快读快输
void out(ll x){//快输
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else out(x/10),putchar(x%10+'0');
}
ll in(){//快读
int k=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}