CSP常用算法

判断闰年

bool leap_year(int year){
	//非整百年的，能被4整除
	if(year % 100 != 0){
    	if(year % 4 == 0){
    		return true;
    	}
	}else{//非整百年的，能被400整除
		if(year % 400 == 0){
    		return true;
    	}
	}
	return false;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13

最大公约数

int gcd(int a, int b){
	int c = 1;
	while(c > 0){
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}
1
2
3
4
5
6
7
8
9

判断素数

bool isprime(int a){
	int sqrt_a = sqrt(a);
	for(int i = 2; i <= sqrt_a; i++){
		if(a % i == 0){
			return false;
		}
	}
	return true;
}
1
2
3
4
5
6
7
8
9

筛法求素数

const int n = 100;
int x[n];
int prime[n];
int prime_list() {
	int count = 1;
	x[0] = x[1] = 1;
	for(int i = 2; i <= n; i++) {
		if(x[i] == 0) {
			prime[count] = i;
			++count;
		}
		for(int j = 1; j < count && prime[j] * i < n; ++j)
			x[prime[j] * i] = 1;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

十进制转X进制

#include 
#include 
using namespace std;
string dict = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//十进制转 x 进制函数。
string ten_to_x(int n, int x){
	string ans = "";
	//模拟短除法。 
	while (n != 0) {
		ans += dict[n % x];
		n /= x;
	}
	string t = "";  //倒取余数。
	for (int i = ans.length()-1; i >= 0; i--) t += ans[i];
	return t; 
}
int main(){
	int n, x;
	cin >> n >> x;
	cout << ten_to_x(n, x);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

X进制转10进制

#include 
using namespace std;

// char转数码
int charToInt(char c) {
    if('0' <=c && c<='9') return c-'0';
    return c-'A' + 10;
}

int x_to_ten(int x, string s){
	int a[105];
    int len = s.size();
    for(int i = len - 1; i >= 0; i--)
        a[len - 1 - i] = charToInt(S[i]);
    int ans = 0, w = 1;
    for(int i = 0; i < len + 1; i++){
        ans = ans + w * a[i];
        w = w * x;
    }
    return ans;
}

int main(void) {
	int x; // 输入x进制
	string s;
    cin >> x >> s;
    cout << x_to_ten(x, s);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

表达式计算

#include
#include
#include
#include
using namespace std;
string str;
 
long long calculate(string str)
{
	int len=str.length(),pos=0;
	stack<long long> sta;
	char ch;
	
	while(pos < len){
		if(str[pos] >='0' && str[pos] <= '9'){
			long long temp=0;
			while(str[pos]!=' '&&str[pos]!='.') temp=temp*10+(str[pos++]-'0');
			sta.push(temp);
		}else if(str[pos]==' '||str[pos]=='.') {
			pos++;
		}else if(str[pos]=='@'){
		 	break;
		}else{
			ch=str[pos++];
			int num1,num2;
			num2=sta.top(); sta.pop();
			num1=sta.top(); sta.pop();
			
			switch(ch){
				case '+': sta.push(num1+num2); break;
				case '-': sta.push(num1-num2); break;
				case '*': sta.push(num1*num2); break;
				case '/': sta.push(num1/num2); break;
			}
		}
	}
	return sta.top();
}
 
int main(){
	getline(cin,str);
	cout << calculate(str);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44