判断几位数

int jiweishu(int p1){
	int w;
    for(int i=0;i<=8;i++){//4
    	w=p1/(pow(10,i));
    	if(w==0){
    		return i;
    		break;
		}
	}
}

回文数

int jiweishu(int p1){
	int w;
    
    for(int i=0;i<=8;i++){//4
    	w=p1/(pow(10,i));
    	if(w==0){
    		return i;
    		break;
		}
	}
	
}
bool huiwenshu(int n){
    int o=n;
    int q=0;
    int w=jiweishu(n);
    for(int i=1;i<=w;i++){//3
    	q=q*10+n%10;
        n=n/10;
	}
    if(o==q){
        return true;
    }else{
       	return false;
    }
}

判断素数

bool fbq(int k){
	if(k<2){
		return 0;
	}
	if(k==2){
		return 1;
	}
	for(int i=2;i*i<=k;i++){
		if(k%i==0){
			return 0;
		}
	}
	return 1;
}

10进制转k进制

string FBQ_p(unsigned long long decimalNum, int k){
    if (decimalNum == 0) {
        return "0";
    }
    string result; 
    bool isNegative = false;
    if (decimalNum < 0) {
        isNegative = true;
        decimalNum = -decimalNum; 
    }
    const char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 
    while (decimalNum > 0) {
        int remainder = decimalNum % k; 
        result += digits[remainder];  
        decimalNum = decimalNum / k;  
    }
    if (isNegative) {
        result += '-';
    }
    reverse(result.begin(), result.end());
    return result;
}

k进制转十进制

unsigned long long FBQ_q(const std::string& kNum, int k) {
	unsigned long long decimal = 0;
	unsigned long long startIndex = 0;
	bool isNegative = false;
	if (kNum[0] == '-') {
		isNegative = true;
		startIndex = 1;
	}
	for (unsigned long long i = startIndex; i < kNum.size(); ++i) {
		char c = kNum[i];
		unsigned long long digit;
		if (isdigit(c)) {
			digit = c - '0';
		}
		else if (isalpha(c)) {
			c = toupper(c);
			digit = 10 + (c - 'A');
		}
		decimal = decimal * k + digit;
	}
	if (isNegative) {
		decimal = -decimal;
	}
	return decimal;
}

高精度辅助代码

string removeLeadingZeros(string num) {
    int start = 0;
   
    while (start < num.length() && num[start] == '0') {
        start++;
    }
   
    if (start == num.length()) {
        return "0";
    }
    return num.substr(start);
}
int compare(string a, string b) {
    a = removeLeadingZeros(a);
    b = removeLeadingZeros(b);
    
    if (a.length() > b.length()) return 1;
    if (a.length() < b.length()) return -1;
    
    for (int i = 0; i < a.length(); i++) {
        if (a[i] > b[i]) return 1;
        if (a[i] < b[i]) return -1;
    }
    return 0;
}

高精度加

string add(string a, string b) {
    string res;
    int carry = 0; 
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    int max_len = max(a.length(), b.length());
    for (int i = 0; i < max_len || carry; i++) {
        int digit_a = (i < a.length()) ? (a[i] - '0') : 0;
        int digit_b = (i < b.length()) ? (b[i] - '0') : 0;
        int sum = digit_a + digit_b + carry;
        carry = sum / 10;
        res.push_back((sum % 10) + '0');
    }
    
    reverse(res.begin(), res.end());
    return removeLeadingZeros(res);
}

高精度减

string subtract(string a, string b) {
    if (compare(a, b) == 0) {
        return "0";
    }
    string res;
    int borrow = 0; 
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int max_len = max(a.length(), b.length());
    for (int i = 0; i < max_len; i++) {
        int digit_a = (i < a.length()) ? (a[i] - '0') : 0;
        int digit_b = (i < b.length()) ? (b[i] - '0') : 0;
        digit_a -= borrow;
        borrow = 0;
        if (digit_a < digit_b) {
            digit_a += 10;
            borrow = 1;
        }
        res.push_back((digit_a - digit_b) + '0');
    }
    reverse(res.begin(), res.end());
    return removeLeadingZeros(res);
}

高精度乘

string multiply(string a, string b) {
    a = removeLeadingZeros(a);
    b = removeLeadingZeros(b);
  
    if (a == "0" || b == "0") {
        return "0";
    }
    
    int len_a = a.length(), len_b = b.length();
   
    string res(len_a + len_b, '0');
    
  
    for (int i = len_a - 1; i >= 0; i--) {
        int carry = 0;
        int digit_a = a[i] - '0';
        for (int j = len_b - 1; j >= 0; j--) {
            int digit_b = b[j] - '0';
            int sum = (res[i + j + 1] - '0') + digit_a * digit_b + carry;
            carry = sum / 10;
            res[i + j + 1] = (sum % 10) + '0';
        }
      
        if (carry > 0) {
            res[i] = (res[i] - '0' + carry) + '0';
        }
    }
    
    return removeLeadingZeros(res);
}

高精度除（要用高精度减）

string divide(string a, string b) {
    string remainder;
    a = removeLeadingZeros(a);
    b = removeLeadingZeros(b);
  
    if (b == "0") {
        remainder = "";
        return "";
    }
   
    if (compare(a, b) == -1) {
        remainder = a;
        return "0";
    }
    
    string quotient; 
    remainder = "0"; 
    
   
    for (int i = 0; i < a.length(); i++) {
        remainder = remainder + a[i];
        remainder = removeLeadingZeros(remainder);
        int cnt = 0;
    
        while (compare(remainder, b) >= 0) {
            remainder = subtract(remainder, b);
            cnt++;
        }
        quotient.push_back(cnt + '0');
    }
    
    quotient = removeLeadingZeros(quotient);
    remainder = removeLeadingZeros(remainder);
    return quotient;
}

冒泡排序

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        bool flag = false; // 优化：无交换则提前退出
        for (int j = 0; j < n-i-1; j++) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
                flag = true;
            }
        }
        if (!flag) break;
    }
}

选择排序

void selectionSort(int a[], int n) {
   for (int i = 0; i < n; i++) {
       int minPos = i;
       for (int j = i+1; j < n; j++) {
           if (a[j] < a[minPos]) minPos = j;
       }
       swap(a[i], a[minPos]);
   }
}

排序

void insertionSort(int a[], int n) {
   for (int i = 1; i < n; i++) {
       int key = a[i];
       int j = i - 1;
       while (j >= 0 && a[j] > key) {
           a[j+1] = a[j];
           j--;
       }
       a[j+1] = key;
   }
}

希尔排序

void shellSort(int a[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = a[i];
            int j;
            for (j = i; j >= gap && a[j - gap] > key; j -= gap) {
                a[j] = a[j - gap];
            }
            a[j] = key;
        }
    }
}

归并排序

void merge(int a[], int l, int mid, int r) {
    int temp[MAXN];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (i = 0; i < k; i++) a[l + i] = temp[i];
}
void mergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);
    merge(a, l, mid, r);
}

快速排序

void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l, j = r, pivot = a[l];
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        a[i] = a[j];
        while (i < j && a[i] <= pivot) i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    quickSort(a, l, i-1);
    quickSort(a, i+1, r);
}

堆排序

void heapify(int a[], int n, int i) {
    int largest = i;
    int left = 2*i+1;
    int right = 2*i+2;
    if (left < n && a[left] > a[largest]) largest = left;
    if (right < n && a[right] > a[largest]) largest = right;
    if (largest != i) {
        swap(a[i], a[largest]);
        heapify(a, n, largest);
    }
}
void heapSort(int a[], int n) {
    for (int i = n/2-1; i >= 0; i--) heapify(a, n, i);
    for (int i = n-1; i > 0; i--) {
        swap(a[0], a[i]);
        heapify(a, i, 0);
    }
}

计数排序

void countingSort(int a[], int n, int maxVal) {
    int* cnt = new int[maxVal + 1](); // 动态分配
    for (int i = 0; i < n; i++) cnt[a[i]]++;
    int k = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (cnt[i] > 0) {
            a[k++] = i;
            cnt[i]--;
        }
    }
    delete[] cnt;
}

桶排

void bucketSort(int a[], int n, int maxVal) {
    int bucketSize = 10; // 桶的数量，可调整
    vector<int>* buckets = new vector<int>[bucketSize];
    // 分配元素到桶
    for (int i = 0; i < n; i++) {
        int idx = (a[i] * bucketSize) / (maxVal + 1);
        buckets[idx].push_back(a[i]);
    }
    // 桶内排序（用插入排序）
    for (int i = 0; i < bucketSize; i++) {
        insertionSort(buckets[i].data(), buckets[i].size());
    }
    // 合并桶
    int k = 0;
    for (int i = 0; i < bucketSize; i++) {
        for (int num : buckets[i]) a[k++] = num;
    }
    delete[] buckets;
}

基数排序

void radixSort(int a[], int n) {
    int maxVal = *max_element(a, a + n);
    // 按每一位排序
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        vector<int> output(n);
        int cnt[10] = {0};
        // 统计每个数字的出现次数
        for (int i = 0; i < n; i++) cnt[(a[i]/exp)%10]++;
        // 计算位置
        for (int i = 1; i < 10; i++) cnt[i] += cnt[i-1];
        // 反向填充，保证稳定性
        for (int i = n-1; i >= 0; i--) {
            int digit = (a[i]/exp) % 10;
            output[cnt[digit] - 1] = a[i];
            cnt[digit]--;
        }
        // 复制回原数组
        for (int i = 0; i < n; i++) a[i] = output[i];
    }
}

01背包

#include <bits/stdc++.h> //万能头文件，包含所有常用库
using namespace std;

int n,p;        // n：物品数量；p：背包总容量
int w[105];     // w[i]：第i件物品的重量
int v[105];     // v[i]：第i件物品的价值
int ans;        // 本题没用到，可删掉
int f[20005];   // 01背包dp数组，f[j]代表：背包容量为j时的最大价值

int main() {
    // 输入：先读背包容量p，再读物品数量n
    cin>>p>>n;
    
    // 循环读入n件物品的重量和价值
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }

    // 外层循环：遍历每一件物品，i代表当前正在处理第i件物品
    for(int i=1;i<=n;i++){
        // 内层循环：倒序遍历背包容量 j，从背包最大容量p往小遍历到w[i]
        // 为什么倒序？！重点！防止同一件物品被重复选取（01背包核心）
        // 如果正序j从小到大，f[j-w[i]]会被当前物品更新，会重复拿多次，变成完全背包
        for(int j=p;j>=w[i];j--){
            // 状态转移方程：
            // f[j] = max( 不选第i件物品，选第i件物品 )
            // 不选第i件：价值就是原来的f[j]
            // 选第i件：必须先腾出w[i]重量，即f[j-w[i]]，再加上这件物品价值v[i]
            f[j] = max(f[j], f[j-w[i]] + v[i]);
        }
    }

    // f[p]：背包容量恰好为p时，可以装的最大价值
    cout<<f[p];
    return 0;
}

多重背包

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

int V,s,v,w,n;
// V:背包总容积
// n:物品种类数
// v:单件物品体积
// w:单件物品价值
// s:当前这种物品最多能选s件
int f[10005]; // dp数组 f[j] = 背包容量j能装的最大价值

int main()
{
    cin>>n>>V;  // 输入：物品种类n，背包总容积V

    // 遍历每一类物品（第i类物品）
    for(int i=1;i<=n;i++){
        cin>>v>>w>>s; // 读入：单件体积v，单件价值w，最多选s件

        // 倒序遍历背包容量，和01背包一样！
        // 倒序目的：防止同一类物品被重复无限选取
        for(int j=V;j>=0;j--){
            // k代表当前物品选k件，k从1到s（最多选s个）
            for(int k=1;k<=s;k++){
                // 判断：背包容量j能不能放下k件物品，k件总体积 = k*v
                if(j>=k*v){
                    // 状态转移：
                    // 不选k件：保留原来f[j]
                    // 选k件：腾出k*v体积，f[j-k*v] + k*w（k件总价值）
                    f[j]=max(f[j],f[j-k*v]+k*w);
                }
            }
        }
    }
    cout<<f[V]; // 背包容量V的最大价值，输出答案
    return 0;
}

完全背包

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

int N,V;
int dp[205];   // dp[j] 表示容量为j的背包能装的最大价值
int w[205];    // w[i] 第i个物品重量
int v[35];     // v[i] 第i个物品价值

int main() {
    cin>>N>>V;   // N背包容量，V物品个数
    
    // 读入V个物品的重量w和价值v
    for(int i=1;i<=V;i++)
        cin>>w[i]>>v[i];

    // 外层循环：遍历每一件物品
    for(int i=1;i<=V;i++){
        // 内层循环：容量【正序从小到大】！！完全背包标志
        // 正序：更新dp[j]时，dp[j-w[i]]已经被当前物品更新过，就可以重复选取
        for(int j=w[i];j<=N;j++){
            // 状态转移方程
            // 不选当前物品：dp[j]保持原值
            // 选当前物品：dp[j - w[i]] + v[i]
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout<<"max="<<dp[N]; // 输出容量N背包的最大价值
    return 0;
}