• 蓝桥杯第十三届省赛C++B组(未完)

    刷题统计

    题目描述

    小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？

    输入格式

    输入一行包含三个整数 a, b 和 n.

    输出格式

    输出一个整数代表天数。

    样例输入

    10 20 99

    样例输出

    8

    提示

    对于 50% 的评测用例，1 ≤ a, b, n ≤ 106 . 对于 100% 的评测用例，1 ≤ a, b, n ≤ 10^18 .

    1. #include
    2. using namespace std;
    3. typedef long long LL;
    4. const int N=2e5+10,M=1e5+10;
    5. int main(){
    6. 	int T=1;
    7. //	cin>>T;
    8. 	while(T--){
    9. 		LL a,b,n;
    10. 		cin>>a>>b>>n;
    11. 		LL t=a*5+b*2;
    12. 		LL ans=0;
    13. 		ans=n/t*7;
    14. 		n%=t;
    15. 		if(n>=a*5){
    16. 			ans+=5;
    17. 			n-=a*5;
    18. 			ans+=(n+b-1)/b;
    19. 		}else{
    20. 			ans+=(n+a-1)/a;
    21. 		}
    22. 		cout<
    23. 	}
    24. 	return 0;
    25. }

    修剪灌木

    题目描述

    爱丽丝要完成一项修剪灌木的工作。有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

    输入格式

    一个正整数 N ，含义如题面所述。

    输出格式

    输出 N 行，每行一个整数，第i行表示从左到右第 i 棵树最高能长到多高。

    样例输入

    3

    样例输出

    4
2
4

    提示

    对于 30% 的数据，N ≤ 10. 对于 100% 的数据，1 < N ≤ 10000.

    1. #include
    2. using namespace std;
    3. typedef long long LL;
    4. const int N=2e5+10,M=1e5+10;
    5. int a[10010];
    6. int main(){
    7. 	int T=1;
    8. //	cin>>T;
    9. 	while(T--){
    10. 		int n;
    11. 		cin>>n;
    12. 		for(int i=1,j=n;i<=j;i++,j--){
    13. 			a[i]=a[j]=2*(n-i);
    14. 		}
    15. 		for(int i=1;i<=n;i++) cout<
    16. 	}
    17. 	return 0;
    18. }

    X进制减法

    题目描述

    进制规定了数字在数位上逢几进一。

    X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X 进制数 321 转换为十进制数为 65。

    现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A − B 的结果最小可能是多少。

    请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。 

    输入格式

    第一行一个正整数 N，含义如题面所述。

    第二行一个正整数 Ma，表示 X 进制数 A 的位数。

    第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。

    第四行一个正整数 Mb，表示 X 进制数 B 的位数。

    第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。

    请注意，输入中的所有数字都是十进制的。

    输出格式

    输出一行一个整数，表示 X 进制数 A − B 的结果的最小可能值转换为十进制后再模 1000000007 的结果。 

    样例输入

    11
3
10 4 0
3
1 2 0

    样例输出

    94

    提示

    当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94。

    对于 30% 的数据，N ≤ 10; Ma, Mb ≤ 8. 对于 100% 的数据，2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B. 

    123
    c（进制数组）1152
    a1040

    A=(a1*c1+a2)*c3+a3；

    1. #include
    2. using namespace std;
    3. typedef long long LL;
    4. const int N=1e5+10;
    5. LL mod=1000000007;
    6. LL a[N];
    7. LL b[N];
    8. LL c[N];
    9. int main(){
    10. 	int T=1;
    11. //	cin>>T;
    12. 	while(T--){
    13. 		LL N;cin>>N;
    14. 		int ma;cin>>ma;
    15. 		for(int i=1;i<=ma;i++) cin>>a[i];
    16. 		int mb;cin>>mb;
    17. 		for(int i=1;i<=mb;i++) cin>>b[i];
    18. 		int k=ma,j=mb;
    19. 		for(k=ma,j=mb;k>=1&&j>=1;k--,j--){
    20. 			c[k]=max(a[k],b[j])+1;
    21. 			if(c[k]<2) c[k]=2;
    22. 		}
    23. 		while(k>=1){
    24. 			c[k]=max((LL)2,a[k]+1);
    25. 			k--;
    26. 		}
    27. 		LL A=a[1];
    28. 		for(int i=2;i<=ma;i++){
    29. 			A=(A*c[i]%mod+a[i])%mod;
    30. 		}
    31. 		LL B=b[1];
    32. 		j=ma-mb+2;
    33. 		for(int i=2;i<=mb;i++,j++){
    34. 			B=(B*c[j]%mod+b[i])%mod;
    35. 		}
    36. 	//	cout<
    37. 		cout<<(A-B+mod)%mod<
    38. 	}
    39. 	return 0;
    40. }

    【前缀和+双指针】统计子矩阵

    给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K? 

    输入格式：

    第一行包含三个整数 N, M 和 K. 

    之后 N 行每行包含 M 个整数，代表矩阵 A.

    输出格式

    一个整数代表答案。

    样例输入

    3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

    样例输出

    19

    提示

    满足条件的子矩阵一共有 19，包含：

    大小为 1 × 1 的有 10 个。

    大小为 1 × 2 的有 3 个。

    大小为 1 × 3 的有 2 个。

    大小为 1 × 4 的有 1 个。

    大小为 2 × 1 的有 3 个。

    对于 30% 的数据，N, M ≤ 20. 对于 70% 的数据，N, M ≤ 100. 

    对于 100% 的数据，1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. typedef long long LL;
    6. const int N=510;
    7. LL w[N][N];
    8. LL s[N][N];
    9. int main(){
    10.     int n,m,k;
    11.     cin>>n>>m>>k;
    12.     for(int i=1;i<=n;i++){
    13.     	for(int j=1;j<=m;j++){
    14.     		cin>>w[i][j];
    15.     		//每一列的前缀和（一维）
    16.     		s[i][j]=s[i-1][j]+w[i][j];
    17. 		}
    18. 	}
    19. 	LL sum=0,ans=0;
    20. 	//找j-i+1行，r-l+1列的子矩阵
    21. 	for(int i=1;i<=n;i++){//上边界
    22. 		for(int j=i;j<=n;j++){//下边界
    23. 			sum=0;
    24. 			for(int l=1,r=1;r<=m;r++){
    25. 				sum+=s[j][r]-s[i-1][r];
    26. 				while(l<=r&&sum>k){
    27. 					sum-=s[j][l]-s[i-1][l];
    28. 					l++;
    29. 				}
    30. 				ans+=r-l+1;
    31. 			}
    32. 		}
    33. 	}
    34. 	cout<
    35. 	//二维；
    36. //    int n,m,k;
    37. //    cin>>n>>m>>k;
    38. //    for(int i=1;i<=n;i++){
    39. //    	for(int j=1;j<=m;j++){
    40. //    		cin>>w[i][j];
    41. //    		s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+w[i][j];
    42. //		}
    43. //	}
    44. //	LL ans=0;
    45. //	for(int x1=1;x1<=n;x1++){
    46. //		for(int x2=x1;x2<=n;x2++){
    47. //			for(int y1=1,y2=1;y2<=m;y2++){
    48. //				while(y1<=y2&&s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]>k) y1++;
    49. //				ans+=y2-y1+1;
    50. //			}
    51. //		}
    52. //	}
    53. //	cout<
    54.     return 0;
    55. }

    【DP】积木画

    题目描述

    小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2 个单位面积）和 L 型（大小为 3 个单位面积）：

    蓝桥杯2022年第十三届省赛真题积木画1

    同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？ 积木可以任意旋转，且画布的方向固定。

    输入格式

    输入一个整数 N，表示画布大小。

    输出格式

    输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。

    样例输入

    3

    样例输出

    5

    提示

    五种情况如下图所示，颜色只是为了标识不同的积木：

    蓝桥杯2022年第十三届省赛真题积木画2

    对于所有测试用例，1 ≤ N ≤ 10000000.

    f[i][0]：表示第 i 列放满得方法数；

    f[i][1]：表示第 i 列放满且第 i+1 列多一个得方案数。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. typedef long long LL;
    6. const int N=1e7+10,mod=1000000007;
    7. LL f[N][2];
    8. int main(){
    9.     int n;
    10.     cin>>n;
    11.     f[1][0]=1,f[1][1]=2,f[2][0]=2,f[2][1]=4;
    12.     for(int i=3;i<=n;i++){
    13.     	f[i][0]=(f[i-1][0]+f[i-2][0]+f[i-2][1])%mod;
    14.     	f[i][1]=(f[i-1][1]+f[i-1][0]*2)%mod;
    15. 	}
    16. 	cout<0]<
    17.     return 0;
    18. }

    【图+DFS】扫雷

    小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下， 在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (xi , yi ,ri) 表示在坐标 (xi , yi) 处存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。

    为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj , yj ,rj) 表示这个排雷火箭将会在 (xj , yj) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆，在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷？ 

    你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

    输入格式

    输入的第一行包含两个整数 n、m.

    接下来的 n 行，每行三个整数 xi , yi ,ri，表示一个炸雷的信息。

    再接下来的 m 行，每行三个整数 xj , yj ,rj，表示一个排雷火箭的信息。

    输出格式

    输出一个整数表示答案。

    样例输入

    2 1
2 2 4
4 4 2
0 0 5

    样例输出

    2

    提示

    示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2 也被排除。

    蓝桥杯2022年第十三届省赛真题扫雷

    对于 40% 的评测用例：0 ≤ x, y ≤ 10^9 , 0 ≤ n, m ≤ 10^3 , 1 ≤ r ≤ 10. 

    对于 100% 的评测用例：0 ≤ x, y ≤ 10^9 , 0 ≤ n, m ≤ 5 × 10^4 , 1 ≤ r ≤ 10. 

    1. #include
    2. #include
    3. #include
    4. #include
    5. #define int long long
    6. //typedef long long LL;
    7. using namespace std;
    8. const int N=5e4+10;
    9. struct str{
    10. 	int x,y,r;
    11. 	int cnt;
    12. 	bool operator<(str const &m) const{
    13. 		if(x==m.x) return y
    14. 		return x
    15. 	}
    16. }arr[N];
    17. int n,m;
    18. vector<int> e[N];
    19. bool vis[N];
    20. mapint,int>,int>mp;
    21. int get(int x1,int y1,int x2,int y2){
    22. 	return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
    23. }
    24. void add(int index){
    25. 	for(int i=index-1;i>=1;i--){
    26. 		if(arr[index].x-arr[index].r>arr[i].x) break;
    27. 		if(arr[index].r*arr[index].r>=get(arr[index].x,arr[index].y,arr[i].x,arr[i].y)){
    28. 			e[index].push_back(i);
    29. 		}
    30. 	}
    31. 	for(int i=index+1;i<=n;i++){
    32. 		if(arr[index].x+arr[index].rbreak;
    33. 		if(arr[index].r*arr[index].r>=get(arr[index].x,arr[index].y,arr[i].x,arr[i].y)){
    34. 			e[index].push_back(i);
    35. 		}
    36. 	}
    37. }
    38. int dfs_2(int index){
    39. 	vis[index]=1;
    40. 	int sum=arr[index].cnt;
    41. 	for(int i=0;isize();i++){
    42. 		int t=e[index][i];
    43. 		if(!vis[t]) sum+=dfs_2(t);
    44. 	}
    45. 	return sum;
    46. }
    47. int dfs_1(int x,int y,int r){
    48. 	int cnt=0;
    49. 	str str1={x-r,y,r};
    50. 	str str2={x+r,y,r};
    51. 	int ll,rr;
    52. 	ll=lower_bound(arr+1,arr+n+1,str1)-arr;
    53.     rr=lower_bound(arr+1,arr+n+1,str2)-arr;
    54.     ll=min(ll,n),rr=min(rr,n);
    55.  
    56. 	for(int i=ll;i<=rr;i++){
    57. 		if(i==0) continue;
    58. 		if(!vis[i]){
    59. 			if(r*r>=get(x,y,arr[i].x,arr[i].y)){
    60. 				cnt+=dfs_2(i);
    61. 			}
    62. 		}
    63. 	}
    64. 	return cnt;
    65. }
    66. signed main(){
    67. 	scanf("%lld%lld",&n,&m);
    68. 	for(int i=1;i<=n;i++){
    69. 		int x,y,r;
    70. 		scanf("%lld%lld%lld",&x,&y,&r);
    71. 		int t=mp[{x,y}];
    72. 		if(t){
    73. 			arr[t].cnt++;
    74. 			arr[t].r=max(arr[t].r,r);
    75. 		}else{
    76. 			mp[{x,y}]=i;
    77. 			arr[i]={x,y,r,1};
    78. 		}
    79. 	}
    80. 	sort(arr+1,arr+n+1);
    81. 	for(int i=1;i<=n;i++){
    82. 		add(i);
    83. 	}
    84. 	int ans=0;
    85. 	for(int i=0;i
    86. 		int x,y,r;
    87. 		scanf("%lld%lld%lld",&x,&y,&r);
    88. 		ans+=dfs_1(x,y,r);
    89. 	}
    90. 	cout<
    91. 	return 0;
    92. }

    李白打酒加强版

    题目描述

    话说大诗人李白，一生好饮。幸好他从不开车。

    一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：

    无事街上走，提壶去打酒。

    逢店加一倍，遇花喝一斗。

    这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花， 他正好把酒喝光了。

    请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？

    注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

    输入格式

    第一行包含两个整数 N 和 M.

    输出格式

    输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。

    样例输入

    5 10

    样例输出

    14

    提示

    如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

    010101101000000
    010110010010000
    011000110010000
    100010110010000
    011001000110000
    100011000110000
    100100010110000
    010110100000100
    011001001000100
    100011001000100
    100100011000100
    011010000010100
    100100100010100
    101000001010100
    对于 40% 的评测用例：1 ≤ N, M ≤ 10。
    对于 100% 的评测用例：1 ≤ N, M ≤ 100。

    DFS (通过64%，ACwing 3/11）;

    1. #include
    2. using namespace std;
    3. #define int long long
    4. int mod=1000000007;
    5. int n,m;
    6. int ans=0;
    7. void dfs(int cnt,int x,int y){
    8. 	if(cnt<0) return ;
    9. 	if(y==m+1){
    10. 		if(x==n+1&&cnt==0){
    11. 			ans++;
    12. 			ans%=mod;
    13. 		//	cout<
    14. 		}
    15. 		return ;
    16. 	}
    17. 	if(cnt>m-y+1||n-x>=m-y) return ;
    18. 	if(y>m+1||x>n+1) return ;
    19. 	dfs(cnt*2,x+1,y);
    20. 	dfs(cnt-1,x,y+1);
    21. }
    22. signed main(){
    23. 	scanf("%d%d",&n,&m);
    24. 	dfs(2,1,1);
    25. 	cout<
    26. 	return 0;
    27. }

     DFS(AC)

    1. #include
    2. #include
    3. using namespace std;
    4. #define int long long
    5. const int N=110;
    6. int mod=1000000007;
    7. int n,m;
    8. int ans=0;
    9. int arr[N][N][N];
    10. int dfs(int n,int m,int cnt){
    11. 	if(m<0||n<0) return 0;
    12. 	if(arr[n][m][cnt]!=-1) return arr[n][m][cnt];
    13. 	if(cnt<0) return 0;
    14. 	if(m==0){
    15. 		if(n==0&&cnt==0) return 1;
    16. 		return 0;
    17. 	}
    18. 	if(cnt>m||n>=m) return 0;
    19. 	ans=dfs(n-1,m,cnt*2)+dfs(n,m-1,cnt-1);
    20. 	ans%=mod;
    21. 	arr[n][m][cnt]=ans;
    22. 	return ans;
    23. }
    24. signed main(){
    25. 	memset(arr,-1,sizeof arr);
    26. 	scanf("%d%d",&n,&m);
    27. 	cout<<dfs(n,m,2)<
    28. 	return 0;
    29. }

    DP（AC）

    f[i][j][k]：走到了第i个位置，遇到了j个花，还剩k斗酒的合法方案数.

     

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int N=110;
    5. int f[N*2][N][N*2];
    6. int mod=1000000007;
    7. signed main(){
    8. 	int n,m;
    9. 	cin>>n>>m;
    10. 	f[0][0][2]=1;
    11. 	for(int i=1;i
    12. 		for(int j=0;j
    13. 			for(int k=0;k<=m;k++){
    14. 				//k为偶数，第i个可以是店，也可以是花，k为奇数，只能是花
    15. 				if(k%2==0){
    16. 					//店转移
    17. 					f[i][j][k]=(f[i][j][k]+f[i-1][j][k>>1])%mod;
    18. 				}
    19. 				//花转移
    20. 				if(j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;
    21. 			}
    22. 		}
    23. 	}
    24. 	cout<-1][m-1][1]<
    25. 	return 0;
    26. }

    砍竹子(X)

  • 相关阅读:
    redis缓存雪崩、穿透、击穿
    常用的 linux开发的shell脚本
    反弹shell原理与实现
    Baichuan 2: Open Large-scale Language Models
    【Power BI】Power BI 入门指南：版本、下载和报表创建的步骤
    使用FFmpeg源码配置程序configure查看所有支持的编码器/解码器/封装/解封装及网络协议
    数据链路层 MTU 对 IP 协议的影响
    CFdiv2-Tournament Countdown-(思维+交互题套路)
    数据结构——链表
    树上问题——树的直径
  • 原文地址：https://blog.csdn.net/m0_74035601/article/details/137409012