oj-基础

oj-基础

高精度

高进度除法

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
45
46
// 比较两个高精度数的大小，a >= b返回true
bool compare(const vector<int>& a, const vector<int>& b) {
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = a.size() - 1; i >= 0; --i) {
        if (a[i] != b[i]) return a[i] > b[i];
    }
    return true;
}

// 高精度减法
vector<int> sub(vector<int>& a, vector<int>& b) {
    vector<int> c;
    for (int i = 0, t = 0; i < a.size(); ++i) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

// 高精度除法，返回商和余数
pair<vector<int>, vector<int>> div(vector<int>& a, vector<int>& b) {
    vector<int> res;  // 商
    vector<int> r;     // 余数
    
    for (int i = a.size() - 1; i >= 0; --i) {
        r.insert(r.begin(), a[i]);
        while (r.size() > 1 && r.back() == 0) r.pop_back();
        
        int cnt = 0;
        while (compare(r, b)) {
            r = sub(r, b);
            cnt++;
        }
        
        res.push_back(cnt);
    }
    
    reverse(res.begin(), res.end());
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    
    return {res, r};
}

递推与递归

递归

自顶向下，逐步分解
P1228 地毯填补问题

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647
int a[1100][1100];

void f(int sx,int sy,int lx,int ly,int gx,int gy)
{
	
	if(sx+1==lx&&sy+1==ly)
	{
		if(a[sx][sy]!=0)
			cout<<lx<<' '<<ly<<' '<<1<<endl;
		else if(a[sx][sy+1]!=0)
			cout<<lx<<' '<<sy<<' '<<2<<endl;
		else if(a[sx+1][sy]!=0)
			cout<<sx<<' '<<ly<<' '<<3<<endl;
		else if(a[sx+1][sy+1]!=0)
			cout<<sx<<' '<<sy<<' '<<4<<endl;
	}
	else
	{
		int sx1=sx,sy1=sy,lx1=(sx+lx)/2,ly1=(ly+sy)/2;
		int sx2=sx,sy2=ly1+1,lx2=lx1,ly2=ly;
		int sx3=lx1+1,sy3=sy,lx3=lx,ly3=ly1;
		int sx4=sx3,sy4=ly1+1,lx4=lx,ly4=ly;
		if(gx>=sx1&&gy>=sy1&&gx<=lx1&&gy<=ly1)
		{
			a[sx4][sy4]=a[sx4-1][sy4]=a[sx4][sy4-1]=1;
			cout<<sx4<<' '<<sy4<<' '<<1<<endl;
			f(sx1,sy1,lx1,ly1,gx,gy);
			f(sx2,sy2,lx2,ly2,sx4-1,sy4);
			f(sx3,sy3,lx3,ly3,sx4,sy4-1);
			f(sx4,sy4,lx4,ly4,sx4,sy4);
		}
		else if(gx>=sx2&&gy>=sy2&&gx<=lx2&&gy<=ly2)
		{
			a[lx1][ly1]=a[lx1+1][ly1]=a[lx1+1][ly1+1]=2;
			cout<<lx1+1<<' '<<ly1<<' '<<2<<endl;
			f(sx1,sy1,lx1,ly1,lx1,ly1);
			f(sx2,sy2,lx2,ly2,gx,gy);
			f(sx3,sy3,lx3,ly3,lx1+1,ly1);
			f(sx4,sy4,lx4,ly4,lx1+1,ly1+1);
		}
		else if(gx>=sx3&&gy>=sy3&&gx<=lx3&&gy<=ly3)
		{
			a[lx1][ly1]=a[lx1][ly1+1]=a[lx1+1][ly1+1]=3;
			cout<<lx1<<' '<<ly1+1<<' '<<3<<endl;
			f(sx1,sy1,lx1,ly1,lx1,ly1);
			f(sx2,sy2,lx2,ly2,lx1,ly1+1);
			f(sx3,sy3,lx3,ly3,gx,gy);
			f(sx4,sy4,lx4,ly4,lx1+1,ly1+1);
		}
		else if(gx>=sx4&&gy>=sy4&&gx<=lx4&&gy<=ly4)
		{
			a[lx1][ly1]=a[lx1+1][ly1]=a[lx1][ly1+1]=4;
			cout<<lx1<<' '<<ly1<<' '<<4<<endl;
			f(sx1,sy1,lx1,ly1,lx1,ly1);
			f(sx2,sy2,lx2,ly2,lx1,ly1+1);
			f(sx3,sy3,lx3,ly3,lx1+1,ly1);
			f(sx4,sy4,lx4,ly4,gx,gy);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,gx,gy;
	cin>>n>>gx>>gy;
	a[gx][gy]=-1;
	f(1,1,1<<n,1<<n,gx,gy);
	return 0;
}

递推

自底向上，逐步求精
P1498 南蛮图腾

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
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647

int h[11]={0,2,4,8,16,32,64,128,256,512,1024};
int w[11]={0,4,8,16,32,64,128,256,512,1024,2048};
string str[11][1100];


int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	str[1][1]=" /\\ ";
	str[1][2]="/__\\";
	for(int i=2;i<=10;i++)
	{
		string s="";
		for(int j=1;j<=w[i-1]/2;j++)
			s=s+" ";
		for(int j=1;j<=h[i-1];j++)
		{
			str[i][j]=s+str[i-1][j]+s;
		}
		for(int j=h[i-1]+1;j<=h[i];j++)
			str[i][j]=str[i-1][j-h[i-1]]+str[i-1][j-h[i-1]];
	}
	for(int i=1;i<=h[n];i++)
		cout<<str[n][i]<<endl;
	return 0;
}

贪心

局部最优->整体最优
P1080 国王游戏

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647
struct rl
{
	int right;
	int left;
}a[1010] ;

string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    
    int m = num1.size(), n = num2.size();
    vector<int> res(m + n, 0); // 结果最多为m+n位数
    
    // 从低位到高位逐位相乘
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int sum = mul + res[i + j + 1]; // 当前位加上之前的进位
            
            res[i + j + 1] = sum % 10;     // 当前位结果
            res[i + j] += sum / 10;        // 进位
        }
    }
    
    // 转换为字符串，去除前导零
    string result;
    for (int num : res) {
        if (!(result.empty() && num == 0)) { // 跳过前导零
            result.push_back(num + '0');
        }
    }
    
    return result.empty() ? "0" : result;
}

bool greaterOrEqual(const string& a, const string& b) {
    if (a.length() != b.length()) return a.length() > b.length();
    return a >= b;
}

// 高精度减法（a >= b）
string subtract(string a, string b) {
    string res;
    int borrow = 0;
    int i = a.length() - 1, j = b.length() - 1;
    
    while (i >= 0 || j >= 0) {
        int x = (i >= 0) ? (a[i--] - '0') : 0;
        int y = (j >= 0) ? (b[j--] - '0') : 0;
        int diff = x - y - borrow;
        
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        
        res.push_back(diff + '0');
    }
    
    // 去除前导零
    while (res.size() > 1 && res.back() == '0') {
        res.pop_back();
    }
    
    reverse(res.begin(), res.end());
    return res;
}

// 高精度除法（返回商和余数）
string divide(string dividend, string divisor) {
    if (divisor == "0") throw runtime_error("Division by zero");
    if (dividend == "0") return {"0", "0"};
    
    string quotient;
    string current;
    
    for (char digit : dividend) {
        current.push_back(digit);
        // 去除前导零
        while (current.size() > 1 && current[0] == '0') {
            current.erase(0, 1);
        }
        
        int q = 0;
        while (greaterOrEqual(current, divisor)) {
            current = subtract(current, divisor);
            q++;
        }
        
        quotient.push_back(q + '0');
    }
    
    // 去除商的前导零
    while (quotient.size() > 1 && quotient[0] == '0') {
        quotient.erase(0, 1);
    }
    
    return quotient;
}
string maxHighPrecision(string num1, string num2) {
    // 去除前导零
    num1.erase(0, num1.find_first_not_of('0'));
    num2.erase(0, num2.find_first_not_of('0'));
    
    // 如果去除前导零后为空，说明是0
    if (num1.empty()) num1 = "0";
    if (num2.empty()) num2 = "0";
    
    // 比较长度
    if (num1.length() > num2.length()) {
        return num1;
    } else if (num1.length() < num2.length()) {
        return num2;
    }
    
    // 长度相同，逐位比较
    for (int i = 0; i < num1.length(); i++) {
        if (num1[i] > num2[i]) {
            return num1;
        } else if (num1[i] < num2[i]) {
            return num2;
        }
    }
    
    // 完全相等，返回任意一个
    return num1;
}

bool cmp(rl a1,rl a2)
{
	
		double b=max(1/(double)a1.right,a1.left/(double)a2.right);
		double c=max(1/(double)a2.right,a2.left/(double)a1.right);
		return b<c;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	cin>>a[0].left>>a[0].right;
	for(int i=1;i<=n;i++)
		cin>>a[i].left>>a[i].right;
	sort(a+1,a+n+1,cmp);
	string ans="0",t=to_string(a[0].left);
	for(int i=1;i<=n;i++)
	{
		string m=divide(t,to_string(a[i].right));
		ans=maxHighPrecision(m,ans);
		t=multiply(t,to_string(a[i].left));
	}
	cout<<ans;
	return 0;
}

二分答案

顾名思义，它用二分的方法枚举答案，并且枚举时判断这个答案是否可行。但是，二分并不是在所有情况下都是可用的，使用二分需要满足两个条件。一个是有界，一个是单调。二分答案应该是在一个单调闭区间上进行的。也就是说，二分答案最后得到的答案应该是一个确定值，而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性，那么这个单调性应该体现在哪里呢？可以这样想，在一个区间上，有很多数，这些数可能是我们这些问题的解，换句话说，这里有很多不合法的解，也有很多合法的解。我们只考虑合法解，并称之为可行解。考虑所有可行解，我们肯定是要从这些可行解中找到一个最好的作为我们的答案， 这个答案我们称之为最优解。
最优解一定可行，但可行解不一定最优。我们假设整个序列具有单调性，且一个数x为可行解，那么一般的，所有的x’(x’<x)都是可行解。并且，如果有一个数y是非法解，那么一般的，所有的y’(y’>y)都是非法解。那么什么时候适用二分答案呢？如果题目规定了有“最大值最小”或者“最小值最大”的东西，那么这个东西应该就满足二分答案的有界性（显然）和单调性（能看出来）。
P2678 跳石头

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
45
46
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647

int a[50010];
int n,len,m;
bool judge(int x)
{
	int count=0;
	for(int i=0;i<n+1;)
	{
		int j=i;
		while (i<n+1&&a[++i]-a[j]<x);
		count=count+i-j-1;
		if(a[i]-a[j]<x)
			count++;
		if(count>m)
			return false;
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	cin>>len>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	a[n+1]=len;
	int l=1,r=len;
	int ans=1;
	for(l;l<=r;)
	{
		int mid=(l+r)/2;
		if(judge(mid))
		{
			ans=mid;
			l=mid+1;
		}
		else
			r=mid-1;
	}
	cout<<ans;
	return 0;
}

二叉树

P1364 医院设置

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
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647

struct tree{
	long long int w;
	int u;
	int v;
	int p=0;
}t[105];

int b[105];
long long int f(int a,int c)
{
	if(a==0||b[a])
		return 0;
	b[a]=1;
	return c*t[a].w+f(t[a].v,c+1)+f(t[a].u,c+1)+f(t[a].p,c+1);
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i].w>>t[i].u>>t[i].v;
		t[t[i].u].p=i;
		t[t[i].v].p=i;
	}
	long long int sum;
	sum=f(1,0);
	memset(b,0,sizeof(b));
	for(int i=2;i<=n;i++)
	{
		sum=min(sum,f(i,0));
		memset(b,0,sizeof(b));
	}
	cout<<sum;

	
	return 0;
}

并查集

拓展域并查集是一种数据结构，用于解决具有多个相互关系集合的问题。它是传统并查集的扩展，能够处理集合间的不同关系，如相互排斥或相互独立的关系。
P1525 关押罪犯

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647

struct a
{
	int x;
	int y;
	int z;
}a1[100010];
int s[40010];

bool cmp(a x1,a x2)
{
	return x1.z>x2.z;
}
int pnt(int i)
{
	if(s[i]==i)
		return i;
	return s[i]=pnt(s[i]);
}
void uon(int u,int v)
{
	int pu=pnt(u),pv=pnt(v);
	if(pu==pv)
		return;
	s[pu]=min(pu,pv);
	s[pv]=min(pu,pv);
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=2*n;i++)
		s[i]=i;
	for(int i=0;i<m;i++)
		cin>>a1[i].x>>a1[i].y>>a1[i].z;
	sort(a1,a1+m,cmp);
	int flag=1;
	for(int i=0;i<m;i++)
	{
		uon(a1[i].x,a1[i].y+n);
		uon(a1[i].y,a1[i].x+n);
		if((pnt(a1[i].x)==pnt(a1[i].x+n))||(pnt(a1[i].y)==pnt(a1[i].y+n)))
		{
			cout<<a1[i].z;
			flag=0;
			break;
		}
	}
	if(flag)
		cout<<0;
	return 0;
}

图

图的问题主要有遍历，拓扑排序，最短路问题
P1983 车站分级

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647

int v[5010];
int edge[10000010];
int nxt[10000010];
int isadd[1001][1001];
int w[5010];
int isread[5010];
int num[5010];
int cnt=0;
int n,m;
set<int> s;
int flag=0;
void in_edge(int a,int b)
{
	 if(isadd[a][b])
         return;
     isadd[a][b]=1;
    num[b]++;
    cnt++;
	edge[cnt]=b;
	nxt[cnt]=v[a];
	v[a]=cnt;
}
void dfs(int u)
{
	int a=v[u];
	isread[u]=1;
	for(a;a!=0;a=nxt[a])
	{
		if(isread[edge[a]]==0)
			dfs(edge[a]);
	}
}
void bfs(int u)
{
	queue<int> q;
	q.push(u);
	isread[u]=1;
	while (!q.empty())
	{
		int a=q.front();
		q.pop();
		maxv[a]=max(maxv[a],u);
		int nt_eg=v[a];
		while (nt_eg!=0)
		{
			if(isread[edge[nt_eg]]==0)
			{
				isread[edge[nt_eg]]=1;
				q.push(edge[nt_eg]);
			}
			nt_eg=nxt[nt_eg];
		}
		
	}
	
}
void spfa(int u)
{
	for(int i=1;i<=n;i++)
		num[i]=1e9;
	num[u]=0;
	queue<int> q;
	q.push(u);
	isread[u]=1;
	while (!q.empty())
	{
		int a=q.front();
		q.pop();
		isread[a]=0;
		for(int j=v[a];j!=0;j=nxt[j])
		{
			if(num[a]+w[j]<num[edge[j]])
			{
				num[edge[j]]=num[a]+w[j];
				if(isread[edge[j]]==0)
				{
					q.push(edge[j]);
					isread[edge[j]]=1;
				}
			}
		}
	}
	
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
    set<pair<int,int> > spair;
	for(int i=1;i<=m;i++)
	{
		int j;
		cin>>j;
		set<int> s1;
		for(int p=1;p<=j;p++)
		{
			int a;
			cin>>a;
			s1.insert(a);
			isread[a]=1;
		}
		int smin=*(s1.begin());
        int smax=*(--(s1.end()));
		for(auto it=s1.begin();it!=s1.end();it++)
		{
			
			for(int k=smin;k<=smax;k++)
				if(isread[k]==0)
					{
                        
                        in_edge((*it),k);
                        
                    }
		}
		memset(isread,0,sizeof(isread));
	}
	int res=0;
	set<int> s2;
	for(int i=1;i<=n;i++)
		if(num[i]==0)
			{s2.insert(i);isread[i]=1;}
	while (!s2.empty())
	{
		set<int> s3;
		for(auto it=s2.begin();it!=s2.end();it++)
		{
			
			int u=(*it);
			for(int i=v[u];i!=0;i=nxt[i])
				num[edge[i]]--;
		}
		for(int i=1;i<=n;i++)
		{
			if(isread[i]==0&&num[i]==0)
			{
				s3.insert(i);isread[i]=1;
			}
		}
		s2=s3;
		res++;
	}
	cout<<res;
	return 0;
}

质数问题

欧拉法筛选素数
P3601 签到题

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
#define INT_MAX 2147483647

vector<int> primes = {2};
void sieveLarge(int n) {
    const int size = (n + 1) / 2;
    vector<bool> isPrime(size, true);

    primes.reserve(n / log(n)); // 预分配空间
    
    for (int i = 1; i < size; ++i) {
        if (isPrime[i]) {
            int p = 2 * i + 1;
            primes.push_back(p);
            if ((long long)p * p > n) continue;
            for (long long j = (long long)p * p; j <= n; j += 2 * p) {
                if (j % 2 == 1) {
                    isPrime[(j - 1) / 2] = false;
                }
            }
        }
    }
}

long long int A[1000010];
long long int B[1000010];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	long long int l,r;
	cin>>l>>r;
	for(long long int i=l;i<=r;i++)
		A[i-l]=B[i-l]=i;
    sieveLarge(1e6);
	int pri_len=primes.size();
	for(int i=0;i<pri_len;i++)
	{
		long long int start=l/primes[i];
		if(l%primes[i]!=0)
			start++;
		for(start=start*primes[i];start<=r;start+=primes[i])
		{
			A[start-l]=A[start-l]/primes[i]*(primes[i]-1);
			while (B[start-l]%primes[i]==0)
			{
				B[start-l]=B[start-l]/primes[i];
			}
		}
	}
	long long int ans=0;
	for(long long int i=l;i<=r;i++)
	{
		if(B[i-l]!=1)	A[i-l]=A[i-l]/B[i-l]*(B[i-l]-1);
		ans=(ans+i-A[i-l])%666623333;
	}
	cout<<ans;
	return 0;
}

author: YaoGuangMing 2025

转载请标明出处！