TODO 还没学明白 TEX 公式格式导出到博客时还要更改
[mathjax]
分治专题
1 快速幂 AC
将指数变成二进制数字,分别求每个 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
|
#include <cstdio>
typedef long long LL;
int to2(LL k,int result[]){
int count = 0;
while(k > 0){
result[count] = k % 2;
k >>= 1; // 向右移位
count ++;
}
return count;
}
int main(){
LL b,p,k;
int midres[32] = {};
scanf("%lld %lld %lld",&b,&p,&k);
LL finalres = 1;
int count = to2(p,midres);
LL num[32] = {b%k};
for(int i = 1;i<count;i++){
num[i] = num[i-1] * num[i-1] % k;
// printf("%d-%lld ",i,num[i]);
}
for(int i = 0;i<count;i++){
if(midres[i] == 1) {
finalres *= num[i];
finalres %= k;
}
}
// 最后需要再 %k 否则 84分 (反例:2 0 1)
printf("%lld^%lld mod %lld=%lld\n",b,p,k,finalres %k);
return 0;
}
|
看了大佬题解发现,自己很多空间都是多余的。最后只要一个计数的答案,因此中间结果并不需要记录下来:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 大佬题解
#include <bits/stdc++.h>
using namespace std;
int main(){
long long ans=1,i,j,k,m,n,b,p;
scanf("%lld%lld%lld",&b,&m,&p);
printf("%lld^%lld mod %lld=",b,m,p);
while(m>0){
if(m%2==1)
ans=ans*b%p;
b=b*b%p;
m=m>>1;
}
printf("%lld",ans%p);
return 0;
}
|
2 幂次方 AC
分治,递归,主要是括号格式问题
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
|
# include <cstdio>
int mi[15] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};// 这里直接偷懒了
void devide(int n){
if(n == 2)printf("2");
else if (n == 4)printf("2(2)");
else{
int sgn = 0,never = 0;
for(int i = 14;i>=0;i--){
if (n >= mi[i] && n > 3){
if (sgn != 0)printf("+");
printf("2(");
devide(i);
printf(")");
n -= mi[i];
sgn ++;
}else if (n == 3){
if (sgn != 0)printf("+");
printf("2+2(0)");
n = 0;
sgn ++;
}else if (n == 2){
if (sgn == 0)printf("(2)");
else printf("+2");
n = 0;
sgn ++;
}else if (n == 1){
if(sgn > 0 && never == 0){
printf("+2(0)");
never = 1;
}
}
}
}
}
int main(){
int n;
scanf("%d",&n);
devide(n);
return 0;
}
|
对于这道题,一开始的几个不需要括号的我单独列出来了,而大佬救是不同凡响,一句话解决
大佬题解
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include<bits/stdc++.h>
using namespace std;
string run(int x,int i=0,string s=string("")){
if(x==0)return string("0");
do if(x&1)s=(i==1?"2":"2("+run(i)+")")+(s==""?"":"+")+s;//拼接字符串,应题意,要把低次方接在后面
while(++i,x>>=1);//每次向右移位
return s;
}
int main(){
int x;cin>>x;
cout<<run(x)<<endl;
}
|
3 逆序对
线段树 # TODO
· 在数组表示🌲的时候,通常左孩子 2*v
在代码中写成 v<<1
;右孩子 2*v+1
写成 v<<1|1
4 画图
杨辉三角是真的秀。 常规方法:建一个 1024 * 2048 的 char 矩阵,将图腾先倒置处理,最后倒序输出。
递归专题
1 台阶问题 AC
# TEX 最原始的思路是 $(a_n = a_{n-1} + … + a_{n-k})$ 代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# include <cstdio>
int n,k,solution[100001] = {1};
int main(){
scanf("%d%d",&n,&k);
for(int i = 1;i<=n;i++){
for(int j = i-k;j<i;j++){
if(j >= 0)
solution[i]=(solution[i] + solution[j])%100003;
}
}
// for(int i = 0;i<=n;i++){
// printf("%d ",solution[i]);
// }
printf("%d",solution[n]);
}
|
大佬的高级方法:
- 高级递归 O( n ) : ( a_n = 2 * a_{n-1} – a_{i-k-1} )
- 矩阵乘法 O( n * logk ):设 n = 4,
$$\begin{matrix} let \quad A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{bmatrix} &
B = \begin{bmatrix} a_n \\ a_{n-1} \\ a_{n-2} \\ a_{n-3} \end {bmatrix}\end{matrix}$$
那么
$$\begin{matrix} B &* &A &= &\begin{bmatrix} a_{n+1} \\ a_{n} \\ a_{n-1} \\ a_{n-2} \end {bmatrix} \end{matrix}$$
所以 $( a_n = (B * A^{n-k})[1] )$ ,此处就可以使用快速幂的方法
- 树状数组 O( n * logk ):树状数组可以解决的问题都可以用线段树解决,但是树状数组的系数要少很多
2 数的划分 AC
这个题做的太奇妙了,我都还没弄懂具体细节,写了个 dfs,题目样例对了,交上去竟然一次 AC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# include <cstdio>
int n,k;
int solu(int n,int k,int min){ // min 是本次子划分最小的数字
if (n == 1 || k == 1)return 1;
if (min > n)return 0;
int solution = 0;
for(int i = min;i<=n/k;i++){
// 每个划分都是从小到大划分
solution += solu(n-i,k-1,i);
}
return solution;
}
int main(){
scanf("%d%d",&n,&k);
printf("%d",solu(n, k, 1));
}
|
看到有人用 #include <bits/stdc++.h>
,意思是包含所有的 C++ 头文件,百炼 OJ 亲测可用!然鹅本地 XCode 的 GCC 竟然不行==
3 传球游戏 AC
太爽了,又是一次 AC
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
|
# include <cstdio>
int main(){
int n,m;
scanf("%d%d",&n,&m);
int res[30][30] = {};
for(int i = 0;i<m;i++){
if(i == 0){
for(int j = 0;j<n;j++){
if (j == n-1 || j % n == 1)
res[i][j] = 1;
}
}else{
for(int j = 0;j<n;j++){
res[i][j] = res[i-1][(j+n-1)%n] + res[i-1][(j+n+1)%n];
}
}
}
// for(int i = 0;i<m;i++){
// for(int j = 0;j<n;j++){
// printf("%d ",res[i][j]);
// }
// printf("\n");
// }
printf("%d",res[m-1][0]);
return 0;
}
|
我的想法就是模拟一次次传播,看到一位大佬和我方法差不多,但是代码风格很新奇:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include<bits/stdc++.h>
using namespace std;
int n,m,f[50][50];
int main()
{
cin>>n>>m;f[0][0]=1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(f[i][j])
f[i+1][(j-1+n)%n]+=f[i][j], // 后面是‘,’可以并列语句,少大括号。
f[i+1][(j+1)%n]+=f[i][j];
cout<<f[m][0];
return 0;
}
|
4 电梯 AC
DFS,有个小错找了好久。记得一定要回溯!不然本条路线的 vis 会被其它路线影响
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 <cstdio>
# include <vector>
# define min(x,y) x<y ? x : y
using namespace std;
vector<int>graph[205];
int vis[205] = {},ans = 0X7fffffff;
void DFS(int start,int step,int end){
// printf("%d - %d -\n",start,step);
if (start == end){
ans = step;
}
if (step >= ans); // 剪枝!
else if (graph[start].size() > 0){
vis[start] = 1;
for(int i = 0;i<graph[start].size();i++){
if (vis[graph[start][i]] == 0)
DFS(graph[start][i],step+1,end);
}
vis[start] = 0; // 回溯,否则其它并行道路会受当前道路的影响而走不通
}
}
int main(){
int n,a,b;
scanf("%d %d %d",&n,&a,&b);
for(int i = 1;i<=n;i++){
int temp;
scanf("%d",&temp);
if (temp != 0){
if (i > temp)
graph[i].push_back(i - temp);
if (i + temp <= n)
graph[i].push_back(i + temp);
}
}
vis[a] = 1;
int step = 0;
DFS(a,step,b);
printf("%d",ans == 0X7fffffff?-1:ans);
return 0;
}
|
5 数字三角形 AC
这道题就是 POJ 2760,也是《引导》第十章第一题,当时做太难了,于是放弃了这本书,开始刷落谷的递归动态规划,没想到现在竟然秒杀。之前其实是粗心的错误,结点的父节点并不是 <<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
|
# include <cstdio>
# include <algorithm>
using namespace std;
const int maxn = 1000001;
int main(){
int n,tri[maxn] = {},sum[maxn] = {};
scanf("%d",&n);
scanf("%d",&tri[1]);
sum[1] = tri[1];
int count = 2;
for(int i = 2;i<=n*(n+1)/2;i++){
scanf("%d",&tri[i]);
if (i != count*(count+1)/2 &&
i-1 != count*(count+1)/2){
int father = i - count*(count-1)/2 + (count-2)*(count-1)/2;
sum[i] = tri[i] + max(sum[father-1],sum[father]);
}
else if(i == count*(count+1)/2){
int father = count*(count-1)/2;
sum[i] = tri[i] + sum[father];
}
else if(i == count*(count+1)/2 + 1){
int father = count*(count-1)/2 + 1;
sum[i] = tri[i] + sum[father];
count ++;
}
}
// // 打印和三角
// count = 1;
// printf("\n");
// for(int i = 1;i<=n*(n+1)/2;i++){
// printf("%3d ",sum[i]);
// if(i == count*(count+1)/2){
// printf("\n");
// for(int j = 0;j<(n - count);j++){
// printf(" ");
// }
// count++;
// }
// }
// // 打印原三角
// count = 1;
// printf("\n");
// for(int i = 1;i<=n*(n+1)/2;i++){
// printf("%3d ",tri[i]);
// if(i == count*(count+1)/2){
// printf("\n");
// for(int j = 0;j<(n - count);j++){
// printf(" ");
// }
// count++;
// }
// }
int maxsum = sum[n*(n-1)/2];
for(int i = n*(n-1)/2;i<=n*(n+1)/2;i++){
maxsum = maxsum > sum[i]?maxsum:sum[i];
}
printf("%d",maxsum);
return 0;
}
|
然而大佬就厉害了:用一维数组做,妙哉!
首先是边读边做,第一层循环 i 从 n 到 1,第二层循环 j 从 i 到 n(为了每次都能取到上次的值),每次读入一个变量 p,
状态转移方程:a[j] = max{a[j],a[j+1]}+p
(a[j]
表示走到第 i 层第 j 个时的最大值)。最后输出 a 数组的最大值即可。
下面我来用测试数据模拟一下 (注意:要开1002的数组,不然会越界):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
a[1] a[2] a[3] a[4] a[5] a[6]
初始化: 0 0 0 0 0 0
第一次: 0 0 0 0 7 0
第二次: 0 0 0 10 15 0
第三次: 0 0 18 16 15 0
第四次: 0 20 25 20 19 0
第五次: 24 30 27 26 24 0
|
代码(c/c++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include<cstdio>
int n,a[1002],i,j,ans,p;
int max(int &x,int &y){return x>y?x:y;}
int main(){
scanf("%d",&n);
for(i=n;i;i--)
for(j=i;j<=n;j++)
scanf("%d",&p),a[j]=max(a[j],a[j+1])+p;
for(i=1;i<=n;i++)
ans=max(ans,a[i]);
printf("%d",ans);
return 0;
}
|
一些其他的没啥用的概念:
-
register
关键字:请求编译器尽可能的将变量存在 CPU 内部寄存器中,而不是通过内存寻址访问,以提高效率。 -
inline
:用法
6 数字分段 TODO
7 丢瓶盖 TODO
这两题都是二分法
8 过河卒 AC
用DFS超时
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
|
# include <cstdio>
int m,n,x,y;
int g[21][21] = {},vis[21][21] = {},res = 0;
int a[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
bool legal(int x,int y){
if (x < 0 || y < 0 || x > m || y >n || g[x][y] || vis[x][y])return false;
return true;
}
void DFS(int i,int j){
vis[i][j] = 1;
if (i == m && j == n)res++;
else{
if (legal(i+1,j)) DFS(i+1,j);
if (legal(i,j+1)) DFS(i,j+1);
// if (legal(i-1,j)) DFS(i-1,j);
// if (legal(i,j-1)) DFS(i,j-1);
}
vis[i][j] = 0;
}
int main(){
scanf("%d %d %d %d",&m,&n,&x,&y);
g[x][y] = 1;
for (int i = 0;i<8;i++){
int nx = x+a[i][0],ny = y+a[i][1];
if (nx >= 0 && ny >= 0 && nx <= m && ny <= n)
g[nx][ny] = 1;
}
DFS(0,0);
printf("%d",res);
return 0;
}
|
递推 AC
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
|
// 2020-03-16 11:46:57
// https://www.luogu.com.cn/problem/P1002
# include <cstdio>
#include<algorithm>
using namespace std;
int m,n,x,y;
int g[30][30] = {},vis[30][30] = {},res = 0;
int a[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
unsigned long long f[30][30];
int main(){
scanf("%d %d %d %d",&m,&n,&x,&y);
g[x][y] = 1;
for (int i = 0;i<8;i++){
int nx = x+a[i][0],ny = y+a[i][1];
if (nx >= 0 && ny >= 0 && nx <= m && ny <= n)
g[nx][ny] = 1;
}
f[0][0] = 1;
for(int i = 0;i<=m;i++){
for(int j = 0;j<=n;j++){
if (g[i][j])continue;
f[i][j] = max(f[i][j],f[i-1][j]+f[i][j-1]);
}
}
printf("%lld",f[m][n]);
return 0;
}
|
9 出栈序列 AC
由于x是最后一个出栈的,所以可以将已经出栈的数分成两部分
比x小
比x大
比x小的数有x-1个,所以这些数的全部出栈可能为f[x-1]
比x大的数有n-x个,所以这些数的全部出栈可能为f[n-x]
这两部分互相影响,所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]
另外,由于x有n个取值,所以
ans = f[0]*f[n-1] + f[1]*f[n-2] + … + f[n-1]*f[0];
这,就是传说中的卡特兰数
1
2
3
4
5
6
7
8
9
10
11
12
13
|
# include <cstdio>
int n,f[20] = {1,1};
int main(){
scanf("%d",&n);
for(int i = 2;i<=n;i++){
for (int j = 0;j<i;j++){
f[i] += f[j] * f[i-j-1];
}
}
printf("%d",f[n]);
return 0;
}
|
10 数的计算 AC
我的方法过于暴力,但是也能过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# include <cstdio>
int n,f[1005] = {1};
int main(){
scanf("%d",&n);
for (int i = 1;i<=n;i++){
for(int j = 0;j<=i/2;j++){
f[i]+=f[j];
}
}
// 这里其实可以只算到 f[n/2],最后输出累加和
printf("%d",f[n]);
return 0;
}
|
大佬的 DP 方法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include<cstdio>
using namespace std;
int main(){
int n,cnt=1,i,f[1010];
f[0]=f[1]=1;
scanf("%d",&n);
for(i=2;i<=n;i++){
if(i%2==0){
f[i]=f[i-1]+f[i/2];
}else{
f[i]=f[i-1];
}
}
printf("%d\n",f[n]);
}
|
11 蜜蜂采蜜 AC
看到范围 1000,用高精!
1
2
3
4
5
6
7
8
9
10
|
# 2020-03-17 09:58:32
inn = input().split(" ")
m = int(inn[0])
n = int(inn[1])
f = [0]*1005
f[m] = 1
for i in range(m+1,n+1):
f[i] = f[i-1] + f[i-2]
print(f[n])
|
12 铺瓷砖 AC
这种题考数学,写出前几项,找规律
1
2
3
4
5
6
7
8
9
10
11
12
|
# include <cstdio>
int n,f[1000000] = {0,1,2,5};
int main(){
scanf("%d",&n);
for (int i = 4;i<=n;i++){
f[i] = f[i-3]+ f[i-1]*2;
f[i] %= 10000;
}
printf("%d",f[n]);
return 0;
}
|
线性数据结构
1 报数淘汰 AC
非常简单的数组模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <cstdio>
int main(){
int n,m,count = 0,j = 0;
scanf("%d %d",&n,&m);
int vis[100] = {};
for(int i = 0;i<n;){
if (vis[j%n] == 0){
count ++;
}
if (count == m){
vis[j%n] = 1;
count = 0;
printf("%d",j%n + 1);
if (i < n-1)printf(" ");
i++;
}
j++;
}
return 0;
}
|
2 最大子段和 AC
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 <cstdio>
int main(){
int n,sum = 0,sgn = 0,max = -0x3fffffff;
scanf("%d",&n);
int a[n];
// 输入,并判断数列中是否有正数
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
if (a[i] > 0)sgn = 1;
max = max<a[i]?a[i]:max;
}
if (sgn == 0){ // 如果全为负,则选一个最大的
printf("%d",max);
return 0;
}else{ // 有正数,则挑选、舍弃
for(int i = 0;i<n;i++){
sum += a[i];
if (sum <= 0)sum = 0;
// printf("%d- ",sum);
max = max<sum?sum:max;
}
printf("%d",max);
return 0;
}
}
|
其中,第一次写的时候遗漏了最大和为负的情况,例如数据“1 -1”答案就不对,于是分类进行讨论
而大佬的方法就厉害了,先判断大于零,再加当前的数字,就能统一算法了!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include<cstdio>
int n,j,sum,maxx;
int main(){
scanf("%d%d",&n,&maxx);
sum=maxx;//输入n
while(--n){
scanf("%d",&j);
sum=sum>0?sum:0;
sum+=j;
maxx=maxx>sum?maxx:sum;
}//贪心,如果负了就舍去
return (printf("%d",maxx))&0;//输出并return 0
}
|
3 括号匹配 AC
送分题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include<cstdio>
int main(){
int count = 0;
char ch;
while(1){
scanf("%c",&ch);
if (ch == '(')count ++;
else if(ch == ')')count --;
else if(ch == '@')break;
if (count < 0){
printf("NO");
return 0;
}
}
if (count == 0)printf("YES");
else printf("NO");
return 0;
}
|
4 链表优化 40 TLE TODO
我直接用的 stl 里面的 vector,我想不到有什么优化的方法。找的过程如果用 hashtable,可以缩短到 O(1) 时间找到,但是在插入的时候,hashtable 就要花费 O(n) 的时间来修改,我现在这样是花费多个 O(logn),改 hash 难道不是得不偿失吗?
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
|
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int main(){
int n,m,lr,v;
vector<int>team(1,1);
scanf("%d",&n);
for(int i = 1;i<n;i++){
scanf("%d %d",&v,&lr);
team.insert(find(team.begin( ),team.end( ), v)+lr,i+1);
}
scanf("%d",&m);
for(int i = 0;i<m;i++){
scanf("%d",&v);
vector<int>::iterator res = find(team.begin( ), team.end( ), v);
if (res != team.end())
team.erase(res);
}
for(int i = 0;i<team.size();i++){
printf("%d",team[i]);
if(i != team.size()-1)printf(" ");
else printf("\n");
}
return 0;
}
|
5 后缀表达式 AC
一开始担心除法,用的 float,67分,改成 long long,AC
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
|
# include <cstdio>
# include <cstring>
# include <stack>
using namespace std;
long long calcu(long long b,long long a,char ch){
if (ch == '*')return a*b;
else if (ch == '/')return a/b;
else if (ch == '-')return a-b;
else return a+b;
}
int main(){
char ch;
int num = 0;
stack<long long>n;
while(1){
scanf("%c",&ch);
if (ch >= '0' && ch <= '9')
num = num * 10 + ch - '0';
else if (ch == '.') {
n.push(num);
num = 0;
}else if (ch == '@'){
break;
}else{
long long tempa = n.top();n.pop();
long long tempb = n.top();n.pop();
n.push(calcu(tempa,tempb,ch));
}
}
printf("%d",(int)n.top());
}
|
6 水list AC
1
2
3
4
5
6
7
8
9
10
11
12
|
# include <cstdio>
int a[2000001],n,m,d;
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++)scanf("%d",&a[i]);
for(int i = 0;i<m;i++){
scanf("%d",&d);
printf("%d\n",a[d-1]);
}
return 0;
}
|
7 map AC
hash 空间不够,改成 map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<cstdio>
#include<map>
using namespace std;
int n,q,p,k;
map<long long,int>b;
long long i,j;
int main()
{
scanf("%d%d",&n,&q);
while(q--)
{
scanf("%d %d %d",&p,&i,&j);
if(p==1)
{
scanf("%d",&k);
b[i*1000000+j]=k;
}
else printf("%d\n",b[i*1000000+j]);
}
return 0;
}
|
8 模拟栈 AC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# include <cstdio>
# include <stack>
using namespace std;
int q,n;
stack<int>st;
int main(){
scanf("%d",&q);
for(;q;q--){
scanf("%d",&n);
int a[n+1],b[n+1];
for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
for(int i = 0;i<n;i++){scanf("%d",&b[i]);}
int i = 0,j = 0;
for(;i<n;i++){
st.push(a[i]);
while (b[j] == st.top()){
st.pop();
j++;
if (st.empty())break;
}
}
if (st.size())printf("No\n");
else printf("Yes\n");
while (!st.empty())st.pop();
}
return 0;
}
|
🌲
1 FBI 树 AC
简单的二叉树概念题,递归建树,后序遍历
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
|
//data
//3
//10001011
// f
// f f
// f b f i
// i b b b i b i i
# include <cstdio>
# include <cmath>
using namespace std;
struct Node{
char value;
Node * lch;
Node * rch;
};
char getCh(char a[],int length){
int exist0 = 0,exist1 = 0;
for(int i = 0;i<length;i++){
if (a[i] == '1')exist1 ++;
else if (a[i] == '0')exist0 ++;
if (exist0 != 0 && exist1 != 0)return 'F';
}
if (exist1 == 0 && exist0 != 0)return 'B';
else if (exist0 == 0 && exist1 != 0)return 'I';
else return 'F';
}
void cutChar(char ch[],char newch[],int start,int afterlen){
for(int i = 0;i<afterlen;i++){
newch[i] = ch[start + i];
}
newch[afterlen] = '\0';
// printf("= %d ",afterlen);
// for(int i = 0;i<afterlen;i++){
// printf("%c",newch[i]);
// }
// printf("\n");
}
Node *generateTree(char ch[],int n){
if (n == -1)return NULL;
int length = pow(2,n);
Node *root = new Node;
root -> value = getCh(ch, length);
// printf("=== ch->%s\n",ch);
// printf("=== root -> %c \n",root->value);
char newchl[(length/2)+1],newchr[(length/2)+1];
cutChar(ch, newchl, 0, (length/2));
cutChar(ch, newchr, (length/2), (length/2));
root -> lch = generateTree(newchl, n-1);
root -> rch = generateTree(newchr, n-1);
return root;
}
void backOrder(Node *root){
if (root == NULL)return;
backOrder(root->lch);
backOrder(root->rch);
printf("%c",root->value);
}
int n,length = 1;
int main(){
scanf("%d",&n);
length <<= n;
char ch[length+1];
scanf("%s",ch);
Node *root = generateTree(ch,n);
backOrder(root);
return 0;
}
|
但是看了大佬题解,发现自己的想法有多处冗余:
- 建树传参时,无需每次都新建子串。只需要每次规定子串的起始位置,随机访问即可;
- 判断 FBI 时,
if (exist1 == 0 && exist0 != 0)
直接写为if (exist0)
就够了(本来前半段也是冗余的) - 建树和后序遍历可以在同一个递归中完成,即在当前函数里,先遍历建树,再打印
root->value
;也可以是在后序遍历的过程中加一些操作。
参考代码如下两种:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
using namespace std;
char s[1050];
void maketree(int x,int y){ // 此函数是在建树的模板上改的
if(y>x){
maketree(x,(x+y)/2);
maketree((x+y+1)/2,y);
}
int B=1,I=1;
for(int i=0;i<=y-x;i++){
if(s[x+i]=='1') B=0;
else if(s[x+i]=='0') I=0;
}
if(B) cout<<'B';
else if(I) cout<<'I';
else cout<<'F';
}
int main() {
int n;
cin>>n>>s;
maketree(0,(1<<n)-1);
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
|
#include <iostream>
#include <string>
using namespace std;
char FBI(string s) // 此函数是在后序遍历模板的基础上改的
{
if (s.length() > 1)
{
cout << FBI(s.substr(0, s.length()/2));
cout << FBI(s.substr(s.length()/2, s.length()/2));
}
if (s == string(s.length(), '0')) return 'B';
if (s == string(s.length(), '1')) return 'I';
return 'F';
}
int main()
{
int n;
cin >> n;
string s;
cin >> s;
cout << FBI(s);
return 0;
}
|
另外有个小技巧:
在输入长串的时候,写 A+1 就能从 A[1] 开始输入了: scanf("%s", A+1);
; 此时若想测长度,则需要用 strlen(A+1)
本题还有一个很巧的想法:
- 直接将 0101 字符串转换为 BIBI 字符串,0->b,1->i
- 倒着建树:一开始字符串为叶节点,父节点的 FBI 可以根据两个孩子直接决定(妙),这样每一层一个字符串,直接合并,就是完全二叉树的层序遍历
- 后序遍历,按照下标访问完全二叉树的元素即可
- 以上想法其实就是线段树的想法 = =
☆ 很多🌲的题目根本不需要事实上把🌲建出来!
2 中序 + 后序 求先序 AC
基础送分题
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
|
# include <cstdio>
# include <iostream>
# include <string>
using namespace std;
struct Node{
char v;
Node* lch;
Node* rch;
};
Node* buildtree(string inorder,string backorder){
Node* root = new Node;
int size = (int)backorder.size() - 1;
root -> v = backorder[size];
root -> lch = root -> rch = NULL;
string::size_type pos = inorder.find(root -> v);
if (pos != string ::npos){
if (pos > 0)
root -> lch = buildtree(inorder.substr(0,pos), backorder.substr(0,pos));
if (size - pos > 0)
root -> rch = buildtree(inorder.substr(pos+1,size - pos), backorder.substr(pos,size - pos));
}
return root;
}
void forthOrder(Node *root){
if (root == NULL)return;
printf("%c",root->v);
forthOrder(root->lch);
forthOrder(root->rch);
}
int main(){
string inorder,backorder;
cin>>inorder>>backorder;
Node* root = buildtree(inorder,backorder);
forthOrder(root);
return 0;
}
|
但是为什么我的代码就要 40 行,大佬的代码只要 20 行呢?
先附上大佬的代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after){
if (in.size()>0){
char ch=after[after.size()-1];
cout<<ch;//找根输出
int k=in.find(ch);
beford(in.substr(0,k),after.substr(0,k));
beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树;
}
}
int main(){
string inord,aftord;
cin>>inord;cin>>aftord;//读入
beford(inord,aftord);cout<<endl;
return 0;
}
|
对比发现有如下原因:
- 只需要一轮递归:在前序遍历的基础上更改即可
- 根本不需要真正建树,只需要递归输出
root
即可 - 变量和函数名,在能表示意义的前提下,越短越好
3 新二叉树 AC
送分题,记住二叉树模板,按照规则建树即可
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
|
# include <cstdio>
# include <iostream>
# include <cstring>
using namespace std;
struct Node{
char c;
Node* l = NULL;
Node* r = NULL;
};
Node* newNode(char a){
Node* root = new Node;
root -> c = a;
root -> l = root -> r = NULL;
return root;
}
Node* create(char a,char b,char c){
Node* root = new Node;
Node* lc = new Node;
Node* rc = new Node;
root -> c = a;
if (b != '*'){
lc -> c = b;
root -> l = lc;
}
if (c != '*'){
rc -> c = c;
root -> r = rc;
}
return root;
}
void insert(Node* now,char a,char b,char c){
if(now == NULL)return;
else if(now -> c == a){
if (b != '*') now -> l = newNode(b);
if (c != '*') now -> r = newNode(c);
}else{
insert(now -> l, a, b, c);
insert(now -> r, a, b, c);
}
}
void forthOrder(Node *root){
if (root == NULL)return;
printf("%c",root->c);
forthOrder(root->l);
forthOrder(root->r);
}
int main(){
int n;
scanf("%d\n",&n);
char a,b,c;
scanf("%c%c%c\n",&a,&b,&c);
Node* root = create(a,b,c);
for(int i = 1;i<n-1;i++){
scanf("%c%c%c\n",&a,&b,&c);
insert(root,a,b,c);
}
scanf("%c%c%c",&a,&b,&c);
insert(root,a,b,c);
forthOrder(root);
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
|
#include<iostream>
#include<string>
#include<cstring>//不加会CE
using namespace std;
int n;
string s;
int main()
{
cin>>n;
cin>>s;
for(int i=2;i<=n;++i)//由于第一个为原串,所以单独输入
{
string ss;//前序遍历序列
cin>>ss;
int x=s.find(ss[0]);//找到这个子树的根节点在原串中的位置
s.erase(x,1);//清除根节点
s.insert(x,ss);//加入子树
}
for(int i=0;i<s.size();++i)
if(s[i]!='*') cout<<s[i];//不输出空节点
else continue;
}
|
或者树,直接用 n*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
|
#include<bits/stdc++.h>
using namespace std;
int n;
char a[30][3];
void f(char x)
{
if(x!='*')
{
cout<<x;
for(int i=1;i<=n;i++)
if(a[i][0]==x)
{
f(a[i][1]);
f(a[i][2]);
}
}
return;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i][0]>>a[i][1]>>a[i][2];
f(a[1][0]);
return 0;
}
|
而这个方法可以有改进:
先补充一下 map:
- map第一个好处是作为一个数组,可以开很大!比如:
map<int,int>x;
,可以把x数组当成普通数组用,不过要注意一点:定义了x数组后,就不能使用c++的数组函数,比如memset
- map第二个好处下标不一定是一个整数,可以甚至可以是一个字符串!
map<下标类型,数值类型>;
比如:map<string,char>a; string st="123"; a[st]='1';
- map不仅可以开一维数组,还可以开二维数组。比如:
map<int,map<int,int>;
注意这里是一定要有空格的,否则会编译错误
于是,此题可以用 map
+ 并查集解决(就不用了 O(n) 寻找了):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <bits/stdc++.h>
using namespace std;
map<char,char>x;//用map来记录一个节点的左儿子
map<char,char>y;//用map来记录一个节点的右儿子
char a[35];//节点
void find(char ch){//并查集
cout<<ch;
if(x[ch]!='*')find(x[ch]);
if(y[ch]!='*')find(y[ch]);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
char left,right;
cin>>a[i]>>left>>right;
x[a[i]]=left;
y[a[i]]=right;
}find(a[1]);//开始遍历整棵树
return 0;//结束程序
}
|
4 对称二叉树 52
思路有错,懒得继续改了
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
|
# include <cstdio>
# include <string>
# define maxn 1000001
using namespace std;
int n;
int tree[maxn][3],childnum[maxn];
string tempa,temp2;
bool c(int i){
printf("%d",i);
int l = tree[i][1],r = tree[i][2];
while(1){
if (tree[l][1] != -1 && tree[r][2] != -1){
l = tree[i][1];
r = tree[i][2];
}else if (tree[l][1] == -1 && tree[r][2] == -1){
return 1;
}else return 0;
}
}
int check(int i){ // 如果是平衡,返回孩子个数,如果不平衡,返回-1
if (tree[i][1] != -1 && tree[i][2] != -1){
// 两边均有孩子
if (tree[tree[i][1]][0] == tree[tree[i][2]][0]){
// 两边均有孩子,且左右孩子相等
int a,b;
a = check(tree[i][1]);
b = check(tree[i][2]);
if (c(i) && a == b && b >= 0){
// 两边均有孩子,且左右子树相等,且左右孩子均为对称
childnum[i] = a * 2 + 2;
return a * 2 + 2;
}else {
// 两边均有孩子,且左右子树相等,但左右孩子不均为对称
childnum[i] = -1;
return -1;
}
}
else {
// 两边均有孩子,但左右孩子不相等
childnum[i] = -1;
return -1;
}
}
else if (tree[i][1] == -1 && tree[i][2] == -1){
// 叶节点
childnum[i] = 0;
return 0;
}
else {
// 仅一边有孩子
childnum[i] = -1;
return -1;
}
}
int main(){
scanf("%d",&n);
if (n == 0){
printf("0");
return 0;
}
for(int i = 1;i<=n;i++){
scanf("%d",&tree[i][0]);
childnum[i] = -2;
}
for(int i = 1;i<=n;i++){
scanf("%d %d",&tree[i][1],&tree[i][2]);
}
for(int i = 1;i<=n;i++){ // 检查每个节点
check(i);
}
int max = 0;
for(int i = 1;i<=n;i++){
// printf("%d,",childnum[i]);
max = max>childnum[i]?max:childnum[i];
}
printf("%d",max+1);
return 0;
}
|
4 先序+中序 求后续 AC
其实也是不用建树的
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
|
# include <cstdio>
# include <cstring>
using namespace std;
char before[30],inorder[30];
struct node{
char c;
node* l;
node* r;
}*root;
node* get(char ll[],char in[]){
node *root;
root = new node;
root -> c = ll[0];
root -> l = NULL;
root -> r = NULL;
int i = 0;
for(;i<strlen(in);i++){
if (in[i] == ll[0])break;
}
char a[30] = {},b[30] = {},c[30] = {},d[30] = {};
for(int j = 1;j<i+1;j++)a[j-1] = ll[j];
for(int j = i+1;j<strlen(ll);j++)b[j-i-1] = ll[j];
for(int j = 0;j<i;j++)c[j] = in[j];
for(int j = i+1;j<strlen(in);j++)d[j-i-1] = in[j];
if(strlen(a) > 0)root -> l = get(a,c);
if(strlen(b) > 0)root -> r = get(b,d);
return root;
}
void postorder(node *root){
if (root -> l != NULL)postorder(root->l);
if (root -> r != NULL)postorder(root->r);
printf("%c",root->c);
}
int main(){
scanf("%s %s",inorder,before);
root = get(before,inorder);
postorder(root);
printf("\n");
return 0;
}
|
背包问题
模板
- 01 背包:n 件物品,背包容量 V,第 i 件物品费用 w[i],价值 v[i]
for (int i = 1; i <= n; i++) for (int j = V; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]);
初始化:- 恰好装满背包:
f[0] = 0;f[1] = ... = f[V] = -∞;
- 无需恰好装满:
f[0] = f[1] = ... = f[V] = 0;
- 恰好装满背包:
- 完全背包:n 种物品,每种无限个,背包容量 V,第 i 件物品费用
w[i]
,价值v[i]
- 转换为 01 背包:第 i 种物品拆成费用为
w[i]∗2^k
、价值为v[i]∗2^k
的若干件物品,即每种物品拆成log(V/w[i])
件物品 - O(VN) 的算法:
for (int i = 1; i <= n; i++) for (int j = w[i]; j <= V; j++) f[j] = max(f[j], f[j - w[i]] + v[i]);
- 转换为 01 背包:第 i 种物品拆成费用为
- 多重背包问题:有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 p[i] 件可用,每件费用是 w[i],价值是 v[i]转化为 01 背包问题
for (int i = 1; i <= n; i++) { int num = min(p[i], V / w[i]); for (int k = 1; num > 0; k <<= 1) { if (k > num) k = num; num -= k; for (int j = V; j >= w[i] * k; j--) f[j] = max(f[j], f[j - w[i] * k] + v[i] * k); } }
- 混合背包问题:综合起来
p[i]:每个物品的件数,0代表无穷个 for (int i = 1; i <= n; i++) if (p[i] == 0) for (int j = w[i]; j <= V; j++) f[j] = max(f[j], f[j - w[i]] + v[i]); else for (int k = 1; k <= p[i]; k++) for (int j = V; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]);
- 二维背包问题:
for (int i = 1; i <= n; i++) for (int j = V; j >= w[i]; j--) for (int k = T; k >= g[i]; k--) f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);
- 分组背包问题:有N件物品和一个容量为V的背包。第i件物品的费用是w[i],价值是v[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。
for (所有的组k) for (int j = V; j >= 0; j--) for (所有属于组k的i) f[j] = max{f[j], f[j - w[i]] + v[i]}
1 01背包 AC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
# include <cstdio>
# include <algorithm>
using namespace std;
const int maxn = 30001;
int main(){
int n,m;
int a[maxn],b[maxn] = {},f[maxn] = {};
scanf("%d %d",&n,&m);
for(int i = 0;i<m;i++){
scanf("%d %d",&a[i],&b[i]);
b[i] *= a[i];
}
for(int i = 0;i<m;i++){
for(int j = n;j>=a[i];j--){
f[j] = max(f[j],f[j-a[i]] + b[i]);
}
}
printf("%d",f[n]);
return 0;
}
|
2 小A点菜 AC
见题解: https://www.luogu.com.cn/blog/user23325/solution-p1164
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# include <cstdio>
int count = 0,n,m,a[10001] = {},f[101][10001]={0};
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
for(int i = 1;i<=n;++i)
for(int j = 1;j<=m;++j)
{
// 为了第一个考虑,故 i 从 1 开始
if(j==a[i])f[i][j]=f[i-1][j]+1;
if(j>a[i]) f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
if(j<a[i]) f[i][j]=f[i-1][j];
}
printf("%d",f[n][m]);
return 0;
}
|
贪心
1 合并果子 AC
用优先级队列,当下最小的两个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
# include <cstdio>
# include <queue>
using namespace std;
int main(){
int n,temp,res = 0;
scanf("%d",&n);
priority_queue<int, vector<int>, greater<int> >pq;
for(int i = 0;i<n;i++) {
scanf("%d",&temp);
pq.push(temp);
}
while(pq.size() > 1){
int a = pq.top();pq.pop();
int b = pq.top();pq.pop();
int c = a + b;
res += c;
pq.push(c);
}
printf("%d",res);
return 0;
}
|
2 数列分段Section I AC
水
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# include <cstdio>
int main(){
int n,m,count = 0,now = 0,temp;
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++){
scanf("%d",&temp);
if(now + temp > m){
count++;
now = temp;
}else{
now += temp;
}
}
printf("%d",count+1);
return 0;
}
|
3 混和牛奶 AC
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
|
# include <cstdio>
# include <queue>
using namespace std;
struct milk{
int volume,price;
friend bool operator < (milk m1,milk m2){
return m1.price > m2.price;
}
milk(int _p,int _a):volume(_a),price(_p){};
};
int main(){
int n,m,p,a,res = 0;
priority_queue<milk>pq;
scanf("%d%d",&n,&m);
for(int i = 0;i<m;i++){
scanf("%d%d",&p,&a);
pq.push(milk(p,a));
}
while(n > 0){
milk now = pq.top();
if (n > now.volume){
res += (now.volume * now.price);
pq.pop();
n -= now.volume;
}else{
res += (n * now.price);
break;
}
}
printf("%d",res);
return 0;
}
|
4 排队接水 AC
总时间要用 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
27
28
29
30
31
32
33
34
|
# include <cstdio>
# include <queue>
using namespace std;
struct s{
int n,i;
s(int _n,int _i):n(_n),i(_i){};
friend bool operator < (s s1,s s2){
if (s1.n != s2.n) return s1.n > s2.n; // 平
else return s1.i > s2.i;
}
};
int main(){
int n,temp;
long long res = 0; // int 不行
priority_queue<s>pq;
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d",&temp);
pq.push(s(temp,i+1));
}
for(int j = 0;j<n;j++){
s now = pq.top();
printf("%d",now.i);
res += (n-j-1) * now.n;
pq.pop();
if (j < n-1) printf(" ");
else printf("\n");
}
printf("%.02lf\n",(double)res/n); // float 不行
return 0;
}
|
还有一个好方法,不需优先队列或结构体排序:
因为 n <= 1000,所以给每个 ti 都 * 1001,在加上当前序号,可以保证排序的时候序号不干扰排序,又可以方便输出序号(只需 mod 1001 输出序号,/1001 输出时间)
5 纪念品分组 AC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# include <cstdio>
# include <algorithm>
using namespace std;
bool cmp(int a,int b){return a>b;}
int main(){
int w,n,a[50001] = {};
scanf("%d%d",&w,&n);
for(int i = 0;i<n;i++){scanf("%d",&a[i]);}
sort(a, a+n, cmp);
for(int i = 0;i<n-1;i++){
// printf("%d ",a[i]);
if (a[n-1] + a[i] <= w)n--;
}
printf("%d",n);
return 0;
}
|
6 线段覆盖 AC
每个线段按结束点从小到大排序,按照这个顺序贪心放置即可
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 <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
struct test{
int begin,end;
test(int _begin,int _end):begin(_begin),end(_end){};
};
bool cmp(test a,test b){
return a.end < b.end;
}
int main(){
int n;
scanf("%d",&n);
vector<test>lst;
for(int i = 0;i<n;i++){
int b,e;
scanf("%d %d",&b,&e);
lst.push_back(test(b,e));
}
int count = 0,nowend = 0;
sort(lst.begin(),lst.end(),cmp);
for(int i = 0;i<n;i++){
if (lst[i].begin >= nowend){
nowend = lst[i].end;
count ++;
}
}
printf("%d",count);
return 0;
}
|
7 移动纸牌 AC
第一堆只能从第二堆索取或者给予,满足第一堆后,就可以删去这一堆,以此类推,删去所有堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# include <cstdio>
int main(){
int n,sum = 0;
int a[101] = {};
scanf("%d",&n);
for (int i = 0;i<n;i++){
scanf("%d",&a[i]);
sum += a[i];
}
int avg = sum/n,count = 0;
for (int i = 0;i<n;i++)a[i] -= avg;
for (int i = 0;i<n;i++){
if (a[i] != 0){
a[i+1] += a[i];
count ++;
}
}
printf("%d",count);
return 0;
}
|
8 高精度 AC
高精度直接用 python!同时注意 // 的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
n = int(input())
king = input().split()
a = []
for i in range(n):
k = input().split()
a.append([int(k[0]),int(k[1])])
# print(a,king)
a.sort(key = lambda x:x[0]*x[1])
maxsum = 0;product = int(king[0])
for i in a:
now = product//i[1]
# // 用来求商,要比除法再取整快得多!
if now>maxsum:
maxsum = now
product = product * i[0]
print(int(maxsum))
|
9 水题 AC
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 <cstdio>
int n,en = 0;
int a[1002][1002] = {};
int sumx[1002] = {},sumy[1002] = {};
struct empty{
int x,y;
empty(){};
empty(int _x,int _y):x(_x),y(_y){}
}e[10002];
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
scanf("%d",&a[i][j]);
if (!a[i][j])e[en++] = empty(i,j);
else{
sumx[i] += a[i][j];
sumy[j] += a[i][j];
}
}
}
int max = 0;
if (en == 0)printf("Bad Game!");
else{
for(int i = 0;i<en;i++){
int t = sumx[e[i].x] + sumy[e[i].y];
if (t > max)max = t;
}
printf("%d",max);
}
return 0;
}
|
10 水题 AC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# include<cstdio>
long long n,x,a[100005] = {};
int main(){
scanf("%lld %lld",&n,&x);
for(int i = 1;i<=n;i++)scanf("%lld",&a[i]);
long long res = 0;
for(int i = 1;i<=n;i++){
if (a[i] + a[i-1] > x){
long long p = a[i] + a[i-1] - x;
a[i] -= p;
res += p;
}
}
printf("%lld",res);
return 0;
}
|
11 铺设道路 AC
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 <cstdio>
int n,a[100005] = {};
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&a[i]);
}
int finish = 1,count = 0;
while (finish){
int start = 0,minn = 0,sgn = 0;
for(int i = 1;i<=n+1;i++){
if (a[i]){
sgn ++;
if(a[i-1]){
minn = minn<a[i]?minn:a[i];
}else{
start = i;
minn = a[i];
}
}else{
if(a[i-1]){
count+= minn;
for (int p = start;p<i;p++)a[p]-=minn;
}
}
}
// for (int i = 1;i<=n;i++)printf("%d ",a[i]);
// printf("%d\n",count);
if (sgn == 0)break;
}
printf("%d",count);
}
|
并查集
1 联通
并查集 + Kruskal:按照时间从小到大排序,每修一条路,如果这条路的两端本身 father 不同(即不连通),则联通的区域数 -1,当联通区域数 == 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
|
# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
int n,m,f,t,l,father[1002] = {};
struct road{
int from,to,length;
road(int _f,int _t,int _l):from(_f),to(_t),length(_l){}
};
bool cmp(road a,road b){
return a.length < b.length;
}
int findfather(int n){
while(n!=father[n]){n = father[n];}
return n;
}
void printfather(){
for(int i = 0;i<5;i++)printf(":%d",father[i]);
printf("\n");
}
int main(){
scanf("%d %d",&n,&m);
vector<road>a;
for(int i = 0;i<m;i++){
scanf("%d %d %d",&f,&t,&l);
a.push_back(road(f,t,l));
}
sort(a.begin(),a.end(),cmp);
for(int i = 0;i<n+1;i++) father[i] = i;
for(int i = 0;i<m;i++){
int fa = findfather(a[i].to),fb = findfather(a[i].from);
if (fa!=fb){
father[fa] = fb;
n --;
if (n == 1){
printf("%d",a[i].length);
return 0;
}
}
// printfather();printf("%d",n);
}
printf("-1");
return 0;
}
|
2 种类并查集 100
种类并查集,两种,开二倍数组
初始化:
1
2
3
|
fa[i] = i;
fa[i + n] = i + n;
|
关键步骤:
1
2
3
|
s[s[x+n]]=s[y];
s[s[x]]=s[y+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
|
// 2020-02-23 17:05:59
# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;
int n,m,fa[40005] = {};
struct edge{
int a,b,value;
edge(int _a,int _b,int _v):a(_a),b(_b),value(_v){}
};
bool cmp(edge a,edge b){
return a.value>b.value;
}
int findfa(int n){
if (fa[n] == n) return n;
return fa[n] = findfa(fa[n]); // 路径压缩,妙!
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 0;i<n;i++){
fa[i] = i;
fa[i + n] = i + n; // 种类并查集,两种,开两倍容量数组?
}
int tempa,tempb,tempv;
vector<edge>lst;
for(int i = 0;i<m;i++){
scanf("%d %d %d",&tempa,&tempb,&tempv);
lst.push_back(edge(tempa,tempb,tempv));
}
sort(lst.begin(),lst.end(),cmp);
for(int i = 0;i<m;i++){
if (findfa(lst[i].a) == findfa(lst[i].b) || findfa(lst[i].a + n) == findfa(lst[i].b + n)){
printf("%d",lst[i].value);
return 0;
}
// 以下两步为种类并查集的关键步骤
fa[fa[lst[i].a + n]] = fa[lst[i].b];
fa[fa[lst[i].a]] = fa[lst[i].b + n];
}
printf("0");
return 0;
}
|
3 种类并查集 AC
同上,这里的写法终于让我明白了:
- 由于有压缩路径,所以
fa[n]
和findfa(n)
是等价的 - 谁是谁的爸爸都可以,因此本题解这样写也是可以滴,以后就以这个为准:
1
2
3
4
5
6
7
|
if (不同类){
fa[findfa(ta + n)] = findfa(tb);
fa[findfa(tb + n)] = findfa(ta);
}else if (同类){
fa[findfa(ta)] = findfa(tb);
}
|
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
|
// 2020-02-23 21:31:50
# include <cstdio>
# include <iostream>
//# include <vector>
//# include <algorithm>
using namespace std;
int n,m,fa[2502] = {};
int findfa(int n){
// 两种不同的路径压缩
// 1
// if(fa[n] == n)return n;
// return fa[n] = findfa(fa[n]);
// 2
if (fa[n] != n) fa[n] = findfa(fa[n]);
return fa[n];
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
fa[i] = i;fa[i+n] = i+n;
}
for(int i = 0;i<m;i++){
char c;
int ta,tb;
cin>>c>>ta>>tb;
// scanf("%*c%c %d %d",&c,&ta,&tb); //%*c是上一行的换行,为什么这个就不行??#TODO
if (c == 'E'){
fa[findfa(ta + n)] = findfa(tb);
fa[findfa(tb + n)] = findfa(ta);
}else if (c == 'F'){
fa[findfa(ta)] = findfa(tb);
}
}
int s=0;
for(int i=1;i<=n;i++){
if(fa[i]==i) s++; //找有多少祖先,就是有多少团伙
}
printf("%d",s);
return 0;
}
|
4 种类并查集 AC
三类,就开三倍的数组并查集:
捕食的关系这样维护:
1
2
3
4
|
若是同类,则 `x+n*k & y+n*k` 共父
若 x 吃 y,则 `x + n*k & y + n*(k-1)` 共父
|
前面如果用了 find()
,那么后面可以直接用 f[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|