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
#include <stdio.h> int main(void) { long long N ; long long x , m ; x = 0 ; scanf("%lld",&N); x=N/5; m=x; while(m!=0) { m=m/5; x+=m; } printf("%lld",x); return 0; }
B - 上台阶 easy
对于该问题，适合用递归的方法来计算。从倒数第一步开始、从未到头思考，倒数第一步可能走了一级台阶，也可能走了两级。对于倒数第一步走一级的情况，可分类成倒数第二步走了一级与两级的情况；对于倒数第一步走了两级的情况，也可分类成倒数第二步走了一级与两级的情况……以此类推，见下图 ：
AC
#include <stdio.h> int arr(int n) { n = n - 1 ; int a = 1 ; int b = 2 ; int c = n ; while (n > 2) { c = a + b ; a = b ; b = c ; n-- ; } return c ; } int main(void) { int n ; int sum ; scanf("%d",&n) ; sum = arr ( n ) ; printf("%d\n", sum ) ; return 0 ; } #include <iostream> using namespace std; int goup(int number){ if(number == 1) return 1; else if(number == 2) return 1; else return goup(number - 1) + goup(number -2); } int main(){ int n; cin >> n; cout << goup(n) << endl; return 0; }
C - 查找
首先题目意思是给一串已经排好了的数字问你某个数字的位置。
如果从1到n扫一遍的话肯定超时。
所以这里用了二分的方法：
首先找到这串数字中间位置的那个数，然后与需要查询的数比较
如果要查询的数小于中间那个数，那么答案肯定在左边
如果要查询的数大于中间那个数，那么答案肯定在右边
如果等于的话继续在左边找，因为找到的位置还不能确定是第一个数
如此重复，直到要查询的区域变为1。
#include<iostream> using namespace std ; const int N = 1e6+10 ; int a[N] ; int n, m , s; int main() { cin >> n >> m ; for(int i=1; i<=n; i++) { cin >> a[i] ; } while(m--) { cin >> s ; int l=1, r=n ; while(l<r) { int mid = l+r >> 1 ; if(a[mid]>=s) r=mid ; else l=mid+1 ; } if(a[l]!=s) cout << "-1 " ; else { cout << l << " " ; } } return 0 ; }
D - Kevin and Permutation
题目翻译：
在他的生日，凯文收到了一组成对的数字1，2，3，…n作为礼物。
他将以一种方式排列这些数字，使得两个连续数字之间的最小绝对差尽可能大。更正式地说，如果他按照P1、P2、…、Pn的顺序排列数字，他希望最大化数值
其中|x|表示x的绝对值。
帮助凯文做到这一点。
题意描述:
给你一个数字 ww, 让你构造一个长度为 ww 的串，其中串元素由 1,2,3......w1,2,3......w 构成，且每个数字只出现一次，要求使得串相邻的两个元素两两之差的最小的绝对值最大
#include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { int n; cin >> n; int s = n/2; if(n%2 == 0) { for(int i=n, j=s; j>0; i--, j--) { cout << j << " " << i << " "; } } else { cout << s+1 << " "; int i, j; for(i=n, j=s; j>0; i--, j--) { cout << i << " " << j << " "; } } cout << endl; } return 0; }
E - Technical Support
题目翻译：
你在一家大公司的技术支持质量控制部门工作。您的工作是确保所有客户问题都已解决。
今天，您需要查看客户和技术支持经理之间的对话副本。根据工作规则，客户机的每条消息后面必须有一条或几条消息，这是支持经理的答案。然而，有时客户问问题的速度太快，以至于在客户问了一些新问题之后，经理对旧问题的一些回答就会出现。
由于隐私政策，您无法获得消息的全文，只能看到消息的顺序以及每条消息的类型：客户问题或技术支持经理的答复。保证对话从客户的问题开始。
您必须确定此对话框是否符合上述工作规则，或者是否确实违反了这些规则。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量t（1<500）。测试用例描述如下。
每个测试用例的第一行包含一个整数（1100）-对话框中的消息总数。
每个测试用例的第二行由n个字符“Q”和“A”组成，按时间顺序描述对话框中的消息类型。字符“”表示带有客户问题的消息，字符“A”表示带有技术支持经理答案的消息。保证行中的第一个字符等于“”
输出
对于每个测试用例，如果对话框可能对应于工作规则，则打印“是”（不带引号），否则打印“否”（不含引号）。
思路：
让我们从左到右处理字符串中的每个字符，并存储未回答问题的数量。最初，该值等于零。考虑字符串的第si个字符。如果等于“”，则将Scnts增加一。如果等于“A”，则减1。如果S变为负数，则意味着某些问题已被多次回答。在这种情况下，让我们为cntss指定零。
如果S在处理完所有字符串后都等于零，那么所有问题都得到了回答，并且答案是“是”。否则，答案是“否”。
AC
#include<bits/stdc++.h> using namespace std; bool flag = false; int main() { int t; cin >> t; while(t--) { flag = false; int k; cin >> k; string n; cin >> n; int v = k-1; int s = 0; int m = 0; while(v >= 0) { if(n[k-1] == 'Q') { flag = true; break; } while(n[v] == 'A') { m++; v--; // cout << v << endl; } while(n[v] == 'Q') { s++; v--; // cout << v << endl; } // cout << s << m; if(s>m) { flag = true; break; } } if(flag) { cout << "No" << endl; } else { cout << "Yes" << endl; } } return 0; }
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<n,需要处理出 n-cnt个2
考虑下标i 的贡献，显然我们需要先操作贡献最大的
注意到只有偶数有贡献，预处理下标2的贡献
不需要对i分解，利用dp的思想（状态保存），f(i)=f(i/2)+1,递推即可
#include<bits/stdc++.h> using namespace std; using ll=long long; const int maxn=2e5+2e1; array<ll,maxn>f; ll div(ll x) { ll cnt=0; while(x%2==0){cnt++;x/=2;} return cnt; } void init() { f[2]=1; for(int i=4;i<maxn;i+=2) { f[i]=f[i/2]+1ll; } } void find_two(int n,ll cnt) { vector<ll>a; for(int i=2;i<=n;i+=2) { a.emplace_back(f[i]); } sort(a.rbegin(),a.rend()); ll k=0,cur=0; for(const auto&i:a) { cur+=i;k++; if(cur>=cnt){cout<<k<<"\n";return;} } cout<<"-1\n"; } void solve() { int n;cin>>n; ll ans=0;ll x; for(int i=0;i<n;i++) { cin>>x; ans+=div(x); } ll cnt=n-ans; if(cnt<=0)cout<<"0\n"; else { find_two(n,cnt); } } int main() { init(); int t;cin>>t; while(t--) { solve(); } return 0; } #include<bits/stdc++.h> using namespace std; const int N = 2e5+10; int a[N]; int main() { int t; cin >> t; while(t--) { int n; cin >> n; int sum = 0; for(int i=1; i<=n; i++) { int k; cin >> k; while(k%2 == 0) { k/=2; sum++; } int j=i; a[i]=0; while(j%2 == 0) { j/=2; a[i]++; } } sort(a+1, a+1+n, greater<int>()); int ans = 0; for(int i=1; i<=n && sum<n; i++) { sum+=a[i]; ans++; } if(sum<n) cout << "-1" << endl; else cout << ans << endl; } return 0; }
G - 迷宫
这是一道经典的深度搜索题目 我们使用二维数据去存下该地图，如有障碍物则该数组位置标为1，经历过的路径我们将其标为2 如果没有障碍并且不是自己走过的，就进一步搜索，把自己走过的路打上标记1，返回时，再将标记还原；这样我们通过判断是否可以到达终点去寻找路径的个数。
AC
#include<bits/stdc++.h> using namespace std; const int N = 10; int n, m ,t; int sx, sy, fx, fy; int vis[N][N]; int sum; int nx[] = {0, 0, 1, -1}; int ny[] = {1, -1, 0, 0}; void dfs(int x, int y) { vis[sx][sy] = 2; if((x == fx) && ( y == fy)) { sum++; return; } for(int i=0; i<4; i++) { int tx = x+nx[i]; int ty = y+ny[i]; if(tx>=1 && tx<=n && ty<=m && ty>=1 && vis[tx][ty] == 0) { vis[tx][ty] = 2; dfs(tx, ty); vis[tx][ty] = 0; } } } int main() { cin >> n >> m >> t; cin >> sx >> sy >> fx >> fy; while(t--) { int n, m; cin >> n >> m; vis[n][m] = 1; } dfs(sx, sy); cout << sum << endl; return 0; }
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,不会超时。
#include<iostream> using namespace std; const int N = 2020; int n, m; int a[N]; int goo(int i, int sum) { if(i == m) return 0; for(int j=i+1, cur=0; j<=m; j++) { cur += a[j-1]; if(cur>sum) return m; if(cur==sum) return max(j-i, goo(j, sum)); } return m; } int solve() { int ans = m; for(int i=0, sur=0; i<m-1; i++) { sur += a[i]; ans = min(ans, goo(0, sur)); } return ans; } int main() { cin >> n; while(n--) { cin >> m; for(int i=0; i<m; i++) cin >> a[i]; cout << solve() << endl; } return 0; }
I - Scuza
题意：有n 个台阶的高度，和k个腿长，求每个腿长能走最长多少米的台阶
思路：前缀最大值+前缀和+二分
现将前缀台阶高度和前缀最大值求出（即到达i位置需要的最大腿长），然后每次在前缀最大值数组里找第j个腿长，找到的位置输出该位置的前缀和，即该腿长能走的台阶最高高度
AC：
#include <bits/stdc++.h> using namespace std; const int N = 2e5+10; int main() { int t; cin >> t; while(t--) { int n, m; cin >> n >> m; vector<long long> pref; vector<int> pref_max; pref.push_back(0); for(int i=0; i<n; i++) { int x; cin >> x; pref.push_back(x+pref.back()); if(i==0) pref_max.push_back(x); else { pref_max.push_back(max(pref_max.back(), x)); } } for(int i=0; i<m; i++) { int k; cin >> k; int ans = upper_bound(pref_max.begin(), pref_max.end(), k)-pref_max.begin(); cout << pref[ans] << " "; } cout << endl; } }
