2018年东北农业大学春季校赛 解题报告

E wyh的阶乘

输入第一行一个整数T(1<=T<=100)，代表测试组数
接下来T行，每行一个数n(1<=n<=10^9)

对于每组测试数据，输出对应答案

5
1
2
3
4
5

0
0
0
0
1

比赛时用c++打标到20以为是5个一组依次增加，交上去WA了，用Python打到100发现是循环除以5加商。
题解：
这个题实际上就是求有多少个5的因子，因为要想末尾出现0，必须要有2*5，那么对于阶乘来说，5的个数肯定会比2的个数少，所以直接找有多少个5的根数就可以了

 1 #include <iostream>
 2 using namespace std;
 3 int slove(int n){
 4     int tot= 0;
 5     while(n > 0){
 6         tot += n / 5;
 7         n = n / 5;
 8     }
 9     return tot;
10 }
11 int main(){
12     int tot;
13     cin>>tot;
14     while(tot--){
15         int n;
16         cin>>n;
17         int ans;
18         ans=slove(n);
19         cout<<ans<<endl;
20     }
21     return 0;
22 }

F wyh的集合
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld


你们wyh学长给你n个点，让你分成2个集合，然后让你将这n个点进行两两连接在一起，连接规则是这样的 
1. 连接的两个点必须在不同的两个集合 
2. 一个集合内部任意两个点之间不能相连 
现在，wyh学长需要让你将这n个点任意分成2个集合之后，最多能连接多少条边？ 




输入描述:
输入第一行一个整数T(1<=T<=100000)
接下来T组测试数据，每组测试数据输入一个整数n(1<=n<=100000)
输出描述:
对于每组测试数据，输出对应答案

示例1


输入

4
0
1
2
4



输出

0
0
1
4



说明

对于4的情况，设4个点为A,B,C,D
第一个集合元素为 A,B
第二个集合元素为C,D
连接的边为AC,AD,BC,BD
此时为最大情况，所以答案为4

题面说的挺高大上的，其实就是求平均数相乘一下因为尽量保证两个集合边数尽可能接近，如果一个集合有n/2条边，另外一个集合就是n-n/2条边，相乘就是结果

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(void) {
 4     ios::sync_with_stdio(false);
 5     cin.tie(NULL);
 6     unsigned long long int ans;
 7     int t, n;
 8     scanf("%d", &t);
 9     while (t--) {
10         scanf("%d", &n);
11         if (n < 2) {
12             cout << 0 << endl;
13             continue;
14         }
15         else if (n % 2 == 0)
16             ans = (n / 2) * (n / 2);
17         else
18             ans = (n / 2 + 1) * (n / 2);
19         cout << ans << endl;
20     }
21     return 0;
22 }

G wyh的考核
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述


wyh非常喜欢lol游戏，一天，他听说学校要选拔lol队员，他非常高兴的就去了，选拔规则是，一共有N个评委，每个评委根据线上对线能力和打团能力给出一个[0,M]之间的一个整数作为分数，然后取平均值，wyh学长非常好奇，他想知道有多少种这样的情况： 
平均分等于其中某一位评委给的分数
例如2个评委，给打的分数都是1分，那么此时平均分是1分，即等于第一个评委的分数，又等于第二个评委的分数，这样答案是2 
但是由于每个评委打的分都是在[0,M]之间，所以会有很多种情况。 
现在请你帮助你们wyh学长数一下有多少种这样的情况，由于结果会很大，请你对1000000007取余 




输入描述:
输入第一行一个整数T（1<=T<=110）
接下来有T组测试数据，对于每组测试数据输入2个数n和M(2<=n<=60,1<=M<=200)，代表有n个评委，每个评委的分数都在[0,M]之间的一个整数
输出描述:
对于每组测试数据，输出对应答案

示例1


输入

1
3 1



输出

6



说明

 
样例解释：
对于样例有以下几种打分情况是符合要求的
 
容斥法
其中每种情况相等的可能性都是三个，比如0分的时候，平均分和第一位、第二位、第三位都相等，所以是3中情况，1的时候也同理，所以答案为6





我们首先枚举均分是多少，然后就知道剩下n-1个人的总分了
然后我们首先考虑剩下的n-1个人里面都选（0-没有上限）的方案数，即隔板法可求
然后再减去一个是（m+1到上限），（n-2）个（0-没有上限）
然后再加上两个个是（m+1到上限），（n-3）个（0-没有上限）
然后再减去三个个是（m+1到上限），（n-4）个（0-没有上限）
……
即容斥一下即可求得答案
效率n*m
 
H wyh的吃鸡
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
 
最近吃鸡游戏非常火，你们wyh学长也在玩这款游戏，这款游戏有一个非常重要的过程，就是要跑到安全区内，否则就会中毒持续消耗血量，我们这个问题简化如下 

假设地图为n*n的一个图，图中有且仅有一块X的联通快代表安全区域，有一个起点S代表缩圈的时候的起点，图中C代表的是车（保证车的数量小于等于100），标记为.的代表空地，可以任意通过，O代表障碍物不能通过。每次没有车的时候2s可以走一个格（只能走自己的上下左右4个方向），有车的话时间为1s走一个格 
现在告诉你最多能坚持的时间为t秒，问你在t秒内（含t秒）能否从s点到达安全区域，能的话输出YES，并且输出最短时间，不能的话输出NO 




输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，每组测试数据输入2个数n和k(1<=n<=100,1<=k<=10^9)
接下来n行，每行n个字符，代表对应的n*n的地图，每个字符都是上面的一种，并且保证只有一个起点，只有一块安全区域。
输出描述:
对于每组测试数据，先输出能否到达，能的话输出YES，然后换行输出最短时间，如果不能的话直接输出NO

示例1


输入

3
2 3
.X
S.
2 3
.X
SC
2 4
.X
S.



输出

NO
YES
3
YES
4




两次 BFS 第一次不考虑车求最短路，第二次从终点向起点BFS 两次vis的和为坐车的结果

  1 #include <bits/stdc++.h>
  2 #define LL long long
  3 using namespace std;
  4 #define maxn 107
  5 char a[maxn][maxn];
  6 int vis1[maxn][maxn],vis2[maxn][maxn];
  7 int mx[]={0,0,1,-1};
  8 int my[]={1,-1,0,0};
  9 int n;
 10 struct node
 11 {
 12     int x,y,t;
 13 }f,ne;
 14 int t0;
 15 void bfs1(int x,int y)
 16 {
 17     int i,j;
 18     for(i=1;i<=n;i++)
 19         for(j=1;j<=n;j++)
 20             vis1[i][j]=-1;
 21     f.x=x;
 22     f.y=y;
 23     f.t=0;
 24     vis1[x][y]=f.t;
 25     queue <node> q;
 26     q.push(f);
 27     while(!q.empty())
 28     {
 29         f=q.front();
 30         q.pop();
 31         for(i=0;i<4;i++)
 32         {
 33             ne=f;
 34             ne.x+=mx[i];
 35             ne.y+=my[i];
 36             ne.t+=2;
 37             if(ne.x>=1&&ne.x<=n&&ne.y>=1&&ne.y<=n&&a[ne.x][ne.y]!='O'&&vis1[ne.x][ne.y]==-1)
 38             {
 39                 vis1[ne.x][ne.y]=ne.t;
 40                 if(a[ne.x][ne.y]=='X') 
 41                     t0=min(t0,ne.t);
 42                 else 
 43                     q.push(ne);
 44             }
 45         }
 46     }
 47 }
 48 void bfs2()
 49 {
 50     int i,j;
 51     for(i=1;i<=n;i++)
 52         for(j=1;j<=n;j++)
 53             vis2[i][j]=-1;
 54     queue <node> q;
 55     for(i=1;i<=n;i++)
 56     {
 57         for(j=1;j<=n;j++)
 58         {
 59             if(a[i][j]=='X')
 60             {
 61                 f.x=i;
 62                 f.y=j;
 63                 f.t=0;
 64                 vis2[i][j]=f.t;
 65                 q.push(f);
 66             }
 67         }
 68     }
 69     while(!q.empty())
 70     {
 71         f=q.front();
 72         //printf("(%d,%d,%d) ",f.x,f.y,f.t);
 73         q.pop();
 74         for(i=0;i<4;i++)
 75         {
 76             ne=f;
 77             ne.x+=mx[i];
 78             ne.y+=my[i];
 79             ne.t++;
 80             if(ne.x>=1&&ne.x<=n&&ne.y>=1&&ne.y<=n&&a[ne.x][ne.y]!='O'&&vis2[ne.x][ne.y]==-1)
 81             {
 82                 vis2[ne.x][ne.y]=ne.t;
 83                 if(a[ne.x][ne.y]=='C')
 84                 {
 85                     if(vis1[ne.x][ne.y]!=-1)
 86                         t0=min(t0,ne.t+vis1[ne.x][ne.y]);
 87                 }
 88                 q.push(ne);
 89             }
 90         }
 91     }
 92 }
 93 int main()
 94 {
 95     int t;
 96     scanf("%d",&t);
 97     while(t--)
 98     {
 99         int k,i,j,x,y;
100         scanf("%d%d",&n,&k);
101         for(i=1;i<=n;i++)
102         {
103             scanf("%s",a[i]+1);
104             for(j=1;j<=n;j++)
105             {
106                 if(a[i][j]=='S')
107                     x=i,y=j;
108             }
109         }
110         t0=1e9+7;
111         bfs1(x,y);
112         if(t0==1e9+7)
113         {
114             printf("NOn");
115             continue;
116         }
117         bfs2();
118         if(t0>k)
119         {
120             printf("NOn");
121         }
122         else
123         {
124             printf("YESn%dn",t0);
125         }
126     }
127     return 0;
128 }

I wyh的物品
时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述


wyh学长现在手里有n个物品，这n个物品的重量和价值都告诉你，然后现在让你从中选取k个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的k个物品的总价值和总重量的比值）






输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每组测试数据，第一行输入两个数n和k(1<=k<=n<=100000)
接下来有n行，每行两个是a和b，代表这个物品的重量和价值
输出描述:
对于每组测试数据，输出对应答案，结果保留两位小数

示例1


输入

1
3 2
2 2
5 3
2 1



输出

0.75



说明

对于样例来说，我们选择第一个物品和第三个物品，达到最优目的


这道题目是一道0-1分数规划求最优值。
方法是一个二分搜索+贪心的题目。
出这道题目就是告诉大家二分不仅可以查找，还可以搜索一个更优值。
要使得单位重量的价值最大，则其最大不超过单个中最大的单位重量的价值，最小当然不小于0.
那么我们就这一在0--最大单位重量的价值中间找一个值ans，使得ans为满足题目条件的最大值。如果满足条件，则可以找更大的。设置一个条件。既二分搜索、
从n个物品中找k个使得k个的价值和/质量和>=ans
为了使得ans尽可能的大，那么这里就要贪心选择。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define INF 1000010
 4 #define eps 1e-4
 5 double w[100005],v[100005];
 6 double y[100005];//v-x*w
 7 double max_ave;
 8 int n,k;
 9 bool get(double x)
10 {
11     int i;
12     double sum=0;
13     for(i=0;i<n;i++)
14     {
15         y[i]=v[i]-x*w[i];
16     }
17     sort(y,y+n);
18     for(i=0;i<k;i++)
19     {
20         sum+=y[n-i-1];
21     }
22     return sum>=0;
23 }
24 void bin()
25 {
26     double low,high,mid;
27     low=0.0;
28     high=INF;
29     for(int i=0;i<100;i++)
30     {
31         mid=(low+high)/2;
32         if(get(mid))
33             low=mid;
34         else high=mid;
35     }
36     printf("%.2lfn",high);
37 }
38 int main()
39 {
40     int i;
41     int tot;
42     cin>>tot;
43     while(tot--)
44     {
45         scanf("%d%d",&n,&k);
46         for(i=0;i<n;i++)
47         {
48             scanf("%lf%lf",&w[i],&v[i]);
49         }
50         bin();
51     }    
52     return 0;
53 }

J wyh的问题
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述


我国现在能源消耗非常严重，现在政府有这样一个工作，每天早上都需要把一些路灯关掉，但是他们想让在关闭的过程中所消耗的能源是最少的，负责路灯关闭的工作人员以1m/s的速度进行行走，假设关闭路灯的时候不需要花费任何的时间，请你编写一个程序，计算在给定路灯位置和每个路灯的消耗能源的多少，求出当所有路灯关闭的时候所需要的最少能量






输入描述:
多组测试数据循环输入
每组测试数据第一行：N表示路灯的数量 （2<=N <=1000）
第二行：V表示开始关灯的路灯号码。 （1<=V<=N）
接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每盏灯的参数
D表示该路灯到原点的距离 (用米为单位来表示)，
W表示灯泡的功率，即每秒该灯泡所消耗的能量数。（0<=D<=1000，0<=W<=1000）
路灯按照顺序给出，起始位置的那盏灯不算消耗的电能里面
输出描述:
输出一个整数，即消耗能量之和的最小值。

示例1


输入

4
3
2 2
5 8
6 1
8 7



输出

56



说明

对于样例，我一开始在第三个路灯的位置，即在6位置
第1s的时候去5把第二盏灯关闭，消耗电能8
然后去第四盏灯，第四盏灯亮的时间是4s 所以消耗电能28
最后去关第一盏灯第一盏灯亮的时间是10s 所以消耗电能20
最后总和为8+28+20=56


关灯的人要么是去左边关灯，或者是去右边关灯，也即要关闭的下一个路灯要么是从已关闭路段的左端过去的，要么是从已关闭的路段的右端过去的，定义：
DP[i][j][0]表示i到j的路灯都已经关闭，人在路灯i的位置，此时已经消耗的最小电能
DP[i][j][1]表示i到j的路灯都已经关闭，人在路灯j的位置，此时已经消耗的最小电能
则状态转移式：
DP[i][j][0] = min(DP[i+1][j][0]+[i+1,j]路段以外未关闭路灯在人从i+1走的i期间消耗的电能，DP[i+1][j][1]+[i+1,j]路段以外未关闭路灯在人从j走到i期间消耗的电能)
DP[i][j][1] = min(DP[i][j-1][0]+[i,j-1]路段以外未关闭路灯在人从i走到j期间消耗的电能，DP[i][j-1][1]+[i,j-1]路段以外未关闭路灯在人从j-1走到j期间消耗的电能)

 1 #include <bits/stdc++.h>
 2 #define LEN 1001
 3 #define min(a,b) ((a<b)?(a):(b))
 4 
 5 int DP[LEN][LEN][2];
 6 int bw[LEN][LEN];
 7 int D[LEN];
 8 int W[LEN];
 9 
10 int main()
11 {
12     int N,V,tw=0;
13     int i,j,t;
14     while(scanf("%d %d",&N,&V)!=EOF)
15     {
16        tw = 0;
17        memset(bw, 0, sizeof(bw));
18        for(i=1; i<=N; ++i)
19        {
20          scanf("%d %d",&D[i],&W[i]); 
21          tw += W[i];
22        }
23        for(i=1; i<=N; ++i)
24        {
25           for(j=i; j<=N; ++j)
26           {
27               bw[i][j] = bw[i][j-1] + W[j];
28           }
29        }
30        
31        //初始化
32        for(i=V-1; i>0; --i)
33        {
34           DP[i][V][0] = DP[i+1][V][0]+(tw-bw[i+1][V])*(D[i+1]-D[i]);
35           DP[i][V][1] = DP[i][V][0] + (tw-bw[i][V])*(D[V]-D[i]);
36        } 
37        for(j=V+1; j<=N; ++j)
38        {
39           DP[V][j][1] = DP[V][j-1][1] + (tw-bw[V][j-1])*(D[j]-D[j-1]);
40           DP[V][j][0] = DP[V][j][1] + (tw-bw[V][j])*(D[j]-D[V]); 
41        }
42        
43        //DP
44        for(i=V-1; i>0; i--)
45        {
46           for(j=V+1; j<=N; ++j)
47           {
48              DP[i][j][0] = min(DP[i+1][j][0]+(tw-bw[i+1][j])*(D[i+1]-D[i]), 
49                                DP[i+1][j][1]+(tw-bw[i+1][j])*(D[j]-D[i]));
50              DP[i][j][1] = min(DP[i][j-1][0]+(tw-bw[i][j-1])*(D[j]-D[i]), 
51                                DP[i][j-1][1]+(tw-bw[i][j-1])*(D[j]-D[j-1]));
52           }
53        }
54        printf("%dn", min(DP[1][N][0], DP[1][N][1]));
55     }
56     return 0;
57 }

3
1 1 2
2 3 1000
32122142412412142 124124124412124 123

1
21
3

2
1234567
123456

1
0