devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法题刷题目录（updating）

作者：知新_RL | 2024-06-04 12:53:43

赞

踩

算法题刷题目录（updating）

递归与递推

92. 递归实现指数型枚举

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. using namespace std;
  6.  
  7. const int N = 16;
  8. int n;
  9. int state[N];
  10. int flag[N];
  11.  
  12. void Fun(int m,int begin)
  13. {
  14. 	if(m>n)	
  15. 	{
  16. 		
  17. 		for(int i=1;i<=n;i++) 
  18. 			if(state[i]) printf("%d ",state[i]);
  19. 		puts("");
  20. 		return;
  21. 	}
  22. 	
  23. 	state[m]=begin;
  24. 	flag[begin]=1;
  25. 	Fun(m+1,begin+1);
  26. 	state[m]=0;
  27. 	flag[begin]=0;
  28. 	
  29. 	Fun(m+1,begin+1);
  30. 	
  31. }
  32.  
  33.  
  34. int main()
  35. {
  36. 	cin>>n;
  37. 	
  38. 	Fun(1,1);
  39. }

 94. 递归实现排列型枚举

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. using namespace std;
  6.  
  7. const int N = 10;
  8. int n;
  9. int state[N];
  10. int flag[N];
  11.  
  12. void Fun(int m)
  13. {
  14. 	if(m>n)	
  15. 	{
  16. 		
  17. 		for(int i=1;i<=n;i++) 
  18. 			printf("%d ",state[i]);
  19. 		puts("");
  20. 		return;
  21. 	}
  22. 	for(int j=1;j<=n;j++)
  23. 	{
  24. 		if(!flag[j])
  25. 		{
  26. 			state[m]=j;
  27. 			flag[j]=1;
  28. 			Fun(m+1);
  29. 			state[m]=0;
  30. 			flag[j]=0;
  31. 		}
  32. 	}
  33. }
  34.  
  35.  
  36. int main()
  37. {
  38. 	scanf("%d",&n);
  39. 	
  40. 	Fun(1);
  41. }

93. 递归实现组合型枚举

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. using namespace std;
  6.  
  7. const int N = 26;
  8. int n,u; 
  9. int state[N];
  10. int flag[N];
  11.  
  12. void Fun(int m,int begin)
  13. {
  14. 	if(m>u)
  15. 	{
  16. 		for(int j=1;j<m;j++) printf("%d ",state[j]);
  17. 		puts("");
  18. 		return;
  19. 	}
  20. 	
  21. 	for(int i=begin;i<=n;i++)
  22. 	{
  23. 		if(!flag[i])
  24. 		{
  25. 			state[m]=i;
  26. 			flag[i]=1;
  27. 			Fun(m+1,i+1);;
  28. 			state[m]=flag[i]=0;
  29. 		}
  30. 	}
  31. 	
  32. }
  33.  
  34. int main()
  35. {
  36. 	cin>>n>>u;
  37. 	
  38. 	Fun(1,1);
  39. }

1209. 带分数

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. using namespace std;
  6.  
  7. const int N = 26;
  8. int n,ans;
  9. int state[N],copystate[N];
  10.  
  11. bool Check(int a,int c)
  12. {
  13. 	memcpy(copystate,state,sizeof state);//使用copystate数组对保存state数组的值，目的是不用对state的值进行修改（直接修改state的值还要再完成函数后恢复现场） 
  14. 	int b=n*c-a*c;
  15. 	if(!a||!b||!c) return 0;//q,b,c中任意一个数为0，都是不符合要求的，所以返回0 
  16. 	
  17. 	while(b)//求出b的各个数位并进行判断和修改 
  18. 	{
  19. 		if(!(b%10)||copystate[b%10]) return 0;//如果b有数位为0或者已被使用过，那么返回0 
  20. 		copystate[b%10]=1;//对于未使用过的数字进行标记 
  21. 		b/=10;
  22. 	}
  23. 	
  24. 	for(int i=1;i<10;i++)//检验是否0~9所有的数都被使用过 
  25. 	{
  26. 		if(!copystate[i]) return 0;//若有未使用过的，那么返回0 
  27. 	}
  28. 	
  29. 	return 1;//否则此种组合成立，返回1 
  30. }
  31.  
  32. void FindC(int m,int a,int c)//确定c，c是分数的分母 
  33. {
  34. 	if(m==n) return;
  35. 	if(Check(a,c)) ans++;//此时a,c都有值了，那么可以尝试看看是否已经满足一种情况 ，所以进入check函数检验 
  36. 	
  37. 	for(int i=1;i<10;i++)
  38. 	{
  39. 		if(!state[i])
  40. 		{
  41. 			state[i]=1;
  42. 			FindC(m+1,a,10*c+i);//对c进行遍历 
  43. 			state[i]=0;//恢复现场 
  44. 		}
  45. 	}
  46. }
  47.  
  48. void FindA(int m,int a)//确定a，a是那个整数 
  49. {
  50. 	if(a>=n) return;
  51. 	if(a) FindC(m+1,a,0);//给a一个取值后，开始对c进行递归求解 
  52. 	
  53. 	for(int i=1;i<10;i++)
  54. 	{
  55. 		if(!state[i])
  56. 		{
  57. 			state[i]=1;
  58. 			FindA(m+1,10*a+i);
  59. 			state[i]=0;//恢复现场 
  60. 		}
  61. 	}
  62. }
  63.  
  64. int main()
  65. {
  66. 	cin>>n;
  67. 	
  68. 	FindA(0,0);
  69. 	
  70. 	printf("%d",ans);
  71. }

717. 简单斐波那契

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9. 	cin>>n;
  10. 	int fib1,fib2,fib3;
  11. 	
  12. 	fib1=0,fib2=1;
  13. 	if(n==1) printf("%d ",fib1);
  14. 	else if(n==2) printf("%d %d",fib1,fib2);
  15. 	else if(n>2) 
  16. 	{
  17. 		printf("%d %d ",fib1,fib2);
  18. 		for(int i=3;i<=n;i++)
  19. 		{
  20. 			fib3=fib1+fib2;
  21. 			fib1=fib2;
  22. 			fib2=fib3;
  23. 			printf("%d ",fib3);
  24. 		}
  25. 	}
  26. }

此为最优算法

95.费解的开关

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. using namespace std;
  7.  
  8. const int N = 5;
  9.  
  10. bool light[N][N];
  11.  
  12. int main()
  13. {
  14. 	int x,y;
  15. 	scanf("%d %d",&x,&y);
  16. 	while(x!=-1)
  17. 	{
  18. 		light[x][y]=!light[x][y];
  19. 		if(x-1>=0) light[x-1][y]=!light[x-1][y];
  20. 		if(y-1>=0) light[x][y-1]=!light[x][y-1];
  21. 		if(x+1<5) light[x+1][y]=!light[x+1][y];
  22. 		if(y+1<5) light[x][y+1]=!light[x][y+1];
  23. 	
  24. 		for(int i=0;i<5;i++)
  25. 		{
  26. 			for(int j=0;j<5;j++)
  27. 			{
  28. 				printf("%d ",light[i][j]);
  29. 			}
  30. 			puts("");
  31. 		}
  32. 		scanf("%d %d",&x,&y);
  33. 		system("cls");
  34. 	}
  35. }

1208.翻硬币

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. using namespace std;
  7.  
  8. char start[102],des[102];
  9.  
  10. void Turn(int i)//将硬币翻转 
  11. {
  12. 	if(start[i]=='*') start[i]='o';
  13. 	else start[i]='*';
  14. }
  15.  
  16. int main()
  17. {
  18. 	cin>>start>>des;
  19. 	int res=0;
  20. 	
  21. 	for(int i=0;i<strlen(start)-1;i++)
  22. 	{
  23. 		if(start[i]!=des[i])
  24. 		{
  25. 			Turn(i),Turn(i+1);
  26. 			res++;
  27. 		}
  28. 	}
  29. 	
  30. 	cout<<res;
  31. }

二分与前缀和

789.数的范围

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. int n,m;
  10. int* arr=new int[n];
  11.  
  12. void Find(int x)
  13. {
  14. 	int l=0,r=n-1,mid,i,j;
  15. 	
  16. 	while(l<r)//二分查找
  17. 	{
  18. 		mid=l+r>>1;
  19. 		if(arr[mid]<x) l=mid+1;
  20. 		else r=mid;
  21. 	}
  22. 	
  23. 	if(arr[l]==x) //查看被找到的数附近还有没有该数
  24. 	{
  25. 		for(i=l-1;arr[i]==x&&i>=0;i--);
  26. 		for(j=l+1;arr[j]==x&&j<n;j++);
  27. 		cout<<i+1<<" "<<j-1<<endl;
  28. 	}
  29. 	else
  30. 	{
  31. 		printf("-1 -1\n");
  32. 	}
  33. }
  34.  
  35. int main()
  36. {
  37. 	int x;
  38. 	cin>>n>>m;
  39. 	
  40. 	for(int i=0;i<n;i++)  cin>>arr[i];
  41. 	
  42. 	for(int i=0;i<m;i++)
  43. 	{
  44. 		cin>>x;
  45. 		Find(x);
  46. 	}
  47. }

730. 机器人跳跃问题

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. int h[100],n;
  10.  
  11. bool Judge(int e)
  12. {
  13. 	for(int i=0;i<n;i++)
  14. 	{
  15. 		e=e*2-h[i];
  16. 		if(e>=*max_element(h,h+n)) return 1;//这句很重要，因为如果不加的话，for循环里面就会缺少终止条件，导致int溢出
  17. 		if(e<0) return 0;
  18. 	}
  19. 	return 1;
  20. }
  21.  
  22. int main()
  23. {
  24. 	cin>>n;
  25. 	for(int i=0;i<n;i++) cin>>h[i];
  26. 	
  27. 	int l=0,r=*max_element(h,h+n),mid;
  28. 	
  29. 	while(l<r)
  30. 	{
  31. 		mid=l+r>>1;
  32. 		if(Judge(mid)) r=mid;//当前mid可以的话，试试能不能再缩小一点 
  33. 		else l=mid+1;//当前mid不可以，增大l 
  34. 	}
  35.  
  36. 	cout<<l;
  37. }

1221. 四平方和

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N=5*1e6;
  10.  
  11. int a,b,c,d;
  12.  
  13. struct sum
  14. {
  15. 	int s;
  16. 	int c;
  17. 	int d;
  18. 	
  19. 	bool operator<(const sum &temp)const
  20. 	{
  21. 		if(s!=temp.s) return s<temp.s;
  22. 		if(c!=temp.c) return c<temp.c;
  23. 		return d<temp.d;
  24. 	}
  25. }sum[N];
  26.  
  27.  
  28. int main()
  29. {
  30. 	int n,i=0,x;
  31. 	cin>>n;
  32. 	
  33. 	for(c=0;c*c<=n;c++)
  34. 		for(d=c;c*c+d*d<=n;d++) sum[i++]={c*c+d*d,c,d};
  35. 		
  36. 	sort(sum,sum+i);
  37. 	
  38. 	for(a=0;a*a<=n;a++)
  39. 	{
  40. 		for(b=a;b*b+a*a<=n;b++)
  41. 		{
  42. 			x=n-a*a-b*b;
  43. 			
  44. 			int l=0,r=i-1;
  45. 			while(l<r)
  46. 			{
  47. 				int mid=r+l>>1;
  48. 				if(sum[mid].s>=x) r=mid;
  49. 				else l=mid+1;
  50. 			}
  51. 			
  52. 			if(sum[l].s==x)
  53. 			{
  54. 				cout<<a<<" "<<b<<" "<<sum[l].c<<" "<<sum[l].d<<endl;
  55. 				return 0;
  56. 			}
  57. 		}
  58. 	}	
  59. }

795.前缀和（重要思想）

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. int x[1000001];
  10.  
  11. int main()
  12. {
  13. 	int n,a,m,a1,a2;
  14. 	cin>>n>>m;
  15. 	
  16. 	for(int i=1;i<=n;i++) 
  17. 	{
  18. 		scanf("%d",&a);
  19. 		x[i]=x[i-1]+a;
  20. 	}
  21. 	
  22. 	while(m)
  23. 	{
  24. 		scanf("%d %d",&a1,&a2);
  25. 		printf("%d",x[a2]-x[a1-1]);
  26. 		m--;
  27. 	}
  28. }
思想：一维前缀和

796.子矩阵的和（重要思想）

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. int mat[1001][1001],sum[1001][1001];
  10. int n,m,q;
  11.  
  12. int main()
  13. {
  14. 	int x1,y1,x2,y2;
  15. 	cin>>n>>m>>q;
  16. 	for(int i=1;i<=n;i++) 
  17. 		for(int j=1;j<=m;j++) cin>>mat[i][j];
  18. 	for(int i=1;i<=n;i++)
  19. 		for(int j=1;j<=m;j++)
  20. 			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i][j];//容斥原理求各矩阵之和 
  21. 			
  22. 	while(q)
  23. 	{
  24. 		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
  25. 		printf("%d",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);//容斥原理根据各矩阵之和求各子矩阵之和 
  26. 		q--;
  27. 	}
  28. }
思想：二维前缀和

注意点就是：

1.求矩阵中的从matrix[0][0]到matrix[i][j]这一矩阵和的过程中为了节省时间使用了动态数组和容斥原理

2.求矩阵的子矩阵和的时候不要单纯认为是sum[x2][y2]-sum[x1][y1],这很明显是不对的，也要使用容斥原理

k倍区间（P）

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. long long x[100001],counts[100001];
  10.  
  11. int main()
  12. {
  13. 	int n,m;
  14. 	long long res=0;
  15. 	cin>>n>>m;
  16. 	for(int i=1;i<=n;i++) 
  17. 	{
  18. 		scanf("%lld",&x[i]);
  19. 		x[i]+=x[i-1];
  20. 	}
  21. 	
  22. 	counts[0]=1;
  23. 	for(int i=1;i<=n;i++)
  24. 	{
  25. 		res+=counts[x[i]%m];
  26. 		counts[x[i]%m]++;
  27. 	}
  28. 	cout<<res;;
  29. }

激光炸弹（P）

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N=5010;
  10. int n,m,s[N][N];
  11.  
  12. int main()
  13. {
  14. 	int cnt,R,res=0;
  15. 	cin>>cnt>>R;
  16. 	R=min(5001,R);
  17. 	
  18. 	n=m=R;
  19. 	while(cnt--)
  20. 	{
  21. 		int x,y,w;
  22. 		cin>>x>>y>>w;
  23. 		s[++x][++y]=w;
  24. 		n=max(n,x),m=max(m,y);
  25. 	}
  26. 	
  27. 	for(int i=1;i<=n;i++)
  28. 		for(int j=1;j<=m;j++)
  29. 			s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
  30. 			
  31. 	for(int i=R;i<=n;i++)
  32. 		for(int j=R;j<=m;j++)
  33. 			res=max(res,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
  34. 	
  35. 	cout<<res;
  36. }

数学与简单DP

买不到的数

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9.  
  10. bool Judge(int p,int q,int i)
  11. {
  12. 	if(!i) return 1;
  13. 	
  14. 	if(i>=p&&Judge(p,q,i-p)) return 1;
  15. 	if(i>=q&&Judge(p,q,i-q)) return 1;
  16. 	
  17. 	return 0;
  18. 	
  19. }
  20.  
  21. int main()
  22. {
  23. 	int p,q,res;
  24. 	cin>>p>>q;
  25. 	
  26. 	for(int i=1;i<=1000;i++)
  27. 		if(!Judge(p,q,i)) res=i;
  28. 	
  29. 	cout<<res;
  30. }

由于暴力搜索时间复杂度太大，所以通过寻找数学规律优化代码，代码如下：

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11. 	int p,q,res;
  12. 	cin>>p>>q;
  13. 	cout<<q*(p-1)-p;
  14. }

通过使用暴力搜索，我们可以打表寻找规律，进而总结出上述的规律

拓展（数学知识）：

1.当p,q互质时，必定存在整数a,b，使得ap+bq=1,所以存在amp+bmq=m,即此时不存在所谓的不存在的数，但是当规定a>0&&b>0时，就存在这样的解了

2.当p,q的最大公约数是d时，那么整数a,b都会使得ap+bq=nd(n是整数），此时也不存在上述解

蚂蚁感冒

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N=55;
  10. int n[N];
  11.  
  12. int main()
  13. {
  14. 	int m;
  15. 	cin>>m;
  16. 	for(int i=0;i<m;i++) cin>>n[i];
  17. 	int left=0,right=0;
  18.     //left表示在感冒蚂蚁的左边且向右爬的蚂蚁个数，right表示在感冒蚂蚁的右边且向左爬的蚂蚁个数
  19. 	
  20. 	if(n[0]>0)//分为两种情况，第一种是感冒的蚂蚁的朝向是右边（左边同理）
  21. 	{
  22. 		for(int i=1;i<m;i++)
  23. 		{
  24. 			if(abs(n[i])<abs(n[0])&&n[i]>0) left++;
  25. 			if(abs(n[i])>abs(n[0])&&n[i]<0) right++;
  26. 		}
  27. 	
  28. 		if(!right) cout<<1;//没有右边的蚂蚁向左爬，那么只会有一个感冒的蚂蚁
  29. 		else cout<<right+left+1;//否则，右边向左爬的蚂蚁和左边向右爬的蚂蚁都会感冒
  30. 	}
  31. 	else if(n[0]<0)
  32. 	{
  33. 		for(int i=1;i<m;i++)
  34. 		{
  35. 			if(abs(n[i])<abs(n[0])&&n[i]>0) left++;
  36. 			if(abs(n[i])>abs(n[0])&&n[i]<0) right++;
  37. 		}
  38. 	
  39. 		if(!left) cout<<1;
  40. 		else cout<<right+left+1;
  41. 	}
  42. }

核心思想：

1.题目中提到的当两只蚂蚁相遇时会调转方向，可以理解为两只蚂蚁依然朝着原来的方向爬

2.右边的向右爬的蚂蚁和左边的向左爬的蚂蚁都不会感染，所以只需要考虑代码中提到的两种情况

饮料换购

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11. 	int n,res;
  12. 	cin>>n;
  13. 	res=n;
  14. 	
  15. 	while(n>=3)
  16. 	{
  17. 		res+=n/3;
  18. 		n=n/3+n%3;
  19. 	}
  20. 	
  21. 	cout<<res;
  22. }
拓展(代码技巧)：

1.向上取整：ceil(a/b)=floor((a+b-1)/b)

2.负数取模：设a<0，则a%b=(a%b+b)%b

枚举，模拟与排序

连号区间数

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N=10010;
  10.  
  11. int n,arr[N],INF=1e8;
  12.  
  13. int main()
  14. {	
  15. 	int res=0;
  16. 	cin>>n;
  17. 	for(int i=0;i<n;i++) cin>>arr[i];
  18.  
  19. 	for(int i=0;i<n;i++)
  20. 	{
  21. 		int minv=INF,maxv=-INF;
  22. 		for(int j=i;j<n;j++)
  23. 		{
  24. 			minv=min(minv,arr[j]);
  25. 			maxv=max(maxv,arr[j]);
  26. 			if(maxv-minv==j-i) res++;
  27. 		}		
  28. 	}
  29. 	cout<<res;
  30. }

最小三元组（重要思想）

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N=10010;
  10.  
  11. int n;
  12. int a[N],b[N],c[N];//存数 
  13. int cnt[N];//前缀和数组 
  14. int acount[N],ccount[N];//acount[i]表示 a数组中小于b[i]的值的个数 ，ccount表示c数组中大于吧b[i]的值的个数 
  15.  
  16. int main()
  17. {	
  18. 	cin>>n;
  19. 	for(int i=0;i<n;i++) scanf("%d",&a[i]),a[i]++;
  20. 	for(int i=0;i<n;i++) scanf("%d",&b[i]),b[i]++;
  21. 	for(int i=0;i<n;i++) scanf("%d",&c[i]),c[i]++;
  22. 	
  23. 	for(int i=0;i<n;i++) cnt[a[i]]++;//统计各值在a数组中出现的次数 
  24. 	for(int i=1;i<N;i++) cnt[i]+=cnt[i-1];//求前缀和，统计a数组中小于等于i的值的个数 
  25. 	for(int i=0;i<n;i++) acount[i]=cnt[b[i]-1];//求a数组中小于b[i]的值的个数
  26. 	
  27. 	memset(cnt,0,sizeof(cnt));
  28. 	for(int i=0;i<n;i++) cnt[c[i]]++;//统计各值在c数组中出现的次数 
  29. 	for(int i=1;i<N;i++) cnt[i]+=cnt[i-1];//求前缀和，统计c数组中小于等于i的值的个数 
  30. 	for(int i=0;i<n;i++) ccount[i]=cnt[N-1]-cnt[b[i]];//求c数组中大于b[i]的值的个数，即用：c数组成员个数-小于等于b[i]的值的个数 
  31. 	
  32. 	long long res=0;
  33. 	for(int i=0;i<n;i++) cout<<acount[i]<<" "<<ccount[i]<<endl,res+=(long long)acount[i]*ccount[i];//对于每一种b[i]的值，求有多少种合适的方案 
  34. 	
  35. 	cout<<res;
  36. }

相比于使用三重循环加判断，这种思路大大减少了时间复杂度

思想：即用一个值来约束另外的2个变量

特别数的和

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N=10010;
  10. int arr[N];
  11.  
  12. int main()
  13. {	
  14. 	int n,res=0;
  15. 	cin>>n;
  16. 	
  17. 	for(int i=1;i<=n;i++)
  18. 	{
  19. 		int t=i;
  20. 		while(t)
  21. 		{			
  22. 			if(t%10==1||t%10==2||t%10==0||t%10==9) 
  23. 			{
  24. 			    res+=i;
  25. 			    break;
  26. 			}
  27. 			t/=10;
  28. 		}
  29. 	}
  30. 	
  31. 	cout<<res;
  32. }

错误票据

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. #include<sstream>
  8. using namespace std;
  9.  
  10. const int N=10010;
  11. int n,arr[N];
  12.  
  13. int main()
  14. {	
  15. 	int cnt;
  16. 	cin>>cnt;
  17. 	string line;
  18. 	
  19. 	getline(cin,line);
  20. 	while(cnt--)
  21. 	{
  22. 		getline(cin,line);
  23. 		stringstream ssin(line);
  24. 		
  25. 		while(ssin>>arr[n]) n++;
  26. 	}
  27.     //while(cin>>arr[n]) n++;用这句就可以简单代替
  28. 	
  29. 	sort(arr,arr+n);
  30. 	int res1,res2;
  31. 	
  32. 	for(int i=1;i<n;i++)
  33. 	{
  34. 		if(arr[i]==arr[i-1]) res1=arr[i];
  35. 		else if(arr[i]-arr[i-1]==2) res2=arr[i]-1;
  36. 	}
  37. 	
  38. 	cout<<res2<<" "<<res1;
  39. }
重点：使用sstream头文件里面的stringstream和getline来读入零散的输入的数字

回文日期

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int Month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//方便查询每月的最大天数
  9.  
  10. bool Check(int date)
  11. {
  12. 	int year=date/10000;
  13. 	int month=date/100%100;
  14. 	int day=date%100;
  15. 	
  16. 	if(month<=0||month>12) return 0;//月份越界
  17. 	if(month!=2&&day>Month[month]) return 0;//日期越界
  18. 	if(month==2)//对二月进行特殊处理
  19. 	{
  20. 		if(day>28+(year%4==0&&year%100||year%400==0)) return 0;//是否为闰年的判断条件
  21. 	}
  22. 	
  23. 	return 1;
  24. }
  25.  
  26. int main()
  27. {	
  28. 	int year1,year2,res=0;
  29. 	cin>>year1>>year2;
  30. 	
  31. 	for(int i=1000;i<=9999;i++)
  32. 	{
  33. 		int year=i,temp=i,cnt=4;
  34. 		while(cnt--) year=year*10+temp%10,temp/=10;//根据前四位得到回文数
  35. 		
  36. 		if(year1<=year&&year<=year2&&Check(year)) res++;
  37. 	}
  38. 	
  39. 	cout<<res;
  40. }
思路转变：在日期范围内找回文数->从回文数中找合法的日期，可以大大减少代码的复杂度

移动距离

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. #include<sstream>
  8. using namespace std;
  9.  
  10. int main()
  11. {	
  12. 	int w,m,n;
  13. 	cin>>w>>m>>n;
  14. 	
  15. 	int x1,y1,x2,y2;
  16. 	x1=m/w,x2=n/w;
  17. 	y1=m%w,y2=n%w;
  18. 	
  19. 	if(x1%2) y1=w-y1+1;
  20. 	if(x2%2) y2=w-y2-1;
  21. 	
  22. 	cout<<abs(x1-x2)+abs(y1-y2);
  23. }

日期问题

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. #include<sstream>
  8. using namespace std;
  9.  
  10. int Month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  11.  
  12. bool Check(int date)
  13. {
  14. 	int year=date/10000;
  15. 	int month=date/100%100;
  16. 	int day=date%100;
  17. 	
  18. 	if(month<=0||month>12)  return 0;
  19. 	if(month!=2&&day>Month[month]||day<=0) return 0;
  20. 	if(month==2)
  21. 	{
  22. 		if(day>28+(year%100&&year%4==0||year%400==0)) return 0;
  23. 	}
  24. 	return 1;
  25. }
  26.  
  27. int main()
  28. {	
  29. 	int a,b,c;
  30. 	scanf("%d/%d/%d",&a,&b,&c);
  31. 	
  32. 	for(int date=19600101l;date<=20591231;date++)
  33. 	{
  34. 		int year=date/10000,month=date/100%100,day=date%100;
  35. 		if(Check(date))
  36. 		{
  37. 			if(year%100==a&&month==b&&day==c
  38. 			||month==a&&day==b&&year%100==c
  39. 			||day==a&&month==b&&year%100==c)
  40. 			
  41. 			printf("%d-%02d-%02d\n",year,month,day);
  42. 		}
  43. 	}
  44. }

航班时间

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. #include<sstream>
  8. using namespace std;
  9.  
  10. int n;
  11.  
  12. int Get_second(int h,int m,int s)
  13. {
  14. 	return h*3600+m*60+s;	
  15. }
  16.  
  17. int Get_time()
  18. {
  19. 	string line;
  20. 	getline(cin,line);
  21. 	if(line.back()!=')') line+=" (+0)";
  22. 	
  23. 	int h1,h2,m1,m2,s1,s2,d;
  24. 	sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
  25. 	
  26. 	return Get_second(h2,m2,s2)-Get_second(h1,m1,s1)+d*24*3600;
  27. }
  28.  
  29. int main()
  30. {	
  31. 	cin>>n;
  32. 	string line;
  33. 	getline(cin,line);
  34. 	
  35. 	while(n--)
  36. 	{
  37. 		int time=(Get_time()+Get_time())/2;
  38. 		int hour=time/3600,minute=time%3600/60,second=time%60;
  39. 		printf("%02d:%02d:%02d\n",hour,minute,second);
  40. 	}
  41. }
重点：如何接受输入的字符串以及对字符串的复杂处理

外卖店优先级

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef pair<int, int> PII;
  8. #define x first
  9. #define y second
  10.  
  11. int n, m, T;
  12. int f[100010];//  f[i]表示店铺i的优先级
  13. int st[100010];//  st[i]表示店铺i是否处于优先缓存
  14. int last[100010];//  last[i]表示店铺i上一次有订单的时间 
  15. PII order[100010];//  订单 
  16.  
  17. int main()
  18. {
  19.     scanf("%d%d%d", &n, &m, &T);
  20.     for (int i = 0; i < m; i++)
  21.     {
  22.         scanf("%d %d", &order[i].x, &order[i].y);
  23.     } 
  24.     sort(order, order + m);
  25.     for (int i = 0; i < m;)
  26.     {
  27.         int j = i;
  28.         while (order[i] == order[j] && j < m) j++;//查看是否同时有多个相同店铺的订单
  29.         int t = order[i].x, id = order[i].y, cnt = j - i;
  30.         i = j;
  31.  
  32.         f[id] -= t - last[id] - 1;//当该店铺有订单时，开始统计店铺的权重，此时先处理减去的权重
  33.         if (f[id] < 0) f[id] = 0;//权重不能为负
  34.         if (f[id] <= 3) st[id] = 0;
  35.  
  36.         f[id] += cnt * 2;//处理要加上的权重
  37.         if (f[id] > 5) st[id] = 1;
  38.  
  39.         last[id] = t;
  40.     }
  41.  
  42.     for (int i = 1; i <= n; i++)
  43.     {
  44.         if (last[i] < T)//若某店铺从最后一次接订单不是在T时刻，那么需要减去权重
  45.         {
  46.             f[i] -= T - last[i];
  47.             if (f[i] <= 3) st[i] = 0;
  48.         }
  49.     }
  50.  
  51.     int ans = 0;
  52.     for (int i = 1; i <= n; i++) ans += st[i];
  53.     cout << ans << endl;
  54.     return 0;
  55. }

树状数组与线段树

动态求连续区间和（重要思想）

解1：

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. #include<sstream>
  8. using namespace std;
  9.  
  10. const int N=100010;
  11.  
  12. int arr[N],tree[N];
  13. int n,m;
  14.  
  15. int Lowbit(int x)
  16. //求出下标为x的元素在树的第几层且距离其父/子节点的距离是多少
  17. //比如x=12(0b1100)，那么return 4(12的二进制后面有两个0，即处在树的第二层，所以返回二进制的100即返回4)
  18. {
  19. 	return x&-x;
  20. }
  21.  
  22. void Add(int x,int y)
  23. //对树状数组进行修改操作，主要是修改下标为x的元素和其父节点(还有父父……节点)的元素
  24. {
  25. 	for(int i=x;i<=n;i+=Lowbit(i)) tree[i]+=y;
  26. }
  27.  
  28. int Sum(int x)
  29. //求前缀和
  30. {
  31. 	int res=0;
  32. 	for(int i=x;i>0;i-=Lowbit(i)) res+=tree[i];
  33. 	return res;
  34. }
  35.  
  36. int main()
  37. {	
  38. 	cin>>n>>m;
  39. 	
  40. 	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
  41.  
  42. 	for(int i=1;i<=n;i++) Add(i,arr[i]);
  43.     //将arr中的与元素添加到tree中，完成对树状数组tree的初始化
  44. 	
  45. 	while(m--)
  46. 	{
  47. 		int flag,x,y;
  48. 		cin>>flag>>x>>y;
  49. 		if(flag==0) cout<<Sum(y)-Sum(x-1)<<endl;
  50. 		else if(flag==1) Add(x,y);
  51. 	}
  52. }
思想：树状数组的建立，动态对某元素值的修改，动态求区间和（前缀和）

解2：

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. #include<sstream>
  8. using namespace std;
  9.  
  10. const int N=100010;
  11.  
  12. struct Tree
  13. {
  14. 	int l,r;
  15. 	int sum;
  16. }tr[N*4];
  17.  
  18. int arr[N],n,m;
  19.  
  20. void Push_up(int u)//通过两个子节点把父节点的sum算出来 
  21. {
  22. 	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;//每次调用这个函数的时候，俩字节点的sum都已经有值了 
  23. }
  24.  
  25. void Build(int u,int l,int r)//创建线段树 
  26. //u是当前节点序号，l，r是想要创建树的数组的左右端点 
  27. {
  28. 	if(l==r) tr[u]={l,r,arr[l]};//当递归到叶子节点了，那么对叶子节点的l,r,sum进行赋值 
  29. 	else//否则，其他非叶子节点只能先赋值l,r，然后通过之前得到的子节点sum来对其sum赋值 
  30. 	{
  31. 		tr[u]={l,r}; 
  32. 		int mid=l+r>>1;//通过此时节点的mid来判断 需要往左还是右子节点递归 
  33. 		Build(u<<1,l,mid);
  34. 		Build(u<<1|1,mid+1,r);
  35. 		Push_up(u);//对非叶节点赋sum 
  36. 	}
  37. }
  38.  
  39. int Query(int u,int l,int r)//查询指定的某段序列的和
  40. //u是当前节点序号，l，r是想要查询的序列的左右端点 
  41. {
  42. 	if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;//当当前节点两端都包含在想要查询的序列两端内时，返回这一部分sum 
  43. 	else
  44. 	{
  45. 		int sum=0,mid=tr[u].l+tr[u].r>>1;//通过mid来判断是需要往左还是右子节点递归 
  46. 		if(l<=mid) sum=Query(u<<1,l,r);
  47. 		if(r>mid) sum+=Query(u<<1|1,l,r);
  48. 		return sum;
  49. 	}
  50. }
  51.  
  52. void Add(int u,int a,int b)//改变arr中的某值 
  53. //u是当前节点序号，a是在数组中的序号，b是对该值的改变量 
  54. {
  55. 	if(tr[u].l==tr[u].r) tr[u].sum+=b;//当递归到叶节点时，才能开始赋新值 
  56. 	else 
  57. 	{
  58. 		int mid=tr[u].l+tr[u].r>>1;//通过mid来判断是需要往左还是右子节点递归 
  59. 		if(a<=mid) Add(u<<1,a,b);
  60. 		else Add(u<<1|1,a,b);
  61. 		Push_up(u);//当对叶节点赋新值完成后，需要递归回去把线段树更新（即把该叶节点的父父父……节点更新）） 
  62. 	}
  63. }
  64.  
  65. int main()
  66. {	
  67. 	cin>>n>>m;
  68. 	int f,a,b;
  69. 	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
  70. 	Build(1,1,n);
  71. 	while(m--)
  72. 	{
  73. 		scanf("%d %d %d",&f,&a,&b);
  74. 		if(!f) cout<<Query(1,a,b)<<endl;
  75. 		else Add(1,a,b);
  76. 	}
  77. }
思想：线段树（用法与树状数组类似）

数星星

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. #include<sstream>
  8. using namespace std;
  9.  
  10. const int N=100010;
  11.  
  12. int tree[N];
  13. int n;
  14. int level[N];
  15.  
  16. int Lowbit(int x)
  17. {
  18. 	return x&-x;
  19. }
  20.  
  21. void Add(int x)
  22. {
  23. 	for(int i=x;i<=N;i+=Lowbit(i)) tree[i]++;
  24. }
  25.  
  26. int Sum(int x)
  27. {
  28. 	int res=0;
  29. 	for(int i=x;i>0;i-=Lowbit(i)) res+=tree[i];
  30. 	return res;
  31. }
  32.  
  33. int main()
  34. {	
  35. 	int x,y;
  36. 	cin>>n;
  37. 	for(int i=0;i<n;i++)
  38. 	{
  39. 		cin>>x>>y;
  40. 		x++;//由于星星只会往右上方移动，所以我们可以只考虑x坐标
  41. 		level[Sum(x)]++;
  42. 		Add(x);
  43. 	}
  44. 	
  45. 	for(int i=0;i<n;i++) cout<<level[i]<<endl;
  46. }

动态求连续区间和

  1. #include<iostream> 
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<bitset>
  6. #include<vector>
  7. #include<sstream>
  8. using namespace std;
  9.  
  10. const int N=100010;
  11. typedef long long LL;
  12.  
  13. struct Tree
  14. {
  15. 	int l,r;
  16. 	int maxv;
  17. }tr[N*4];
  18.  
  19. int arr[N],n,m;
  20. LL INF=2147483647;
  21.  
  22. void Build(int u,int l,int r)//创建线段树 
  23. //u是当前节点序号，l，r是想要创建树的数组的左右端点 
  24. {
  25. 	if(l==r) tr[u]={l,r,arr[l]};//当递归到叶子节点了，那么对叶子节点的l,r,max进行赋值 
  26. 	else//否则，其他非叶子节点只能先赋值l,r，然后通过之前得到的子节点max来对其max赋值 
  27. 	{
  28. 		tr[u]={l,r}; 
  29. 		int mid=l+r>>1;//通过此时节点的mid来判断 需要往左还是右子节点递归 
  30. 		Build(u<<1,l,mid);
  31. 		Build(u<<1|1,mid+1,r);
  32. 		tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
  33. 	}
  34. }
  35.  
  36. int Query(int u,int l,int r)
  37. //u是当前节点序号，l，r是想要查询的序列的左右端点 
  38. {
  39. 	if(l<=tr[u].l&&r>=tr[u].r) return tr[u].maxv;//当当前节点两端都包含在想要查询的序列两端内时，返回这一部分max 
  40. 	else
  41. 	{
  42. 		int maxv=-INF,mid=tr[u].l+tr[u].r>>1;//通过mid来判断是需要往左还是右子节点递归 
  43. 		if(l<=mid) maxv=Query(u<<1,l,r);
  44. 		if(r>mid) maxv=max(maxv,Query(u<<1|1,l,r));
  45. 		return maxv;
  46. 	}
  47. }
  48.  
  49. int main()
  50. {	
  51. 	cin>>n>>m;
  52. 	int a,b;
  53. 	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
  54. 	Build(1,1,n);
  55. 	while(m--)
  56. 	{
  57. 		scanf("%d %d",&a,&b);
  58. 		printf("%d\n",Query(1,a,b));
  59. 	}
  60. }

本题就是线段树的变形，把线段树里面的sum成员改成了maxv

还有一点不同是，此题不需要更新数组，所以不用写Add()和Push_up()函数（Add函数会调用Push_up函数）

小朋友排队（P）

  1. #include<iostream>
  2. #include<cstring>
  3. #define ll long long
  4. using namespace std;
  5.  
  6. const int N = 1000010;
  7.  
  8. int n;
  9. int tr[N];
  10. int sum[N];
  11. int h[N];
  12.  
  13. int lowbit(int x)
  14. {
  15.     return x&-x;
  16. }
  17.  
  18. void add(int x,int w)
  19. {
  20.     for(int i=x;i<=N;i+=lowbit(i))tr[i]+=w;
  21. }
  22.  
  23. ll solve(int x)
  24. {
  25.     ll ans=0;
  26.     for(int i=x;i>0;i-=lowbit(i))ans+=tr[i];
  27.     return ans;
  28. }
  29.  
  30. int main()
  31. {
  32.     cin>>n;
  33.     for(int i=0;i<n;i++)cin>>h[i],h[i]++; //可能有身高为0的小朋友（你小子真是二刺螈啊）
  34.  
  35.     //在某数前面比某数大的数
  36.     for(int i=0;i<n;i++)
  37.     {
  38.         sum[i]+=solve(N-1)-solve(h[i]); //计算更大的数个数当然是更大数总数减更小数总数啦
  39.         add(h[i],1);    //存入，权值为1
  40.     }
  41.  
  42.     memset(tr,0,sizeof tr);
  43.  
  44.     //在某数后面然而更小的数
  45.     for(int i=n-1;i>=0;i--)
  46.     {
  47.         sum[i]+=solve(h[i]-1);
  48.         add(h[i],1);
  49.     }
  50.  
  51.     ll ans=0;
  52.     for(int i=0;i<n;i++)ans+=sum[i]*1ll*(sum[i]+1)/2;   //你好，高斯
  53.  
  54.     cout<<ans<<'\n';
  55.  
  56.     return 0;
  57. }

油漆面积（P）

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5.  
  6. using namespace std;
  7.  
  8. const int N = 10010;
  9.  
  10. int n;
  11.  
  12. struct Segment
  13. {
  14.     int x, y1, y2; //x为横坐标，y1,y2为线段树维护的两个纵坐标
  15.     int k; //k表示我们要加的权值，为+1或-1
  16.     //由于要把所有的线段按照横坐标排序，所以要重载小于号
  17.     bool operator< (const Segment &t)const
  18.     {
  19.         return x < t.x;
  20.     }
  21. }seg[N * 2]; //线段最多有两倍(每个矩形两条竖边)
  22.  
  23. struct Node
  24. {
  25.     int l, r;
  26.     int cnt, len;
  27. }tr[N * 4];
  28.  
  29. void pushup(int u) //用子节点的信息更新父结点的信息
  30. {
  31.     if(tr[u].cnt > 0) tr[u].len = tr[u].r - tr[u].l + 1;
  32.     else if(tr[u].l == tr[u].r) tr[u].len = 0;
  33.     else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
  34. }
  35.  
  36. void build(int u, int l, int r)
  37. {
  38.     tr[u] = {l, r, 0, 0}; //cnt和len默认为0
  39.     if(l == r) return;
  40.     int mid = l + r >> 1;
  41.     build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  42. }
  43.  
  44. void modify(int u, int l, int r, int k) //维护的是一段小段区间的值,k为要在这个区间加上或减去的权值
  45. {
  46.     //当前区间已经被完全包含
  47.     if(tr[u].l >= l && tr[u].r <= r)
  48.     {
  49.         tr[u].cnt += k;
  50.         pushup(u);
  51.     }
  52.     else //往下更新
  53.     {
  54.         int mid = tr[u].l + tr[u].r >> 1;
  55.         if(l <= mid) modify(u << 1, l, r, k);
  56.         if(r > mid) modify(u << 1 | 1, l, r, k);
  57.         pushup(u);
  58.     }
  59. }
  60.  
  61. int main()
  62. {
  63.     int n;
  64.     scanf("%d", &n);
  65.     int m = 0; //表示当前线段的数量
  66.     for(int i = 0; i < n; i ++ )
  67.     {
  68.         int x1, y1, x2, y2;
  69.         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  70.         seg[m ++ ] = {x1, y1, y2, 1}; //矩形左竖边
  71.         seg[m ++ ] = {x2, y1, y2, -1}; //矩形右竖边
  72.     }
  73.  
  74.     sort(seg, seg + m); //给所有线段排序
  75.  
  76.     build(1, 0, 10000);
  77.  
  78.     int res = 0;
  79.     for(int i = 0; i < m; i ++ ) //遍历所有线段
  80.     {
  81.         if(i > 0) //不能是第一条线，需要等第二条过来才能算面积
  82.         {
  83.             res += tr[1].len * (seg[i].x - seg[i - 1].x); //根结点的len * 阴影部分高度
  84.         }
  85.         modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k); //维护的是一小段区间
  86.     }
  87.  
  88.     printf("%d\n", res);
  89.     return 0;
  90. }

三体攻击（P）

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. typedef long long LL;
  5. const int N = 2000010;
  6. int A, B, C, m;
  7. LL s[N];  // 原数组
  8. LL b[N], bp[N];  // 差分数组
  9. int d[8][4] = {  // 差分数组和原数组 相互转换 使用到的偏移量和系数
  10.     {0, 0, 0, 1},
  11.     {0, 0, 1, -1},
  12.     {0, 1, 0, -1},
  13.     {0, 1, 1, 1},
  14.     {1, 0, 0, -1},
  15.     {1, 0, 1, 1},
  16.     {1, 1, 0, 1},
  17.     {1, 1, 1, -1},
  18. };
  19. int op[N / 2][7];
  20. int get(int i, int j, int k) 
  21. {
  22.     return (i * B + j) * C + k;
  23. }
  24. bool check(int mid) 
  25. {
  26.     memcpy(b, bp, sizeof bp);
  27.     for (int i = 1; i <= mid; i++) 
  28.     {
  29.         // 给(x1, y1, z1), (x2, y2, z2)之间加上c
  30.         int x1 = op[i][0], x2 = op[i][1];
  31.         int y1 = op[i][2], y2 = op[i][3];
  32.         int z1 = op[i][4], z2 = op[i][5];
  33.         int c = -op[i][6];
  34.         b[get(x1    , y1    , z1)]      += c;
  35.         b[get(x1    , y1    , z2 + 1)]  -= c;
  36.         b[get(x1    , y2 + 1, z1)]      -= c;
  37.         b[get(x1    , y2 + 1, z2 + 1)]  += c;
  38.         b[get(x2 + 1, y1    , z1)]      -= c;
  39.         b[get(x2 + 1, y1    , z2 + 1)]  += c;
  40.         b[get(x2 + 1, y2 + 1, z1)]      += c;
  41.         b[get(x2 + 1, y2 + 1, z2 + 1)]  -= c;
  42.     }
  43.     memset(s, 0, sizeof s);
  44.     for (int i = 1; i <= A; i++)
  45.         for (int j = 1; j <= B; j++)
  46.             for (int k = 1; k <= C; k++) 
  47.             {
  48.                 s[get(i, j, k)] += b[get(i, j, k)];
  49.                 for (int u = 1; u < 8; u++) 
  50.                 {
  51.                     int x = i - d[u][0], y = j - d[u][1], z = k - d[u][2], t = d[u][3];
  52.                     s[get(i, j, k)] -= s[get(x, y, z)] * t;
  53.                 }
  54.                 if (s[get(i, j, k)] < 0) return true;
  55.             }
  56.     return false;
  57. }
  58. int main() {
  59.     // 读取原数组
  60.     scanf("%d%d%d%d", &A, &B, &C, &m);
  61.     for (int i = 1; i <= A; i++)
  62.         for (int j = 1; j <= B; j++)
  63.             for (int k = 1; k <= C; k++)
  64.                 scanf("%lld", &s[get(i, j, k)]);
  65.     // 根据原数组s计算差分数组
  66.     for (int i = 1; i <= A; i++)
  67.         for (int j = 1; j <= B; j++)
  68.             for (int k = 1; k <= C; k++)
  69.                 for (int u = 0; u < 8; u++) 
  70.                 {
  71.                     int x = i - d[u][0], y = j - d[u][1], z = k - d[u][2], t = d[u][3];
  72.                     bp[get(i, j, k)] += s[get(x, y, z)] * t;
  73.                 }
  74.     // 读取操作
  75.     for (int i = 1; i <= m; i++)
  76.         for (int j = 0; j < 7; j++)
  77.             scanf("%d", &op[i][j]);
  78.     // 二分答案
  79.     int l = 1, r = m;
  80.     while (l < r) 
  81.     {
  82.         int mid = l + r >> 1;
  83.         if (check(mid)) r = mid;
  84.         else l = mid + 1;
  85.     }
  86.     printf("%d\n", r);
  87.     return 0;
  88. }

双指针，BFS和图论

螺旋折线

  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long LL;
  6.  
  7. int main()
  8. {
  9.     LL x, y;
  10.     cin >> x >> y;
  11.     //1.寻找点所在的层数
  12.     //-------
  13.     LL k = max(abs(x) , abs(y) );   //注意先取绝对值，然后取max，若是负数取max之后，绝对值是小的，对应层数就错误了
  14.     //-------
  15.     //找规律发现 y = x对角线的步数恰好是 4 * x^2 （x 和 y相等，此处写哪个都可以）
  16.     //2.根据在中间节点的前后，判断前进还是后退。（以y=x直线作为划分）
  17.     LL res = 0;
  18.     if(x >= y) //对角线的下半部分，加上距离对角点的曼哈顿距离
  19.         res = 4 * k * k + abs(k - x) + abs(k - y); //前进
  20.     else   
  21.         res = 4 * k * k - abs(k - x) - abs(k - y); //后退
  22.  
  23.     cout << res << endl;
  24.     return 0;
  25. }

找规律题

日志统计

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int N = 100010;   //根据题目数据范围，定N大小，此题则主要根据N,ts,id来确定的
  9. typedef pair<int, int> PII; //定义一个PII类型以及一对int整型用于存储ts和id
  10.  
  11. #define x first //为了代码简洁，则分别把first, second 宏定义为x, y
  12. #define y second
  13. int n, d, k;
  14. int cnt[N]; //用于存储每个id号获得赞数，所以后面代码为cnt[t] ++;
  15. bool st[N]; //用于存储每个帖子是否是热帖，所以用bool类型
  16. PII logs[N];//用于存储日志ts, id
  17.  
  18. int main()
  19. {
  20.     scanf("%d %d %d", &n, &d, &k);
  21.     for(int i = 0; i < n; i ++) scanf("%d %d\n", &logs[i].first, &logs[i].second);
  22.  
  23.     sort(logs, logs + n);
  24.  
  25.     for(int i = 0, j = 0; i < n; i ++)//双指针算法，i在前，j在后
  26.     {
  27.         int t = logs[i].second;//把每个获赞的帖子id存入t
  28.         cnt[t] ++;//获得一个赞，所以此刻 ++；
  29.         while(logs[i].first - logs[j].first >= d)//如果俩个帖子时间相差超过d，说明该赞无效
  30.         {
  31.             cnt[logs[j].second] --;//所以此刻--；
  32.             j ++;//要把指针j往后，否则死循环
  33.         }
  34.         if(cnt[t] >= k) st[t] = true; //如果该id贴赞超过k，说明是热帖
  35.     }
  36.     for(int i = 0; i < 100000; i ++)
  37.     {
  38.         if(st[i])//如果为真，则把热帖的id打印出来
  39.             cout << i << endl;
  40.     }
  41.  
  42.     return 0;
  43. }

献给阿尔吉侬的花束

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<queue>
  6.  
  7. #define x first
  8. #define y second
  9.  
  10. using namespace std;
  11.  
  12. const int N = 210;
  13. typedef pair<int, int> PII;
  14.  
  15. int n, m;
  16. char g[N][N];
  17. int dist[N][N];  // 把判重和距离数组合为一个
  18.  
  19. int bfs(PII start, PII end)  // 注意 start end都是PII类型的 别写错了
  20. {
  21.     queue<PII> q;
  22.     memset(dist, -1, sizeof dist);  // 把距离数组都初始化成-1
  23.     dist[start.x][start.y] = 0;  // 起点开始，距离为0
  24.  
  25.     q.push(start);  // 起点 入队
  26.  
  27.     int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  28.  
  29.     while(q.size())
  30.     {
  31.         PII t = q.front();
  32.  
  33.         // 弹出队头
  34.         q.pop();
  35.  
  36.         for (int i = 0; i < 4; i ++ )
  37.         {
  38.             int a = t.x + dx[i], b = t.y + dy[i]; 
  39.  
  40.             if (a < 0 || a >= n || b < 0 || b >= m) continue;  // 出界，跳出本次循环
  41.             if (dist[a][b] != -1) continue;    // 走过了，跳出本次循环
  42.             if (g[a][b] == '#') continue;    // 撞到障碍物
  43.  
  44.             dist[a][b] = dist[t.x][t.y] + 1;
  45.  
  46.             if (end == make_pair(a, b)) return dist[a][b];  // 走到终点了，返回距离
  47.  
  48.             q.push({a, b});
  49.         }
  50.  
  51.     }
  52.  
  53.     return -1;
  54. }
  55.  
  56. int main()
  57. {
  58.     int T;
  59.     cin >> T;
  60.  
  61.     while(T --)
  62.     {
  63.  
  64.         scanf("%d%d", &n, &m);
  65.  
  66.         for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
  67.  
  68.         PII start, end;
  69.         for (int i = 0; i < n; i ++ )
  70.             for (int j = 0; j < m; j ++ )
  71.                 if (g[i][j] == 'S') start = {i, j};
  72.                 else if (g[i][j] == 'E') end = {i, j};
  73.  
  74.         int distance = bfs(start, end);
  75.  
  76.         if (distance == -1) printf("oop!\n");
  77.         else printf("%d\n", distance);
  78.  
  79.     }
  80.  
  81.     return 0;
  82. }

交换瓶子

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. const int N=1e5+5;
  7. int a[N];
  8. bool st[N];
  9.  
  10. int main(){
  11.     int n;
  12.     cin >> n;
  13.     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  14.     int cnt=0;
  15.  
  16.     for(int i=1;i<=n;i++)
  17.     {
  18.         if(!st[i]){
  19.             cnt++;
  20.  
  21.             for(int j=i;!st[j];j=a[j])//位置j指向a[j]的元素
  22.             {
  23.                 st[j]=true;
  24.             }
  25.         }
  26.     }
  27.  
  28.     cout << n-cnt;
  29. }

完全二叉树的权值

  1. #include <iostream>
  2.  
  3. using namespace std;
  4. const int N = 100010;
  5.  
  6. long long q[N];
  7.  
  8. int main() {
  9.     int n;
  10.     cin >> n;
  11.  
  12.     for(int i = 1; i <=n; i++) cin >> q[i];
  13.     int max_ = -1e18;
  14.  
  15.     /*
  16.     完全二叉树 每层的开头为   2^(n-1) 结尾则是 2^n - 1
  17.     计算每层的数值只需要两个positioner 分别指向开头和结尾
  18.     */
  19.  
  20.     int depth = 1;
  21.     int res = 1;
  22.  
  23.     for(int i = 1; i <= n; i *= 2){
  24.         long long s = 0;
  25.         for(int j = i;  j <=  i*2 - 1 && j <= n; j ++) s += q[j];
  26.  
  27.         if(s > max_) 
  28.         {
  29.             max_ = s;
  30.             res = depth;
  31.         }
  32.  
  33.         depth++;
  34.     }
  35.  
  36.     cout << res;
  37. }

地牢大师

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=110;
  5.  
  6. int l,r,c;  //迷宫参数
  7. int px,py,pz,ex,ey,ez;  //pi为S的位置，ei为E的位置
  8.  
  9. char mp[N][N][N];  //记录迷宫
  10. int ans[N][N][N];  //存储答案
  11. bool vis[N][N][N];  //记录该点是否走过的状态
  12.  
  13. struct point{  //点的坐标
  14.     int x,y,z;
  15. };
  16.  
  17. queue<point> st;  //搜索队列
  18.  
  19. int dx[]={1,-1,0,0,0,0},dy[]={0,0,1,-1,0,0},dz[]={0,0,0,0,1,-1};  //偏移量数组
  20.  
  21. int bfs()
  22. {
  23.     while(!st.empty())
  24.     {  //当队头不为空时，扩展搜索队头
  25.         auto p=st.front();
  26.  
  27.         for(int i=0;i<6;i++)
  28.         {
  29.             int m_x=p.x+dx[i],m_y=p.y+dy[i],m_z=p.z+dz[i];  //偏移之后的点的坐标
  30.  
  31.             if(m_x<=l&&m_y<=r&&m_z<=c&&m_x>=1&&m_y>=1&&m_z>=1&&!vis[m_x][m_y]                                                    
  32.               [m_z]&&mp[m_x][m_y][m_z]!='#')
  33.             {  //判断条件
  34.                 vis[m_x][m_y][m_z]=1;  //更新该点走过的状态
  35.                 ans[m_x][m_y][m_z]=ans[p.x][p.y][p.z]+1;  //更新偏移后的点距离S的步骤
  36.                 if(mp[m_x][m_y][m_z]=='E') return  ans[m_x][m_y][m_z];  //搜到E直接返回答案
  37.                 st.push({m_x,m_y,m_z});  //将该点入队，继续扩展搜索
  38.             }
  39.         }
  40.  
  41.         st.pop();  //队头扩展搜索完毕后出队
  42.     }
  43.  
  44.     return 0;  //所有的点扩展搜索完后若还未返回搜到E，说明无解
  45. }
  46.  
  47. int main()
  48. {
  49.     while(cin>>l>>r>>c&&l&&r&&c)
  50.     {  //多实例读入
  51.         //还原数据
  52.         memset(ans,0,sizeof(ans)); 
  53.         memset(mp,0,sizeof(mp));
  54.         memset(vis,0,sizeof(vis));
  55.  
  56.         while(st.size())
  57.         {
  58.             st.pop();
  59.    
  60.         //读入迷宫
  61.         for(int i=1;i<=l;i++)
  62.         {
  63.             for(int j=1;j<=r;j++)
  64.             {
  65.                 for(int k=1;k<=c;k++)
  66.                 {
  67.                     cin>>mp[i][j][k];
  68.  
  69.                     if(mp[i][j][k]=='S') px=i,py=j,pz=k;  
  70.                     if(mp[i][j][k]=='E') ex=i,ey=j,ez=k;  
  71.                 }
  72.             }
  73.         }
  74.  
  75.         vis[px][py][pz]=1;  //标记S已经走过
  76.  
  77.         st.push({px,py,pz}); //S点入队
  78.  
  79.         int cnt=bfs();  //调用搜索，将从S点开始搜索
  80.  
  81.         if(cnt!=0) printf("Escaped in %d minute(s).\n",cnt);
  82.         else cout<<"Trapped!"<<endl;
  83.     }
  84.  
  85.     return 0;
  86. }

全球变暖

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define x first
  5. #define y second
  6.  
  7. const int N = 1010;
  8.  
  9. typedef pair<int, int> PII;
  10.  
  11. int n;
  12. char g[N][N];
  13. bool st[N][N], under[N][N];
  14. int dx[] = {0, 1, 0, -1};
  15. int dy[] = {1, 0, -1, 0};
  16. int ans;
  17.  
  18. void bfs(int x, int y) 
  19. {
  20.  
  21.     queue<PII> q;
  22.     q.push({x, y});
  23.     st[x][y] = true;
  24.  
  25.     int sum = 1, down = 0;
  26.     while (q.size()) 
  27.     {
  28.         PII t = q.front();
  29.         q.pop();
  30.  
  31.         bool is_bound = false;
  32.  
  33.         for (int i = 0; i < 4; i ++ ) 
  34.         {
  35.             int x = t.x + dx[i], y = t.y + dy[i];
  36.  
  37.             if (x < 0 || y < 0 || x >= n || y >= n) continue;
  38.             if (st[x][y]) continue;
  39.  
  40.             if (g[x][y] == '.')
  41.              {
  42.                 is_bound = true;
  43.                 continue;
  44.             }
  45.  
  46.             sum ++ ;
  47.             st[x][y] = true;
  48.             q.push({x, y});
  49.         }
  50.  
  51.         if (is_bound) down ++ ;
  52.     }
  53.  
  54.     if (down >= sum) ans ++ ;
  55. }
  56.  
  57. int main() {
  58.     scanf("%d", &n);
  59.  
  60.     for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
  61.  
  62.     for (int i = 1; i < n; i ++ ) 
  63.         for (int j = 1; j < n; j ++ ) 
  64.             if (g[i][j] == '#' && !st[i][j]) bfs(i, j);
  65.  
  66.     cout << ans << endl;
  67.  
  68.     return 0;
  69. }

大臣的旅费

  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 100010;
  7.  
  8. int n;
  9. struct Node
  10. {
  11.     int id,w;
  12. };
  13. vector<Node> h[N];
  14. int dist[N];
  15.  
  16. void dfs(int u,int father,int distance)
  17. {
  18.     dist[u] = distance;
  19.  
  20.     for(auto node : h[u])
  21.         if(node.id != father)
  22.             dfs(node.id, u, distance + node.w);
  23. }
  24.  
  25. int main()
  26. {
  27.     cin >> n;
  28.     for(int i = 0;i < n - 1;i ++)
  29.     {
  30.         int a,b,w;
  31.         cin >> a >> b >> w;
  32.         h[a].push_back({b,w}); // 无向图建双向边
  33.         h[b].push_back({a,w});
  34.     }
  35.  
  36.     dfs(1,-1,0);
  37.  
  38.     int u = 1;
  39.     for(int i = 1;i <= n; i++ )
  40.         if(dist[i] > dist[u])
  41.             u = i;
  42.  
  43.     dfs(u,-1,0);
  44.  
  45.     for(int i = 1;i <= n; i++ )
  46.         if(dist[i] > dist[u])
  47.             u = i;
  48.  
  49.     int s = dist[u]; // s就是树的直径
  50.     printf("%lld\n",s * 10 + s * (s + 1ll) / 2); // 注意最坏情况下爆int
  51.  
  52.     return 0;
  53. }

贪心

股票买卖

  1. #include<iostream>
  2. using namespace std;
  3. const int maxn = 100010;
  4. int f[maxn];
  5.  
  6. int main()
  7. {
  8.     int n;
  9.     cin>>n;
  10.     for(int i=0;i<n;++i) cin>>f[i];
  11.  
  12.     int ans = 0;
  13.     for(int i=0;i<n-1;++i)
  14.     {
  15.         ans += max(0,f[i+1]-f[i]);
  16.     }
  17.  
  18.     cout<<ans<<endl;
  19. }

货仓选址

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4.  
  5. using namespace std ;
  6.  
  7. typedef long long LL ;
  8. const int N = 100010 ;
  9.  
  10. int q[N] ;
  11. int n ;
  12.  
  13. int main(){
  14.     cin >> n ;
  15.  
  16.     for(int i=1;i<=n;i++){
  17.         cin >> q[i] ;
  18.     }
  19.  
  20.     sort(q+1,q+1+n) ;
  21.     LL res = 0 ;
  22.  
  23.     for(int i=1;i<=n;i++){
  24.         res += abs(q[i]-q[(n+1)/2]) ;
  25.     }
  26.  
  27.     cout << res << endl ;
  28.  
  29.     return 0 ;
  30. }

糖果传递

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long LL;
  9.  
  10. const int N = 1000010;
  11.  
  12. int n;
  13. int a[N];
  14. LL c[N];
  15.  
  16. int main() {
  17.     scanf("%d", &n);
  18.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  19.  
  20.     LL sum = 0;
  21.     for (int i = 1; i <= n; i++) sum += a[i];
  22.  
  23.     LL avg = sum / n;
  24.     for (int i = n; i > 1; i--) {
  25.         c[i] = c[i + 1] + avg - a[i];
  26.     }
  27.     c[1] = 0;
  28.  
  29.     sort(c + 1, c + n + 1); // 将数轴上所有点排序
  30.  
  31.     LL res = 0;
  32.     for (int i = 1; i <= n; i++) res += abs(c[i] - c[(n + 1) / 2]); //距离和
  33.  
  34.     printf("%lld\n", res);
  35.  
  36.     return 0;
  37. }

雷达设备

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<double, double> PDD;
  9. const int N = 1010;
  10. const double eps = 1e-6, INF = 1e10;
  11.  
  12. int n, d;
  13. PDD seg[N];
  14.  
  15. int main()
  16. {
  17.     cin >> n >> d;
  18.  
  19.     bool success = true;
  20.  
  21.     for (int i = 0; i < n; i ++ )
  22.     {
  23.         int x, y;
  24.         cin >> x >> y;
  25.         if (y > d)
  26.         {
  27.             success = false;
  28.             break;
  29.         }
  30.         auto len = sqrt(d * d - y * y);
  31.         seg[i] = {x + len, x - len};
  32.     }
  33.  
  34.     if (!success) puts("-1");
  35.     else
  36.     {
  37.         sort(seg, seg + n);
  38.         int res = 0;
  39.         double last = -INF;
  40.         for (int i = 0; i < n; i ++ )
  41.         {
  42.             if (seg[i].second > last + eps)
  43.             {
  44.                 res ++ ;
  45.                 last = seg[i].first;
  46.             }
  47.         }
  48.         cout << res << endl;
  49.     }
  50.     return 0;
  51. }

付账问题

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. int n;
  9. double s;
  10. int a[500010];
  11.  
  12. int main()
  13. {
  14.     scanf("%d %lf", &n, &s);
  15.     for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  16.  
  17.     sort(a, a + n);
  18.  
  19.     double ave = s / n, sum = 0;
  20.     for (int i = 0; i < n; i++)
  21.     {
  22.         double cur=s/(n-i);
  23.         if (a[i] < cur) cur=a[i];
  24.         
  25.         s -= cur;
  26.         sum += (cur - ave) * (cur - ave); 
  27.     }
  28.  
  29.     printf("%.4lf\n", sqrt(sum / n));
  30.     return 0;
  31. }

乘积最大

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. typedef long long LL ;
  7. const int N = 100010 , mod = 1000000009 ;
  8. int a[N];
  9.  
  10.  
  11. int main()
  12. {
  13.     int n , k ;
  14.     scanf("%d%d",&n,&k);
  15.     for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);
  16.  
  17.     sort(a,a + n);
  18.  
  19.     LL res = 1 ; //乘积初始化
  20.     int l = 0 , r = n - 1 ;//双指针初始化
  21.     int sign = 1 ; // 符号初始化
  22.  
  23.     //由于4种情况除了 k 是奇数且 k < n 的时候需要特判一下处理一下符号 ,其他的时候都可以转化为双指针做法
  24.     //k 是奇数是先选出最大的数, k-- 就是偶数,两边再同时取对,转化成相同的双指针做法
  25.     if(k % 2 )
  26.     {
  27.         res =  a[r--]; // 取出最大的一个数，右指针移动
  28.         k -- ; //个数减1
  29.  
  30.         if(res < 0) sign = -1;  // 如果最大值都是负数,就证明全是负数,那么符号要发生改变
  31.     }
  32.     while(k) // 双指针做法
  33.     {
  34.         LL x = (LL)a[l] * a[l + 1] , y = (LL)a[r] * a[r - 1];//两边同时取对
  35.         //选择更大的一对,和归并排序思路相近
  36.         if(x * sign > y * sign)
  37.         {
  38.             res = x % mod * res % mod; // 需要注意的是 :不可以写成(x * res) % mod ,也不可以写成是 res % mod * x % mod
  39.                                        // 因为x最大是 10^10，如果不先取模的话，和res相乘的结果最大是 10^19,会暴long long。            
  40.             l += 2; // 指针移动                                 
  41.         }
  42.         else 
  43.         {
  44.             res = y % mod * res % mod; 
  45.             r -= 2; 
  46.         }
  47.         k -= 2; 
  48.     }
  49.     printf("%lld",res);
  50.     return 0;
  51. }

后缀表达式

  1. #include<iostream>
  2. #include<algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int N=2E5+10;//因为数据总量实际是M+N+1
  7. int a[N];
  8.  
  9. int main()
  10. {
  11.     int m,n;
  12.     cin>>n>>m;
  13.     int k = m+n+1;
  14.  
  15.     for(int i=0;i<k;i++)cin>>a[i];//读入数据
  16.     sort(a,a+k);
  17.  
  18.     long long res=0;
  19.     if(!m)for(int i=0;i<k;i++)res+=a[i];//如果没有-号
  20.     else 
  21.     {
  22.         res=a[k-1]-a[0];
  23.         for(int i=1;i<k-1;i++)res+=abs(a[i]);
  24.     }
  25.  
  26.     cout<<res;
  27.     return 0;
  28. }

灵能传输（P）

  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. typedef long long LL;
  6.  
  7. const int N = 3e5 + 10;
  8.  
  9. int t, n;
  10. LL s[N], a[N]; // s为前缀和数组 a为存放前缀和顺序的数组
  11. bool st[N];
  12.  
  13. int main()
  14. {
  15.     cin >> t;
  16.     while (t--)
  17.     {
  18.         cin >> n;
  19.         memset(st, 0, sizeof st);
  20.         for (int i = 1; i <= n; i++)
  21.             cin >> s[i], s[i] += s[i - 1];
  22.         LL s0 = s[0], sn = s[n];
  23.         if (s0 > sn)
  24.             swap(s0, sn);
  25.         sort(s, s + n + 1);
  26.         // 寻找排完序后s0和sn的位置
  27.         // 如果s0和sn相同的话则前面的为s0 后面的为sn
  28.         for (int i = 0; i <= n; i++)
  29.             if (s[i] == s0)
  30.             {
  31.                 s0 = i;
  32.                 break;
  33.             }
  34.         for (int i = n; i >= 0; i--)
  35.             if (s[i] == sn)
  36.             {
  37.                 sn = i;
  38.                 break;
  39.             }
  40.         int l = 0, r = n;
  41.         for (int i = s0; i >= 0; i -= 2)
  42.         {
  43.             a[l++] = s[i];
  44.             st[i] = 1;
  45.         }
  46.         for (int i = sn; i <= n; i += 2)
  47.         {
  48.             a[r--] = s[i];
  49.             st[i] = 1;
  50.         }
  51.         for (int i = 0; i <= n; i++)
  52.             if (!st[i])
  53.                 a[l++] = s[i];
  54.         LL res = 0;
  55.         for (int i = 1; i <= n; i++)
  56.             res = max(res, abs(a[i] - a[i - 1]));
  57.         cout << res << endl;
  58.     }
  59.     return 0;
  60. }

数论

等差数列

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 100010;
  8.  
  9. int a[N];
  10.  
  11. //求最大公约数
  12. int gcd(int a, int b){
  13.     return b ? gcd(b, a % b) : a;
  14. }
  15.  
  16. int main(){
  17.     int n;
  18.     scanf("%d", &n);
  19.  
  20.     for(int i = 0; i < n; i ++){
  21.         scanf("%d", &a[i]);
  22.     }
  23.  
  24.     sort(a, a + n);
  25.  
  26.     //求后面各项与第一项所有差值的最大公约数
  27.     int d = 0;
  28.     for(int i = 1; i < n; i ++) d = gcd(d, a[i] - a[0]);
  29.  
  30.     if(!d) printf("%d\n", n);
  31.     else printf("%d\n", (a[n - 1] - a[0]) / d + 1);
  32.  
  33.     return 0;
  34. }
用到的数论知识：辗转相除法

辗转相除法（gcd）求两个数的最大公约数_gcd辗转相除法-CSDN博客

算法：辗转相除算法

X的因子链

  1. #include<cstdio>
  2.  
  3. typedef long long ll;
  4.  
  5. const int N = (1 << 20) + 10;
  6.  
  7. int primes[N];// 存质数
  8. int min_p[N]; //存最小质因子
  9. int cnt;
  10. bool st[N]; // 表示对应元素是否被筛过
  11.  
  12. // 线性筛法(欧拉筛法)
  13. void get_primes(int n) 
  14. {
  15.     for (int i = 2; i <= n; i++) 
  16.     {
  17.         if (!st[i]) 
  18.         {
  19.             min_p[i] = i;
  20.             primes[++cnt] = i;
  21.         }
  22.         for (int j = 1; primes[j] * i <= n; j++) 
  23.         {
  24.             int t = primes[j] * i;
  25.             st[t] = true; //标记合数
  26.             min_p[t] = primes[j];
  27.  
  28.             if (i % primes[j] == 0) 
  29.             {
  30.                 //如果i是前面某个素数的倍数时, 说明i以后会由某个更大的数乘这个小素数筛去
  31.                 //同理, 之后的筛数也是没有必要的, 因此在这个时候, 就可以跳出循环了
  32.                 break;
  33.             }
  34.         }
  35.     }
  36. }
  37. int sum[N]; //记录每个质因子出现的次数
  38.  
  39. int main()
  40.  {
  41.     get_primes(N);
  42.     int x;
  43.  
  44.     while (scanf("%d", &x) != EOF) 
  45.     {
  46.         //tol用于记录最大长度,k表示第i个质因子的下标, 从0开始
  47.         int k = 0, tol = 0;
  48.  
  49.         // 依次处理各个质因子, 求出对应质因子出现的次数
  50.         while (x > 1)
  51.         {
  52.             int p = min_p[x]; // 通过while, 依次取出最小质因子
  53.             sum[k] = 0;
  54.  
  55.             //处理当前质因子, 求其出现的次数
  56.             while (x % p == 0) 
  57.             {
  58.                 sum[k]++;
  59.                 tol++;
  60.                 x /= p;
  61.             }
  62.  
  63.             k++; // 准备处理下一个质因子
  64.             /*
  65.              例:
  66.                 x=12 --> 3*2^2
  67.                 p = 2
  68.                 sum[1]=1
  69.                 x=6
  71.                 sum[1]=2
  72.                 x=3
  73.                 ****************
  74.                 p=3
  75.                 sum[2]=1
  76.                 x=1 --> 结束
  77.              */
  78.         }
  79.  
  80.         //求所有质因子出现总次数的全排列
  81.         ll res = 1;
  82.         for (int i = 2; i <= tol; i++)  res *= i; // tol!
  83.         //去除各个质因子重复出现的次数
  84.         for (int i = 0; i < k; i++)
  85.             for (int j = 1; j <= sum[i]; j++) res /= j;
  86.  
  87.         printf("%d %lld\n", tol, res); //输出最长序列的长度, 以及满足最大长度的序列的个数
  88.     }
  89.  
  90.     return 0;
  91. }
用到的数论知识：算数基本定理

算术基本定理 - gongpixin - 博客园 (cnblogs.com)

算法：线性筛法

 聪明的燕姿

  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 50000;//N = sqrt(2e9)
  7. bool st[N];
  8. int primes[N],cnt = 0;//线性筛
  9. int S,res[N],len;
  10.  
  11. void get_primes(int n)
  12. {
  13.     for(int i = 2;i <= n;i++)
  14.     {
  15.         if(!st[i]) primes[cnt++] = i;
  16.         for(int j = 0;primes[j]*i <= n;j++)
  17.         {
  18.             st[primes[j]*i] = true;
  19.             if(i % primes[j] == 0) break;
  20.         }
  21.     }
  22. }
  23.  
  24. int is_prime(int n)
  25. {
  26.     if(n < N) return !st[n];//没有被筛过说明就是质数，返回true
  27.     for(int i = 0;primes[i] <= n / primes[i];i++)
  28.     {
  29.         if(n % primes[i] == 0) return false;
  30.     }
  31.     return true;
  32. }
  33.  
  34. void dfs(int last,int product,int S)//last表示上一个用的质数的下标是什么,product当前最高次项的结果,S表示每次处理后剩余多少
  35. {
  36.     if(S == 1)
  37.     {
  38.         res[len++] = product;
  39.         return ;
  40.     }
  41.     //比如20 = 2^2 * 5
  42.     //N = P1^a1 * P2^a2 * ... * Pn^an
  43.     //S = (1+p1+p1^2+...+p1^a1)(1+p2+p2^2+...+p2^a2)...(1+pn+pn^2+...+pn^an)
  44.     //42 = (1 + 2 + 2^2)*(1 + 5),其中2^2和5就分别是最高次项p1^2*p2^1
  45.     if(S-1 > ((last < 0) ? 0 : primes[last]) && is_prime(S-1)) 
  46.         res[len++] = product * (S-1);
  47.  
  48.     for(int i = last+1;primes[i] <= S / primes[i];i++)
  49.     {
  50.         int p = primes[i];
  51.  
  52.         for(int j = 1+p,t = p;j <= S;t *= p,j += t)
  53.         {
  54.             if(S % j == 0) dfs(i,product*t,S/j);
  55.         }
  56.     }
  57. }
  58.  
  59. int main()
  60. {
  61.     get_primes(N-1);
  62.     while(cin>>S)
  63.     {
  64.         len = 0;
  65.         dfs(-1,1,S);
  66.  
  67.         sort(res,res+len);
  68.  
  69.         cout << len << endl;
  70.         if (len)
  71.         {
  72.             sort(res, res + len);
  73.             for (int i = 0; i < len; i ++ ) cout << res[i] << ' ';
  74.             cout << endl;
  75.         }
  76.     }
  77.     return 0;
  78. }

五指山

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. using namespace std;
  5.  
  6. typedef long long LL;
  7.  
  8. LL exgcd(LL a,LL b,LL &x,LL &y)//拓展欧几里得算法
  9. {
  10.     if(!b)
  11.     {
  12.         x = 1,y = 0;
  13.         return a;
  14.     }
  15.  
  16.     int d = exgcd(b,a%b,y,x);
  17.     y -= a/b*x;
  18.     return d;
  19. }
  20.  
  21. int main()
  22. {
  23.     int T;
  24.     scanf("%d",&T);
  25.  
  26.     while(T--)
  27.     {
  28.         LL n,d,x,y,a,b;
  29.         scanf("%lld%lld%lld%lld",&n,&d,&x,&y);
  30.  
  31.         int gcd = exgcd(n,d,a,b);
  32.  
  33.         if((y-x)%gcd)
  34.         {
  35.             printf("Impossible\n");
  36.         }
  37.         else
  38.         {
  39.             b*=(y-x)/gcd;
  40.             n/=gcd;
  41.             printf("%lld\n",(b%n+n)%n);
  42.         }
  43.     }
  44.  
  45.     return 0;
  46. }
用到的数论知识：裴蜀定理（扩展欧几里得定理）

数论基础——扩展欧几里得【详细】_欧几里得引理-CSDN博客

算法：扩展欧几里得算法

最大比例(P)

  1. #include<iostream>
  2. #include<algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int N=110;
  7.  
  8. typedef long long LL;
  9.  
  10. LL x[N],a[N],b[N];
  11. int cnt=0;
  12.  
  13. //假设原数列为 a,a*(p/q)^1,a*(p/q)^2,...,a*(p/q)^(n-1)
  14. //假设抽取的数列  b0,b1,...,b(N-1)  (从小到大排好序了)
  15. //  b1/b0,b2/b0,...,b(N-1)/b0-->  (p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)
  16. //  我们要求的是：  （p/q）^k  (p/q)>1,所以使k最大，即求 x1~x(N-1)的最大公约数
  17. //这里我们使用更相减损术，因为我们没有得到确切的x1~x(N-1)是多少，我们只有(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)这些的值
  18.  
  19. /*更相减损术：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
  20. 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
  21. 则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。*/
  22.  
  23. //更相减损术总用较大的减去较小的
  24. /*例子：
  25.     98-63=35
  26.     63-35=28
  27.     35-28=7
  28.     28-7=21
  29.     21-7=14
  30.     14-7=7
  31. 所以，98和63的最大公约数等于7。*/
  32.  
  33. //我们这里要用更相减损术的是指数，所以要让(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)，两两计算，互除，除到结果为1,即x1=x2,此时幂次为0，结果为1，这其实就是y总的思路，再次感叹y总的才华
  34. //把分子分母分别去算，结果是相同的因为，分子分母的幂次是相同的
  35. LL gcd(LL a,LL b)
  36. {
  37.     return b? gcd(b,a%b):a;
  38. }
  39.  
  40. LL gcd_sub(LL a,LL b)  
  41. {
  42.     if(a<b)  swap(a,b);  //更相减损术总是大减小（它们的底数是一样的）
  43.     if(b==1)  return a;
  44.     return gcd_sub(b,a/b);
  45. }
  46.  
  47. int main()
  48. {
  49.     int n;
  50.     cin>>n;
  51.  
  52.     for(int i=0; i<n; i++)  scanf("%lld",&x[i]);
  53.  
  54.     sort(x,x+n);
  55.  
  56.     for(int i=1; i<n; i++)
  57.     {
  58.         if(x[i] != x[i-1])
  59.         {
  60.             LL d=gcd(x[i],x[0]);  
  61.             a[cnt]=x[i] / d;  //得到x[i]/x[0]的分子
  62.             b[cnt]=x[0] / d;  //得到x[i]/x[0]的分母
  63.             cnt++;
  64.         }
  65.     }
  66.  
  67.     LL up=a[0],down=b[0];
  68.  
  69.     for(int i=1; i<cnt; i++)
  70.     {
  71.         up=gcd_sub(up,a[i]);  //两两求最大公约数
  72.         down=gcd_sub(down,b[i]);
  73.     }
  74.  
  75.     cout<<up<<"/"<<down<<endl;
  76.  
  77.   
  78. }
用到的数论知识：更相减损术，欧几里得算法

C语言 用更相减损术求最大公约数，最小公倍数_最小公倍数c语言 更像减损-CSDN博客

C循环（P）

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4.  
  5. typedef long long LL;
  6.  
  7. LL exgcd (LL &x,LL &y,LL a,LL b)
  8. {
  9.     if (!b) 
  10.     {
  11.         x = 1,y = 0;
  12.         return a;
  13.     }
  14.  
  15.     LL d = exgcd (y,x,b,a % b);
  16.     y -= a / b * x;
  17.  
  18.     return d;
  19. }
  20.  
  21. int main () 
  22. {
  23.     LL a,b,c,k;
  24.     while (cin >> a >> b >> c >> k,a || b || c || k) 
  25.     { //注意要用或者，否则会提前退出的，(POJ没有样例，acwing看到数据才知道)
  26.         LL x,y;
  27.         LL gcd = exgcd (x,y,c,1ll << k);
  28.         LL mod = (1ll << k) / gcd;
  29.  
  30.         if ((b - a) % gcd) puts ("FOREVER");
  31.         else cout << ((x * (b - a) / gcd) % mod + mod) % mod << endl;
  32.     }
  33.  
  34.     return 0;
  35. }
用到的数论知识：扩展欧几里得算法

正则问题（P）

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std ;
  6.  
  7. int k ;
  8. string str ;
  9.  
  10. int dfs()
  11. {
  12.     int res = 0 ;
  13.  
  14.     while(k<str.size())
  15.     {
  16.         if(str[k] == '(')
  17.         {
  18.             k ++ ;
  19.             res += dfs() ;
  20.             k ++ ;
  21.         }
  22.         else if(str[k] == ')')
  23.         {
  24.             // k ++ ;
  25.             break ;
  26.         }
  27.         else if(str[k] == '|')
  28.         {
  29.             k ++ ;
  30.             res = max(res,dfs()) ;
  31.         }
  32.         else
  33.         {
  34.             k ++ ;
  35.             res ++ ;
  36.         }
  37.     }
  38.  
  39.     return res ;
  40. }
  41.  
  42. int main()
  43. {
  44.     cin >> str ;
  45.  
  46.     cout << dfs() << endl ;
  47.  
  48.     return 0 ;
  49.  
  50. }

糖果（P）

  1. //时间复杂度为O(n * 2^m) 为1e8勉强能过
  2. //状态表示：dp[i][s]为从前i个糖果中选,选出来的糖果种类状态为s的所需最少糖果数量
  3. //阶段划分：类似于01背包问题中，从前i个物品中选
  4. //转移方程：划分依据：对于第i个物品选还是不选
  5. //dp[i][s] = min(dp[i-1][s],dp[i-1][s & (~w[i])] + 1) 
  6. //dp[i-1][s]好说 表示不选第i个物品
  7. //关键是dp[i-1][s & (~w[i])]，举个例子若现在s为 11011，表示已经选出来的糖果种类为1,2,8,16
  8. //假设第i包糖果的状态为01011，那么他是从10000这个状态转移过来的
  9. //那么s & (~w[i])的目的就是先将w[i]的糖果种类去掉,~w[i]按位取非,在与s相于就行了，实质上就是s & (w[i]在s中的补集)
  10.  
  11. //边界:dp初始化为INF dp[0][0] = 0;
  12. //目标:dp[n][(1<<m)-1]
  13. #include <iostream>
  14. #include <cstring>
  15. #include <algorithm>
  16.  
  17. using namespace std;
  18. const int N = 110,M = 1 << 20,INF = 0x3f3f3f3f;
  19. int w[N],dp[M],n,m,k;//注意优化成一维不然暴空间
  20. int main(void)
  21. {
  22.     cin>>n>>m>>k;
  23.     for(int i = 1;i<=n;i++) 
  24.         for(int j = 1;j<=k;j++)
  25.         {
  26.             int num;
  27.             cin>>num;
  28.             w[i] |= (1 << num - 1);//将每一件糖果所包含的糖果种类压缩
  29.         }
  30.  
  31.     memset(dp,0x3f,sizeof dp);
  32.  
  33.     dp[0] = 0;
  34.  
  35.     for(int i = 1;i<=n;i++)
  36.         for(int s = 0;s < (1 << m);s ++) dp[s] = min(dp[s],dp[s & (~w[i])] + 1);
  37.  
  38.     if(dp[(1<<m)-1] == INF) cout<<-1<<endl;
  39.     else cout<<dp[(1<<m) - 1]<<endl;
  40.  
  41.     return 0;
  42. }

复杂DP

背包九讲

背包问题汇总参考：背包九讲——全篇详细理解与代码实现-CSDN博客

01背包

最基础DP解法：

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 1010;
  10. int w[N], v[N];
  11. int n, m;
  12. int x[N][N];
  13.  
  14. int main()
  15. {
  16. 	cin >> n >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);
  19.  
  20. 	for (int i = 1; i <= n; i++)
  21. 	{
  22. 		for (int j = 1; j <= m; j++)
  23. 		{
  24. 			x[i][j] = x[i - 1][j];
  25. 			if (j >= v[i]) x[i][j] = max(x[i][j], x[i - 1][j - v[i]] + w[i]);
  26. 		}
  27. 	}
  28.  
  29. 	cout << x[n][m];
  30. }

空间优化：把结果数组x[N][N]从二维数组优化为一维数组

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 1010;
  10. int w[N], v[N];
  11. int n, m;
  12. int x[N];
  13.  
  14. int main()
  15. {
  16. 	cin >> n >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);
  19.  
  20. 	for (int i = 1; i <= n; i++)
  21. 		for (int j = m; j >= v[i]; j--)
  22. 			x[j] = max(x[j], x[j - v[i]] + w[i]);
  23.  
  24. 	cout << x[m];
  25. }

思路参考： AcWing 2. 01背包问题 - AcWing

完全背包

最基础DP解法：(数字太大会超时)

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 1010;
  10. int w[N], v[N];
  11. int n, m;
  12. int x[N][N];
  13.  
  14. int main()
  15. {
  16. 	cin >> n >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);
  19.  
  20. 	for (int i = 1; i <= n; i++)
  21. 		for (int j = 1; j <= m; j++)
  22. 			for(int k = 0; k <= j/v[i]; k++)
  23. 			    x[i][j] = max(x[i][j], x[i - 1][j - k * v[i]] + k * w[i]);
  24.  
  25. 	cout << x[n][m];
  26. }

时间空间优化：省去第三重循环，把结果数组x[N][N]从二维数组优化为一维数组

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 1010;
  10. int w[N], v[N];
  11. int n, m;
  12. int x[N];
  13.  
  14. int main()
  15. {
  16. 	cin >> n >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);
  19.  
  20. 	for (int i = 1; i <= n; i++)
  21. 		for (int j = v[i]; j <= m; j++)
  22. 				x[j] = max(x[j], x[j - v[i]] + w[i]);
  23.  
  24. 	cout << x[m];
  25. }

思路参考：AcWing 3. 完全背包问题（逐步优化） - AcWing

多重背包1

数据范围很小，不需做优化，只需要在完全背包代码上加一层判断条件

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 1010;
  10. int w[N], v[N], s[N];
  11. int n, m;
  12. int x[N][N];
  13.  
  14. int main()
  15. {
  16. 	cin >> n >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++) scanf("%d %d %d", &v[i], &w[i], &s[i]);
  19.  
  20. 	for (int i = 1; i <= n; i++)
  21. 		for (int j = 1; j <= m; j++)
  22. 			for (int k = 0; k <= j / v[i] && k <= s[i]; k++)
  23. 				x[i][j] = max(x[i][j], x[i - 1][j - k * v[i]] + k * w[i]);
  24.  
  25. 	cout << x[n][m];
  26. }
多重背包2

数据范围变大，需要进行二进制优化以缩短时间复杂度

优化思路是将多重背包问题转化为01背包问题（将s[i]个第i个物品变为排列开的1，2，4，8，16……个第i个物品的集合），通过二进制来处理，例如将15个第2个物品变为1，2，4，8这4个i物品的集合

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 12010, M = 2010;
  10. int w[N], v[N];
  11. int n, m;
  12. int f[M];
  13.  
  14. int main()
  15. {
  16. 	cin >> n >> m;
  17.  
  18. 	int a, b, c;
  19. 	int cnt = 0;
  20. 	for (int i = 1; i <= n; i++)//通过二进制将多重背包问题转化为01背包
  21. 	{
  22. 		scanf("%d %d %d", &a, &b, &c);
  23.  
  24. 		int flag = 1;
  25. 		while (flag <= c)
  26. 		{	
  27. 			v[++cnt] = a * flag;
  28. 			w[cnt] = b * flag;
  29.  
  30. 			c -= flag;
  31. 			flag *= 2;
  32. 		}
  33.  
  34. 		if (c)
  35. 		{
  36. 			v[++cnt] = c * a;
  37. 			w[cnt] = c * b;
  38. 		}
  39. 	}
  40.  
  41. 	n = cnt;
  42. 	
  43. 	for (int i = 1; i <= n; i++)//进行01背包解法
  44. 		for (int j = m; j >= v[i]; j--)
  45. 			f[j] = max(f[j], f[j - v[i]] + w[i]);
  46.  
  47. 	cout << f[m];
  48. }

思路参考：AcWing 5. 二进制优化，它为什么正确，为什么合理，凭什么可以这样分？？ - AcWing

多重背包3

数据范围巨大，进行空间时间上的优化

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 20010;
  10. int n, m;
  11. int f[N], cop[N], q[N];
  12.  
  13. int main()
  14. {
  15. 	cin >> n >> m;
  16.  
  17. 	for (int i = 1; i <= n; i++)
  18. 	{
  19. 		memcpy(cop, f, sizeof f);
  20. 		int v, w, s;
  21. 		scanf("%d %d %d", &v, &w, &s);
  22.  
  23. 		for (int j = 0; j < v; j++)
  24. 		{
  25. 			int tail = -1, head = 0;
  26.  
  27. 			for (int k = j; k <= m; k += v)
  28. 			{
  29. 				if (head <= tail && k - s * v > q[head]) head++;
  30. 				if (head <= tail) f[k] = max(cop[k], cop[q[head]] + (k - q[head]) / v * w);
  31. 				while (head <= tail && cop[k] >= cop[q[tail]] + (k - q[tail]) / v * w) tail--;
  32. 				q[++tail] = k;
  33. 			}
  34. 		}
  35. 	}
  36.  
  37. 	cout << f[m];
  38. }

思路参考：


AcWing 6. 多重背包问题 III 详解 + yxc大佬代码解读 - AcWing

E13 背包DP 多重背包 单调队列优化_哔哩哔哩_bilibili

混合背包问题

 将三种背包问题（01，完全，多重）都转化为多重背包2

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 10100;
  10. int n, m;
  11. int f[N], v[N], w[N], cnt;
  12.  
  13. int main()
  14. {
  15. 	int a, b, s;
  16. 	cin >> n >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++)
  19. 	{
  20. 		scanf("%d %d %d", &a, &b, &s);
  21. 		if (!s) s = m / a;//如果是完全背包，那么s=m/a,即1取上限
  22. 		else if (s < 0) s = 1;//如果是01背包，那么s=1
  23.  
  24. 		int flag = 1;
  25. 		while(flag <= s)
  26. 		{
  27. 			v[++cnt] = a * flag;
  28. 			w[cnt] = b * flag;
  29.  
  30. 			s -= flag;
  31. 			flag *= 2;
  32. 		}
  33.  
  34. 		if (s)
  35. 		{
  36. 			v[++cnt] = a * s;
  37. 			w[cnt] = b * s;
  38. 		}
  39. 	}
  40.  
  41. 	n = cnt;
  42.  
  43. 	for (int i = 1; i <= n; i++)
  44. 		for (int j = m; j >= v[i]; j--)
  45. 			f[j] = max(f[j], f[j - v[i]] + w[i]);
  46.  
  47. 	cout << f[m];
  48. }

或者是把计算f[]的循环写到第一个for循环里面，看起来会干净一点

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 10100;
  10. int n, m;
  11. int f[N], v[N], w[N], cnt;
  12.  
  13. int main()
  14. {
  15. 	int a, b, s;
  16. 	cin >> n >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++)
  19. 	{
  20. 		scanf("%d %d %d", &a, &b, &s);
  21. 		if (!s) s = m / a;
  22. 		else if (s < 0) s = 1;
  23.  
  24. 		int flag = 1, pre = cnt;
  25. 		while(flag <= s)
  26. 		{
  27. 			v[++cnt] = a * flag;
  28. 			w[cnt] = b * flag;
  29.  
  30. 			s -= flag;
  31. 			flag *= 2;
  32. 		}
  33.  
  34. 		if (s)
  35. 		{
  36. 			v[++cnt] = a * s;
  37. 			w[cnt] = b * s;
  38. 		}
  39.  
  40. 		for(int j=pre+1;j<=cnt;j++)
  41. 			for (int k = m; k >= v[j]; k--)
  42. 				f[k] = max(f[k], f[k - v[j]] + w[j]);
  43. 	}
  44.  
  45. 	cout << f[m];
  46. }

思路参考：AcWing 7. 混合背包问题 - AcWing

二维背包的费用问题

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 1010;
  10. const int M = 110;
  11. int n, v, m;
  12. int f[M][M];
  13.  
  14. int main()
  15. {
  16. 	cin >> n >> v >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++)
  19. 	{
  20. 		int v1, m1, w1;
  21. 		scanf("%d %d %d", &v1, &m1, &w1);
  22.  
  23. 		for (int j = v; j >= v1; j--)
  24. 			for (int k = m; k >= m1; k--)
  25. 				f[j][k] = max(f[j][k], f[j - v1][k - m1] + w1);
  26. 	}
  27.  
  28. 	cout << f[v][m];
  29. }

直接把一维情况下的进行简单拓展处理就可以

分组背包问题

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 110;
  10. int n, m, v[N][N], w[N][N], s[N];
  11. int f[N][N];
  12.  
  13.  
  14. int main()
  15. {
  16. 	cin >> n >> m;
  17.  
  18. 	for (int i = 1; i <= n; i++)
  19. 	{
  20. 		scanf("%d", &s[i]);
  21. 		for (int j = 1; j <= s[i]; j++) scanf("%d %d", &v[i][j], &w[i][j]);
  22. 	}
  23.  
  24. 	for (int i = 1; i <= n; i++)
  25. 	{
  26. 		for (int j = 1; j <= m; j++)
  27. 		{
  28. 			f[i][j] = f[i - 1][j];
  29. 			for (int k = 1; k <= s[i]; k++)
  30. 			{
  31. 				if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
  32. 			}
  33. 		}
  34. 	}
  35.  
  36. 	cout << f[n][m];
  37. }

类比为多重背包1就可以，只是每组里面的各物品数值不一样

有依赖的背包问题

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 110;
  10. int n, m, v[N], w[N];
  11. int f[N][N],root;
  12. vector<int> tr[N];
  13.  
  14. void Find(int u)
  15. {
  16. 	for (int i = v[u]; i <= m; i++) f[u][i] = w[u];
  17.  
  18. 	for (int i = 0; i < tr[u].size(); i++)
  19. 	{
  20. 		int son = tr[u][i];
  21. 		Find(son);
  22.  
  23. 		for (int j = m; j >= v[son]; j--)
  24. 		{
  25. 			for (int k = 0; k <= j - v[u]; k++)
  26. 			{
  27. 				f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
  28. 			}
  29. 		}
  30. 	}
  31. }
  32.  
  33. int main()
  34. {
  35. 	cin >> n >> m;
  36.  
  37. 	int c;
  38. 	for (int i = 1; i <= n; i++)
  39. 	{
  40. 		cin >> v[i] >> w[i] >> c;
  41.  
  42. 		if (c == -1) root = i;
  43. 		else tr[c].push_back(i);
  44. 	}
  45.  
  46. 	Find(root);
  47.  
  48. 	cout << f[root][m];
  49. }

思路参考：

AcWing 10. 有依赖的背包问题（思路不同于dxc，但是个人感觉更好理解） - AcWingAcWing 10. 有依赖的背包问题 - 哔哩哔哩 (bilibili.com)

背包问题求方案数

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 1010, mod = 1e9 + 7;
  10. int n, m;
  11. int f[N], cnt[N];
  12.  
  13. int main()
  14. {
  15. 	cin >> n >> m;
  16. 	for (int i = 0; i <= m; i++) cnt[i] = 1;
  17.  
  18. 	int v, w;
  19. 	for (int i = 1; i <= n; i++)
  20. 	{
  21. 		scanf("%d %d", &v, &w);
  22.  
  23. 		for (int j = m; j >= v; j--)
  24. 		{
  25. 			int temp = f[j - v] + w;
  26. 			if (temp > f[j])
  27. 			{
  28. 				f[j] = temp;
  29. 				cnt[j] = cnt[j - v];
  30. 			}
  31. 			else if (temp == f[j])
  32. 				cnt[j] = (cnt[j - v] + cnt[j]) % mod;
  33. 		}
  34. 	}
  35.  
  36. 	cout << cnt[m];
  37. }

思路参考：

AcWing 11. 背包问题求方案数 - AcWing

背包问题求具体方案

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1010;
  6.  
  7. int n, m;
  8. int w[N], v[N];
  9. int f[N][N];
  10. int path[N], cnt;
  11.  
  12. int main()
  13. {
  14.     cin >> n >> m;
  15.     for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
  16.     for (int i = n; i >= 1; -- i)
  17.     {
  18.         for (int j = 0; j <= m; ++ j)
  19.         {
  20.             f[i][j] = f[i + 1][j];
  21.             if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
  22.         }
  23.     }
  24.     for (int i = 1, j = m; i <= n; ++ i)
  25.     {
  26.         if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
  27.         {
  28.             path[cnt ++ ] = i;
  29.             j -= v[i];
  30.         }
  31.     }
  32.     for (int i = 0; i < cnt; ++ i) cout << path[i] << " ";
  33.     cout << endl;
  34.     return 0;
  35. }

思路参考：

AcWing 12. 背包问题求具体方案【01背包 + 背包DP输出方案】 - AcWing

鸣人的影分身

  1. #include<iostream>
  2. using namespace std;
  3. const int N = 15;
  4. int f[N][N];
  5. int m,n;
  6. int T;
  7. int main()
  8. {
  9.     cin>>T;
  10.     while(T--)
  11.     {
  12.         cin>>m>>n;
  13.         for(int i=0;i<=n;++i)f[0][i]=1;
  14.         for(int i=1;i<=m;++i)
  15.         {
  16.             for(int j=1;j<=n;++j)
  17.             {
  18.                 f[i][j]=f[i][j-1];
  19.                 if(i-j>=0)
  20.                     f[i][j]+=f[i-j][j];
  21.             }
  22.         }
  23.         cout<<f[m][n]<<endl;
  24.     }
  25.     return 0;
  26. }

DP思路：

糖果

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6.  
  7. const int N = 100 + 5;
  8. int n, k, w[N];
  9. //dp(i, j)代表前i个物品 总价值%k=j的集合
  10. int dp[N][N];
  11.  
  12. int main(void)
  13. {
  14.     cin >> n >> k;
  15.     for (int i = 1; i <= n; ++i) cin >> w[i];
  16.     for (int i = 0; i < N; ++i)
  17.         for (int j = 0; j < N; ++j)
  18.             dp[i][j] = INT_MIN;
  19.  
  20.     //dp(0 ,i) (i != 1)都是不存在的状态，所以必须要初始化为负无穷，不然的话可以选择先初始化第一件物品的所有情况，再迭代第二个物品之后
  21.     //dp(i ,j) <-  max(dp(i - 1, j), dp(i - 1, (j - w[i]) % k) + w[i])
  22.     // (s + w[i]) % k = j -> s % k = (j - w[i]) % k
  23.  
  24.     dp[0][0] = 0;
  25.     for (int i = 1; i <= n; ++i)
  26.     {
  27.         for (int j = 0; j <= k - 1; ++j)
  28.             dp[i][j] = max(dp[i - 1][j], dp[i - 1][((j - w[i]) % k + k) % k] + w[i]);
  29.     }
  30.  
  31.     cout << dp[n][0];
  32.     return 0;
  33. }

DP思路：

密码脱落

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1010;
  8.  
  9. char s[N];
  10. int f[N][N];//区间 [l, r] 中所有子序列的最大长度
  11.  
  12. int main(){
  13.     scanf("%s", s);
  14.  
  15.     int n = strlen(s);
  16.  
  17.     for(int len = 1; len <= n; len ++)
  18.     {
  19.         for(int l = 0; l + len - 1 < n; l ++)
  20.         {
  21.             int r = l + len - 1;
  22.  
  23.             if(len == 1) f[l][r] = 1;
  24.             else
  25.             {
  26.                 if(s[l] == s[r]) f[l][r] = f[l + 1][r - 1] + 2;
  27.                 f[l][r] = max(f[l][r], f[l][r - 1]);
  28.                 f[l][r] = max(f[l][r], f[l + 1][r]);
  29.             }
  30.         }
  31.     }
  32.  
  33.     printf("%d\n", n - f[0][n - 1]);
  34.  
  35.     return 0;
  36. }

DP思路：

也是闫氏分析法（），但是下面这个在它基础上更好理解 

1222. 密码脱落 - AcWing题库

生命之树

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8.  
  9. const int N = 100010, M = N * 2;// N个顶点至多2*N条有向边
  10.  
  11. int n;
  12. int w[N];// 节点的权值
  13. int h[N], e[M], ne[M], idx;
  14. // h是顶点集，e[i]=b表示a指向b（一条边），ne[i]表示结点i的next的指针，idx指向当前需要插入（已经用过）的结点
  15. LL f[N];// 在以u为根的子树中包含u的所有连通块的权值的最大值
  16.  
  17. void add(int a, int b)// 这里采用数组实现邻接表来存储图，也就是将多个单链表h[i]拼起来
  18. {
  19.     e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;// 头插法创建单链表，新节点指向已有节点
  20.     // h[a]是单链表a的起点，最后一个插入元素的地址，也是idx区间的终点
  21. }
  22.  
  23. void dfs(int u, int father)// 求f[i]，第二个参数记录父节点，防止往回走
  24. {
  25.     f[u] = w[u];
  26.     for (int i = h[u]; i != -1; i = ne[i])
  27.     {
  28.         int j = e[i];
  29.  
  30.         if (j != father)
  31.         {
  32.             dfs(j, u);
  33.             f[u] += max(0ll, f[j]);// long long的0，和0比较一下，如果<=0没必要加上
  34.         }
  35.     }
  36. }
  37.  
  38. int main()
  39. {
  40.     scanf("%d", &n);
  41.     memset(h, -1, sizeof h);// 记得h数组置-1
  42.  
  43.     for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  44.     for (int i = 0; i < n - 1; i ++ )// 一共n-1条边
  45.     {
  46.         int a, b;
  47.         scanf("%d%d", &a, &b);
  48.         add(a, b), add(b, a);// 构建无向图
  49.     }
  50.  
  51.     dfs(1, -1);
  52.  
  53.     LL res = f[1];
  54.     for (int i = 2; i <= n; i ++ ) res = max(res, f[i]);// 求f[1]到f[n]的max
  55.  
  56.     printf("%lld\n", res);
  57.  
  58.     return 0;
  59. }
无向图的邻接表的新写法Get!(数组实现邻接表)

算法如下：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8.  
  9. const int N = 100010, M = N * 2;// N个顶点至多2*N条有向边
  10.  
  11. int n;
  12. int w[N];// 节点的权值
  13. int h[N], e[M], ne[M], idx;
  14.  
  15. void add(int a, int b)// 这里采用数组实现邻接表来存储图，也就是将多个单链表h[i]拼起来
  16. {
  17.     e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;// 头插法创建单链表，新节点指向已有节点
  18.     // h[a]是单链表a的起点，最后一个插入元素的地址，也是idx区间的终点
  19. }
  20.  
  21. int main()
  22. {
  23.     scanf("%d", &n);
  24.     memset(h, -1, sizeof h);// 记得h数组置-1
  25.  
  26.     for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  27.     for (int i = 0; i < n - 1; i ++ )// 一共n-1条边
  28.     {
  29.         int a, b;
  30.         scanf("%d%d", &a, &b);
  31.         add(a, b), add(b, a);// 构建无向图
  32.     }
  33. }

构建图的代码中的各全局变量解释如图：

图解&手撸构建过程：

 包子凑数(P)

  1. #include <cstdio>
  2. #include <iostream>
  3. using namespace std;
  4. const int N = 105; 
  5. const int M = 1e4 + 5;
  6.  
  7. int arr[N], f[M];
  8.  
  9. int gcd(int a, int b)
  10. {
  11.     return b? gcd(b, a%b):a;
  12. }
  13.  
  14. int main()
  15. {
  16.     int n;
  17.     scanf("%d", &n);
  18.     for (int i = 0; i < n; ++i)
  19.         scanf("%d", &arr[i]);
  20.     int tmp = arr[0];
  21.     for (int i = 1; i < n; ++i)
  22.         tmp = gcd(tmp, arr[i]);
  23.     if (tmp != 1)
  24.     {
  25.         puts("INF");
  26.         return 0;
  27.     }
  28.     f[0] = 1;
  29.     for (int i = 0; i < n; ++i)
  30.     {
  31.         for (int j = arr[i]; j < M; ++j)
  32.         {
  33.             f[j] = max(f[j], f[j-arr[i]]);
  34.         }
  35.     }
  36.  
  37.     int res = 0;
  38.     for (int i = 1; i < M; ++i)
  39.     {
  40.         if (!f[i])
  41.             res++; 
  42.     }
  43.     printf("%d", res);
  44.     return 0;
  45. }

DP思路：

 

 括号配对(P)

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. const int N = 110, inf = 0x3f3f3f3f;
  8.  
  9. char s[N];
  10. int f[N][N]; // f[i][j]代表将i~j个字符变成GBE的所有方案的集合的最小值
  11.  
  12. bool check(int a, int b)
  13. {
  14.     if (s[a] == '[' && s[b] == ']' || s[a] == '(' && s[b] ==')') return true;
  15.     return false;
  16. }
  17.  
  18. int main()
  19. {
  20.     scanf("%s", s + 1);
  21.     int n = strlen(s + 1);
  22.  
  23.     for (int len = 1; len <= n; len++)
  24.         for (int l = 1; l + len - 1 <= n; l++)
  25.         {
  26.             int r = l + len - 1;
  27.             if (len == 1) f[l][r] = 1;
  28.             else
  29.             {
  30.                 f[l][r] = inf;
  31.                 if (check(l, r)) f[l][r] = min(f[l][r], f[l + 1][r - 1]);
  32.                 for (int k = l; k <= r; k++)
  33.                     f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
  34.             }
  35.         }
  36.  
  37.     cout << f[1][n] << endl;
  38.  
  39.     return 0;
  40. }

 旅游规划(P)

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int N = 200010, M = N * 2;
  9.  
  10. int n;
  11. int h[N], e[M], ne[M], idx;
  12. int d1[N], d2[N], p1[N], up[N];//p1存下u节点往下最大路走的子节点，up存下u节点往上走的最长路径
  13. int maxd;
  14.  
  15. void add(int a, int b)
  16. {
  17.     e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
  18. }
  19.  
  20. void dfs_d(int u, int father)//dfs一下往下走的路径的次大值和最大值
  21. {
  22.     for (int i = h[u]; ~i; i = ne[i])
  23.     {
  24.         int j = e[i];
  25.         if (j != father)
  26.         {
  27.             dfs_d(j, u);
  28.             int distance = d1[j] + 1;
  29.             if (distance > d1[u])//更新最大值和次大值
  30.             {
  31.                 d2[u] = d1[u], d1[u] = distance;
  32.                 p1[u] = j;
  33.             }
  34.             else if (distance > d2[u]) d2[u] = distance;
  35.         }
  36.     }
  37.  
  38.     maxd = max(maxd, d1[u] + d2[u]);
  39. }
  40.  
  41. void dfs_u(int u, int father)
  42. {
  43.     for (int i = h[u]; ~i; i = ne[i])
  44.     {
  45.         int j = e[i];
  46.         if (j != father)
  47.         {
  48.             up[j] = up[u] + 1;
  49.             if (p1[u] == j) up[j] = max(up[j], d2[u] + 1);
  50.             else up[j] = max(up[j], d1[u] + 1);
  51.             dfs_u(j, u);
  52.         }
  53.     }
  54. }
  55.  
  56. int main()
  57. {
  58.     scanf("%d", &n);
  59.     memset(h, -1, sizeof h);
  60.     for (int i = 0; i < n - 1; i ++ )
  61.     {
  62.         int a, b;
  63.         scanf("%d%d", &a, &b);
  64.         add(a, b), add(b, a);
  65.     }
  66.  
  67.     dfs_d(0, -1);
  68.     dfs_u(0, -1);
  69.  
  70.     for (int i = 0; i < n; i ++ )
  71.     {
  72.         int d[3] = {d1[i], d2[i], up[i]};
  73.         sort(d, d + 3);
  74.         if (d[1] + d[2] == maxd) printf("%d\n", i);
  75.     }
  76.  
  77.     return 0;
  78. }

垒骰子 (P)

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8.  
  9. const int N = 6, P = 1e9 + 7;
  10.  
  11. int n, m;
  12. int op[] = {3, 4, 5, 0, 1, 2};
  13. bool st[N][N];
  14.  
  15. void mul(int c[], int a[], int b[][N])
  16. {
  17.     int temp[N] = {0};
  18.     for (int i = 0; i < N; i ++ )
  19.     {
  20.         for (int j = 0; j < N; j ++ )
  21.         {
  22.             temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % P;
  23.         }
  24.     }
  25.     memcpy(c, temp, sizeof(temp));
  26. }
  27.  
  28. void mul(int c[][N], int a[][N], int b[][N])
  29. {
  30.     int temp[N][N] = {0};
  31.     for (int i = 0; i < N; i ++ )
  32.     {
  33.         for (int j = 0; j < N; j ++ )
  34.         {
  35.             for (int k = 0; k < N; k ++ )
  36.             {
  37.                 temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % P;
  38.             }
  39.         }
  40.     }
  41.  
  42.     memcpy(c, temp, sizeof(temp));
  43. }
  44.  
  45. int main()
  46. {
  47.     cin >> n >> m;
  48.     for (int i = 0; i < m; i ++ )
  49.     {
  50.         int a, b;
  51.         cin >> a >> b;
  52.         st[a - 1][b - 1] = st[b - 1][a - 1] = true;
  53.     }
  54.  
  55.     int f1[N] = {4, 4, 4, 4, 4, 4};
  56.     int a[N][N];
  57.     for (int i = 0; i < N; i ++ )
  58.     {
  59.         for (int j = 0; j < N; j ++ )
  60.         {
  61.             if (st[j][op[i]]) a[j][i] = 0;
  62.             else a[j][i] = 4;
  63.         }
  64.     }
  65.  
  66.     n -- ;
  67.     while(n)
  68.     {
  69.         if (n & 1) mul(f1, f1, a);
  70.         mul(a, a, a);
  71.         n >>= 1;
  72.     }
  73.  
  74.     int res = 0;
  75.     for (int i = 0; i < N; i ++ )
  76.     {
  77.         res = (res + f1[i]) % P;
  78.     }
  79.     cout << res;
  80.  
  81.     return 0;
  82. }

其他题

修改数组

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8.  
  9. const int N = 1e6+10;
  10. int n, a[N];
  11. int pre[N];
  12.  
  13. void Init()//初始化并查集
  14. {
  15. 	cin >> n;
  16. 	for (int i = 0; i <= N; i++) pre[i] = i;//最开始根节点就是自己
  17. 	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  18. }
  19.  
  20. int Find(int x)//并查集的Find功能
  21. {
  22. 	if (pre[x] != x) return pre[x] = Find(pre[x]);//压缩路径
  23. 	return pre[x];
  24. }
  25.  
  26. int main()
  27. {
  28. 	Init();
  29.     
  30. 	for (int i = 0; i < n; i++)
  31. 	{
  32. 		a[i] = Find(a[i]);//将a[i]更新为其根节点的值，若a[i]还没被使用过，那这个更新的值就是自己，否则就是下一个还没有被使用过的值，即a[i]的根节点
  33. 		printf("%d ", a[i]);
  34. 		pre[a[i]] = a[i] + 1;//每次将a[i]的根节点更新为之前根节点加一，此时a[i]的值已经是它之前的根节点
  35. 	}
  36. }

思路：使用并查集的结构，将每个值从这个值开始，到最后一个可以达到的值看作一个棵并查集的树。每次进行pre[]的更新相当于并查集中的union操作

斐波那契(P)

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8.  
  9. LL p;
  10.  
  11. //龟速乘（解决相乘爆longlong的问题）
  12. LL qmul(LL a, LL b) {
  13.     LL res = 0;
  14.     while (b) {
  15.         if (b & 1) res = (res + a) % p;
  16.         a = (a + a) % p;
  17.         b >>= 1;
  18.     }
  19.     return res;
  20. }
  21. //计算2x2矩阵相乘，c=a*b
  22. void mul(LL c[][2], LL a[][2], LL b[][2]) {
  23.     static LL t [2][2];
  24.     memset(t, 0, sizeof t);
  25.     for (int i = 0; i < 2; ++i) {
  26.         for (int j = 0; j < 2; ++j) {
  27.             for (int k = 0; k < 2; ++k) {
  28.                 t[i][j] = (t[i][j] + qmul(a[i][k], b[k][j])) % p;
  29.             }
  30.         }
  31.     }
  32.     memcpy(c, t, sizeof t);
  33. }
  34. //快速幂（解决求斐波那契数列第n项的问题）
  35. LL F(LL n) {
  36.     if (!n) return 0;
  37.     LL f[2][2] = {1, 1}; //f(1)=f(2)=1
  38.     LL a[2][2] = {
  39.         {0, 1},
  40.         {1, 1}
  41.     };
  42.     //快速幂
  43.     for (LL k = n - 1; k; k >>= 1) {
  44.         if (k & 1) mul(f, f, a); //f = f * a
  45.         mul(a, a, a); //a = a * a
  46.     }
  47.     return f[0][0];
  48. }
  49. //(F(m-1) * F(n mod m) - 1) mod F(m)
  50. LL H(LL m, LL k) {
  51.     if (k % 2) return F(m - k) - 1;
  52.     else {
  53.         if (k == 0 || m == 2 && m - k == 1) return F(m) - 1;
  54.         else return F(m) - F(m - k) - 1;
  55.     }
  56. }
  57. //求(F(n) - 1)mod F(m)
  58. LL G(LL n, LL m) {
  59.     //m是偶数
  60.     if (m % 2 == 0) {
  61.         //n/2m也是偶数
  62.         if (n / m % 2 == 0) {
  63.             if (n % m == 0) return F(m) - 1;
  64.             else return F(n % m) - 1;
  65.         }
  66.         //n/2m是奇数
  67.         else {
  68.             return H(m, n % m);
  69.         }
  70.     }
  71.     //m是奇数
  72.     else {
  73.         //n/m是偶数，且n/2m是偶数
  74.         if (n / m % 2 == 0 && n / 2 / m % 2 == 0) {
  75.             if (n % m == 0) return F(m) - 1;
  76.             else return F(n % m) - 1;
  77.         }
  78.         //n/m是偶数，且n/2m是奇数
  79.         else if (n / m % 2 == 0 && n / 2 / m % 2) {
  80.             if (m == 2 && n % m == 1) return F(m) - 1;
  81.             else return F(m) - F(n % m) - 1;
  82.         }
  83.         //n/m是奇数，且n/2m是偶数
  84.         else if (n / m % 2 && n / 2 / m % 2 == 0) {
  85.             return H(m, n % m);
  86.         }
  87.         //n/m是奇数，且n/2m是奇数
  88.         else {
  89.             if (n % m % 2) {
  90.                 if (m == 2 && m - n % m == 1) return F(m) - 1;
  91.                 else return F(m) - F(m - n % m) - 1;
  92.             } else {
  93.                 return F(m - n % m) - 1;
  94.             }
  95.         }
  96.     }
  97.  
  98. }
  99. int main() {
  100.     LL n, m;
  101.     while (cin >> n >> m >> p) cout << (G(n + 2, m) % p + p) % p << endl;
  102.     return 0;
  103. }

剪格子(P)

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <unordered_set>
  5. #include <vector>
  6. #define x first
  7. #define y second
  8.  
  9. using namespace std;
  10.  
  11. const int N = 10, INF = 1e8, P = 131;
  12.  
  13. typedef unsigned long long ULL;
  14. typedef pair<int, int> PII;
  15.  
  16. int n, m;
  17. int g[N][N];
  18. bool st[N][N];   // st用于判断剩余方块是否是一个连通块
  19. int sum, ans = INF;  // sum是所有数的总和，ans是答案
  20. PII cands[N * N];  // 搜索路径上已经选择的点
  21. int p[N * N];   // 并查集判断连通块
  22. int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 偏移量
  23.  
  24. unordered_set<ULL> hash_table;
  25.  
  26. int find(int x)  // 并查集模板
  27. {
  28.     if(p[x] != x) p[x] = find(p[x]);
  29.     return p[x];
  30. }
  31.  
  32. bool check_connet(int k)  // 判断剩余方块是否是一个连通块
  33. {
  34.     for(int i = 0; i < n * m; i ++) p[i] = i; // 初始化并查集
  35.  
  36.     int cnt = n * m - k;  // 剩余的点的数量
  37.  
  38.     for(int i = 0; i < n; i ++)
  39.         for(int j = 0; j < m; j ++)
  40.             if(!st[i][j])
  41.             {
  42.                 for(int u = 0; u < 4; u ++)
  43.                 {
  44.                     int a = i + dx[u], b = j + dy[u];
  45.                     // 如果越界或者已经搜过则跳过
  46.                     if(a < 0 || a >= n || b < 0 || b >= m) continue;
  47.                     if(st[a][b]) continue;
  48.                     // 得到对应方格的编号对应的并查集中的父节点
  49.                     int p1 = find(i * m + j), p2 = find(a * m + b);
  50.                     if(p1 != p2) // 合并
  51.                     {
  52.                         p[p1] = p2;
  53.                         cnt --;
  54.                     }
  55.                 }
  56.             }
  57.     if(cnt != 1) return false;
  58.     return true;
  59. }
  60.  
  61. bool check_exists(int k) // 这是剪枝的关键，判断扩展后的结果在之前是否出现过
  62. {
  63.     PII bk[N * N];
  64.     for(int i = 0; i < k; i ++) bk[i] = cands[i];
  65.  
  66.     sort(bk, bk + k); // 这里不排序就会tle， 不知道为啥，求评论区大佬解惑？
  67.  
  68.     //严格来说，这并不是字符串哈希，只是运用那种思想来对每种情况进行区分而已
  69.     ULL x = 0;
  70.     for(int i = 0; i < k; i ++)
  71.     {
  72.         x = x * P + bk[i].x + 1;
  73.         x = x * P + bk[i].y + 1;
  74.     }
  75.     if(hash_table.count(x)) return true; // 如果之前已经出现过,则返回真
  76.  
  77.     hash_table.insert(x);
  78.     return false;
  79. }
  80.  
  81. void dfs(int s, int k) // s 表示当前搜索数的总和，k 表示当前搜索路径的点的数量
  82. {
  83.     if(s == sum / 2)
  84.     {
  85.         // 如果剩下的方块是一个连通块，则更新答案
  86.         if(check_connet(k)) ans = min(ans, k);
  87.         return;
  88.     }
  89.  
  90.     vector<PII> points; // 存储可扩展的点
  91.  
  92.     for(int i = 0; i < k; i ++)  // 对搜索路径上的每个点进行扩展
  93.     {
  94.         int x = cands[i].x, y = cands[i].y;
  95.         for(int j = 0; j < 4; j ++)
  96.         {
  97.             int a = x + dx[j], b = y + dy[j];
  98.             if(a < 0 || a >= n || b < 0 || b >= m) continue;
  99.             if(st[a][b]) continue;
  100.  
  101.             cands[k] = {a, b};  // 将该点加入点集，才可以判断有这个点的连通块的情况
  102.             // 如果新扩展的点使得数量比答案要大或者前面已经有过这种扩展方案，则不用扩展该点
  103.             if(k + 1 < ans && !check_exists(k + 1))
  104.                 points.push_back({a, b});
  105.         }
  106.     }
  107.  
  108.     // 对可扩展的点要从大到小排序
  109.     sort(points.begin(), points.end());
  110.     reverse(points.begin(), points.end());
  111.  
  112.     for(int i = 0; i < points.size(); i ++)
  113.         if(!i || points[i] != points[i - 1]) // 如果是第一个点或者该点与上一个点不同
  114.         {
  115.             cands[k] = points[i];
  116.             int x = points[i].x, y = points[i].y;
  117.             st[x][y] = true;
  118.             dfs(s + g[x][y], k + 1);  // 往下扩展
  119.             st[x][y] = false;   // 恢复现场
  120.         }
  121. }
  122.  
  123. int main()
  124. {
  125.     cin >> m >> n;
  126.     for(int i = 0; i < n; i ++)
  127.         for(int j = 0; j < m; j ++)
  128.         {
  129.             cin >> g[i][j];
  130.             sum += g[i][j];
  131.         }
  132.  
  133.     if(sum % 2 == 0){  // 偶数才可以平分
  134.         st[0][0] = true;  // 从左上角开始搜
  135.         cands[0] = {0, 0};
  136.         dfs(g[0][0], 1);
  137.     }
  138.  
  139.     if(ans == INF) ans = 0;
  140.     cout << ans << endl;
  141.     return 0;
  142. }

组合数问题

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 2010;
  8.  
  9. int t, k;
  10. int c[N][N], s[N][N];
  11.  
  12. int main()
  13. {
  14.     scanf("%d%d", &t, &k);
  15.  
  16.     for(int i = 0; i < N ; i ++) //处理所有组合数
  17.         for(int j = 0; j <= i; j ++)
  18.             if(!j) c[i][j] = 1 % k; //c[][0] 都为 1
  19.             else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % k;
  20.  
  21.  
  22.     for(int i = 0; i < N; i ++)
  23.         for(int j = 0 ; j < N ; j ++) //前缀和
  24.         {
  25.             if(j <= i && c[i][j] == 0) s[i][j] = 1;
  26.             //当组合数合法并且可以整除k时，它的值为1
  27.             if(i - 1 >= 0) s[i][j] += s[i - 1][j];
  28.             if(j - 1 >= 0) s[i][j] += s[i][j - 1];
  29.             if(i - 1 >= 0 && j - 1 >= 0) s[i][j] -= s[i - 1][j - 1];
  30.         } 
  31.  
  32.  
  33.     while(t --)
  34.     {
  35.         int n, m;
  36.         scanf("%d%d", &n, &m);
  37.         printf("%d\n", s[n][m]);
  38.     }
  39.     return 0;
  40. }

思路：使用二维前缀和与组合数的递推性质

具体见：AcWing 523. 组合数问题(递推 + 前缀和) - AcWing

各种最长字串or序列问题

最长回文子串

DP写法（n*n)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() 
  5. {
  6.     string s;
  7.     cin >> s;
  8.  
  9. 	int n = s.length();
  10.     vector<vector<bool>> dp(n, vector<bool>(n, false));
  11.     int maxLength = 1;  // 最小回文子串长度为1
  12.     
  13.     // 所有长度为1的子串都是回文子串
  14.     for (int i = 0; i < n; i++) {
  15.         dp[i][i] = true;
  16.     }
  17.     
  18.     // 检查长度为2的子串
  19.     for (int i = 0; i < n - 1; i++) {
  20.         if (s[i] == s[i + 1]) {
  21.             dp[i][i + 1] = true;
  22.             maxLength = 2;
  23.         }
  24.     }
  25.     
  26.     // 检查长度大于2的子串
  27.     for (int len = 3; len <= n; len++) {
  28.         for (int i = 0; i <= n - len; i++) {
  29.             int j = i + len - 1;
  30.             if (s[i] == s[j] && dp[i + 1][j - 1]) {
  31.                 dp[i][j] = true;
  32.                 maxLength = max(maxLength, len);
  33.             }
  34.         }
  35.     }
  36.     
  37.     printf("%d",maxLength);
  38.     return 0;
  39. }

manacher算法(n)

  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. const int N = 22000010;
  9. char s[N], str[N];
  10. int p[N];   //用于存放每个字符可以中心扩展几次
  11.  
  12. int init()              //处理原字符串
  13. {
  14.     int len = strlen(s);
  15.     str[0] = '#'; str[1] = '$';         //@是防止越界
  16.     int j = 2;
  17.     for (int i = 0; i < strlen(s); i++)
  18.         str[j++] = s[i], str[j++] = '$';
  19.     str[j] = '\0';
  20.     return j;
  21. }
  22.  
  23. int manacher()
  24. {
  25.     int ans = -1, len = init(), r = 0, c = 0;
  26.     for (int i = 1; i < len; i++)
  27.     {
  28.         if (i <= r) p[i] = min(p[c * 2 - i], r - i);             //situation1
  29.         else p[i] = 1;                                  //situation2
  30.         while (str[i + p[i]] == str[i - p[i]]) p[i]++;                //扩展  
  31.         if (p[i] + i > r)
  32.         {
  33.             r = p[i] + i;
  34.             c = i;          //更新中心位置
  35.         }
  36.  
  37.         ans = max(ans, p[i] - 1);
  38.     }
  39.     return ans;
  40. }
  41.  
  42. int main()
  43. {
  44.     int cnt = 0;
  45.     while (cin >> s)
  46.         cout << manacher() << endl;
  47. }

思路参考：

【蓝桥杯每日一题】3.8 最长回文子序列_蓝桥杯最长回文子串-CSDN博客

最长上升序列

  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. vector<int>v;
  8. int m, n, a[1006];
  9. int f[1006];
  10.  
  11. void fun()
  12. {
  13. 	for (int i = 1; i <= n; i++)
  14. 	{
  15. 		for (int j = 1; j < i; j++)
  16. 		{
  17. 			if (a[j] < a[i]) f[i] = max(f[j] + 1, f[i]);
  18. 		}
  19. 	}
  20. }
  21.  
  22. int main()
  23. {
  24. 	cin >> m;
  25. 	while (m--)
  26. 	{
  27. 		cin >> n;
  28. 		for (int i = 1; i <= n; i++) f[i] = 1;
  29. 		for (int i = 1; i <= n; i++) cin >> a[i];
  30. 		fun();
  31. 		int Max = -1;
  32. 		for (int i = 1; i <= n; i++)
  33. 			if (f[i] > Max) Max = f[i];
  34. 		cout << Max << endl;
  35. 	}
  36. }

 思路参考：

最长上升子序列 (LIS) 详解+例题模板 (全)-CSDN博客

最长公共子串

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. string s1, s2;
  9. int f[105][105];
  10.  
  11. void fun()
  12. {
  13. 	for (int i = 1; i <= s2.size(); i++)
  14. 	{
  15. 		for (int j = 1; j <= s1.size(); j++)
  16. 		{
  17. 			if (s2[i - 1] == s1[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;
  18. 			else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
  19. 			
  20. 		}
  21. 	}
  22. }
  23.  
  24. int main()
  25. {
  26. 	while (cin >> s1 >> s2)
  27. 	{
  28. 		fun();
  29. 		cout << f[s2.size()][s1.size()] << endl;
  30. 		for (int i = 0; i <= s2.size(); i++)
  31. 			for (int j = 0; j <= s1.size(); j++) f[i][j] = 0;
  32. 	}
  33. }

思路参考：

最长公共子序列问题 C++ （超详细）_最长公共子序列c++代码-CSDN博客

逆波兰表达式

将正常运算表达式转化为逆波兰表达式
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include<stack>
  5. #include <algorithm>
  6. #include<sstream>
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11. 	stack<string>s;//用于存放符号的栈
  12. 	vector<string>v;//存放后缀表达式
  13. 	string str, S;//str是当前要处理的字符串，S是输入的正常的运算表达式
  14.  
  15. 	getline(cin, S);
  16. 	stringstream ss(S);
  17.  
  18. 	while (ss >> str)//依次获取正常运算表达式的每一项
  19. 	{
  20. 		int flag = 1;//标志位,若当前字符是运算符号，则置为0
  21. 		if (!isdigit(str[0])) flag = 0;
  22.  
  23. 		if (flag) v.push_back(str);//是数字，直接进入队列
  24. 		else//若是运算符，那么处理稍复杂
  25. 		{
  26. 			if (str == "(" || str == "*" || str == "/") s.push(str);//是 ( * /，那么直接入栈
  27. 			else if (str == ")")//是 ),则应该把与 （ 之间的符号都弹栈存到队列中
  28. 			{
  29. 				while (s.top() != "(")
  30. 				{
  31. 					v.push_back(s.top());
  32. 					s.pop();
  33. 				}
  34. 				s.pop();//弹出 (
  35. 			}
  36. 			else if (str == "+" || str == "-")//是 + or - ,那么若栈顶符号是 * or /，先将栈顶出栈存入队列中
  37. 			{
  38. 				if (!s.empty())
  39. 				{
  40. 					while (s.top() == "*" || s.top() == "/")
  41. 					{
  42. 						v.push_back(s.top());
  43. 						s.pop();
  44. 					}
  45. 				}
  46. 				s.push(str);//入栈
  47. 			}
  48. 		}
  49. 	}
  50. 	while (!s.empty())//把栈中存留元素出栈存入队列
  51. 	{
  52. 		v.push_back(s.top());
  53. 		s.pop();
  54. 	}
  55.  
  56. 	for (string it : v) cout << it << " ";//输出后缀表达式
  57. }
  58.  
  59.

思路参考：逆波兰表达式（后缀表达式）-CSDN博客

逆波兰表达式的计算

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/671912
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号