牛客OI赛制测试赛1（ＡＢＣＤＥＦ）

链接：https://www.nowcoder.com/acm/contest/181/A
来源：牛客网

斐波那契

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

设f[i]表示斐波那契数论的第i项
f[1]=1,f[2] =1,f[i] = f[i - 1] + f[i - 2]
给定一个n
求

输入描述:

一个整数n

输出描述:

一个整数，表示答案

示例1

输入

复制

输出

复制

备注:

对于

$30 \%$

的数据，

$n \leqslant 5$

对于

$50 \%$

的数据，

$n \leqslant 10^5$

对于

$80 \%$

的数据，

$n \leqslant 10^{15}$

对于

$100 \%$

的数据，

$2 \leqslant n \leqslant 10^{1000000}$



看起来挺难的，其实手写几个就可以看出规律了．判断奇偶．

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 char s[1000005];
 4 int main(){
 5     cin>>s;
 6     int len = strlen(s);
 7     int x = s[len-1]-'0';
 8     if(x%2)
 9         cout<<"-1"<<endl;
10     else
11         cout<<"1"<<endl;
12     return 0;
13 }

链接：https://www.nowcoder.com/acm/contest/181/B
来源：牛客网

送分题

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

对于一套题来说，没有一道送分题，就很不符合常理，但是我又懒得写送分题，所以你可以直接复制以下代码，即可ac本题.

#include<cstdio>#include<iostream> using namespace std; int a,b,c; int main(){long long l=1,r=int(1e9)<<1:cin》a>>b;while(r-l>1){c=(l+r)>>1;if(c-b<a)l=c;else if(c-b>a)r=c;else return printf("%d ",c); } if(l!=r)return printf("%d ",r); }

输入描述:

输入共一行，两个整数a和b，范围在int之间

输出描述:

输出一个整数表示答案

示例1

输入

复制

5 123

输出

复制

128

这种题放出来真的是签到，
我就没看题目描述，看完样例直接输进去，都没测．

 1 #include <iostream>
 2 #define ll long long int
 3 using namespace std;
 4 
 5 int main(){
 6     ll n,m;
 7     cin>>n>>m;
 8     cout<<n+m<<endl;
 9     return 0;
10 }

链接：https://www.nowcoder.com/acm/contest/181/C
来源：牛客网

序列

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

小a有n个数，他想把他们划分为连续的权值相等的k段，但他不知道这是否可行。

每个数都必须被划分

这个问题对他来说太难了，于是他把这个问题丢给了你。

输入描述:

第一行为两个整数n,q，分别表示序列长度和询问个数。
第二行有n个数，表示序列中的每个数。
接下来的q行，每行包含一个数k，含义如题所示。

输出描述:

输出q行，每行对应一个数Yes或者No，分别表示可行/不可行

示例1

输入

复制

输出

复制

Yes
No
Yes

备注:

对于 $30\%$ 的数据， $n \leqslant 10,q \leqslant 20$

对于 $60\%$ 的数据， $n \leqslant 2000,q \leqslant 2000$

对于 $100\%$ 的数据， $n \leqslant 100000,q \leqslant 1000000$

设a_i表示数列中的第i个数，保证 $\sum a_i \leqslant 10^{13}$

保证数据完全随机

这题说实话，后台数据有点问题．本应该不能过的代码，却能得100分．

比如这组数据：

5 3
12 -3 -3 -3 9
4
2
1

输出应该如下：

No
Yes
Yes

正确代码应该如此如此，这般这般．

 1 #include <bits/stdc++.h>
 2 #define ll long long int
 3 using namespace std;
 4 const int maxn = 2 * 1e6 + 10, inf = 1e9 + 10;
 5 int a[maxn];
 6 bool ans[maxn];
 7 int main() {
 8     int n , m ;
 9     cin>>n>>m;
10     ll sum = 0;
11     for(int i = 1; i <= n; i++)
12         cin>>a[i], sum += a[i];
13     for(int i = 1; i <= n; i++) {
14         if(sum % i != 0) {
15             ans[i] = 0;
16             continue;
17         }
18         ll cur = 0, k = 0;
19         for(int j = 1; j <= n; j++) {
20             cur += a[j];
21             if(cur == sum / i)
22                 cur = 0, k++;
23         }
24         ans[i] = (cur == 0 && k == i);
25     }
26     while(m--) {
27         int x;
28         cin>>x;
29         puts(!ans[x] ? "No" : "Yes");
30     }
31 }

这是我过了，但是过不了自己出的数据的代码．

 1 #include <bits/stdc++.h>
 2 #define ll long long int
 3 #define N 100005
 4 using namespace std;
 5 map<ll,int> mp;
 6 ll n,m;
 7 ll x;
 8 ll an[N];
 9 int main(){
10     scanf("%lld%lld",&n,&m);
11     ll sum = 0;
12     for(int i=0;i<n;i++){
13         cin>>an[i];
14         sum += an[i];
15         if(mp.count(sum)==0){
16             mp[sum] = 1;
17         }else{
18             mp[sum] ++;
19         }
20     }
21     while(m--){
22         scanf("%lld",&x);
23         if(sum%x){
24             printf("No
");
25             continue;
26         }
27         bool prime = true;
28         for(ll i=sum/x;i<=sum;i+=sum/x){
29             if(mp.count(i)==0){
30                 prime = false;
31                 break;
32             }
33         }
34         if(prime){
35             printf("Yes
");
36         }else{
37             printf("No
");
38         }
39     }
40     return 0;
41 }

链接：https://www.nowcoder.com/acm/contest/181/D
来源：牛客网

小叶的巡查

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld

题目描述

8102年，牛客系列竞赛空前繁荣。为了更好地管理竞赛，小叶决定巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了小叶最常做的事情。小叶有一个钱袋，用于存放往来城市间的路费。

这个国家有一套优秀的交通方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

如果不在某个城市停下来修整，在连续行进过程中，小叶所花的路费与他已走过的距离有关，在走第x-1千米到第x千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

因为国家力挺牛客系列竞赛，所以国家会给小叶报销全部的路费。

现在组织想知道：小叶从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入描述:

输入的第一行包含一个整数n，表示包括首都在内的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述高速路（高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。

输出描述:

输出一个整数，表示小叶最多花费的路费是多少。

示例1

输入

复制

输出

复制

备注:

n<23333

两遍ｄｆｓ就可以找到最长路径．

 1 #include <bits/stdc++.h>
 2 #define N 24333
 3 #define ll long long int
 4 using namespace std;
 5 struct Node{
 6     int to;
 7     ll val;
 8 };
 9 vector<Node> v[N];
10 bool vis[N],is[N];
11 ll ans,sum = 0;
12 
13 void dfs(int x,ll al){
14     vis[x] = 1;
15     if(al>sum){
16         sum = al;
17         ans = x;
18     }
19     for(int i=0;i<v[x].size();i++){
20         Node node = v[x][i];
21         if(vis[node.to]==0){
22             dfs(node.to,al+node.val);
23         }
24     }
25 }
26 
27 
28 int main(){
29     int n;
30     cin>>n;
31     int x,y;
32     ll z;
33     for(int i=1;i<n;i++){
34          cin>>x>>y>>z;
35          Node it ;
36          it.val = z,it.to = y;
37          v[x].push_back(it);
38          it.to = x;
39          v[y].push_back(it);
40     }
41     dfs(1,0);
42     sum = 0;
43     memset(vis,0,sizeof(vis));
44     dfs(ans,0);
45     ll cnt;
46     cnt = sum*10 + (sum*(sum+1))/2;
47     cout<<cnt<<endl;
48     return 0;
49 }

链接：https://www.nowcoder.com/acm/contest/181/E
来源：牛客网

旅行青蛙

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

一只青蛙出去旅游，因为中国有一句古话说的好：“由简入奢易，由奢入俭难”，所以这只青蛙当看的当前景点比前面看过的景点差的时候，青蛙就会说“不开心”为了避免这只青蛙说“不开心”，并且使青蛙看的景点尽量的多，所以他请你帮忙给他安排一条线路，使青蛙可以看到尽量多的景点，并且不走回头路。

输入描述:

第一行为一个整数n，表示景点的数量
接下来n行，每行1个整数，分别表示第i个景点的质量

输出描述:

一个整数，表示青蛙最多可以看到几个景点

示例1

输入

复制

输出

复制

备注:

景点质量为1到n+23的整数
10<=n<23 10%

23<=n<233 30%

233<=n<2333 60%

2333<=n<23333 100%

这题最长非递减序列．
模板题．

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int a[40005];
 5 int dp[40005];
 6 
 7 int main(){
 8     int n;
 9     scanf("%d",&n);
10     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
11     if (n==0){
12         printf("0
");
13         return 0;
14     }
15     dp[1]=a[1];  //初始化
16     int len=1;
17     for (int i=2;i<=n;i++){
18         if (a[i]>=dp[len]) dp[++len]=a[i];
19         else{
20             int j=upper_bound(dp+1,dp+len+1,a[i])-dp;
21             dp[j]=a[i];
22         }
23     }
24     printf("%d
",len);
25     return 0;
26 }

链接：https://www.nowcoder.com/acm/contest/181/F
来源：牛客网

子序列

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给出一个长度为n的序列，你需要计算出所有长度为k的子序列中，除最大最小数之外所有数的乘积相乘的结果

输入描述:

第一行一个整数T，表示数据组数。
对于每组数据，第一行两个整数N，k，含义如题所示

接下来一行N个整数，表示给出的序列

保证序列内的数互不相同

输出描述:

对于每组数据，输出一个整数表示答案，对

取模
每组数据之间以换行分割

示例1

输入

复制

3
4 3 
5 3 1 4
5 4
3 7 5 2 1
10 3 
100 1020 2050 102 12 235 4 57 32135 54354

输出

复制

144
81000
521918013

说明

第一组数据解释

所有长度为3的子序列为 $\ (5, 3, 1)\ (5, 3, 4) \ (3, 1, 4) \ (5, 1, 4)$

最终答案为

备注:

对于

$30 \%$

的数据：

$T \leqslant 10, N \leqslant 100, k \leqslant N$


对于

$60 \%$

的数据：

$T \leqslant 10, N \leqslant 1000, k \leqslant N$


对于

$100\%$

的数据：

$T \leqslant 1000, N \leqslant 1000, k \leqslant N$


保证序列中的元素互不相同且

$\leqslant 10^6$

，

$k \geqslant 3$


这题应该算是压轴题啦．
欧拉降幂＋组合数
对于每个数的累乘次数，将其看成是所有的次数之和减去最大数和最小数的种数

指数爆炸的时候就要降幂

就是求a^b mod c

可以转化为

a^(b mod phi(c)+phi(c)) mod c

phi 为欧拉函数

 1 #include <bits/stdc++.h>
 2 #define ll long long int
 3 #define mod (int)(1e9+7)
 4 #define N 1005
 5 using namespace std;
 6 ll c[N][N];
 7 
 8 ll poww(ll a,ll b){
 9     ll ans = 1;
10     while(b){
11         if(b&1){
12             ans = (ans*a)%mod;
13         }
14         b>>=1;
15         a = (a*a)%mod;
16     }
17     return ans;
18 }
19 
20 void init(){
21     c[0][0] = 1;
22     for(int i=0;i<=1000;++i){
23         for(int j=0;j<=i;++j){
24             if(j==0||i==j){
25                 c[i][j] = 1;
26             }else{
27                 c[i][j] = (c[i-1][j]+c[i-1][j-1])%(mod-1);//mod的欧拉值为(mod-1)
28             }
29         }
30     }
31 }
32 
33 int t,n,m;
34 ll a[N];
35 int main(){
36     ios::sync_with_stdio(false);
37     cin.tie(0),cout.tie(0);
38     cin>>t;
39     init();
40     while(t--){
41         cin>>n>>m;
42         for(int i=0;i<n;i++)
43             cin>>a[i];
44         sort(a,a+n);
45         ll cnt = 1;
46         for(int i=0;i<n;i++){
47             ll tmp = c[n-1][m-1];
48             // if(n-i-1>=m-1)
49                 tmp = (tmp-c[n-i-1][m-1]+mod-1)%(mod-1);
50             // if(i>=m-1)
51                 tmp = (tmp - c[i][m-1] + mod-1)%(mod-1);
52             cnt = cnt*poww(a[i],tmp)%mod;
53         }
54         cout<<cnt<<endl;
55     }
56     return 0;
57 }
58 
59 // ll phi( ll n ) { //欧拉函数
60 //     ll ans = n;
61 //     for( ll i = 2; i*i <= n; i ++ ) {
62 //         if( n%i == 0 ) {
63 //             ans -= ans/i;
64 //             while( n%i == 0 ) {
65 //                 n /= i;
66 //             }
67 //         }
68 //     }
69 //     if( n > 1 ) {
70 //         ans -= ans/n;
71 //     }
72 //     return ans;
73 // }