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的因子之后的总个数。

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

#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

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

#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在处理完所有字符串后都等于零，那么所有问题都得到了回答，并且答案是“是”。否则，答案是“否”。

#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，返回时，再将标记还原；这样我们通过判断是否可以到达终点去寻找路径的个数。

#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;
  }
}

XUST——Kcsoftware Part3 题目题解

A - 阶乘后面0的数量

B - 上台阶 easy

C - 查找

D - Kevin and Permutation

E - Technical Support

F - Divisibility by 2^n

G - 迷宫

H - Minimize the Thickness

I - Scuza

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

XUST——Kcsoftware Part3 题目题解

A - 阶乘后面0的数量

B - 上台阶 easy

C - 查找

D - Kevin and Permutation

E - Technical Support

F - Divisibility by 2^n

G - 迷宫

H - Minimize the Thickness

I - Scuza

热门文章

最新文章

相关电子书