牛客-常州大学新生寒假训练会试

妖狐艹你老母 2022-05-31 05:26 184阅读 0赞

####  ####

## A.添加逗号 ##

## 题目描述 ##

对于一个较大的整数 N(1<=N<=2,000,000,000)

比如 980364535，我们常常需要一位一位数这个数字是几位数，但是如果在这 个数字每三位加一个逗号，它会变得更加易于朗读。

因此，这个数字加上逗号成如下的模样：980,364,535请写一个程序帮她完成这件事情

## 输入描述: ##

一行一个整数 N

## 输出描述: ##

一行一个字符串表示添加完逗号的结果

思路：一眼签到题 直接上代码

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  \#include <iostream>  
2.  \#include <cstring>  
3.  \#include <set>  
4.  \#include <map>  
5.  \#include <vector>  
6.  \#include <algorithm>  
7.    
8.  using namespace std;  
9.  typedef long long ll;  
10. const int maxn = 1e6+11;  
11. int prime\[maxn\],cnt;  
12. bool is\_prime\[maxn\];  
13. int main()\{  
14.        
15.     ll n;  
16.     char str\[15\];  
17.     char ans\[20\];  
18.     while(cin>>str)\{  
19.         int len = strlen(str);  
20.         int cnt = 0;  
21.         int a\_c = 0;  
22.         for(int i=len-1;i>=0;i--)\{  
23.                ans\[a\_c++\] = str\[i\];  
24.                cnt++;  
25.                if(cnt==3)\{  
26.                     if(i==0) break;  
27.                     ans\[a\_c++\] = ',';  
28.                     cnt = 0;  
29.                \}  
30.         \}  
31.         for(int i=a\_c-1;i>=0;i--) cout<<ans\[i\];  
32.   
33.         cout<<endl;  
34.     \}  
35.   
36. \}

#include <iostream>
    #include <cstring>
    #include <set>
    #include <map>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    typedef long long ll;
    const int maxn = 1e6+11;
    int prime[maxn],cnt;
    bool is_prime[maxn];
    int main(){
         
        ll n;
        char str[15];
        char ans[20];
        while(cin>>str){
            int len = strlen(str);
            int cnt = 0;
            int a_c = 0;
            for(int i=len-1;i>=0;i--){
                   ans[a_c++] = str[i];
                   cnt++;
                   if(cnt==3){
                        if(i==0) break;
                        ans[a_c++] = ',';
                        cnt = 0;
                   }
            }
            for(int i=a_c-1;i>=0;i--) cout<<ans[i];
    
            cout<<endl;
        }
    
    }

## B.对称 ##

## 题目描述 ##

萌新AA喜欢对称，最近她喜欢把棋子放进她的棋盘中，这个棋盘是由 N×M 个格 子构成的(1 <= N <= 1,000,000,000;1<=M<=1,000,000,000) 为了保证对称，AA  会以这样的方式摆放她的棋子。她把棋子放在棋盘正中央的方格内， 如果不存在这样的方格，她就会停止。然后她以这个方格为中心把棋盘分成四部分，然后对于每 个小棋盘进行上述的操作。 下面是一个 N=7,M=15 的例子，其中'C'表示棋子

![303891_1516888812084_3675A951DB088D22E0F6C50771A6063C][]

这样子，需要 21个棋子。如果 N=M=5 的话，AA只需要摆放一个棋子，因为分成的四 个小棋盘分别是 2×2 的大小，无法在放进去新的棋子。现在，请你帮助 AA来计算，需要 多少个棋子。

## 输入描述: ##

一行两个整数 N,M

## 输出描述: ##

一行一个整数，即需要的棋子数

思路：只有n和m是奇数时才能分成4部分.

比如样例 n=7 m=15

第一次 :  n%2==1 m%2==1 时可以拆的 ，这次放置了1个棋子

第二次:  (n/2)%2==1 (m/2)%2==1 也满足，这次放了4个棋子

第三次 .......  这次放了16个棋子

你会发现 其实是个等比数列，公比是4

只要我们求出 n（即能拆多少次）就能求出等比数列和

不过这里注意一个坑点，就是当n==1||m==1时 ans=1;

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  \#include <iostream>  
2.  \#include <stdio.h>  
3.  \#include <cstring>  
4.  \#include <set>  
5.  \#include <map>  
6.  \#include <vector>  
7.  \#include <algorithm>  
8.  using namespace std;  
9.  typedef unsigned long long ll;  
10. const int maxn = 1e6+11;  
11. int prime\[maxn\],cnt;  
12. bool is\_prime\[maxn\];  
13. struct qwe\{  
14.     int h,m,s;  
15. \}q\[5015\];  
16. ll q\_mod(ll x,ll n)\{  
17.     ll res = 1;  
18.     while(n)\{  
19.         if(n&1) res =res\*x;  
20.         x = x\*x;  
21.         n>>=1;  
22.     \}  
23.     return res;  
24. \}  
25. int main()\{  
26.     ll n,m;  
27.     while(scanf("%lld%lld",&n,&m)!=EOF)\{  
28.         ll cnt = 0;  
29.         ll ans = 0;  
30.         if((n==1&&m!=1)||(n!=1&&m==1))\{  
31.             cout<<"1"<<endl;  
32.         \}else\{  
33.             while((n%2==1)&&(m%2==1))\{  
34.                 cnt++;  
35.                 if(n==1||m==1) break;  
36.                 n/=2;  
37.                 m/=2;  
38.             \}  
39.              ans += (q\_mod(4,cnt)-1)/3;  
40.              printf("%lld\\n",ans);  
41.         \}  
42.   
43.   
44.     \}  
45.     return 0;  
46. \}

#include <iostream>
    #include <stdio.h>
    #include <cstring>
    #include <set>
    #include <map>
    #include <vector>
    #include <algorithm>
    using namespace std;
    typedef unsigned long long ll;
    const int maxn = 1e6+11;
    int prime[maxn],cnt;
    bool is_prime[maxn];
    struct qwe{
        int h,m,s;
    }q[5015];
    ll q_mod(ll x,ll n){
        ll res = 1;
        while(n){
            if(n&1) res =res*x;
            x = x*x;
            n>>=1;
        }
        return res;
    }
    int main(){
        ll n,m;
        while(scanf("%lld%lld",&n,&m)!=EOF){
            ll cnt = 0;
            ll ans = 0;
            if((n==1&&m!=1)||(n!=1&&m==1)){
                cout<<"1"<<endl;
            }else{
                while((n%2==1)&&(m%2==1)){
                    cnt++;
                    if(n==1||m==1) break;
                    n/=2;
                    m/=2;
                }
                 ans += (q_mod(4,cnt)-1)/3;
                 printf("%lld\n",ans);
            }
    
    
        }
        return 0;
    }

## C.竞赛技巧 ##

##  ##

## 题目描述 ##

在ACM竞赛中，当遇到有两个队伍（人） 解出相同的题目数量的时候，我们需要通过他们解决问题的总时间进行排序。

一共有 N(1<=N<=5,000)条时间被以时(0<=Hours<=99)， 分(0<=Minutes<=59)，秒(0<=Seconds<=59)的形式记录。

你必须要把他们按时，分，秒排序为 升序，最少的时间最先。 考虑到如下的样例，这三个解出相同题目数量的时间为

11:20:20

11:15:12

14:20:14

正确的排序结果应该是这样的：

11:15:12

11:20:20

14:20:14

## 输入描述: ##

第 1 行，一个整数 N 第 2~n+1 行，每行 3 个整数，表示时，分，秒

## 输出描述: ##

共 n 行，每行 3 个整数，表示排序完后的结果

## 思路：写个排序函数 直接sort  ##

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  \#include <iostream>  
2.  \#include <stdio.h>  
3.  \#include <cstring>  
4.  \#include <set>  
5.  \#include <map>  
6.  \#include <vector>  
7.  \#include <algorithm>  
8.    
9.  using namespace std;  
10. typedef long long ll;  
11. const int maxn = 1e6+11;  
12. int prime\[maxn\],cnt;  
13. bool is\_prime\[maxn\];  
14. struct qwe\{  
15.     int h,m,s;  
16. \}q\[5015\];  
17.   
18. int cmp(qwe a,qwe b)\{  
19.     if(a.h!=b.h)\{  
20.         return a.h<b.h;  
21.     \}  
22.     else if(a.m!=b.m)\{  
23.         return a.m<b.m;  
24.     \}  
25.     else return a.s<b.s;  
26. \}  
27. int main()\{  
28.       
29.     int n;  
30.     while(scanf("%d",&n)!=EOF)\{  
31.         for(int i=0;i<n;i++)\{  
32.             scanf("%d%d%d",&q\[i\].h,&q\[i\].m,&q\[i\].s);  
33.         \}  
34.         sort(q,q+n,cmp);  
35.         for(int i=0;i<n;i++)\{  
36.             printf("%d %d %d\\n",q\[i\].h,q\[i\].m,q\[i\].s);  
37.         \}  
38.   
39.     \}  
40.     return 0;  
41. \}

#include <iostream>
    #include <stdio.h>
    #include <cstring>
    #include <set>
    #include <map>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    typedef long long ll;
    const int maxn = 1e6+11;
    int prime[maxn],cnt;
    bool is_prime[maxn];
    struct qwe{
        int h,m,s;
    }q[5015];
    
    int cmp(qwe a,qwe b){
        if(a.h!=b.h){
            return a.h<b.h;
        }
        else if(a.m!=b.m){
            return a.m<b.m;
        }
        else return a.s<b.s;
    }
    int main(){
        
        int n;
        while(scanf("%d",&n)!=EOF){
            for(int i=0;i<n;i++){
                scanf("%d%d%d",&q[i].h,&q[i].m,&q[i].s);
            }
            sort(q,q+n,cmp);
            for(int i=0;i<n;i++){
                printf("%d %d %d\n",q[i].h,q[i].m,q[i].s);
            }
    
        }
        return 0;
    }

##     ##

## D.训练技巧 ##

## 题目描述 ##

常州大学组织了 新生寒假训练一共N天，每天训练可以获得的训练效果是Ei。但是如果连续训练超过K天，萌新们会受不了而被劝退。

现在负责人想知道，如何安排能保证萌新不会被劝退并且能获得最大的训练效果。

## 输入描述: ##

第一行：两个用空格隔开的整数：N和K，1≤N≤100000，1≤K≤N
    第二行到N+1行：第i+1行有一个整数，表示第N天的训练效果是Ei，(0 <= Ei <= 1,000,000,000）

## 输出描述: ##

第一行：单个整数，表示最大的能力之和

思路：这应该是10道题里最好得一题 （大佬勿喷）

题目要求我们求最大得训练效果，我们转换下只要求出最小得损失效果，然后用总效果减去即可

怎么求最小损失效果?

我们用dp\[i\]表示在第i天休息得情况下前i天损失得最小效果,很容易想到dp方程为dp\[i\]=min(dp\[j\])+a\[i\] (j是从i-k-->i-1)

那么这样复杂度就是O(n\*k)了

那么我们可以用递增得优先队列维护下\[i-k,i-1\]内得最小值即可。

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  \#include <bits/stdc++.h>  
2.  \#include <cstdio>  
3.  \#include <cmath>  
4.  \#include <queue>  
5.  \#include <cstring>  
6.  \#include <algorithm>  
7.  using namespace std;  
8.  \#define mst(a,b) memset((a),(b),sizeof(a))  
9.  typedef long long ll;  
10. const int maxn = 100005;  
11. const ll mod = 1e9+7;  
12. const ll INF = 1e18;  
13. const double eps = 1e-9;  
14. int n,k;  
15. int a\[maxn\];  
16. ll dp\[maxn\];  
17. struct qwe\{  
18.     ll x;  
19.     int i;  
20.     bool operator < (const qwe& a)const\{  
21.         return x>a.x;  
22.     \}  
23. \};  
24. int main()  
25. \{  
26.     while(scanf("%d%d",&n,&k)!=EOF)  
27.     \{  
28.         priority\_queue<qwe>q;  
29.         qwe tp,num;  
30.         mst(dp,0);  
31.         ll sum=0;  
32.         for(int i=1;i<=n;i++)  
33.         \{  
34.             scanf("%lld",&a\[i\]);  
35.             sum+=a\[i\];  
36.         \}  
37.   
38.         for(int i=1;i<=n;i++)  
39.         \{  
40.             if(k+1>=i)\{  
41.                 dp\[i\] = a\[i\];  
42.                 num.x=a\[i\];  
43.             \}else\{  
44.                 while(q.top().i<(i-k-1)) q.pop();  
45.                 if(q.top().i>=i-k-1)\{  
46.                     dp\[i\] = q.top().x+a\[i\];  
47.                 \}  
48.                 num.x=dp\[i\];  
49.             \}  
50.             //cout<<dp\[i\]<<endl;  
51.             num.i=i;  
52.             q.push(num);  
53.         \}  
54.         ll ans=INF;  
55.         for(int i=n-k;i<=n;i++)                   //求出损失的最小训练效果  
56.         \{  
57.             ans=min(ans,dp\[i\]);  
58.         \}  
59.         printf("%lld\\n",sum-ans);  
60.     \}  
61.     return 0;  
62. \}

#include <bits/stdc++.h>
    #include <cstdio>
    #include <cmath>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define mst(a,b) memset((a),(b),sizeof(a))
    typedef long long ll;
    const int maxn = 100005;
    const ll mod = 1e9+7;
    const ll INF = 1e18;
    const double eps = 1e-9;
    int n,k;
    int a[maxn];
    ll dp[maxn];
    struct qwe{
        ll x;
        int i;
        bool operator < (const qwe& a)const{
            return x>a.x;
        }
    };
    int main()
    {
        while(scanf("%d%d",&n,&k)!=EOF)
        {
            priority_queue<qwe>q;
            qwe tp,num;
            mst(dp,0);
            ll sum=0;
            for(int i=1;i<=n;i++)
            {
                scanf("%lld",&a[i]);
                sum+=a[i];
            }
    
            for(int i=1;i<=n;i++)
            {
                if(k+1>=i){
                    dp[i] = a[i];
                    num.x=a[i];
                }else{
                    while(q.top().i<(i-k-1)) q.pop();
                    if(q.top().i>=i-k-1){
                        dp[i] = q.top().x+a[i];
                    }
                    num.x=dp[i];
                }
                //cout<<dp[i]<<endl;
                num.i=i;
                q.push(num);
            }
            ll ans=INF;
            for(int i=n-k;i<=n;i++)                   //求出损失的最小训练效果
            {
                ans=min(ans,dp[i]);
            }
            printf("%lld\n",sum-ans);
        }
        return 0;
    }

## E.这是道数学题 ##

## 题目描述 ##

已知有一个n+1个数的数列,对于给定的A 0和A n ，当i满足当1<=i<=n-1时有

![303891_1517542209335_60BE8B1D8772AF368C3CB11B8FA9680B][]

现在小星想知道对于这个数列一段区间的和。

## 输入描述: ##

第一行输入四个数 n,A0,An,Q

接下来Q行 每行输入两个数l,r

0=< n,A 0,An<=1e9,Q<=100000

0<=l<=r<=n

## 输出描述: ##

对于每组查询输出Al到Ar的和

思路：

化简一下得：Ai=Ao\*C(n-1,i)/C(n,i)+An\*C(n-1,i-1)/C(n,i);

再简一下得 Ai = Ao\*(n-i)/n+An\*i/n    ps:为什么？自己再纸上搞搞吧

设组数据看下  例如 n=3

A1 = Ao\*2/3+An\*1/3

A2 = Ao\*1/3+An\*2/3

所以 Ao+A1+A2+A3 = Ao\*(3/3+2/3+1/3)+An\*(1/3+2/3+3/3);可以发现分子和是等差和

那么根据给定得区间以及公式即可求出答案

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  \#include<iostream>  
2.  \#include<cstdlib>  
3.  using namespace std;  
4.  typedef long long ll;  
5.  int main()\{  
6.      ll n,Ao,An,q;  
7.      //cin >> n >> Ao >> An >> q;  
8.      scanf("%lld%lld%lld%lld",&n,&Ao,&An,&q);  
9.      for(int i = 1 ; i <=q ;i++)  
10.       \{  
11.         double l,r,a,b;  
12.         scanf("%lf%lf",&l,&r);  
13.         a = (2\*n-l-r)\*(r-l+1)\*1.0/2.0;  
14.         b = (l+r)\*(r-l+1)\*1.0/2.0;  
15.         double s = (a\*Ao+b\*An)\*1.0/n\*1.0;  
16.         printf("%.0f\\n",s);  
17.       \}  
18.     return 0;  
19. \}

#include<iostream>
    #include<cstdlib>
    using namespace std;
    typedef long long ll;
    int main(){
        ll n,Ao,An,q;
        //cin >> n >> Ao >> An >> q;
        scanf("%lld%lld%lld%lld",&n,&Ao,&An,&q);
        for(int i = 1 ; i <=q ;i++)
          {
            double l,r,a,b;
            scanf("%lf%lf",&l,&r);
            a = (2*n-l-r)*(r-l+1)*1.0/2.0;
            b = (l+r)*(r-l+1)*1.0/2.0;
            double s = (a*Ao+b*An)*1.0/n*1.0;
            printf("%.0f\n",s);
          }
        return 0;
    }

## G 零下e度 ##

链接： [https://www.nowcoder.net/acm/contest/78/G][https_www.nowcoder.net_acm_contest_78_G]  
来源：牛客网

## 题目描述 ##

在家好冷!

又多冷呢？

大概是零下e度!

为什么是零下e度呢?

不知道，因为我编不下去了。

求给定一个数n，求出最接近n!/e的整数

## 输入描述: ##

一行一个整数n
    1<=n<=10^8

## 输出描述: ##

一行一个整数，即题目描述中所求，由于这个数字可能很大，我们只需要知道mod 998244353后的结果（出题人负责任地告诉你，这个数字是个质数）

思路 ：

后面才知道 原来是错排公式  （太弱了 好好补充下数论知识才行

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  \#include <iostream>  
2.  using namespace std;  
3.  const int mod = 998244353;  
4.  typedef long long ll;  
5.  int main()\{  
6.    
7.          ll n ;  
8.          cin>>n;  
9.          ll ans;  
10.         if(n==1) ans=1;  
11.         if(n==2) ans=2;  
12.         ll x=0,y=1;  
13.         for(int i=3;i<=n;i++)\{  
14.             ll tem = (x+y)\*(i-1)%mod;  
15.             x=y;y=tem;  
16.         \}  
17.         if(n>2)  
18.             ans = y;  
19.         cout<<ans<<endl;  
20.         return 0;  
21. \}

#include <iostream>
    using namespace std;
    const int mod = 998244353;
    typedef long long ll;
    int main(){
    
        	ll n ;
        	cin>>n;
       	    ll ans;
        	if(n==1) ans=1;
            if(n==2) ans=2;
            ll x=0,y=1;
        	for(int i=3;i<=n;i++){
                ll tem = (x+y)*(i-1)%mod;
                x=y;y=tem;
            }
            if(n>2)
                ans = y;
            cout<<ans<<endl;
        	return 0;
    }

## J同分异构体 ##

这题没什么好说，签到题，数据n<=9 直接推出前9种即可

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

1.  \#include <iostream>  
2.  \#include <cstring>  
3.  \#include <set>  
4.  \#include <map>  
5.  \#include <vector>  
6.  \#include <algorithm>  
7.    
8.  using namespace std;  
9.  typedef long long ll;  
10. const int maxn = 1e6+11;  
11. int prime\[maxn\],cnt;  
12. bool is\_prime\[maxn\];  
13.   
14.   
15. int main()\{  
16.      
17.     int n;  
18.     while(cin>>n)\{  
19.         if(n<=3) cout<<"1"<<endl;  
20.         else if(n==4)\{  
21.             cout<<"2"<<endl;  
22.         \}  
23.         else if(n==5)\{  
24.             cout<<"3"<<endl;  
25.         \}  
26.         else if(n==6)\{  
27.             cout<<"5"<<endl;  
28.         \}  
29.         else if(n==7)\{  
30.             cout<<"9"<<endl;  
31.         \}  
32.         else if(n==8)\{  
33.             cout<<"18"<<endl;  
34.         \}  
35.         else cout<<"35"<<endl;  
36.     \}  
37.     return 0;  
38. \}

[view plain]: http://blog.csdn.net/qq_35916858/article/details/79286925#
[303891_1516888812084_3675A951DB088D22E0F6C50771A6063C]: https://uploadfiles.nowcoder.net/images/20180125/303891_1516888812084_3675A951DB088D22E0F6C50771A6063C
[303891_1517542209335_60BE8B1D8772AF368C3CB11B8FA9680B]: https://uploadfiles.nowcoder.net/images/20180202/303891_1517542209335_60BE8B1D8772AF368C3CB11B8FA9680B
[https_www.nowcoder.net_acm_contest_78_G]: https://www.nowcoder.net/acm/contest/78/G