周赛（二）
Digital Roots
转跳链接
Factorial
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
给定一个整数n，求n的阶乘末尾0的个数。
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| using namespace std; int main() { int t; cin>>t; while(t--) { int sum=0,temp=5; int n; cin>>n; while(1) { if(n/temp==0) break; sum+=n/temp; temp*=5; } cout<<sum<<endl; } return 0; }
|
思路
末尾的0只能由5和末尾是2，4，6，8的数相乘得到，所以末尾0的个数取决于n分解因式中有多少个5.
注意事项
在求有多少5的因子时，用n/temp(初始化为5)后temp*=5再进入循环可以高效率。
Common Subsequence
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
求两个字符串的最长上升（不下降）子序列。
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| using namespace std; int dp[500][500]; int main() { string X,Y; int i, j; memset(dp,0,sizeof(dp)); while(cin>>X>>Y) { int len1 = X.length(); int len2 = Y.length(); for(i = 1; i <= len1; i++) for(j = 1; j <= len2; j++) { if(X[i-1] == Y[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else if(dp[i][j-1] > dp[i-1][j]) dp[i][j] = dp[i][j-1]; else dp[i][j] = dp[i-1][j]; } cout<<dp[len1][len2]<<endl; } return 0; }
|
思路
典型dp问题。如果字符串匹配，那么这一状态的值等于上一状态的值+1，若不匹配，那么该状态的值为：a串中不匹配的位置与b串匹配的结果和b串不匹配的位置与a串匹配
的结果的较大者。
注意事项
写出状态转移方程是关键，分为匹配成功和不成功两个状态。
A strange lift
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
电梯在每一层都只能上升下降规定的层数，要求从a层上升到b层的最小移动次数。
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| using namespace std; int vis[250],k[250],a,b; int bfs(int k1,int k2) { int now; queue<int>q; q.push(k1); vis[k1]=0; while(!q.empty()) { now=q.front(); q.pop(); if(now==k2) break; int next=now+k[now]; if(next>=1&&next<=b&&!vis[next]) { q.push(next); vis[next]=vis[now]+1; } next=now-k[now]; if(next>=1&&next<=b&&!vis[next]) { q.push(next); vis[next]=vis[now]+1; } } return vis[k2]; } int main() { int n; while(cin>>n>>a>>b) { if(n==0) break; for(int i=1;i<=n;i++) cin>>k[i]; memset(vis,0,sizeof(vis)); cout<<bfs(a,b)<<endl; } return 0; }
|
思路
典型的宽搜问题。使用宽搜+队列快速求解。
注意事项
基础题，需要牢牢掌握。
Shaolin
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
有一个能力值为max的老和尚，新来的和尚需要和老和尚切磋，必须和能力值最接近的老和尚切磋，输入顺序为进入顺序，求输出（切磋）顺序。
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| using namespace std; int main() { map<int,int>m; int n,id,power; while(cin>>n&&n) { m.clear(); m[1000000000]=1; for(int i=1;i<=n;i++) { cin>>id>>power; map<int,int>::iterator it=m.lower_bound(power); if(it==m.end()) { it--; cout<<id<<" "<<it->second<<endl; m[power]=id; continue; } int t1=it->first; int tmp=it->second; if(it!=m.begin()) { it--; if(power-it->first<=t1-power) cout<<id<<" "<<it->second<<endl; else cout<<id<<" "<<tmp<<endl; } else cout<<id<<" "<<it->second<<endl; m[power]=id; } } return 0; }
|
思路
使用stl中的map可以使题目快速得到求解。map中把能力值映射到编号中，再定义一个map中的迭代器it指向m中大于等于power的第一个位置。接着把it的位置分为三种情况：
开头末位和中间，中间又分为插入位置的前者和后者两种情况。
注意事项
it->first:映射map中的键(key),本题为能力值
it->second:映射map中的值(value)，本题为编号
若没有找到，lower_bound返回的是最后一个位置的下一个位置。
map中的lower_bound若返回的是一个迭代器，传参的个数为1，平常当函数使用时传参的个数为3个（也可为4个）：数组的启末位置和查找的索引。
Find Q
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
查找一个字符串中的连续的q中的连续子序列。
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| using namespace std; int main() { char s[100050]; int t; cin>>t; while(t--) { cin>>s; long long int sum=0,i=0; while(s[i]!='\0') { long long int k=0,flag=1; while(s[i]=='q') { i++; k++; flag=0; } sum+=k*(k+1)/2; if(flag) i++; } cout<<sum<<endl; } return 0; }
|
思路
一个长度为k的相同字符串中所有的连续子串个数为：k*(k+1)/2。查找字符串中每个q的起始位置和长度后算出子串个数加入sum中。
注意事项
连续子串的公式可由数学归纳法得出。
