专栏文章

笔记

FFractsidus
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2g8o4
此快照首次捕获于
2025/12/01 19:28
3 个月前
此快照最后确认于
2025/12/01 19:28
3 个月前
查看原文

求质数模板

CPP
#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(){
	
}

头文件

CPP
#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;
}

字符串

大小写转换

CPP
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;
}

反转字符串

CPP
string f2(string a){
	string f="";
	for(int i=a.size()-1;i>=0;i--){
		f+=a[i];
	}
	return f;
}

map

CPP
#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 排序

CPP
bool cmp(no x,no y){
	if(x.fe != y.fe) return x.fe > y.fe;
	return x.mi < y.mi;
}

进制

10 进制转 x 进制

CPP
#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 进制

CPP
#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;
}

队列

初始状态：
CPP
haed=tail=0
队尾插入：
CPP
q[tail]=x;
弹出队首：
CPP
head++；
使用队首：
CPP
cout<<q[head];
使用队尾：
CPP
cout<<q[tail-1];
查找元素：
CPP
tail-head;

pair

在 C++ 中，pair 是一个模板类，用于将两个不同类型的数据组合成一个单元。以下是其主要用法和特点：
  1. ‌基本定义与头文件‌ pair 定义在头文件中，使用时需包含该头文件。 类模板声明形式为：template<class T1, class T2> struct pair;，其中 T1 和 T2 分别为两个成员的数据类型。
  2. ‌成员变量‌ first：存储第一个数据，类型为 T1。 second：存储第二个数据，类型为 T2。
  3. ‌初始化方式‌ 默认构造‌：pair <T1, T2> p;（成员值未初始化）。 直接初始化‌：pair <T1, T2> p (val1, val2);。 拷贝构造‌：pair <T1, T2> p2 (p1);。 使用 make_pair‌：auto p = make_pair (val1, val2);（自动推导类型）。
  4. ‌常用操作‌ 访问成员‌：通过 p.first 和 p.second 直接访问。 赋值操作‌：支持 = 赋值，如 p1 = p2; 或 p1 = make_pair (val1, val2);。 比较操作‌：按字典序比较（先比较 first，再比较 second）。
  5. ‌典型应用场景‌ STL 容器‌：如 map、unordered_map 的键值对存储。 函数多返回值‌：通过 pair 返回两个值。 排序与优先队列‌：可作为 priority_queue 的元素，自定义排序规则。 示例代码
CPP
#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;
}
  1. ‌扩展说明‌ 与 tuple 的区别‌：pair 仅支持两个元素，而 tuple 支持多个元素。 性能‌：因底层为结构体，直接访问成员变量效率较高。
通过灵活使用 pair，可以简化需要组合数据的场景，提升代码可读性和维护性。

二分

普通二分

CPP
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;
	}

二分查找右侧边界

CPP

   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"<<' ';

二分查找左边界

CPP
    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"<<' ';

函数二分

前缀和

CPP
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;

位运算

CPP
cout<<(a&b)<<endl;
    cout<<(a|b)<<endl;
    cout<<(a^b)<<endl;
    cout<<(~a)<<endl;
    cout<<(a<<k)<<endl;
    cout<<(a>>k);

DFS

迷宫搜索（判断是否能到）

CPP
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 种）

CPP
#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);
}

全排列

CPP
#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);
}

高精度

加法

CPP
#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;
}

减法

CPP
#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;
}

高精度乘低精度

CPP
#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;
}

高精度除低精度

CPP
#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;
}

同余

CPP
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()

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...