• XUST——Kcsoftware Part3 题目题解

    A - 阶乘后面0的数量

    题解：

    题目要求我们计算阶乘结果后0的个数，刚开始很多同学都是去尝试进行暴力求解，计算出最后结果再统计，毫无疑问这个是会爆掉的，所以我们要去思考新的办法去解决这个问题。

    那么我们就要观察其中的本质，对于两个大数字相乘，都可以拆分成多个质数的相乘，而

    此类问题很显然属于数学问题，一定要找到其中的本质规律才能得到正确的数学模型。

    两个大数字相乘，都可以拆分成多个质数相乘，而质数相乘结果尾数为0的，只可能是2*5。如果想到了这一点，那么就可以进一步想到：两个数相乘尾数0的个数其实就是依赖于2和5因子的个数。又因为每两个连续数字就会有一个因子2，个数非常充足，所以此时只需要关心5因子的个数就行了。

    然后我们就只需要去考虑如何找到n！中5因子的个数呢？

    我们不妨举例子假设：

    10！=10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1            可以看到10！中5的因子为10和5，有两个

    15！=15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1             15！中5的因子是15、10和5，有三个

    由此可见，n除以5便可得到5的因子sum。

    但是，当5的因子不止含有一个5呢？例如25、125、625。

    当5的因子含有2个5相乘时，25 = 5 * 5，我们需要将sum加上n除以5再除以5的个数，这时sum就包含将25分成两个5的因子之后的总个数。

    当5的因子含有3个5相乘时，125 = 5 * 5 * 5，我们需要将sum加上n除以5再除以5再除以5的个数，这时sum就包含将125分成3个5的因子之后的总个数。

    根据这个原理我们就可以解出这道题目了

    AC

    1. #include 
    2.  
    3. int main(void)
    4. {
    5. 	long long N ;
    6. 	long long  x , m ;
    7. 	x = 0 ;
    8. 	scanf("%lld",&N);
    9. 	x=N/5;
    10. 	m=x;
    11. 	while(m!=0)
    12. 	{
    13. 		m=m/5;
    14. 		x+=m;
    15. 	}
    16. 	printf("%lld",x);
    17. 	return 0;
    18. }

    B - 上台阶 easy

    对于该问题，适合用递归的方法来计算。从倒数第一步开始、从未到头思考，倒数第一步可能走了一级台阶，也可能走了两级。对于倒数第一步走一级的情况，可分类成倒数第二步走了一级与两级的情况；对于倒数第一步走了两级的情况，也可分类成倒数第二步走了一级与两级的情况……以此类推，见下图 ：

     

    AC

    1. #include 
    2.  
    3. int arr(int n)
    4. {
    5. 	n = n - 1 ;
    6. 	int a = 1 ;
    7. 	int b = 2 ;
    8. 	int c = n ;
    9. 	while (n > 2)
    10. 	{
    11. 		c = a + b ;
    12. 		a = b ;
    13. 		b = c ;
    14. 		n-- ;
    15. 	}
    16. 	return c ;
    17. }
    18.  
    19. int main(void)
    20. {
    21. 	int n  ;
    22. 	int sum ;
    23. 	scanf("%d",&n) ;
    24. 	sum = arr (  n ) ;
    25. 	printf("%d\n", sum ) ;
    26. 	return 0 ;
    27.  } 
    1. #include 
    2. using namespace std;
    3.  
    4. int goup(int number){
    5. 	if(number == 1) return 1;
    6. 	else if(number == 2) return 1;
    7. 	else return goup(number - 1) + goup(number -2);
    8. }
    9.  
    10. int main(){
    11. 	int n;
    12. 	cin >> n;
    13. 	cout << goup(n) << endl;
    14. 	return 0;
    15. }

    C - 查找

    首先题目意思是给一串已经排好了的数字问你某个数字的位置。
    如果从1到n扫一遍的话肯定超时。
    所以这里用了二分的方法：

    首先找到这串数字中间位置的那个数，然后与需要查询的数比较

    如果要查询的数小于中间那个数，那么答案肯定在左边

    如果要查询的数大于中间那个数，那么答案肯定在右边

    如果等于的话继续在左边找，因为找到的位置还不能确定是第一个数

    如此重复，直到要查询的区域变为1。

    1. #include
    2.  
    3. using namespace std ;
    4.  
    5. const int N = 1e6+10 ;
    6.  
    7. int a[N] ;
    8. int n, m , s;
    9.  
    10.  
    11. int main()
    12. {
    13.     cin >> n >> m ;
    14.     
    15.     for(int i=1; i<=n; i++)
    16.     {
    17.         cin >> a[i] ;
    18.     }
    19.  
    20.     while(m--)
    21.     {
    22.         cin >> s ;
    23.         
    24.         int l=1, r=n ;
    25.  
    26.         while(l
    27.         {
    28.             int mid = l+r >> 1 ;
    29.                 
    30.             if(a[mid]>=s)   r=mid ;
    31.             else    l=mid+1 ;
    32.         }
    33.  
    34.         if(a[l]!=s) cout << "-1 " ;
    35.         else
    36.         {
    37.             cout << l << " " ;
    38.         }
    39.  
    40.  
    41.     }   
    42.  
    43.     return 0 ;
    44. }

     

    D - Kevin and Permutation

     题目翻译：

    在他的生日，凯文收到了一组成对的数字1，2，3，…n作为礼物。
    他将以一种方式排列这些数字，使得两个连续数字之间的最小绝对差尽可能大。更正式地说，如果他按照P1、P2、…、Pn的顺序排列数字，他希望最大化数值

    其中|x|表示x的绝对值。
    帮助凯文做到这一点。 

    题意描述:

    给你一个数字 ww, 让你构造一个长度为 ww 的串，其中串元素由 1,2,3......w1,2,3......w 构成，且每个数字只出现一次，要求使得串相邻的两个元素两两之差的最小的绝对值最大

     

    1. #include
    2.  
    3. using namespace std;
    4.  
    5.  
    6. int main()
    7. {
    8. 	int t;
    9. 	cin >> t;
    10. 	
    11. 	while(t--)
    12. 	{
    13. 		int n;
    14. 		cin >> n;
    15. 		
    16. 		int s = n/2;
    17. 		
    18. 		if(n%2 == 0)
    19. 		{
    20. 			for(int i=n, j=s; j>0; i--, j--)
    21. 			{
    22. 				cout << j <<  " " << i << " "; 
    23. 			}
    24. 		}
    25. 		else
    26. 		{
    27. 			cout << s+1 << " ";
    28. 			
    29. 			int i, j;
    30. 			for(i=n, j=s; j>0; i--, j--)
    31. 			{
    32. 				cout << i <<  " " << j << " "; 
    33. 			}
    34. 		}
    35. 		
    36. 		cout << endl;
    37. 	}
    38. 	
    39. 	return 0;
    40. }

     

    E - Technical Support

    题目翻译：

    你在一家大公司的技术支持质量控制部门工作。您的工作是确保所有客户问题都已解决。
    今天，您需要查看客户和技术支持经理之间的对话副本。根据工作规则，客户机的每条消息后面必须有一条或几条消息，这是支持经理的答案。然而，有时客户问问题的速度太快，以至于在客户问了一些新问题之后，经理对旧问题的一些回答就会出现。
    由于隐私政策，您无法获得消息的全文，只能看到消息的顺序以及每条消息的类型：客户问题或技术支持经理的答复。保证对话从客户的问题开始。
    您必须确定此对话框是否符合上述工作规则，或者是否确实违反了这些规则。 

    输入
    每个测试包含多个测试用例。第一行包含测试用例的数量t（1<500）。测试用例描述如下。
    每个测试用例的第一行包含一个整数（1100）-对话框中的消息总数。
    每个测试用例的第二行由n个字符“Q”和“A”组成，按时间顺序描述对话框中的消息类型。字符“”表示带有客户问题的消息，字符“A”表示带有技术支持经理答案的消息。保证行中的第一个字符等于“”
    输出
    对于每个测试用例，如果对话框可能对应于工作规则，则打印“是”（不带引号），否则打印“否”（不含引号）。

    思路：

    让我们从左到右处理字符串中的每个字符，并存储未回答问题的数量。最初，该值等于零。考虑字符串的第si个字符。如果等于“”，则将Scnts增加一。如果等于“A”，则减1。如果S变为负数，则意味着某些问题已被多次回答。在这种情况下，让我们为cntss指定零。
    如果S在处理完所有字符串后都等于零，那么所有问题都得到了回答，并且答案是“是”。否则，答案是“否”。

    AC

    1. #include
    2.  
    3. using namespace std;
    4.  
    5. bool flag = false;
    6.  
    7. int main()
    8. {
    9. 	int t;
    10. 	cin >> t;
    11. 	while(t--)
    12. 	{
    13. 		flag = false;
    14. 		
    15. 		int k;
    16. 		cin >> k;		
    17. 		
    18. 		string n;
    19. 		cin >> n;
    20. 		
    21. 		int v = k-1;
    22. 		int s = 0;
    23. 		int m = 0;
    24. 		
    25. 		while(v >= 0)
    26. 		{
    27. 			if(n[k-1] == 'Q')
    28. 			{
    29. 				flag = true;
    30. 				break;
    31. 			}
    32. 			
    33. 			while(n[v] == 'A')
    34. 			{
    35. 				m++;
    36. 				v--;
    37. 			//	cout << v << endl;
    38. 			}
    39. 			
    40. 			while(n[v] == 'Q')
    41. 			{
    42. 				s++;
    43. 				v--;
    44. 			//	cout << v << endl;
    45. 			}
    46. 			
    47. 		//	cout << s << m;
    48. 			
    49. 			if(s>m)
    50. 			{
    51. 				flag = true;
    52. 				break;
    53. 			}
    54.  
    55. 		}
    56. 		
    57. 	
    58. 		if(flag)
    59. 		{
    60. 			cout << "No" << endl;
    61. 		}
    62. 		else
    63. 		{
    64. 			cout << "Yes" << endl;
    65. 		}
    66. 		
    67. 	}
    68. 	return 0;
    69. }

    F - Divisibility by 2^n

     

    题意：

    给定数列a1,a2,....an

    令ans=a1*a2*a2*....an

    每次可以选择一个i（只能选一次），使得ai=ai*i

    若操作后存在（2^n）| ans，输出最小的操作次数，否则输出-1

    解：

    可以发现，ans的结果与操作是可以分离开的

    如果(2^n)|ans,则ans的2的幂次>=n

    在输入的时候即可处理ans的2的幂次，记为cnt

    cnt>=n,不需要处理，输出0

    cnt

    考虑下标i 的贡献，显然我们需要先操作贡献最大的

    注意到只有偶数有贡献，预处理下标2的贡献

    不需要对i分解，利用dp的思想（状态保存），f(i)=f(i/2)+1,递推即可

    1. #include
    2. using namespace std;
    3. using ll=long long;
    4. const int maxn=2e5+2e1;
    5. arrayf;
    6. ll div(ll x)
    7. {
    8.     ll cnt=0;
    9.     while(x%2==0){cnt++;x/=2;}
    10.     return cnt;
    11. }
    12. void init()
    13. {
    14.     f[2]=1;
    15.     for(int i=4;i2)
    16.     {
    17.         f[i]=f[i/2]+1ll;
    18.     }
    19. }
    20. void find_two(int n,ll cnt)
    21. {
    22.     vectora;
    23.     for(int i=2;i<=n;i+=2)
    24.     {
    25.         a.emplace_back(f[i]);
    26.     }
    27.     sort(a.rbegin(),a.rend());
    28.     ll k=0,cur=0;
    29.     for(const auto&i:a)
    30.     {
    31.         cur+=i;k++;
    32.         if(cur>=cnt){cout<"\n";return;}
    33.     }
    34.     cout<<"-1\n";
    35. }
    36. void solve()
    37. {
    38.     int n;cin>>n;
    39.     ll ans=0;ll x;
    40.     for(int i=0;i
    41.     {
    42.         cin>>x;
    43.         ans+=div(x);
    44.     }
    45.     ll cnt=n-ans;
    46.     if(cnt<=0)cout<<"0\n";
    47.     else
    48.     {
    49.         find_two(n,cnt);
    50.     }
    51. }
    52. int main()
    53. {
    54.     init();
    55.     int t;cin>>t;
    56.     while(t--)
    57.     {
    58.         solve();
    59.     }
    60.     return 0;
    61. }
    1. #include
    2.  
    3. using namespace std;
    4.  
    5. const int N = 2e5+10;
    6. int a[N];
    7.  
    8.  
    9. int main()
    10. {
    11. 	int t;
    12. 	cin >> t;
    13. 	
    14. 	while(t--)
    15. 	{
    16. 		int n;
    17. 		cin >> n;
    18. 		int sum = 0;
    19. 		
    20. 		for(int i=1; i<=n; i++)
    21. 		{
    22. 			int k;
    23. 			cin >> k;
    24. 			
    25. 			while(k%2 == 0)
    26. 			{
    27. 				k/=2;
    28. 				sum++;
    29. 			}
    30. 			
    31. 			int j=i;
    32. 			a[i]=0;
    33. 			
    34. 			while(j%2 == 0)
    35. 			{
    36. 				j/=2;
    37. 				a[i]++;
    38. 			}
    39. 		}
    40. 		
    41. 		sort(a+1, a+1+n, greater<int>());
    42. 		
    43. 		int ans = 0;
    44. 		for(int i=1; i<=n && sum
    45. 		{
    46. 			sum+=a[i];
    47. 			ans++;
    48. 		}
    49. 		
    50. 		if(sum"-1" << endl;
    51. 		else	cout << ans << endl;
    52. 	}
    53. 	
    54. 	return 0;
    55. }

    G - 迷宫

    这是一道经典的深度搜索题目 我们使用二维数据去存下该地图，如有障碍物则该数组位置标为1，经历过的路径我们将其标为2 如果没有障碍并且不是自己走过的，就进一步搜索，把自己走过的路打上标记1，返回时，再将标记还原；这样我们通过判断是否可以到达终点去寻找路径的个数。

    AC 

    1. #include
    2.  
    3. using namespace std;
    4.  
    5. const int N = 10;
    6.  
    7. int n, m ,t;
    8. int sx, sy, fx, fy;
    9. int vis[N][N];
    10.  
    11. int sum;
    12.  
    13. int nx[] = {0, 0, 1, -1};
    14. int ny[] = {1, -1, 0, 0};
    15.  
    16. void dfs(int x, int y)
    17. {
    18. 	vis[sx][sy] = 2;
    19. 	if((x == fx) && ( y == fy))
    20. 	{
    21. 		sum++;
    22. 		return;
    23. 	}
    24. 	
    25. 	for(int i=0; i<4; i++)
    26. 	{
    27. 		int tx = x+nx[i];
    28. 		int ty = y+ny[i];
    29. 		
    30. 		if(tx>=1 && tx<=n && ty<=m && ty>=1 && vis[tx][ty] == 0)
    31. 		{
    32. 			vis[tx][ty] = 2;
    33. 			dfs(tx, ty);
    34. 			vis[tx][ty] = 0;
    35. 		}
    36. 		
    37. 	}
    38. 	
    39. }
    40.  
    41.  
    42.  
    43. int main()
    44. {
    45. 	cin >> n >> m >> t;
    46. 	
    47. 	cin >> sx >> sy >> fx >> fy;
    48. 	
    49. 	while(t--)
    50. 	{
    51. 		int n, m;
    52. 		cin >> n >> m;
    53. 		
    54. 		vis[n][m] = 1;
    55. 	}
    56. 	
    57. 	dfs(sx, sy);
    58.  
    59. 	cout << sum << endl;
    60. 	
    61. 	return 0;
    62. }

    H - Minimize the Thickness

     题意:给一个数列，把它切成若干段，要求每段包含元素的和相等，

    给出定义：thickness，即切成若干段后包含最多元素的那一段的元素数量。

    求怎么切使thickness最小，输出最小的thickness

    思路：此题目需要多次求数列某i ~  j项的和，为了简化代码便于实现，把数列每一项元素替换为他的前缀和(前缀和就是从某项开始,之前所有项的和)。

    eg:  数列  {a1 a2 a3 a4}  替换为{S1 S2 S3 S4}  

    如果用枚举，我们只需要枚举切前k项作为第一段，此时段的元素的和便确定，之后只需要遍历第一段后的数组元素，判断这么切能不能使最后所有段的和相等，若符合，且该种分法的thickness小于前一种分法，则更新答案。时间复杂度：套两层for，约为O(n^2),TL:2s , 数列项数小于2000,不会超时。

    1. #include
    2.  
    3. using namespace std;
    4.  
    5. const int N = 2020;
    6.  
    7. int n, m;
    8. int a[N];
    9.  
    10. int goo(int i, int sum)
    11. {
    12. 	if(i == m)	return 0;
    13. 	for(int j=i+1, cur=0; j<=m; j++)
    14. 	{
    15. 		cur += a[j-1];
    16. 		
    17. 		if(cur>sum)	return m;
    18. 		if(cur==sum) return max(j-i, goo(j, sum));
    19. 	}
    20. 	return m;
    21. }
    22.  
    23.  
    24. int solve()
    25. {
    26. 	int ans = m;
    27. 	
    28. 	for(int i=0, sur=0; i-1; i++)
    29. 	{
    30. 		sur += a[i];
    31. 		ans = min(ans, goo(0, sur));
    32. 	}
    33. 	
    34. 	return ans;
    35. }
    36.  
    37. int main()
    38. {
    39. 	cin >> n;
    40. 	
    41. 	while(n--)
    42. 	{
    43. 		cin >> m;
    44. 		
    45. 		for(int i=0; i> a[i];
    46. 		
    47. 		cout << solve() << endl;
    48. 	}
    49. 	
    50. 	return 0;
    51. }

    I - Scuza

    题意：有n 个台阶的高度，和k个腿长，求每个腿长能走最长多少米的台阶

    思路：前缀最大值+前缀和+二分

    现将前缀台阶高度和前缀最大值求出（即到达i位置需要的最大腿长），然后每次在前缀最大值数组里找第j个腿长，找到的位置输出该位置的前缀和，即该腿长能走的台阶最高高度

     AC：

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 2e5+10;
    6.  
    7. int main()
    8. {
    9. 	int t;
    10. 	cin >> t;
    11. 	
    12. 	while(t--)
    13. 	{
    14. 		int n, m;
    15. 		cin >> n >> m;
    16. 		
    17. 		vector<long long> pref;
    18. 		vector<int> pref_max;
    19. 		
    20. 		pref.push_back(0);
    21. 		
    22. 		for(int i=0; i
    23. 		{
    24. 			int x;
    25. 			cin >> x;
    26. 			pref.push_back(x+pref.back());
    27. 			
    28. 			if(i==0)	pref_max.push_back(x);
    29. 			else
    30. 			{
    31. 				pref_max.push_back(max(pref_max.back(), x));
    32. 			}
    33. 		}
    34. 		
    35. 		for(int i=0; i
    36. 		{
    37. 			int k;
    38. 			cin >> k;
    39. 			
    40. 			int ans = upper_bound(pref_max.begin(), pref_max.end(), k)-pref_max.begin();
    41. 			
    42. 			cout << pref[ans] << " ";
    43. 		}
    44. 		cout << endl;
    45. 	}
    46. }

  • 相关阅读:
    【LeetCode】省份数量（并查集）
    Qt 创建控件的两种方式
    python爬山算法求函数值
    23. 深度学习 - 多维向量自动求导
    机器学习模型常用评价指标（Accuracy, Precision, Recall、F1-score、MSE、RMSE、MAE、R方）
    伟大的micropython smartconfig 配网它来了！！！
    “对症下药”，高效控价——直击低价成因
    分享一个使用MoviePy库编写的实用脚本示例
    nodejs+vue 医院病历管理系统
    记录一次服务器CPU负载高，利用率正常的处理方法
  • 原文地址：https://blog.csdn.net/qq_62464995/article/details/127772958