模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
void solve(){
    
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

对浮点的处理

const double pi=acos(-1,0)//或者2*acos(0);

[!CAUTION]

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
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 0x3f3f3f3f;
const double EPS = 1e-8; 
const int MAX_DEPTH = 20;


double jie(double x) {

 if (x <= 0 || fabs(x - round(x)) > EPS) {
     return -1; 
 }
 int n = (int)round(x);
 if (x > 20) return -1;

 int res = 1;
 for (int i = n; i >= 1; i--) {
     res *= i;
 }
 return res;
}

stack<string> st; 
bool found = false; 

bool equals(double a, double b) {
 return fabs(a - b) < EPS;
}

void dfs(double x, int depth) {

 if (found || depth > MAX_DEPTH) {
     return;
 }


 if (equals(x, 3.0)) {
     found = true;
     cout << "YES\n";
     cout << "操作路径: ";
     vector<string> path;
     while (!st.empty()) {
         path.push_back(st.top());
         st.pop();
     }
     reverse(path.begin(), path.end());
     for (const auto& op : path) {
         cout << op << " -> ";
     }
     cout << "3\n";
     return;
 }

 double next = sqrt(x);
 if (next > 0) {
     st.push("sqrt(" + to_string((int)round(x)) + ")");
     dfs(next, depth + 1);
     if (!found) st.pop();
     else return;
 }

 next = ceil(x);
 if (next != x) { 
     st.push("ceil(" + to_string(x) + ")");
     dfs(next, depth + 1);
     if (!found) st.pop();
     else return;
 }

 // 尝试阶乘操作
 next = jie(x);
 if (next != -1) {
     st.push("jie(" + to_string((int)round(x)) + ")");
     dfs(next, depth + 1);
     if (!found) st.pop();
     else return;
 }
}

void solve() {
 dfs(4.0, 0);
}

signed main() {
 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 int t = 1;
 // cin >> t;
 while (t--) {
     solve();
 }
 return 0;
}







#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5,MAX_Depth=20;
const double eps=1e-8;

bool equal(double a,double b){
 return fabs(a-b)<eps;
}
stack<string>st;
double jie(double x){
 if(x<=0||fabs(x-round(x)>eps))return -1;
 int n=(int)round(x);
 if(x>20)return -1;
 int res=1;
 for(int i=n;i>=1;i--){
     res*=i;
 }
 return res;
}

void dfs(double x,int dep){
 if(dep>MAX_Depth)return;
 if(equal(x,3.0)){
     queue<string>q;
     while(!st.empty()){
         q.push(st.top());
         st.pop();
     }
     cout<<"3 :";
     while(!q.empty()){
         cout<<q.front()<<"-->";
         q.pop();
     }
		exit(0);
 }
 double next=sqrt(x);
 if(next>0){
     st.push("sqrt");
     dfs(next,dep+1);
     st.pop();
 }

 next=ceil(x);
 if(next!=x){
     st.push("ceil");
     dfs(next,dep+1);
     st.pop();
 }

 next=jie(x);
 if(next!=-1){
     st.push("jie");
     dfs(next,dep+1);
     st.pop();
 }

}
void solve(){
 dfs(4.0,0);
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
 // cin>>t;
 while(t--){
     solve();
 }
	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
a ^ b % p = ((a % p)^b) % p 
(A + B) % mod = ((A % mod) + (B % mod)) % mod
(A * B) % mod = ((A % mod) * (B % mod)) % mod
//减法取模    
(A - B) % mod =((A % mod) - (B % mod) +mod) % mod
//除法取模
(A / B) % mod = ((A % mod) * (inv(B) % mod)) % mod
    
LL qkpow(LL a,LL p,LL mod)
{
	LL t=1,tt=a%mod;
	while(p)
	{
		if(p&1)t=t*tt%mod;
		tt=tt*tt%mod;
		p>>=1;
	}
	return t;
}
LL getInv(LL a,LL mod)
{
	return qkpow(a,mod-2,mod);
}

878. 第 N 个神奇数字 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//二分答案->检验答案好统计
//简单的容斥原理
class Solution {
public:
long long mod=1e9+7;
    int nthMagicalNumber(int n, int a, int b) {
        long long mid;
        long long l=0,r=(long long)n*min(a,b);
        long long gcd=__gcd(a,b);
        long long lcm=a/gcd*b;
        while(l<=r){
            mid=(l+r)>>1;
            if((mid/a+mid/b-mid/lcm)>=n){//容斥原理
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return (int)(l%mod);
    }
};

异或运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1.袋子里一共a个白球,b个黑球,每次从袋子里拿2个求,每个球每次被拿出的机会均等,如果拿出的是2个白球或者2个黑球,那么就往袋子里重新放入1个白球,如果拿出的是1个白球和1个黑球,那么就往袋子里重新放入一个黑球,那么最终袋子里只会剩下一个球,请问最终的球是黑的概率是多少?
    黑球:1
    白球:0
    最终球的颜色取决于:黑球数量为奇数概率100%
        黑球数量为偶数概率0%
        
        
2.异或运算:数值交换
    在数组中保证a,b为两个下标不同的数
  a=a^b;
  b=a^b;
  a=a^b;
3.一个数异或上它的相反数:可以得到它仅保留最右侧1的数字状态
    
4.找在一个数组中出现奇数次数的a和奇数次数的b
 先所有异或:得到a^b这个结果
 (a^b)^(~(a^b))
 这个结果必然存在某个x数位上为1,故我们再次将数组分为x数位上为1和不为1的,遍历数位x上为1的数最后的结果即为a,b=a^b^a;

位运算

201. 数字范围按位与 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
//主要思想是关注保留下来的1
class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while(left<right){
            right-=(right&-right);
        }
        return right;
    }
};

190. 颠倒二进制位 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//采用分治思想
//abcdefgh
//两个为一组,交换组内元素的位置badcfehg
//四个为一组,大组内在两个为一小组,交换两个小组dcbahgfe
//同理hgfedcba
//第一个操作中:&上10101010右移
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {  // 使用uint32_t确保无符号性
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        n = (n >> 16) | (n << 16);
        return n;
    }
};

461. 汉明距离 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//统计一个数的二进制有多少个1
//一位中统计1的个数,二位中统计1的个数,四位中统计1的个数,八位中统计1的个数,16位中统计1的个数,最后返回32位中1的个数
class Solution {
public:
    int hammingDistance(int x, int y) {
        return solve(x^y);
    }
    int solve(int x){
        x=(x&0x55555555)+((x>>1)&0x55555555);
        x=(x&0x33333333)+((x>>2)&0x33333333);
        x=(x&0x0f0f0f0f)+((x>>4)&0x0f0f0f0f);
        x=(x&0x00ff00ff)+((x>>8)&0x00ff00ff);
        x=(x&0x0000ffff)+((x>>16)&0x0000ffff);
        return x;
    }
};

1.贪心

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
////骑士的工作
//// //每位骑士只能杀一个头
//// //贪心策略:尽量雇花费少的
//// #include <bits/stdc++.h>
//// using namespace std;
//// #define asd(i,a,b) for(int i=a;i<=b;i++)
//// #define int long long
//// const int inf=0x3f3f3f3f,N = 2e4 + 5;
//// int Size[N];
//// int v[N];
//// void solve(){
////     int n,m;
////     cin>>n>>m;
////     for(int i=1; i<=n; i++){
////         cin>>Size[i];
////     }
////     for(int i=1; i<=m; i++){
////         cin>>v[i];
////     }
////     sort(v+1,v+m+1);
////     sort(Size+1,Size+n+1);
////     int l=1,ans=0,i;
////     for(i=1;i<=n;i++){
////         while(l<=m&&Size[i]>v[l]){
////             l++;
////         }
////         if(l>m) break;
////         ans+=v[l];
////         l++;
////     }
////     if(i!=n+1){
////         cout<<"you died!"<<endl;
////     }
////     else cout<<ans<<endl;
//// }
//// signed main()
//// {
//// 	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//// 	int t=1;
////     // cin>>t;
////     while(t--){
////         solve();
////     }
//// 	return 0;
//// }
//
//
//
//#include <bits/stdc++.h>
//using namespace std;
//#define asd(i,a,b) for(int i=a;i<=b;i++)
//#define int long long
//const int inf=0x3f3f3f3f,N = 1e6 + 5;
//int a[N];
//void solve(){
//    int n;
//    cin>>n;
//    for(int i=1;i<=n;i++){
//        cin>>a[i];
//    }
//    int ans=0,l=1;
//    while(l<=n){
//        if(ans%2==0){
//            while(a[l]==0&&l<=n)l++;
//        }else{
//            while(a[l]==1&&l<=n)l++;
//        }
//        ans++;
//    }
//    cout<<ans<<"\n";
//}
//signed main()
//{
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t=1;
//    // cin>>t;
//    while(t--){
//        solve();
//    }
//	return 0;
//}



//一个人可能与多个人说话(1),但不一定会和周围的人说话(2)
//若用两两标记则与(1)相悖,标记被打乱,若只要标记就认为他们一定会说话则与(2) 相悖 
//#include <bits/stdc++.h>
//using namespace std;
//#define asd(i,a,b) for(int i=a;i<=b;i++)
//#define int long long
//const int inf=0x3f3f3f3f,N = 1e3+ 5;
//int mark[N][N];
//struct B{
//    int num;
//    int cnt=0;
//}r[2005],c[2005];
//bool cmp(B a,B b){
//    return a.cnt>b.cnt;
//}
//bool cmp1(B a,B b){
//    return a.num<b.num;
//}
//void solve(){
//    int m,n,k,l,d;
//    cin>>m>>n>>k>>l>>d;
//    for(int i=1;i<=d;i++){
//        int x,y,x1,y1;
//        cin>>x>>y>>x1>>y1;
//        if(x==x1){
//            c[min(y,y1)].num=min(y,y1);
//            c[min(y,y1)].cnt++;
//        }
//        if(y==y1){
//            r[min(x,x1)].num=min(x,x1);
//            r[min(x,x1)].cnt++;
//        }
//    }
//    sort(r+1,r+m+1,cmp);
//    sort(c+1,c+n+1,cmp);
//    sort(r+1,r+k+1,cmp1);
//    sort(c+1,c+l+1,cmp1);
//    for(int i=1;i<=k-1;i++){
//        cout<<r[i].num<<" ";
//    }
//    cout<<r[k].num<<'\n';
//    for(int i=1;i<=l-1;i++){
//        cout<<c[i].num<<" ";
//    }
//    cout<<c[l].num<<endl;
//}
//
//signed main()
//{
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t=1;
//    // cin>>t;
//    while(t--){
//        solve();
//    }
//	return 0;
//}


//P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e4 + 5;
void solve(){
    int n,a;
    cin>>n;
   //创建优先队列从小到大排序
    priority_queue<int,vector<int>,greater<int>> pq;
    for(int i=1;i<=n;i++){
        cin>>a;
        pq.push(a);
    }
    int ans=0;
    while(pq.size()>1){
        int x=pq.top();
        pq.pop();
        int y=pq.top();
        pq.pop();
        ans+=x+y;
        pq.push(x+y);
    }
    cout<<ans<<endl;

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1106 删数问题
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;

void solve(){
    string s;
    int k;
    cin>>s>>k;
    stack<char> st;
    char x;
    for(int i=0;i<s.size();i++){
        if(!st.empty())x=st.top();
        else{
        	st.push(s[i]);
        	continue;
		}
		
        if(s[i]<x&&k>0){
            st.pop();
            k--;
            i--;
            //i--是因为此处的i值还应与st中的top()进行比较
            //从而让st中的数值呈现递减的状态
        }
        else st.push(s[i]);
    }
    while(k--){
        st.pop();
        //删完k个数
    }
    stack<char> st1;
    while(!st.empty()){
    	st1.push(st.top());
    	st.pop();
        //将st中的数值倒序存入st1中,以便删除前导零
    }
	while(!st1.empty()&&st1.top()=='0'){
		st1.pop();
        //删除前导零
	}
	string ans="";
    if(st1.empty()){
        cout<<0<<endl;
        return;
    }
    while(!st1.empty()){
    	ans+=st1.top();
    	st1.pop();
	}
    cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

//最完全的替换
//找到t中第一个出现1的位置
//贪心策略:从高位到低位遍历
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
void solve(){
    int n,m,first=0;
	cin>>n>>m;
	string s,t;
	cin>>s>>t;
	for(int i=0;i<m;i++){
		if(t[i]=='1'){
			first=i;
			break;
		}
	}
	int len = m-first-1;
	int ans=0;
	for(int i=0;i<n;i++){
		if(s[i]=='1'&&i+len<n){
			ans++;
			for(int j=first;j<m;j++){
				if(t[j]==s[i+j-first]){
					s[i+j-first]='0';
				}else s[i+j-first]='1';
			}
		}
	}

	for(int i=0;i<n;i++){
		if(s[i]=='1'){
			cout<<"-1\n";
			return ;
		}
	}
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//子序列
//保持区间最大,减去杂数
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e6 + 5;
int a[N], pos[N];
void solve(){
    int n;
    cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pos[a[i]]=i;
	}
	int ans=1,mn=pos[n],mx=pos[n];
	for(int i=n-1;i>=1;i--){
		mn=min(mn,pos[i]),mx=max(mx,pos[i]);
		ans=max(ans,mx-mn+1-(n-i-1));
	}
	cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

//P1843 奶牛晒衣服
//为什么会想到二分答案:求的是晒每件衣服中所花费时间中最大时间的最小值
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 5e5 + 5;
int n,a,b;
int w[N];
bool check(int x){
    //x即是最大的花费时间,也是烘干能使用的最大次数
    //那些地方必须的用烘干才用,若用超了这说明不行
    int cnt=0;
    for(int i=1;i<=n;i++){
        int re=max(0ll,w[i]-x*a);
        if(re==0)continue;

        cnt+=re/b+(re%b==0?0:1);
        if(cnt>x)return false;
    }
    return true;

}
void solve(){
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)cin>>w[i];
    int l=0,r=5e5+1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

2.01背包 搞清楚谁是容积谁是价值

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//P1048 [NOIP 2005 普及组] 采药
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e2 + 5;
int ttime[N],val[N],dp[1005];
void solve(){
    int t,m;
    cin>>t>>m;
    for(int i=1;i<=m;i++){
        cin>>ttime[i]>>val[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=t;j>=ttime[i];j--){
            dp[j]=max(dp[j],dp[j-ttime[i]]+val[i]);
        }
    }
    cout<<dp[t]<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1060 [NOIP 2006 普及组] 开心的金明
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 3e4 + 5;
int w[30],v[30],dp[N];
//w是价格,v代表价格和重要度的乘积
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>w[i]>>v[i];
        v[i]=w[i]*v[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=n;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[n]<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

//P1164 小A点菜
//计数背包
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e3 + 5;
int a[N],dp[10005];
//dp表是花费i元时的点菜总方案数
void solve(){
    int n,m,p;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[0]=1;
    //我们不进行任何操作时,便可知结果的(隐藏条件告知),花费0元时的总方案为1
    //当dp[4]=dp[4]+dp[4-4]时,故可知dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=a[i];j--){
			dp[j]=dp[j]+dp[j-a[i]];
		}
	}
	cout<<dp[m]<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1734 最大约数和
//s是容积,每个数是体积,每个数约数和是价值
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int a[1005],dp[1005];
//dp[i]i表示选的这几个数的和在i以内,dp[i]表示选的这几个数的约数和的最大值
void solve(){
    int s;
    cin>>s;
    for(int i=1;i<=s;i++){
        for(int j=1;j<i;j++){
            if(i%j==0){
                a[i]+=j;
            }
        }
    }


    for(int i=1;i<=s;i++){
        for(int j=s;j>=i;j--){
            dp[j]=max(dp[j],dp[j-i]+a[i]);
        }
    }
    cout<<dp[s]<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1507 NASA的食物计划
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 400 + 5;
int dp[N][N];
struct node{
    int h,t,k;
}a[55];
void solve(){
    int H,T,n;
    cin>>H>>T>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].h>>a[i].t>>a[i].k;
    }
    for(int i=1;i<=n;i++){
        for(int j=H;j>=a[i].h;j--){
            for(int x=T;x>=a[i].t;x--){
                dp[j][x]=max(dp[j][x],dp[j-a[i].h][x-a[i].t]+a[i].k);
            }
        }
    }
    cout<<dp[H][T]<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

3.最短路

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
//dijkstra

int dis[N],vis[N],f[N][N];//dis用于记录从起点到i的最短路,vis标记是否用过,f用于存储前驱到后驱的权值

//n为n个点
void dijkstra() {
	//初始化
	memset(dis,inf,sizeof(dis));
	dis[s]=0;//起点到自己当然是0
	for(int i=1; i<=n; i++) {
		int t=-1;//用于找第一个未被标记的点
		for(int j=1; j<=n; j++)
			if(!vis[j] && (t==-1 || dis[j]<dis[t])) t=j;//未标记或找到更近的
		vis[t]=1;//标记，防止再次计算
		for(int j=1; j<=n; j++) {
			dis[j] = min(dis[j],dis[t]+f[t][j]);
		}
	}
}


int dis[N],vis[N];
vector<pair<int, int>> g[N]; 
struct Node {
    int x, w; // x表示点编号，w表示源点到x的最短距离
    bool operator<(const Node& u) const {
        return w == u.w ? x < u.x : w > u.w; // 按照w降序，在优先队列中w最小的作为堆顶
    }
};

priority_queue<Node> pq;

void dijkstra(int st) {
    // 初始化距离数组为无穷大
    memset(dis, inf, sizeof(dis));
    // 初始化访问标记数组为false
    memset(vis, 0, sizeof(vis));
    pq.push({st, dis[st] = 0}); // 源点到源点的距离为0
    while (!pq.empty()) { // 只要队列不为空
        auto [x, w] = pq.top(); pq.pop(); // 取出队头元素
        if (vis[x]) continue; // 如果走过直接跳过
        vis[x] = 1; // 标记为走过
        for (const auto &[y, dw] : g[x]) { // x->y, 边权为dw的边
            if (dis[x] + dw < dis[y]) { // 这一步十分关键
                dis[y] = dis[x] + dw;
                pq.push({y, dis[y]});
            }
        }
    }
}



int dis[N],vis[N];
vector<pair<int, int> > g[N]; 
struct Node {
    int x, w; // x表示点编号，w表示源点到x的最短距离
    bool operator<(const Node& u) const {
        return w == u.w ? x < u.x : w > u.w; // 按照w降序，在优先队列中w最小的作为堆顶
    }
};

priority_queue<Node> pq;

void dijkstra(int st) {
    // 初始化距离数组为无穷大
    memset(dis, inf, sizeof(dis));
    // 初始化访问标记数组为false
    memset(vis, 0, sizeof(vis));
    pq.push({st, dis[st] = 0}); // 源点到源点的距离为0
    while (!pq.empty()) { // 只要队列不为空
        int x= pq.top().x; pq.pop(); // 取出队头元素
        if (vis[x]) continue; // 如果走过直接跳过
        vis[x] = 1; // 标记为走过
        for (int i=0;i<g[x].size();i++) { // x->y, 边权为dw的边
        	int y=g[x][i].first;
        	int dw=g[x][i].second;
            if (dis[x] + dw < dis[y]) { // 这一步十分关键
                dis[y] = dis[x] + dw;
                pq.push({y, dis[y]});
            }
        }
    }
}





//P1359 租用游艇
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int dis[10005],vis[10005],f[10001][10001];
int n,s=1;
void dijkstra() {
	//初始化
	memset(dis,inf,sizeof(dis));
	dis[s]=0;//起点到自己当然是0
	for(int i=1; i<=n; i++) {
		int t=-1;//用于找第一个未被标记的点
		for(int j=1; j<=n; j++)
			if(!vis[j] && (t==-1 || dis[j]<dis[t])) t=j;//未标记或找到更近的
		vis[t]=1;//标记，防止再次计算
		for(int j=1; j<=n; j++) {
			dis[j] = min(dis[j],dis[t]+f[t][j]);
		}
	}
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) f[i][j]=0;
            else f[i][j]=inf;
        }
    }
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            cin>>f[i][j];
        }
    }
    dijkstra();
    cout<<dis[n]<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

//堆优化之后,此题是有向图,即从站点1出发不可在站点1停靠
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e2 + 5;
int dis[N],vis[N];
vector<pair<int, int>> g[N]; 
struct Node {
    int x, w; // x表示点编号，w表示源点到x的最短距离
    bool operator<(const Node& u) const {
        return w == u.w ? x < u.x : w > u.w; // 按照w降序，在优先队列中w最小的作为堆顶
    }
};

priority_queue<Node> pq;

void dijkstra(int st) {
    // 初始化距离数组为无穷大
    memset(dis, inf, sizeof(dis));
    // 初始化访问标记数组为false
    memset(vis, 0, sizeof(vis));
    pq.push({st, dis[st] = 0}); // 源点到源点的距离为0
    while (!pq.empty()) { // 只要队列不为空
        auto [x, w] = pq.top(); pq.pop(); // 取出队头元素
        if (vis[x]) continue; // 如果走过直接跳过
        vis[x] = 1; // 标记为走过
        for (const auto &[y, dw] : g[x]) { // x->y, 边权为dw的边
            if (dis[x] + dw < dis[y]) { // 这一步十分关键
                dis[y] = dis[x] + dw;
                pq.push({y, dis[y]});
            }
        }
    }
}
void solve(){
    int n,w;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            cin>>w;
            g[i].push_back({j,w});
        }
    }
    dijkstra(1);
    cout<<dis[n]<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1629 邮递员送信
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e3 + 5;
int dis[N],vis[N];
vector<pair<int, int>> g[N]; 
struct Node {
    int x, w; // x表示点编号，w表示源点到x的最短距离
    bool operator<(const Node& u) const {
        return w == u.w ? x < u.x : w > u.w; // 按照w降序，在优先队列中w最小的作为堆顶
    }
};

priority_queue<Node> pq;

void dijkstra(int st) {
    // 初始化距离数组为无穷大
    memset(dis, inf, sizeof(dis));
    // 初始化访问标记数组为false
    memset(vis, 0, sizeof(vis));
    pq.push({st, dis[st] = 0}); // 源点到源点的距离为0
    while (!pq.empty()) { // 只要队列不为空
        auto [x, w] = pq.top(); pq.pop(); // 取出队头元素
        if (vis[x]) continue; // 如果走过直接跳过
        vis[x] = 1; // 标记为走过
        for (const auto &[y, dw] : g[x]) { // x->y, 边权为dw的边
            if (dis[x] + dw < dis[y]) { // 这一步十分关键
                dis[y] = dis[x] + dw;
                pq.push({y, dis[y]});
            }
        }
    }
}
void solve(){
    int n,m,u,v,w;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    dijkstra(1);
    int ans=0;
    for(int i=2;i<=n;i++){
        ans+=dis[i];
    }
    for(int i=2;i<=n;i++){
        dijkstra(i);
        ans+=dis[1];
    }
    cout<<ans<<"\n";

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

4.区间求中位数:前缀和+哈希表

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e3 + 5;
int a[N],sum[N],s[2*N];
void solve(){
    int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		memset(s,0,sizeof(s));
		for(int j=1;j<=n;j++){
			if(a[j]<a[i]){
				sum[j]=sum[j-1]+(-1);
			}else if(a[j]>a[i]){
				sum[j]=sum[j-1]+1;
			}else {
				sum[j]=sum[j-1];
			}
		}
		sum[0]=0;
		for(int j=0;j<i;j++){
			s[sum[j]+2001]+=j+1;
		}
		for(int j=i;j<=n;j++){
			ans+=j*s[sum[j]+2001]*a[i];
		}

	}
	cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

5.二分

最大值最小化,最小值最大化

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
//找到数x
int binary_search(int l,int r,int x){
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x){
            return mid;
        }
        else if(a[mid]>x){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return -1;
}

//找到第一个x的位置,尽量往左找
int binary_search(int l,int r,int x){
	while(l<r){
		int mid=l+(r-l)/2;
		if(check(mid)){
			r=mid;
		}else {
			l=mid+1;
		}
	}
	if(a[l]==x)return l;
	return -1;
}
//尽量往右找
int binary_search(int l,int r,int x){
	while(l<r){
		int mid=l+(r-l)/2;
		if(check(mid)){
			l=mid;
		}else {
			r=mid-1;
		}
	}
	if(a[l]==x)return l;
	return -1;
}

//浮点二分
double bsearch(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)  // 两种写法：此时是用精度控制循环次数，直接控制循环100次也是OK的！
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}


                         
//二分答案
int l=0,r=100000000;//把左端与右端定义，这个地方有些题范围不能开太大，有一定的要求，不过这里就OK了
while(l<=r){
	int mid=(l+r)/2;
	if(judge(mid))//判断步骤 
		l=mid+1;
	else
		r=mid-1;//有些题这里有微调……不过不影响 
} 
cout<<r; 



//P1577 切绳子
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6+ 5;
int a[N];
int n,k;
bool judge(int x){
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=a[i]/x;
    }
    if(ans>=k) return true;
    else return false;
}
int binary_search(int l,int r){
    while(l<=r){
	int mid=(l+r)/2;
	if(mid==0) break;
	if(judge(mid))
		l=mid+1;
	else
		r=mid-1;
    } 
    return r;
}
void solve(){
    cin>>n>>k;
    double b;
    for(int i=1;i<=n;i++) {
        cin>>b;
        a[i]=(int)(b*100);
    }
    int ans=binary_search(0,10000000);
    printf("%0.2f",ans/100.0);
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1182	数列分段 Section II
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
int a[N];
int n,m;
bool check(int x){
    int sum=0,cnt=1;

    for(int i=1;i<=n;i++){
        if(a[i]+sum>x){
            sum=a[i];
            cnt++;
        }else {
            sum+=a[i];
        }
    }
    if(cnt>m) return true;
    return false;
}
void solve(){
    cin>>n>>m;
    int r=0,l=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        r+=a[i];
        l=max(l,a[i]);
    }
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<l<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1281 [CERC1998] 书的复制
//与上一题的思路基本一致,只是最后从后往前遍历,保证越往前抄的越少
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
int a[N];
int m,k;
bool check(int x){
    int sum=0,cnt=1;

    for(int i=1;i<=m;i++){
        if(a[i]+sum>x){
            sum=a[i];
            cnt++;
        }else {
            sum+=a[i];
        }
    }
    if(cnt>k) return true;
    return false;
}
void solve(){
    cin>>m>>k;
    int r=0,l=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        r+=a[i];
        l=max(l,a[i]);
    }
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    stack<pair<int,int> >st;
    int sum=0,ansr=m;
    for(int i=m;i>=1;i--){
        if(a[i]+sum==l){
            sum=0;
            st.push({i,ansr});
            ansr=i-1;
        }else if(a[i]+sum>l){
            sum=a[i];
            st.push({i+1,ansr});
            ansr=i;
        }else {
            sum+=a[i];
            if(i==1){
                st.push({i,ansr});
            }
        }
    }
    while(!st.empty()){
        auto [l,r]=st.top();
        st.pop();
        cout<<l<<" "<<r<<endl;
    }
    
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1396 营救
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e4+5;
//N一开始开大了导致MLE
int n,m,s,t;
int vis[N];//一开始没开vis数组导致TLE
vector<pair<int,int>>g[N];
bool check(int x){
    //bfs
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        if(u==t)return true;
        q.pop();
        for(auto [v,w]:g[u]){
            if(vis[v])continue;
            if(w>x)continue;
            q.push(v);vis[v]=1;
        }
    }
    return false;

}
void solve(){
    cin>>n>>m>>s>>t;
    int l=0,r=0;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        r=max(r,w);
        //无向图
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)){
            r=mid-1;
        }
        else {
            l=mid+1;
        }
    }
    cout<<l<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1570 KC 喝咖啡
//难点:公式变形,变形之后如何往二分答案上靠
//∑(1,m)c*x-∑(1,m)*v=0,我们只需尽可能的让式子的左侧尽可能的靠近0
//也就是说我们选择的c[i]*x-v[i]要尽可能的小,所以贪心排序,选择前m个较小的c[i]*x-v[i]
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e2 + 5;
int n,m;
struct node{
    int v,c;
    double val;
    bool operator<(const node &a)const{
        return val<a.val;
    }
}a[N];
bool check(double x){
    for(int i=1;i<=n;i++)a[i].val=x*a[i].c-a[i].v;
    sort(a+1,a+1+n);
    double sum=0;
    for(int i=1;i<=m;i++){
        sum+=a[i].val;
    }
    return sum<=0;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i].v;
    for(int i=1;i<=n;i++)cin>>a[i].c;
    //浮点二分模版
    double l=0,r=1000;
    while(r-l>1e-6){
        double mid=(l+r)/2;
        if(check(mid)){
            l=mid;
        }else{
            r=mid;
        }
    }
    cout<<fixed<<setprecision(3)<<l<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}


//P1661 扩散
//为什么用二分答案:这道题求得是两点之间花费时间的最大值中的最小值
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 50 + 5;
int n;
int bseach[N];
vector<pair<int,int>>v(N);
//判断是否连通:并查集
int find(int x){
    if(bseach[x]==x)return x;
    return bseach[x]=find(bseach[x]);
}
bool check(int x){
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int a=abs(v[i].first - v[j].first);
            int b=abs(v[i].second - v[j].second);
            //a+b为两点之间的连通所花费时间的两倍(两个点都可以扩散)
            if(a+b<=2*x){
                int fa=find(i),fb=find(j);
                if(fa!=fb){
                    bseach[fa]=fb;
                }
            }
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        if(bseach[i]==i){
            cnt++;
        }
    }
    //当x很大时,所有点都连通
    if(cnt==1){
        return true;
    }else {
        return false;
    }
}
void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i].first>>v[i].second;
    }
    //二分答案模版
    int l=0,r=1e9+10;
    while(l<=r){
        int mid=l+(r-l)/2;
        for(int i=0;i<n;i++){
            bseach[i]=i;
        }
        if(check(mid)){
            r=mid-1;
        }else {
            l=mid+1;
        }
    }
    
    cout<<l<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}



//P1843 奶牛晒衣服
//为什么会想到二分答案:求的是晒每件衣服中所花费时间中最大时间的最小值
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 5e5 + 5;
int n,a,b;
int w[N];
bool check(int x){
    //哪些地方必须得用烘干才用,若用超了这说明不行
    //x既代表了花费的最大时间,也代表了最多可使用的烘干次数
    int cnt=0;
    for(int i=1;i<=n;i++){
        int re=max(0ll,w[i]-x*a);
        //在x的时间内若可直接晒干,则直接跳过
        if(re==0)continue;
        //记录烘干次数
        cnt+=re/b+(re%b==0?0:1);
        if(cnt>x)return false;
    }
    return true;

}
void solve(){
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)cin>>w[i];
    int l=0,r=5e5+1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

6.双指针+模拟

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
//P1638 逛画展
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int a[N],b[2005],cnt;
void in(int x){
    if(b[x]==0)cnt++;
    b[x]++;
}
void d(int x){
    if(b[x]==1)cnt--;
    b[x]--;
}
void solve(){ 
    int n,m;  
    cin>>n>>m;  
    for(int i=1;i<=n;i++){  
        cin>>a[i];  
    }
    int l=1,ans=inf,ansl=1,ansr=n;  
    for(int i=1;i<=n;i++){
        in(a[i]);
        while(true){
            d(a[l]);
            if(cnt==m)l++;
            else {
                in(a[l]);
                break;
            }
        }
        if(cnt==m&&i-l+1<ans)ans=i-l+1,ansl=l,ansr=i;
    }
    cout<<ansl<<" "<<ansr<<endl; 
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

7.最小生成树

Kruskal算法

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
struct Edge {
    int x, y, c;
    bool operator< (const Edge &u) const {
        return c < u.c;
    }
};

int pre[N];

int root(int x) {
    return pre[x] == x ? x : root(pre[x]);
}

void solve() {
    int n, m; cin >> n >> m;
    vector<Edge> es;
    for(int i = 1; i <= m; ++ i) {
        int x, y, c; cin >> x >> y >> c;
        es.push_back({x, y, c});
    }
    sort(es.begin(), es.end());
    for(int i = 1; i <= n; ++ i) pre[i] = i;
    int ans = 0;
    for(const auto& [x, y, c] : es) {
        if(root(x) == root(y)) continue;
        ans = max(ans, c);
        pre[root(x)] = root(y);
    }
    cout << ans << '\n';
}




//P1661 扩散
//点之间的最短时间是确定的,我们要找出最短时间的最大值
//连通且最短时间确定,故用最小生成树
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
struct Edge {
    int x, y, c;
    bool operator< (const Edge &u) const {
        return c < u.c;
    }
};

int pre[N];

int root(int x) {
    return pre[x] == x ? x : root(pre[x]);
}

void solve() {
    int n; cin >> n ;
    vector<Edge> es;
    vector<pair<int,int>>d;
    for(int i = 0; i < n; ++ i) {
        int x, y; cin >> x >> y;
        d.push_back({x,y});
    }
    //kruskal模版
    for(int i = 0; i < n; ++ i) {
        for(int j=i+1;j<n;++j){
            int c = (abs(d[i].first - d[j].first)+abs(d[i].second - d[j].second)+1)/2;//计算时间
            //曼哈顿距离为奇数时:c=dis/2+1=(dis+1)/2
            es.push_back({i, j, c});
        }
    }
    sort(es.begin(), es.end());
    for(int i = 0; i < n; ++ i) pre[i] = i;
    int ans = 0;
    for(const auto& [x, y, c] : es) {
        if(root(x) == root(y)) continue;
        ans = max(ans, c);
        pre[root(x)] = root(y);
    }
    cout << ans << '\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

Prim算法

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
struct Edge {
    ll x, c;
    bool operator< (const Edge &u) const {
        return c == u.c ? x > u.x : c < u.c;
    }
};

vector<Edge> g[N];

ll d[N];
int n, m;

int prim() {
    priority_queue<Edge> pq;
    bitset<N> vis;
    d[1] = 0;
    pq.push({1, d[1]});
    ll res = 0;
    while(pq.size()) {
        int x = pq.top().x; pq.pop();
        if(vis[x]) continue;
        vis[x] = true;

        res = max(res, d[x]);

        for(const auto &[y, w] : g[x]) {
            if(!vis[y]) {
                d[y] = min(d[y], w);
                pq.push({y, d[y]});
            }
        }
    }
    return res;
}

8.并查集

1
2
3
4
int root(int x) {
    if (pre[x] == x) return x; // 如果当前节点是自身的父节点，则它是根节点
    return root(pre[x]); // 否则，递归地查找父节点的根
}

路径压缩优化

1
2
3
int root(int x) {
    return pre[x] = (pre[x] == x ? x : root(pre[x])); // 路径压缩，将沿途节点直接指向根节点
}

合并操作

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(int x, int y) {
    int rx = root(x), ry = root(y); // 找到两个节点的根节点
    if (rx == ry) return; // 如果两个根节点相同，则无需合并

    // 如果rx所在集合更大，则交换rx和ry，以保证rx所在集合的大小不超过ry所在集合
    if (siz[rx] > siz[ry]) swap(rx, ry);

    // 将rx所在集合合并到ry所在集合中
    pre[rx] = ry; // 将rx的根节点指向ry
    siz[ry] += siz[rx]; // 更新ry所在集合的大小

    // 合并完成后，rx将不再作为根节点，其大小信息也失去了意义
}
947. 移除最多的同行或同列石头 - 力扣（LeetCode）
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
//从边缘到中心逐渐消减石头
//最后发现属于一个集合的只会剩下一块石头
class Solution {
public:
int father[1001];
int siz[1001];
int mpx[10001];
int mpy[10001];
    int root(int x) {
        return father[x] = (father[x] == x ? x : root(father[x])); 
    }
    void merge(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry)return ;

        if(siz[rx]>siz[ry])swap(rx,ry);
        father[rx]=ry;
        siz[ry]+=siz[rx];
    }
    int removeStones(vector<vector<int>>& stones) {
        int n=stones.size();
        for(int i=1;i<=n;i++){
            father[i]=i;
        }
        for(int i=0;i<n;i++){
            int x=stones[i][0];
            int y=stones[i][1];
            if(mpx[x]==0){
                mpx[x]=i+1;
            }else{
                merge(mpx[x],i+1);
            }

            if(mpy[y]==0){
                mpy[y]=i+1;
            }else{
                merge(mpy[y],i+1);
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(father[i]==i)ans++;
        }
        return n-ans;
    }
};
P1111 修复公路 - 洛谷

//需要在合并的时候判断:

若两个集合的father相同那么就判一下他们father的siz集合个数是否达到n,

若两个集合的father不同,那么就一定没有实现所有元素在一个集合,故对他们进行合并.合并后在判断是否集合个数达到n,即所有元素在同一个集合

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
struct node{
    int x,y,t;
}arr[N];
bool cmp(node a,node b){
    return a.t<b.t;
}
int father[1005],siz[1005],n,m;;
int root(int x){
    if(x==father[x])return x;
    return father[x]=root(father[x]);
}
bool merge(int x,int y){
    int fx=root(x),fy=root(y);
    if(fx==fy){//father相同
        if(siz[fx]==n){
            return true;
        }
        return false;
    }
    //father不同
    if(siz[fx]>siz[fy]){
        swap(fx,fy);
    }
    father[fx]=fy;
    siz[fy]+=siz[fx];
    if(siz[fy]==n){
        return true;
    }
    return false;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>arr[i].x>>arr[i].y>>arr[i].t;
    }
    sort(arr+1,arr+m+1,cmp);
    for(int i=1;i<=n;i++){
        father[i]=i;
        siz[i]=1;
    }
    for(int i=1;i<=m;i++){
        if(merge(arr[i].x,arr[i].y)){
            cout<<arr[i].t<<endl;
            return;
        }
    }
    cout<<-1<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P3958 NOIP 2017 提高组] 奶酪 - 洛谷

//思路就是:将能够相交的划分为一组,然后将存放坐标的数组依据z值从小到大排序,l从小到大跑,rr从大到小跑,如果满足arr[l].z-r<=0并且arr[rr].z+r>=h则说明上下连通,接着判断二者是否连通即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e3 + 5;
struct node{
    int x,y,z,id;
} arr[N];
bool cmp(node a,node b){
    return a.z<b.z;
}
int father[N],siz[N];
int root(int x){
    if(father[x]==x)return x;
    return father[x]=root(father[x]);
}
void merge(int x,int y){
    int fx=root(x),fy=root(y);
    if(fx==fy)return ;
    if(siz[fx]>siz[fy]){
        swap(fx,fy);
    }
    father[fx]=fy;
    siz[fy]+=siz[fx];
}
void solve(){
    memset(father,0,sizeof(father));
    memset(siz,0,sizeof(siz));
    int n,h,r;
    cin>>n>>h>>r;
    for(int i=1;i<=n;i++){
        cin>>arr[i].x>>arr[i].y>>arr[i].z;
        father[i]=i;
        siz[i]=1;
        arr[i].id=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(abs((arr[i].x-arr[j].x)*(arr[i].x-arr[j].x)+(arr[i].y-arr[j].y)*(arr[i].y-arr[j].y)+(arr[i].z-arr[j].z)*(arr[i].z-arr[j].z))<=4*r*r){
                merge(i,j);
            }
        }
    }
    sort(arr+1,arr+1+n,cmp);
    for(int l=1;l<=n;l++){
        for(int rr=n;rr>=l;rr--){//一开始rr写成r,导致错误
            if((arr[l].z-r)<=0&&(arr[rr].z+r>=h)){
                if(root(arr[l].id)==root(arr[rr].id)){
                    cout<<"Yes\n";
                    return;
                }
            }else{
                break;
            }
        }
    }
    cout<<"No\n";
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P1525 NOIP 2010 提高组] 关押罪犯 - 洛谷

//这道题我忽略的点:

只有两所监狱

//所以怨气值越大的肯定就越要分开,所以对怨气值进行从大到小的排序,

//从大到小遍历怨气值,如果遍历到的两个犯人已经被分配到同一个监狱则输出二人的怨气值即可

//若没有被分配到同一个监狱,他们互为敌人,则分别将他们敌人的敌人与他们自己合并(分配到同一个监狱),

//用b[i]记录i的敌人代表(开始b[i]为0,则将第一个敌人赋给b[i])

[!CAUTION]

当m=1时需进行特判,原因是因为它并没有机会在循环中输出

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int f[20005],e[20005];
struct node{
    int a,b,c;
}arr[100005];
bool cmp(node a,node b){
    return a.c>b.c;
}
int find(int x){
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy)return;
    f[fx]=fy;
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>arr[i].a>>arr[i].b>>arr[i].c;
    }
    if(m==1){
        cout<<0<<'\n';
        return ;
    }
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    sort(arr+1,arr+1+m,cmp);
    for(int i=1;i<=m;i++){
        if(find(arr[i].a)==find(arr[i].b)){
            cout<<arr[i].c<<endl;
            return;
        }else{
            if(!e[arr[i].a]){
                e[arr[i].a]=arr[i].b;
            }else{
                merge(arr[i].b,e[arr[i].a]);
            }
            if(!e[arr[i].b]){
                e[arr[i].b]=arr[i].a;
            }else{
                merge(arr[i].a,e[arr[i].b]);
            }
        }
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P4185 USACO18JAN] MooTube G - 洛谷

//这道题给我的教训是:

我的贪心的思维很差

//贪心思路(+离线思路):

先把k值大的数量统计(该合并的合并),则k值小的包含k值大的答案

遍历r的思路是:

从大到小,则每次的r都是各点到其他点的最小可能r(其他比r大的R所关联的点已连接)

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 long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
struct node1{
    int p,q,r;
}arr[N];
struct node2{
    int k,v,id;
}brr[N];
int ans[N];
bool cmp1(node1 a,node1 b){
    return a.r>b.r;
}
bool cmp2(node2 a,node2 b){
    return a.k>b.k;
}
int pre[N],siz[N];
int root(int x) {
    return pre[x] = (pre[x] == x ? x : root(pre[x])); // 路径压缩，将沿途节点直接指向根节点
}
void merge(int x, int y) {
    int rx = root(x), ry = root(y); // 找到两个节点的根节点
    if (rx == ry) return; // 如果两个根节点相同，则无需合并

    // 如果rx所在集合更大，则交换rx和ry，以保证rx所在集合的大小不超过ry所在集合
    if (siz[rx] > siz[ry]) swap(rx, ry);

    // 将rx所在集合合并到ry所在集合中
    pre[rx] = ry; // 将rx的根节点指向ry
    siz[ry] += siz[rx]; // 更新ry所在集合的大小

    // 合并完成后，rx将不再作为根节点，其大小信息也失去了意义
}
void solve(){
    int N,Q;
    cin>>N>>Q;
    for(int i=1;i<N;i++){
        cin>>arr[i].p>>arr[i].q>>arr[i].r;
    }
    for(int i=1;i<=Q;i++){
        cin>>brr[i].k>>brr[i].v;
        brr[i].id=i;
    }
    for(int i=1;i<=N;i++){
        pre[i]=i;
        siz[i]=1;
    }
    sort(arr+1,arr+1+N,cmp1);
    sort(brr+1,brr+1+Q,cmp2);
    int j=1;
    for(int i=1;i<=Q;i++){
        while(j<N&&arr[j].r>=brr[i].k){
            merge(arr[j].p,arr[j].q);
            j++;
        }
        ans[brr[i].id]=siz[root(brr[i].v)];
    }
    for(int i=1;i<=Q;i++){
        cout<<ans[i]-1<<"\n";
    }
    
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P2024 NOI2001] 食物链 - 洛谷

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
//种类并查集

#include <cstdio>

inline int read() {
	char c = getchar(); int n = 0;
	while (c < '0' || c > '9') { c = getchar(); }
	while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
	return n;
}

const int maxN = 100005;

int n, m, ans, fa[maxN * 3];

int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); }

/*
 * 主函数，处理输入数据并执行集合操作
 * 使用并查集实现关系判断和合并
 * 处理两种操作：opt=1 表示同类关系，opt=2 表示捕食关系
 */
int main() {
	n = read(), m = read();
	for (int i = 1; i <= n * 3; i++) { fa[i] = i; }
	for (; m; m--) {
		int opt = read(), u = read(), v = read();
		if (u > n || v > n) { ans++; continue; }
		if (opt == 1) {
			if (find(u + n) == find(v) || find(u) == find(v + n)) { ans++; }
			else {
				fa[find(u)] = find(v);
				fa[find(u + n)] = find(v + n);
				fa[find(u + n + n)] = find(v + n + n);
			}
		} else {
			if (find(u) == find(v) || find(u) == find(v + n)) { ans++; }
			else {
				fa[find(u + n)] = find(v);
				fa[find(u + n + n)] = find(v + n);
				fa[find(u)] = find(v + n + n);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

9.思维题

(1)

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
//1292B - Aroma's Search
//越靠前点越密集,dis(xi,xi+1)的min值为xi,dis(xi,x0)=xi-x0,两式相减可得dis(xi,,xi+1)>dis(xi,x0)(因为x0>1),故捡数据点时,应先寻找点密集的那一侧,再返回点疏的那一侧
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int n,x[100],y[100];
int dis(int x1,int y1,int x2,int y2){
    return abs(x1-x2)+abs(y1-y2);
}
void solve(){
    int x0,y0,ax,ay,bx,by,xs,ys,t,ans=0;
    cin>>x0>>y0>>ax>>ay>>bx>>by>>xs>>ys>>t;
    x[0]=x0,y[0]=y0;
    while(++n){
        x[n]=ax*x[n-1]+bx;
        y[n]=ay*y[n-1]+by;
        if(x[n]>xs&&y[n]>ys&&dis(x[n],y[n],xs,ys)>t)break;
    }
    for(int i=0;i<n;i++){
        int tans=0,tt=t;
        if(dis(x[i],y[i],xs,ys)<=tt)tt-=(dis(x[i],y[i],xs,ys)),tans++;
        else {ans=max(ans,tans);continue;}//大于则直接跳过以下步骤
        for(int j=i;j;j--){
            if(dis(x[j],y[j],x[j-1],y[j-1])<=tt)tt-=(dis(x[j],y[j],x[j-1],y[j-1])),tans++;
            else break;
        }
        for(int j=0;j<n-1;j++){//必须从0开始,因为这里不知计算数据点,还要对tt进行处理
            if(dis(x[j],y[j],x[j+1],y[j+1])<=tt)tt-=(dis(x[j],y[j],x[j+1],y[j+1])),tans+=j>=i;
            else break;
        }
        ans=max(ans,tans);
    }
    cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}




(2)

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
//CF1304C Air Conditioner
//维护区间
//能够及时变温的条件是前后区间有交集
//是否有交集可以通过sl是否大于sr判断
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;

void solve(){
    int n,sl,sh,st=0;
    cin>>n>>sl;
    int t,l,h;
    sh=sl;
    bool flag=0;
    for(int i=1;i<=n;i++){
        cin>>t>>l>>h;
        sh=min(h,t-st+sh);
        sl=max(l,sl-t+st);
        st=t;
        if(sl>sh)flag=1;
    }
    if(flag) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

(3)

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
//CF1385D a-Good String
//根据对称性想到了平衡树(二叉树),故直接遍历每种可能选出消耗最少得操作方法    
//时间复杂度由master公式可知为nlogn; 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 131072;
int ans,num;
void bfs(string l,string r,int len,char c){
    if(len==0){
        string zi="";
        zi+=c;
        if(r==zi){
            ans=min(ans,num);
        }else{
            ans=min(ans,num+1);
        }
        return;
    }
    for(int i=0;i<len;i++){
        if(l[i]!=c){
            num++;
        }
    }
    bfs(r.substr(0,len/2),r.substr(len/2,len),len/2,(char)(c+1));
    for(int i=0;i<len;i++){
        if(l[i]!=c){
            num--;
        }
    }

    for(int i=0;i<len;i++){
        if(r[i]!=c){
            num++;
        }
    }
    bfs(l.substr(0,len/2),l.substr(len/2,len),len/2,(char)(c+1));
    for(int i=0;i<len;i++){
        if(r[i]!=c){
            num--;
        }
    }
}
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    ans=inf,num=0;
    if(n==1){
        if(s=="a")cout<<0<<'\n';
        else cout<<1<<'\n';
        return;
    }
    string l=s.substr(0,n/2),r=s.substr(n/2,n);
    bfs(l,r,n/2,'a');
    cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

10.排序

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void shell_sort(int a[],int n){
    int gap=n;
    while(gap>1){
        gap=gap/3+1;
        for(int i=1;i<=gap;i++){//控制组数
            for(int j=i;j<=n-gap+1;j+=gap){//控制组内需插入的元素个数
                int key=a[j];
                int end=j-gap;
                while(end>=1&&a[end]>key){
                    a[end+gap]=a[end];
                    end-=gap;
                }
                a[end+gap]=key;
            }
        }
    }
}

归并排序

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
int arr[N],help[N],n;
void merge(int l,int mid,int r){
    int i=l,a=l,b=mid+1;
    while(a<=mid&&b<=r){
        help[i++]=arr[a]>arr[b]?arr[b++]:arr[a++];
    }
    while(a<=mid){
        help[i++]=arr[a++];
    }
    while(b<=r){
        help[i++]=arr[b++];
    }
    for(int i=l;i<=r;i++){
        arr[i]=help[i];
    }
}

void mergeSort1(int l,int r){
    if(l==r)return ;
    int mid=(l+r)>>1;
    mergeSort1(l,mid);
    mergeSort1(mid+1,r);
    merge(l,mid,r);
}

void mergeSort2(int l,int r){
    for(int l,m,r,step=1;step<=n;step<<=1){
        l=0;
        while(l<=n){
            m=l+step-1;
            if(m+1>n)break;
            r=min(l+step*2-1,n);
            merge(l,m,r);
            l=r+1;
        }
    }
}

快速排序

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
//最好通过随机数划分,的平均复杂度
void quickSort(int l,int r){
    if(l>=r)return;
    int i=l-1,j=r+1,x=arr[l+r>>1];
    while(i<j){
        do{i++;}while(arr[i]<x);
        do{j--;}while(arr[j]>x);
        if(i<j)swap(arr[i],arr[j]);
    }
    quickSort(l,j),quickSort(j+1,r);
}



int first,last;
void partition(int l,int r,int x){
    first=l,last=r;
    int i=l;
    while(i<=last){
        if(arr[i]<x){
            swap(arr[i++],arr[first++]);
        }else if(arr[i]==x)i++;
        else{
            swap(arr[i],arr[last--]);
        }
    }
}
void quickSort2(int l,int r){
    if(l>=r)return;
    int x=arr[l+r>>1];
    partition(l,r,x);
    quickSort2(l,first-1);
    quickSort2(last+1,r);
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cnt[N];
void countSort(int l,int r){
    int Max=arr[l],Min=arr[l];
    for(int i=l;i<=r;i++){
        if(arr[i]>Max)Max=arr[i];
        if(arr[i]<Min)Min=arr[i];
    }
    int len=Max-Min+1;
    for(int i=l;i<=r;i++){
        cnt[arr[i]-Min]++;
    }
    int it=1;
    for(int i=0;i<len;i++){
        while(cnt[i]>0){
            arr[it++]=i+Min;
            cnt[i]--;
        }
    }
}

11.0递归

11.01经典递归

//1.返回字符串的所有子序列O(2^n*n)

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
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    set<string>st;
    vector<string>ans;
    int len;
    vector<string> generatePermutation(string s) {
        len=s.length();
        solve("",0,s);
        for(auto it:st){
            ans.push_back(it);
        }
        return ans;
    }
   void solve(string s,int i,string ss){
        if(i==len){
            st.insert(s);
            return ;
        }
        string s1=s;
        solve(s1,i+1,ss);
        s1=s+ss[i];
        solve(s1,i+1,ss);
        return;
    }
};

//2. O(2^n*n)

//1,1,1,2,2,4,4

//分组:只有0个1的时候,只有1个1的时候,只有2个1的时候,只有3个1的时候(同理只有0个2的时候,只有1个2的时候,只有2个2的时候)

90. 子集 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<vector<int>>ans;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int>vec;
        fun(nums,0,vec);
        return ans;
    }
    void fun(vector<int>& nums,int i,vector<int> vec){
        if(i==nums.size()){
            ans.push_back(vec);
            return ;
        }
        int j=i+1;
        while(j<nums.size()&&nums[i]==nums[j])j++;
        fun(nums,j,vec);
        for(int t=i;t<j;t++){
            vec.push_back(nums[t]);
            fun(nums,j,vec);
        }
    }
};

//输出n个数的所有排列(n*n!)

//以原先给定的数组为基准,尝试将每个数交换到i位置,递归下去即可

46. 全排列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<vector<int>>ans;
    vector<vector<int>> permute(vector<int>& nums) {
        fun(nums,0);
        return ans;
    }
    void fun(vector<int>& nums,int i){
        if(i==nums.size()){
            vector<int>temp;
            for(auto it:nums){
                temp.push_back(it);
            }
            ans.push_back(temp);
        }
        for(int j=i;j<nums.size();j++){
            swap(nums[i],nums[j]);
            fun(nums,i+1);
            swap(nums[i],nums[j]);
        }
    }
};

//汉罗塔

1
2
3
4
5
6
7
8
void hanluota(int size,char a,char b,char c){
    if(size==0){
        return;
    }
    hanluota(size-1,a,c,b);
    cout<<a<<"->"<<b<<endl;
    hanluota(size-1,c,b,a);
}
11.02嵌套类递归

[!IMPORTANT]

  1. 定义全局变量where,记录每次嵌套条件结束后i的值,以便后续对i进行更新
  2. 结束条件为总问题结结尾或是嵌套问题的结尾

//计算含多层括号的表达式

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int where;
void pushFun(deque<int>&numbers,deque<char>&ops,int num,char op){
    int size=numbers.size();
    if(size==0||ops.back()=='+'||ops.back()=='-'){
        numbers.push_back(num);
        ops.push_back(op);
    }else{
        int num1=numbers.back();
        char op1=ops.back();
        numbers.pop_back();
        ops.pop_back();
        if(op1=='*'){
            numbers.push_back(num*num1);
        }else{
            numbers.push_back(num/num1);
        }
        ops.push_back(op);
    }
}
int final(deque<int>&numbers,deque<char>&ops){
    int ans=numbers.front();
    numbers.pop_front();
    while(!numbers.empty()){
        ans+=(ops.front()=='+'?numbers.front():-numbers.front());
        numbers.pop_front();
        ops.pop_front();
    }
    return ans;
}
//i++,忘了几次 
int calculate(string s,int i){
    int cur=0;
    deque<int>numbers;deque<char>ops;
    while(i<s.length()&&s[i]!=')'){
        if(s[i]>='0'&&s[i]<='9'){
            cur=cur*10+s[i++]-'0';
        }else if(s[i]!='('){
            pushFun(numbers,ops,cur,s[i++]);
            cur=0;
        }else{
            cur=calculate(s,i+1);
            i=where+1;
        }
    }
    pushFun(numbers,ops,cur,'+');
    where=i;
    return final(numbers,ops);
}

void solve(){
    string s;
    cin>>s;
    cout<<calculate(s,0)<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

11.动态规划

983. 最低票价
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
//递归
class Solution {
public:
    const int inf=0x3f3f3f3f;
    int duration[3]={1,7,30},dp[366]={0};
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        return solve(days,costs,0);
    }
    int solve(vector<int>& days,vector<int>& costs,int i){
        if(i==days.size())return 0;
        if(dp[i])return dp[i];
        int ans=inf;
        for(int k=0,j=i;k<3;k++){
            while(j<days.size()&&days[i]+duration[k]>days[j])j++;
            ans=min(ans,costs[k]+solve(days,costs,j));
        }
        dp[i]=ans;
        return ans;
    }
};


//动态规划
class Solution {
public:
    const int inf=0x3f3f3f3f;
    int duration[3]={1,7,30},dp[366];
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        return solve(days,costs,days.size());
    }
    int solve(vector<int>& days,vector<int>& costs,int n){
        for(int i=0;i<366;i++){
            dp[i]=inf;
        }
        int ans=inf;
        dp[n]=0;
        for(int i=n-1;i>=0;i--){
            for(int k=0,j=i;k<3;k++){
                while(j<n&&days[i]+duration[k]>days[j])j++;
                dp[i]=min(dp[i],costs[k]+dp[j]);
            }
        }
        return dp[0];
    }
};
91. 解码方法
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
//记忆化搜索
class Solution {
public:
    int dp[105];
    int numDecodings(string s) {
        return solve(s,0);
    }

    int solve(string s,int i){
        if(i==s.length())return 1;
        if(dp[i])return dp[i];
        int ans=0;
        if(s[i]=='0'){
            ans=0;
        }else{
            ans=solve(s,i+1);
            if(i+1<s.length()&&(s[i]-'0')*10+s[i+1]-'0'<=26){
                ans+=solve(s,i+2);
            }
        }
        dp[i]=ans;
        return ans;
    }
};

//动态规划
class Solution {
public:
    int dp[105];
    int numDecodings(string s) {
        return solve(s,0);
    }

    int solve(string s,int i){
        dp[s.length()]=1;
        for(int i=s.length()-1;i>=0;i--){        
            if(s[i]=='0'){
                dp[i]=0;
            }else{
                dp[i]=dp[i+1];
                if(i+1<s.length()&&(s[i]-'0')*10+s[i+1]-'0'<=26){
                    dp[i]+=dp[i+2];
                }
            }
        }
        return dp[0];
    }
};

//从动态规划得到解依赖于其后一个和后后一个数的解,故知道可通过记录后两个数的解即可得到这个数的解,这样节省了空间,从数组到两个变量
class Solution {
public:
    int numDecodings(string s) {
        return solve(s,0);
    }

    int solve(string s,int i){
        int n=1,nn=0,cnt;
        for(int i=s.length()-1;i>=0;i--){        
            if(s[i]=='0'){
                cnt=0;
                nn=n;
                n=cnt;
            }else{
                cnt=n;
                if(i+1<s.length()&&(s[i]-'0')*10+s[i+1]-'0'<=26){
                    cnt+=nn;
                }
                nn=n;
                n=cnt;
            }
        }
        return n;
    }
};
639. 解码方法 II
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
//动态规划
//注意超出类型范围,所以用long
class Solution {
public:
const long mod=1e9+7;
long dp[100005];
    int numDecodings(string s) {
        return (int)fun(s);
    }
    long fun(string s){
        int n=s.length();
        dp[n]=1;
        for(int i=n-1;i>=0;i--){
            if(s[i]=='0')continue;
            dp[i]=dp[i+1]*(s[i]=='*'?9:1);
            if(i+1<n){
                if(s[i]!='*'){
                    if(s[i+1]!='*'){
                        if(((s[i]-'0')*10+s[i+1]-'0')<=26){
                            dp[i]+=dp[i+2];
                        }
                    }else{
                        if(s[i]=='1'){
                            dp[i]+=dp[i+2]*9;
                        }else if(s[i]=='2'){
                            dp[i]+=dp[i+2]*6;
                        }
                    }
                }else{
                    if(s[i+1]!='*'){
                        if(s[i+1]<='6')dp[i]+=dp[i+2]*2;
                        else dp[i]+=dp[i+2];
                    }else{
                        dp[i]+=dp[i+2]*15;
                    }
                }
            }
            dp[i]=dp[i]%mod;
        }
        return dp[0];
    }
};

//变量转移,节省空间
class Solution {
public:
const long mod=1e9+7;
    int numDecodings(string s) {
        return (int)fun(s);
    }
    long fun(string s){
        int len=s.length();
        long nn=0,n=1,cur;
        for(int i=len-1;i>=0;i--){
            if(s[i]=='0'){
                cur=0;
                nn=n;
                n=cur;
                continue;
            }
            cur=n*(s[i]=='*'?9:1);
            if(i+1<len){
                if(s[i]!='*'){
                    if(s[i+1]!='*'){
                        if(((s[i]-'0')*10+s[i+1]-'0')<=26){
                            cur+=nn;
                        }
                    }else{
                        if(s[i]=='1'){
                            cur+=nn*9;
                        }else if(s[i]=='2'){
                            cur+=nn*6;
                        }
                    }
                }else{
                    if(s[i+1]!='*'){
                        if(s[i+1]<='6')cur+=nn*2;
                        else cur+=nn;
                    }else{
                        cur+=nn*15;
                    }
                }
            }
            cur=cur%mod;
            nn=n;
            n=cur;
        }
        return n;
    }
};
32. 最长有效括号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//得到一个字符后,以其为开始的点向左延伸,得到这个字符的最长子串
//若遇'(',则dp[i]=0;
//若遇')',则dp[i]=(s[i-1-dp[i-1]]=='('?dp[i-1]+2+dp[i-1-dp[i-1]-1]:0)
class Solution {
public:
    int dp[3*10000+5];
   int longestValidParentheses(string s) {
        s=" "+s;
        int n=s.length();
        for(int i=1;i<n;i++){
            if(s[i]==')'){
                int j=i-1-dp[i-1];
                if(s[j]=='('){
                    dp[i]=dp[i-1]+2+dp[j-1];
                }
            }
        }
        int ans=0;
        for(int i=1;i<n;i++){
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};
1274: D003 Help Jimmy

P1274 - D003 Help Jimmy - NENUOJ

Min(i,true)表示从第i块板子的左侧出发到地面的最短距离

minleft[i]用来记录从第i块板子的左侧出发到地面的最短距离

minright[i]用来记录从第i块板子的右侧出发到地面的最短距离

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e3 + 5;
int minleft[N];
int minright[N],Max,n;
struct node{
    int x1,x2,h;
}arr[N];
bool cmp(node a,node b){
    return a.h>b.h;
}
int Min(int k,bool left){
    int x,y=arr[k].h,i;
    //往左侧行就给x赋值为k左侧的坐标x1
    if(left){
        x=arr[k].x1;
    }else {
        x=arr[k].x2;
    }
    //查询k块板子的下面是否有其他木板
    for(i=k+1;i<=n;i++){
        if(arr[i].x1<=x&&arr[i].x2>=x){
            break;
        }
    }
    //若没有
    if(i==(n+1)){
        if(y>Max)return inf;//第k块板子到地面的距离大于Max,则直接返回inf
        else return y;
        //若小于则所花费的时间就是y
    }
    //若有
    else{
        //第k块板子到i块板子的距离大于Max,则返回inf
        if(y-arr[i].h>Max)return inf;
    }
    //分别计算从第i块板子的左侧,右侧出发所花费的水平方线上的时间
    int lefttime=y-arr[i].h+x-arr[i].x1,righttime=y-arr[i].h+arr[i].x2-x;
    if(minleft[i]==-1){
        minleft[i]=Min(i,true);
    }
    if(minright[i]==-1){
        minright[i]=Min(i,false);
    }
    //第k块板子(下面有板子i)到地面的最短时间,k块板子到i块板子的水平距离+降落到i块板子的竖直距离+第i块板子到地面的最短距离(分从第i块板子的左侧出发还是右侧出发)
    return min(minleft[i]+lefttime,minright[i]+righttime);
}
void solve(){
    int x,y;
    cin>>n>>x>>y>>Max;
    arr[0].x1=x,arr[0].x2=x,arr[0].h=y;
    for(int i=0;i<=n;i++){
        minleft[i]=-1;
        minright[i]=-1;
    }
    for(int i=1;i<=n;i++){
        cin>>arr[i].x1>>arr[i].x2>>arr[i].h;
    }
    sort(arr+1,arr+1+n,cmp);
    cout<<Min(0,true)<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}
1275: D004 最长公共子序列

//动态规划的重要思想就是将整体问题划分为子问题

当s1的第i个字母与s2的第j个字母一样时,我们原本要求的s1中的前i个字母和s2中的前j个字母/有多少个最长公共子序列的问题(即求dp/[i]/[j])便转化为了求dp/[i-1]/[j-1]

当它们不一样时,我们便可在dp/[i-1]/[j]和dp/[i]/[j-1]中取最大值

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 2e2 + 5;
int dp[N][N];
string s1,s2;
void solve(){
    while(cin>>s1>>s2){
        s1=" "+s1;
        s2=" "+s2;
        int len1=s1.length();
        int len2=s2.length();
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<len1;i++){
            for(int j=1;j<len2;j++){
                if(s1[i]==s2[j]){
                    dp[i][j] = dp[i-1][j-1] + 1; 
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 
                }
            }
        }
        cout<<dp[len1-1][len2-1]<<endl;
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

12.差分

P5026 Lycanthropy - 洛谷
等差数列差分

[!NOTE]

1
在arr[l]+=s,arr[l+1]+=(d-s),arr[r+1]-=(d+e),arr[r+2]+=e;

两轮叠加:

第一轮s d d d d d d -e 0 0

第二轮s s+d s+2d s+3d s+4d s+5d s+6d 0 0 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
45
46
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5,OFFSET=30005;
//OFFSET解决了对下标可能为负数的讨论
int arr[N+OFFSET*2];
void setArr(int l,int r,int s,int d,int e){
    arr[l+OFFSET]+=s;
    arr[l+1+OFFSET]+=d-s;
    arr[r+1+OFFSET]-=(e+d);
    arr[r+2+OFFSET]+=e;
}
void solve(){
    int n,m;
    cin>>n>>m;
    while(n--){
        int v,x;
        cin>>v>>x;
        setArr(x-3*v+1,x-2*v,1,1,v);
        setArr(x-2*v+1,x,v-1,-1,-v);
        setArr(x+1,x+2*v,-v+1,1,v);
        setArr(x+2*v+1,x+3*v,v-1,-1,0);
    }
    //等差数列差分需进行二次叠加
    for(int i=1;i<=m+OFFSET;i++){
        arr[i]+=arr[i-1];
    }
    for(int i=1;i<=m+OFFSET;i++){
        arr[i]+=arr[i-1];
    }
    for(int i=1+OFFSET;i<=m+OFFSET;i++){
        cout<<arr[i]<<' ';
    }

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

问题:
1
2
3
4
5
6
7
8
9
//为啥这样改不对    
while(n--){
        int v,x;
        cin>>v>>x;
        setArr(x-3*v,x-2*v,0,1,v);
        setArr(x-2*v,x,v,-1,-v);
        setArr(x,x+2*v,-v,1,v);
        setArr(x+2*v,x+3*v,v,-1,0);
    }

13.堆结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//插入并构建大根堆(向上调整)
void heapInsert(int i){
    while(arr[i]>arr[(i-1)/2]){
        swap(arr[i],arr[(i-1)/2]);
        i=(i-1)/2;
    }
}

//i位置的数变小了,需维持大根堆结构,向下调整大根堆(向下调整)
//当前堆的大小为size
void heapify(int i,int size){
    int l=2*i+1;
    while(l<size){
        int best=(l+1<size&&arr[l+1]>arr[l])?(l+1):l;
        best=arr[i]>arr[best]?i:best;
        if(best==i)break;
        swap(arr[i],arr[best]);
        i=best;
        l=2*i+1;
    }
}
堆排序
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
void heapInsert(int i){
    while(arr[i]>arr[(i-1)/2]){
        swap(arr[i],arr[(i-1)/2]);
        i=(i-1)/2;
    }
}

//i位置的数变小了,需维持大根堆结构,向下调整大根堆(向下调整)
//当前堆的大小为size
void heapify(int i,int size){
    int l=2*i+1;
    while(l<size){
        int best=(l+1<size&&arr[l+1]>arr[l])?(l+1):l;
        best=arr[i]>arr[best]?i:best;
        if(best==i)break;
        swap(arr[i],arr[best]);
        i=best;
        l=2*i+1;
    }
}

void heapSort(){
    int n=10;//堆的大小
    for(int i=0;i<n;i++){
        heapInsert(i);
    }
    int size=n;
    while(size>1){
        swap(arr[0],arr[--size]);
        heapify(0,size);
    }
}

14.二叉树

1.二叉树的层序遍历
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
TreeNode* q[2100];
vector<int>arr;
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root!=nullptr){
            int l=0,r=0;
            q[r++]=root;
            while(l<r){
                int size=r-l;//r-l
                while(size--){
                    TreeNode* x=q[l++];
                    if(x==nullptr)continue;
                    arr.push_back((x->val));
                    if(x->left!=nullptr){
                        q[r++]=x->left;
                    }
                    if(x->right!=nullptr){
                        q[r++]=x->right;
                    }
                }
                ans.push_back(arr);
                arr.clear();
            }
        }
        return ans;
    }
    
};
2.二叉树的锯齿形层序遍历
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
TreeNode* q[2005];
vector<int>arr;
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        if(root!=nullptr){
            int l=0,r=0;
            q[r++]=root;
            bool flag=false;
            while(l<r){
                int size=r-l,i;
                if(flag==false)i=l;
                else i=r-1;
                for(int k=1;k<=size;k++){
                    if(q[i]==nullptr)continue;
                    arr.push_back(q[i]->val);
                    if(flag)i--;
                    else i++;
                }
                while(size--){
                    TreeNode* x=q[l++];
                    if(x==nullptr)continue;
                    if(x->left!=nullptr){
                        q[r++]=x->left;
                    }
                    if(x->right!=nullptr){
                        q[r++]=x->right;
                    }
                }
                ans.push_back(arr);
                flag=!flag;
                arr.clear();
            }
        }
        return ans;
    }
};
3.二叉树的最大宽度

662. 二叉树最大宽度 - 力扣（LeetCode）

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
//可能出现很多null值导致下标极大,故用unsigned long long
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
TreeNode* nq[3005];
unsigned long long q[3005];
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long ans=0;
        if(root==nullptr)return ans;
        unsigned long long l=0,r=0;
        nq[r]=root;
        q[r++]=1;
        while(l<r){
            unsigned long long size=r-l;
            ans=max(ans,q[r-1]-q[l]+1);
            while(size--){
                TreeNode* x=nq[l];
                unsigned long long iq=q[l++];
                if(x==nullptr)continue;
                if(x->left!=nullptr){
                    nq[r]=x->left;
                    q[r++]=iq*2;
                }
                if(x->right!=nullptr){
                    nq[r]=x->right;
                    q[r++]=iq*2+1;
                }
            }
        }
        return (int)ans;
    }
};
4.二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

1
2
3
int maxDepth(TreeNode* root){
    return (root==nullptr?0:max(maxSolve(root->left),maxSolve(root->right))+1);
}
5.二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
int minDepth(TreeNode* root){
    if(root==nullptr)return 0;
    if(root->left==nullptr&&root->right==nullptr)return 1;
    int leftDepth=inf,rightDepth=inf;
    if(root->left!=nullptr){
        leftDepth=minDepth(root->left);
    }
    if(root->right!=nullptr){
        rightDepth=minDepth(root->right);
    }
    return min(leftDepth,rightDepth)+1;
}
6.知前中序遍历求后序
1
2
3
4
5
6
7
8
9
10
11
12
13
void tree(string front,string mid){
    if(front.empty())return;
    char root=front[0];
    int k=mid.find(root);
    front.erase(front.begin());
    string leftfront=front.substr(0,k);
    string rightfront=front.substr(k);
    string leftmid=mid.substr(0,k);
    string rightmid=mid.substr(k+1);
    tree(leftfront,leftmid);
    tree(rightfront,rightmid);
    cout<<root;
}
7.知后中序遍历写前序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void work(string mid,string back){
    if(back.empty())return ;
    char root=back[back.size()-1];
    int k=mid.find(root);
    back.erase(back.end()-1);
    string leftmid=mid.substr(0,k);
    string rightmid=mid.substr(k+1);
    string leftback=back.substr(0,k);
    string rightback=back.substr(k);
    cout<<root;
    work(leftmid,leftback);
    work(rightmid,rightback);
}

8.计算二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣（LeetCode）

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr)return 0;
        return f(root,1,findDepth(root,1));
    }
    int f(TreeNode* root,int level,int h){
        if(level==h)return 1;
        if(findDepth(root->right,level+1)==h){
            return (1<<(h-level))+f(root->right,level+1,h);
        }else{
            return (1<<(h-level-1))+f(root->left,level+1,h);
        }
    }
    int findDepth(TreeNode* root,int level){
        while(root){
            level++;
            root=root->left;
        }
        return level-1;
    }
};
9.二叉树的最近公共祖先
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr||root==p||root==q)return root;
        TreeNode* l=lowestCommonAncestor(root->left,p,q);
        TreeNode* r=lowestCommonAncestor(root->right,p,q);
        if(l!=nullptr&&r!=nullptr){
            return root;
        }
        if(l==nullptr&&r==nullptr){
            return nullptr;
        }
        return l==nullptr?r:l;
    }
};

//二叉搜索数的最近公共祖先
//p,q都在root这个节点之下
TreeNode* solve(TreeNode* root ,TreeNode* p,TreeNode* q){
    while(root!=p&&root!=q){
        if(min(p->val,q->val)<root->val&&max(p->val,q->val)>root->val){
            break;
        }
        root=root->val<min(p->val,q->val)?root->right:root->left;
    }
    return root;
}
10.路径总和

113. 路径总和 II - 力扣（LeetCode）

//注意回溯

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
vector<vector<int>>ans;
deque<int>q;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr)return ans;
        solve(root,targetSum,0);
        return ans;
    }
    void solve(TreeNode* root,int targetSum,int curSum){
        if(root->left==nullptr&&root->right==nullptr){
            if(root->val+curSum==targetSum){
                q.push_back(root->val);
                copy();
                q.pop_back();
            }
        }else{
            q.push_back(root->val);
            if(root->left!=nullptr){
                solve(root->left,targetSum,curSum+root->val);
            }
            if(root->right!=nullptr){
                solve(root->right,targetSum,curSum+root->val);
            }
            q.pop_back();
        }
    }
    void copy(){
        vector<int>arr;
        for(auto it:q){
            arr.push_back(it);
        }
        ans.push_back(arr);
    }
};
11.验证平衡二叉树

//flag的重要性

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
bool ans;
    bool isBalanced(TreeNode* root) {
        ans=true;
        height(root);
        return ans;
    }

    int height(TreeNode* root){
        if(!ans||root==nullptr){
            return 0;
        }
        int lh=height(root->left);
        int rh=height(root->right);
        if(abs(lh-rh)>1){
            ans=false;
        }
        return max(lh,rh)+1;
    }
};
12.验证二叉搜索树(涉及中序遍历的非递归实现)
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root==nullptr)return true;
        stack<TreeNode*>st;
        TreeNode* pre=nullptr;
        while(!st.empty()||root!=nullptr){
            if(root!=nullptr){
                st.push(root);
                root=root->left;
            }else{
                root=st.top();
                st.pop();
                if(pre!=nullptr&&pre->val>=root->val){
                    return false;
                }
                pre=root;
                root=root->right;
            }
        }
        return true;
    }
};


//记录左子树的最大最小值和右子树的最大最小值,中间的值要大于左子树的最大值,要小于右子树的最小值
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
long long Max,Min;
const long long MMAX=3000000000,MMIN=-3000000000;
    bool isValidBST(TreeNode* root) {
        if(root==nullptr){
            Max=MMIN;
            Min=MMAX;
            return true;
        }
        bool lok=isValidBST(root->left);
        long long lmax=Max;
        long long lmin=Min;
        bool rok=isValidBST(root->right);
        long long rmax=Max;
        long long rmin=Min;
        Max=max(max(lmax,rmax),(long long)(root->val));
        Min=min(min(lmin,rmin),(long long)(root->val));
        return lok&&rok&&(lmax<(long long)(root->val))&&((long long)(root->val)<rmin);
    }
};
13.修剪搜索二叉树（递归)

669. 修剪二叉搜索树 - 力扣（LeetCode）

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root==nullptr)return nullptr;
        if(root->val<low){
            return trimBST(root->right,low,high);
        }
        if(root->val>high){
            return trimBST(root->left,low,high);
        }
        root->left=trimBST(root->left,low,high);
        root->right=trimBST(root->right,low,high);
        return root;
    }
};
14.打家劫舍iii

337. 打家劫舍 III - 力扣（LeetCode）

//yes代表偷子节点,no代表不投子节点

//y代表偷当前子节点,n代表不投当前子节点

//很像dp了

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
int yes,no;
    int rob(TreeNode* root) {
        f(root);
        return max(yes,no);
    }
    void f(TreeNode* root){
        if(root==nullptr){
            yes=0;
            no=0;
        }else{
            int y=root->val;
            int n=0;
            f(root->left);
            y+=no;
            n+=max(yes,no);
            f(root->right);
            y+=no;
            n+=max(yes,no);
            yes=y;
            no=n;
        }
    }
};

15.树状数组

[P3605 USACO17JAN] Promotion Counting P - 洛谷未解决

树状数组理解

应用:(可求逆序对数)

每个下标a管的范围:其二进制最右侧的1变为0,然后加1,变为b

[b,a];

//[前缀树状数组]单点增加,范围查询(前缀)

//t[i]代表具有一定规律的某一范围的和

1
2
3
4
5
6
7
8
9
10
11
12
int lowbit(int x) {
    return x & -x;
}
void update(int k, int x) {
    for(int i = k; i <= n; i += lowbit(i)) t[i] += x;
}
//1~k范围求和
int getprefix(int k) {
    int res = 0;
    for(int i = k; i > 0; i -= lowbit(i)) res += t[i];
    return res;
}
1.

[P1966 NOIP 2013 提高组] 火柴排队 - 洛谷

第一次错是因为结果忘记取模

//疑问如果高度有相同的会不会影响结果,样例是没有这部分测试的或许

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5,mod=1e8-3;
struct node{
    int val,id;
} a[N],b[N];
bool cmp(node x,node y){
    return x.val<y.val;
}
int c1[N];
int c2[N];
int c3[N];
int t[N],n;
//树状数组模版
int lowbit(int x){
    return x&(-x);
}
void update(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i)){
        t[i]+=y;
    }
}
int query(int x){
    int res = 0;
    for(int i=x;i>0;i-=lowbit(i)){
        res=(res%mod+t[i]%mod)%mod;
    }
    return res;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].val;
        a[i].id=i;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i].val;
        b[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    //1342
    //1234(开始时从1到n,上下两列都是)
    //1724
    
    //转换参照物
    //1423(排序后)
    //1342(排序后)(1234)
    
    //上列查1得1,查2得3,查3得4,查4得2
    //1342
    //1423
    //得到原排序顺序
    
    //1423对应1234,查1342所对应的
    //1342(1423)
    //1423(1234)
    
    //得到1423
    //相对于1234
    
    //求1423的逆序对即可
    //证明略,猜的
    for(int i=1;i<=n;i++){
        c1[a[i].id]=i;
        c2[b[i].id]=i;
    }
    for(int i=1;i<=n;i++){
        c3[c2[i]]=i;
    }
    for(int i=1;i<=n;i++){
        c2[i]=c3[c1[i]];
    }
    
    int res=0;
    for(int i=1;i<=n;i++){
        update(c2[i],1);
        res=((res%mod+query(n)%mod)%mod+(-query(c2[i])%mod+mod)%mod)%mod;
    }
    cout<<res<<endl;

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}
//[差分树状数组]范围增加,单点查询,利用差分数组(差分)

//t[i]代表某一范围的差分和

//求和可得某一位置的数

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int n,t[N],arr[N];
int lowbit(int x){
    return x&(-x);
}
void update(int x,int val){
    for(int i=x;i<=n;i+=lowbit(i))t[i]+=val;
}
int query(int x){
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))ans+=t[i];
    return ans;
}
void solve(){
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=1;i<=n;i++){
        update(i,arr[i]-arr[i-1]);
    }
    while(m--){
        int op,x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            update(x,k);
            update(y+1,-k);
        }
        else{
            cin>>x;
            cout<<query(x)<<endl;
        }
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	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
void build(int s, int t, int p) {
  if (s == t) {
    d[p] = a[s];
    return;
  }
  int m = s + ((t - s) >> 1);
  build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[(p * 2) + 1];
}

void pushdown(int s, int e, int o) {
    if (lz[o]) {
        int mid = (s + e) / 2;
        t[o * 2] += (mid - s + 1) * lz[o];
        t[o * 2 + 1] += (e - mid) * lz[o];
        lz[o * 2] += lz[o];
        lz[o * 2 + 1] += lz[o];
        lz[o] = 0;
    }
}

void update(int l, int r, int v, int s, int e, int o) {
    if (l <= s && r >= e) {
        t[o] += (e - s + 1) * v;
        lz[o] += v;
        return;
    }
    pushdown(s, e, o);
    int mid = (s + e) / 2;
    if (l <= mid) update(l, r, v, s, mid, o * 2);
    if (r > mid) update(l, r, v, mid + 1, e, o * 2 + 1);
    pushup(o);
}


int getsum(int l, int r, int s, int t, int p) {
  if (l <= s && t <= r)
    return d[p]; 
  pushdown(s,t,p);
  int m = s + ((t - s) >> 1), sum = 0;
  if (l <= m) sum += getsum(l, r, s, m, p * 2);
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  return sum;
}

可持久化线段树

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
void build(int& x, int l, int r)
{
    x = ++idx;
    if (l == r)return;
    int mid = (l + r) >> 1;
    build(lc(x), l, mid);
    build(rc(x), mid + 1, r);
}
void update(int pre, int& o, int l, int r, int v)
{
    o = ++idx;
    t[o] = t[pre];
    t[o].val++;
    if (l == r)return;
    int mid = (l + r) >> 1;
    if (v <= mid)
        update(lc(pre), lc(o), l, mid, v);
    else
        update(rc(pre), rc(o), mid + 1, r, v);
}
int query(int x, int y, int l, int r, int k)
{
    if (l == r)return l;
    int mid = (l + r) >> 1;
    int s = t[lc(y)].val - t[lc(x)].val;
    if (k <= s)
        return query(lc(x), lc(y), l, mid, k);
    else
        return query(rc(x), rc(y), mid + 1, r, k - s);
}

欧拉筛

如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 𝑂(𝑛)O(data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void euler(int n) {
    vector<int> primes;
    bool vis[n + 1] = {false};  // 初始化vis数组，默认所有数都是质数候选
    vis[0] = vis[1] = true;     // 0和1不是质数
 
    for (int i = 2; i <= n; ++i) {
        // 如果i没有被筛除，说明i是质数，存入vector中
        if (!vis[i]) {
            primes.push_back(i);
        }
        // 注意枚举条件，i * primes[j]表示要被筛除的数字（一定不是质数）
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            vis[i * primes[j]] = true;
            // 如果i能被primes[j]整除，说明primes[j+1]已经不是i * primes[j+1]的最小质因子了
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
}

Kruskal算法

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
struct Edge {
    int x, y, c;
    bool operator< (const Edge &u) const {
        return c < u.c;
    }
};

int pre[N];

int root(int x) {
    return pre[x] == x ? x : root(pre[x]);
}

void solve() {
    int n, m; cin >> n >> m;
    vector<Edge> es;
    for(int i = 1; i <= m; ++ i) {
        int x, y, c; cin >> x >> y >> c;
        es.push_back({x, y, c});
    }
    sort(es.begin(), es.end());
    for(int i = 1; i <= n; ++ i) pre[i] = i;
    int ans = 0;
    for(const auto& [x, y, c] : es) {
        if(root(x) == root(y)) continue;
        ans = max(ans, c);
        pre[root(x)] = root(y);
    }
    cout << ans << '\n';
}

Prim算法

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
struct Edge {
    ll x, c;
    bool operator< (const Edge &u) const {
        return c == u.c ? x > u.x : c < u.c;
    }
};

vector<Edge> g[N];

ll d[N];
int n, m;

int prim() {
    priority_queue<Edge> pq;
    bitset<N> vis;
    d[1] = 0;
    pq.push({1, d[1]});
    ll res = 0;
    while(pq.size()) {
        int x = pq.top().x; pq.pop();
        if(vis[x]) continue;
        vis[x] = true;

        res = max(res, d[x]);

        for(const auto &[y, w] : g[x]) {
            if(!vis[y]) {
                d[y] = min(d[y], w);
                pq.push({y, d[y]});
            }
        }
    }
    return res;
}

16.链表

[!NOTE]

写链表的题是要特别注意非空判断,避免空指针异常

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
//https://www.luogu.com.cn/problem/P1996
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
void solve(){
    int n,m;
    cin>>n>>m;
    ListNode* head=new ListNode(1);
    ListNode* p=head;
    for(int i=2;i<=n;i++){
        p->next=new ListNode(i);
        p=p->next;
    }
    p->next=head;//成环

    int num=n;//记录总共的节点个数

    p=head;
    ListNode* pre=p;//记录前一个节点,用于删除节点

    while(num){
        //保证p要不为空
        for(int i=1;i<=m-1&&p!=nullptr;i++){
            pre=p;
            p=p->next;
        }
        if(p==nullptr) break;
        cout<<p->val<<" ";
        pre->next=p->next;
        delete p;//删除节点
        p=pre->next;//把p指向下一个节点
        num--;
    }

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

//双重循环会超时(1e5*1e5),但一般看到这个我们还会想到一种方法,那就是对应数值索引

//这道题的思路很简单,就是的注意非空判断,以及更改的先后顺序

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5;
struct ListNode{
    int val;
    ListNode *next,*pre;
    ListNode():val(0),next(nullptr){}
    ListNode(int x):val(x),next(nullptr){}
}arr[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        arr[i].val=i;
    }
    for(int i=2;i<=n;i++){
        int k,p;
        cin>>k>>p;
        if(p==1){
            //arr[k].next依赖与arr[k],故需要将arr[k].next保存起来,才可修改arr[k].next->pre
            //插后面,先管后,再管前
            arr[i].next=arr[k].next;
            if(arr[k].next!=nullptr)arr[k].next->pre=&(arr[i]);
            arr[k].next=&(arr[i]);
            arr[i].pre=&(arr[k]);
        }else{
            //插前面,先管前,再管后
            arr[i].pre=arr[k].pre;
            if(arr[k].pre!=nullptr)arr[k].pre->next=&(arr[i]);
            arr[i].next=&(arr[k]);
            arr[k].pre=&(arr[i]);
        }

    }
    int m;
    cin>>m;
    while(m--){
        int x;
        cin>>x;
        if(arr[x].val==0)continue;
        arr[x].val=0;
        if(arr[x].pre!=nullptr)arr[x].pre->next=arr[x].next;
        if(arr[x].next!=nullptr)arr[x].next->pre=arr[x].pre;
        arr[x].pre=nullptr;
        arr[x].next=nullptr;
    }
    int mark=0;
    for(int i=1;i<=n;i++){
        if(arr[i].pre==nullptr&&arr[i].next!=nullptr){
            mark=i;
            break;
        }
    }
    ListNode *head=&(arr[mark]);
    while(head){
        cout<<head->val<<" ";
        head=head->next;
    }

}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

17.打表

构造题就打表

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 long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int n;
int vis[N];
deque<int>ans;
int cnt;//通过cnt使得答案只输出一次

void dfs(int dep,int sum){
    if(dep==n&&cnt==0){//设置结束条件
        cnt++;
        for(auto x:ans){
            cout<<x<<" ";
        }
        cout<<endl;
        return ;
    }
    for(int i=0;i<=n-1;i++){
        if(vis[i])continue;
        if(!(sum^i))continue;
        vis[i]=1;
        ans.push_back(i);
        dfs(dep+1,sum^i);
        vis[i]=0;
        ans.pop_back();//回退vis以及ans
    }
}
void solve(){
    cnt=0;
    cin>>n;
    dfs(0,0);
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	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
45
46
//https://codeforces.com/gym/105386/problem/G
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int a[N];
void solve(){
    int n;
    cin>>n;
    if(n%4==0||n==1){
        cout<<"impossible\n";
        return ;
    }
    if(n==2){
        cout<<"1 0\n";
        return;
    }
    if(n==3){
        cout<<"1 0 2\n";
        return ;
    }
    a[0]=1;
    a[1]=0;
    a[2]=2;
    for(int i=3;i<n;i++){
        a[i]=i;
        if(i%4==0){
            swap(a[i-1],a[i]);
        }
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<' ';
    }
    cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

18.唯一分解定理

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
for (int i = 2; i <= x / i; ++i) {
        // 如果不能整除直接跳过
        if (x % i) continue;
        
        // 如果可以整除，那么必然是一个质因子（从小到大枚举的特性决定）
        int cnt = 0;
        // 一直除，直到除干净
        while (x % i == 0) cnt++, x /= i;
        v.push_back({i, cnt});
    }
    
    // 如果x大于1，说明x本身就是一个质数
    if (x > 1) v.push_back({x, 1});
    
    // 输出所有质因数及其对应的指数
    for (const auto& i : v) cout << i.first << ' ' << i.second << '\n'; 




因数个数的寻找与一些数学谜题息息相关。现在小编为大家分享一下自我研究出的通过分解质因数寻找因数个数的方法。

首先讲一个数分解质因数，如果有相同的质因数就整理成幂次方的形式。将结果的指数加一，再将此结果相乘得到其因数个数。

举例：72，用列举法不易找出其因数个数。而72＝2×2×2×3×3＝2³×3²，分别将指数3,2加一变成4,3，4×3＝12个。列举证明1,2,3,4,6,8,9,12,18,24,36,72共12个因数。

19.搜索

[P1219 USACO1.5] 八皇后 Checker Challenge - 洛谷

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
//无敌暴力,遗憾超时
//用brr来辅助进行对角线是否有相同元素的查询
//第一次brr辅助查询右下角是否有重叠
//第二次brr辅助查询左下角是否有重叠
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int arr[15][15],brr[15][15],n,ans;
deque<int>st;
bool check(){
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      brr[i][j]=arr[i][j];
    }
  }
  for(int i=1;i<=n;i++){
    int sum=0;
    for(int j=1;j<=n;j++){
      sum+=brr[j][i];
    }
    if(sum!=1)return false;
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(brr[i][j]==1){
        if(i+1>n||j+1>n){continue;}
        if(brr[i+1][j+1]==1){
          return false;
        }
        brr[i+1][j+1]=1;
      }
    }
  }
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        brr[i][j]=arr[i][j];
      }
    }

    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        if(brr[i][j]==1){
          if(i+1>n||j-1<1){continue;}
          if(brr[i+1][j-1]==1){
            return false;
          }
          brr[i+1][j-1]=1;
      }
    }
  }
  return true;
}
void dfs(int x, int y){
    if(x==n){
      if(check()){
        ans++;
        if(ans>3)return ;
        for(auto it:st){
          cout<<it<<" ";
        }
        cout<<'\n';
      }
      return ;
    }
    for(int i=1;i<=n;i++){
      arr[x+1][i]=1;
      st.push_back(i);
      dfs(x+1,i);
      arr[x+1][i]=0;
      st.pop_back();
    }
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
      arr[1][i]=1;
      st.push_back(i);
      dfs(1,i);
      arr[1][i]=0;
      st.pop_back();
    }
    cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

直接用vis1和vis2对斜对角线上的元素是否有重叠进行标记

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int arr[15][15],brr[15][15],n,ans;
deque<int>st;
int vis[15],vis1[35],vis2[35];
void dfs(int x, int y){
    if(x==n){
        ans++;
        if(ans>3)return ;
        for(auto it:st){
          cout<<it<<" ";
        }
        cout<<'\n';
      return ;
    }
    
    for(int i=1;i<=n;i++){
      if(vis[i]){continue;}
      if(vis1[i-(x+1)+n]){continue;}
      if(vis2[i+x+1]){continue;}
      arr[x+1][i]=1;
      vis[i]=1;
      vis1[i-(x+1)+n]=1;
      vis2[i+x+1]=1;
      st.push_back(i);
      dfs(x+1,i);
      arr[x+1][i]=0;
      vis[i]=0;
      st.pop_back();
      vis1[i-(x+1)+n]=0;
      vis2[i+x+1]=0;
    }
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
      arr[1][i]=1;
      vis[i]=1;
      st.push_back(i);
      vis1[i-1+n]=1;
      vis2[i+1]=1;
      dfs(1,i);
      arr[1][i]=0;
      st.pop_back();
      vis[i]=0;
      vis1[i-1+n]=0;
      vis2[i+1]=0;
    }
    cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

math

位运算

[P5657 CSP-S2019] 格雷码 - 洛谷

打表找规律

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
vector<string> digui(int n){
    if(n==1){
        vector<string>ans;
        ans.push_back("0");
        ans.push_back("1");
        return ans;
    }
    vector<string>temp;
    temp=digui(n-1);
    vector<string>res;
    for(int i=0;i<temp.size();i++){
        res.push_back("0"+temp[i]);
    }
    for(int i=temp.size()-1;i>=0;i--){
        res.push_back("1"+temp[i]);
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    vector<string>ans=digui(n);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<' ';
    }
    cout<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

这道题很明显是有蹊跷的,数据范围过大。

但是让我找规律我未必能发现

但仔细思考一下,位数高达64位,我们不可能生成所有数再查询,所以只可能是每一个数的每位是0还是1有规律可寻,所以我们自然而然的去关注打表后每一个数的每一位是否呈现某种规律

规律:

倒数第n位就是 2^(n−1) 个 0 , 2^(n−1) 个 1 , 2^(n−1) 个 1 , 2^(n−1) 个 0 循环

位数高达64,得用unsigned long long

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
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int ans[64];
int num[]={0,1,1,0};
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=n-1;i>0;i--){
        cout<<num[(k/((int)(1)<<i))%4];
    }
    cout<<num[k%4]<<endl;//最后要单独输出，否则会出现inf
    //若这里不单独输出,当i等于0时,进行i--操作后,i会变成unsigned long long 所能表示的最大整数(18446744073709551615),使得循环无法结束,故需特殊处理
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

第k个格雷码=k^(k>>1)

我们再输出每一位即可

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
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int num[]={0,1,1,0};
void solve(){
    int n,k;
    cin>>n>>k;
    k=k^(k>>1);
    while(n){
        n--;
        if(k==-1) break;
        cout<<((k>>n)&1);
    }
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

[P5514 MtOI2019] 永夜的报应 - 洛谷

a最大可达1e9则我们设置a的二进制最大有32位,统计每一个a的每一位是否为1,

cnt[i]代表i位为1的a的个数,若该位的1为奇数个,则无论如何组合该位都会留下,其他位同理,我们最后只需对留下的1乘以他们所对应的位权即可

从以上推出更简单的结果所得公式ans=0;ans^=a;cout<<ans;

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 long long
const int inf=0x3f3f3f3f,N = 1e6 + 5;
int cnt[35];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        for(int j=31;j>=0;j--){
            cnt[j]+=((a>>j)&1);
        }
    }
    int ans=0;
    for(int i=31;i>=0;i--){
        if(cnt[i]%2==1)
        ans+=(1<<i);
    }
    cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

P5539 【XR-3】Unknown Mother-Goose - 洛谷(bitset优化)

题目要求的是把 S 集合中所有的数的倍数标记之后，连续 3 个都被标记的位置的数量(这步采用位运算,非常巧妙。)

  • bs 数组：用二进制位标记数字是否被选中。unsigned long long 是 64 位，因此 bs[k] 对应数字 k*64 ~ (k+1)*64-1，其中第 b 位（0≤b<64）为 1 表示数字 k*64 + b 被标记。
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
#include<bits/stdc++.h>
#define N 1000000003
#define reg register
using namespace std;

unsigned long long bs[(N>>6)+10];
unsigned long long tmp[65];
int n,m,s,l,ans;

//统计1的个数,即连续3个都被标记的位置的数量
inline int count(unsigned long long x){
    reg int res = 0;
    while(x){
        res += x&1;
        x >>= 1;
    }
    return res;
}

int main(){
    cin>>n>>s;
    m = (n>>6)+1;
    while(s--){
        cin>>l;
        if(l<64){ //两种情况判一下,保证加入的复杂度是 n/w
            memset(tmp,0,sizeof(tmp));
            for(reg int i=0;i<(l<<6);i+=l)
                tmp[i>>6] |= 1ull<<(i&63); //加入的数比较小,开另一个数组,作为重复单元,i&63相当于i%64
            for(reg int i=0;i<=m;i+=l)
            for(reg int j=0;j<l;++j)
                bs[i+j] |= tmp[j];    
        }else{
            for(reg int i=0;i<=n;i+=l)
                bs[i>>6] |= 1ull<<(i&63);
        }
    }
    --m;
    if((n&63)!=63) bs[m] &= (1ull<<(n+1-(m<<6)))-1; //特判一下最后一块
    bs[0] &= -2ull; //除去第 0 项,-2的补码为11111111110
    //连续的出现在同一块中
    for(reg int i=0;i<=m;++i) ans += count(bs[i]&(bs[i]<<1)&(bs[i]<<2));
    //连续的出现在不同块中,有两种情况
    //x = (i-1)*64 + 62，x+1 = (i-1)*64 + 63，x+2 = i*64 + 0
    //x = (i-1)*64 + 63，x+1 = i*64 + 0，x+2 = i*64 + 1
    for(reg int i=1;i<=m;++i) ans += count(bs[i]&(bs[i-1]>>62)&((bs[i-1]>>63)|(bs[i]<<1)));
    cout<<ans;
    return 0;
}

素数

Miller Rabin(高精度素数判定)
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
bool millerRabin(int n) {
  if (n < 3 || n % 2 == 0) return n == 2;
  if (n % 3 == 0) return n == 3;
  int u = n - 1, t = 0;
  while (u % 2 == 0) u /= 2, ++t;
  // test_time 为测试次数，建议设为不小于 8
  // 的整数以保证正确率，但也不宜过大，否则会影响效率
  for (int i = 0; i < test_time; ++i) {
    // 0, 1, n-1 可以直接通过测试, a 取值范围 [2, n-2]
    int a = rand() % (n - 3) + 2, v = quickPow(a, u, n);
    if (v == 1) continue;
    int s;
    for (s = 0; s < t; ++s) {
      if (v == n - 1) break;  // 得到平凡平方根 n-1，通过此轮测试
      v = (long long)v * v % n;
    }
    // 如果找到了非平凡平方根，则会由于无法提前 break; 而运行到 s == t
    // 如果 Fermat 素性测试无法通过，则一直运行到 s == t 前 v 都不会等于 -1
    if (s == t) return 0;
  }
  return 1;
}



完整版:
ll bmul(ll a, ll b, ll m) {  // 快速乘
  ull c = (ull)a * (ull)b - (ull)((long double)a / m * b + 0.5L) * (ull)m;
  if (c < (ull)m) return c;
  return c + m;
}

ll qpow(ll x, ll p, ll mod) {  // 快速幂
  ll ans = 1;
  while (p) {
    if (p & 1) ans = bmul(ans, x, mod);
    x = bmul(x, x, mod);
    p >>= 1;
  }
  return ans;
}

bool Miller_Rabin(ll p) {  // 判断素数
  if (p < 2) return false;
  if (p == 2) return true;
  if (p == 3) return true;
  ll d = p - 1, r = 0;
  while (!(d & 1)) ++r, d >>= 1;  // 将d处理为奇数
  for (ll k = 0; k < 10; ++k) {
    ll a = rand() % (p - 2) + 2;
    ll x = qpow(a, d, p);
    if (x == 1 || x == p - 1) continue;
    for (int i = 0; i < r - 1; ++i) {
      x = bmul(x, x, p);
      if (x == p - 1) break;
    }
    if (x != p - 1) return false;
  }
  return true;
}

P5535 【XR-3】小道消息 - 洛谷

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
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
using ull=unsigned long long;
const int inf=0x3f3f3f3f,N = 1e6 + 5;
ll bmul(ll a, ll b, ll m) {  // 快速乘
  ull c = (ull)a * (ull)b - (ull)((long double)a / m * b + 0.5L) * (ull)m;
  if (c < (ull)m) return c;
  return c + m;
}

ll qpow(ll x, ll p, ll mod) {  // 快速幂
  ll ans = 1;
  while (p) {
    if (p & 1) ans = bmul(ans, x, mod);
    x = bmul(x, x, mod);
    p >>= 1;
  }
  return ans;
}

bool Miller_Rabin(ll p) {  // 判断素数
  if (p < 2) return false;
  if (p == 2) return true;
  if (p == 3) return true;
  ll d = p - 1, r = 0;
  while (!(d & 1)) ++r, d >>= 1;  // 将d处理为奇数
  for (ll k = 0; k < 10; ++k) {
    ll a = rand() % (p - 2) + 2;
    ll x = qpow(a, d, p);
    if (x == 1 || x == p - 1) continue;
    for (int i = 0; i < r - 1; ++i) {
      x = bmul(x, x, p);
      if (x == p - 1) break;
    }
    if (x != p - 1) return false;
  }
  return true;
}
void solve(){
    ll n,k;
    cin>>n>>k;
    n=n+1;
    k=k+1;
    //对n和k进行处理,使得n变成最大标号,k变成其对应的标号
    if(Miller_Rabin(k)){
        //若k为质数
        
        //对于存在其倍数的,需第二天其他质数标记
        if(n/k>1){
            cout<<"2\n";
        }else{
        //对于不存在其倍数的,因其是质数,与其他的剩余的数均是互质的
            cout<<"1\n";
        }
    }else{
        //如果k是合数,则其很明显不能标记它的质因子,需第二天其他质数来标记
        cout<<"2\n";
    }
   
    
    
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}
质因数分解(最朴素的算法)
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> result;
void breakdown(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            while(n%i==0)n/=i;
            result.push_back(i);
        }
    }
    if(n!=1){
        result.push_back(n);
    }
}
Pollard_Rho算法(找到数x的一个平凡因子)以下配合找到数x的最大质因子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ll max_factor, n;
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
ll Pollard_Rho(ll x) {
  ll s = 0, t = 0;
  ll c = (ll)rand() % (x - 1) + 1;
  int step = 0, goal = 1;
  ll val = 1;
  for (goal = 1;; goal *= 2, s = t, val = 1) {  // 倍增优化
    for (step = 1; step <= goal; ++step) {
      t = (bmul(t, t, x) + c) % x;
      val = bmul(val, abs(t - s), x);
      if ((step % 127) == 0) {
        ll d = gcd(val, x);
        if (d > 1) return d;
      }
    }
    ll d = gcd(val, x);
    if (d > 1) return d;
  }
}

数学期望

[P8774 蓝桥杯 2022 省 A] 爬树的甲壳虫 - 洛谷

期望题

image-20251125175550370

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f,N = 1e5 + 5,mod=998244353;
int f[N];
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        f[i]=((f[i-1]+1)%mod*((y%mod)*quick(y-x,mod-2)%mod)%mod)%mod;
    }
    cout<<f[n]<<endl;
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}

AtCoder Link

AT_abc360_e Random Swaps of Balls - 洛谷

image-20251125183107676

注意减法的同余原理

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 long long
const int inf=0x3f3f3f3f,N = 1e5 + 5,mod=998244353;
int f[N];
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
void solve(){
    int n,k;
    cin>>n>>k;
    f[0]=1;
    for(int i=1;i<=k;i++){
        f[i]=(f[i-1]*((n-1)*(n-1)%mod+1)%mod*quick(n*n%mod,mod-2)%mod+(2*quick(n*n%mod,mod-2)*(n*(n+1)/2%mod-f[i-1]%mod+mod)%mod)%mod)%mod;
    }
    cout<<f[k]<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
	return 0;
}