肺炎疫情之套题

外面疫情严重，假期延长，在家多看视频多刷题，不给国家添乱又强自我。疫情背景训练赛欢迎大家AK！！！

这个新年不寻常，大家都窝在家里。原因是武汉的疫情大爆发，不过国家马上采取了措施，将疫情控制在最小范围内。 

著名医学家院士钟南山给你9条防护建议： 

1 最重要一条，不要到处跑

2 不要参加机会，减少感染机会

3 出门要戴口罩，不一定要戴N95

4 摘口罩也有讲究，不要抓着污染面

5 注意洗手卫生，防自己也防别人

6 发烧要去医院，不要待在家等

7 接待过武汉来的人，可做一些普查检测

8 春运返程测体温有必要

9 首先要保护好自己，才能很好地救别人

此次套题有L1,L2,L3,难度不一，欢迎大家AK

回答问题

题目描述

武汉新型肺炎疫情严重，现在很多小区及进城通道都会有工作人员在值守，他们一般会问以下几个问题：
1 你最近是否接触过武汉人？
2 最近有没有跟从武汉回来的人一起呆过？
3 最近有没有跟发烧的人在一起呆过？
4 有没有发烧或咳嗽？
对于每个问题你需根据实际情况回答“是”或者“否”，1代表“是”，0代表“否”。如果以上4项回答都是“否”，恭喜你
只要保持，待疫情过去就可以。如果有一项不是“否”，那么你就要密切关注自己的身体健康。

 

输入

输入4个整数，分别表示4个问题的答案

 

输出

如果4个问题全是否，输出ok，否则输出sorry

 

样例输入

1 1 0 0

 

样例输出

sorry

题解：

因太简单，而无题解（L1题，Easy）

源代码：

#include<bits/stdc++.h>
using namespace std;
int main() {int a,b,c,d;cin>>a>>b>>c>>d;if(a==0&&b==0&&c==0&&d==0) cout<<"ok"<<endl;else cout<<"sorry"<<endl;return 0;
}

统计疫情

题目描述

疫情尽管有效控制住了，但确诊人数还在攀升。关心疫情发展的你，查询了各地的疫情报告，统计下
全国共有多少人确诊了。

 

输入

第一行输入一个整数n，表示统计的地区第二行是n个数，表示各地区的确诊人数

 

输出

输出确诊人数

 

样例输入

6
5806 537 436 352 332 240

 

样例输出

7703

题解：

无详细题解，可以直接定义一个sum函数，直接把a[i]相加。OK \(^o^)/~

源代码：

#include<bits/stdc++.h>
using namespace std;
int main() {int n,sum=0,a[1110];cin>>n;for(int i=0; i<n; i++) cin>>a[i];for(int i=0; i<n; i++)    {sum+=a[i];}cout<<sum<<endl;return 0;
}

发口罩

题目描述

很多医护人员奋斗在第一线，他们也面临着被感染的风险。小王用自己省下来的压岁钱
买了几千个口罩，但好多医院缺乏口罩，小王只有给最缺的一些医院捐赠了。小王了解
了各医院口罩的缺口，但数据好多，你能帮忙按缺口罩数量从高到低排个序吗？

 

输入

第一行输入一个整数n(n<=20)
第二行输入n个整数

 

输出

在一行内按缺口从高到低输出，2个数之间一个空格

 

样例输入

4
1 3 5 6

 

样例输出

6 5 3 1

题解：

基础排序——选择，冒泡，桶排，sort……

源代码：

#include<stdio.h>
int main() {int a[1100],i,j,k,n;scanf("%d",&n);for(i=0; i<n; i++) scanf("%d",&a[i]);for(i=0; i<n-1; i++) {for(j=i+1; j<n; j++) {if(a[i]<a[j] ) {k=a[i];a[i]=a[j];a[j]=k;}}}for(i=0; i<n; i++) printf("%d ",a[i]);printf("\n");return 0;
}

支援WH

题目描述

甲、乙两名医护人员同时从HZ A地出发要尽快同时赶到火车站去WH。出发时HZ A地有一辆小车，可是
这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用
小车才能使两人尽快同时到达。

 

输入

 仅一行，三个整数， 分别表示A与火车站 两地的距离s 米（≤2000）， 人的步行速度a 米/秒， 车的速度b 
米/秒，2000>b>a。 

 

输出

两人同时到达火车站需要的最短时间,单位秒，保留5 位小数。 

 

样例输入

120 5 25 

 

样例输出

9.60000

题解：

一个公式解决一切

源代码：

#include<bits/stdc++.h>
using namespace std;
double s,a,b;
int main() {scanf("%lf%lf%lf",&s,&a,&b);double sum=s*(b*b-a*a)/(2*a*b-3*a*a+b*b);printf("%0.5lf\n",sum/b+(s-sum)/a);return 0;
}

寻找失踪的口罩

题目描述

杭州某爱心公司给wh捐赠了一些口罩，但运到时有人喊道：“这些口罩少了几个！”众人一数，果然是少了。于是捐
赠者得意地说：“这是一批特制的口罩，我知道整批口罩每一张的重量。只要我们称一下剩下的口罩的总重量，就
能知道少了哪些口罩了。”大家都觉得这个办法不错，于是称出剩下的口罩的总重量，开始计算少了哪些口罩。由
于数据量比较大，过了不久，大家都算得头晕了。这时，小王大声说：“你们看我的吧！”于是他拿出笔记本电脑，
编出了一个程序，很快就把缺少的口罩找了出来。如果是你遇到了这样的情况呢？你能办到同样的事情吗？

 

输入

第一行一个整数TotalW，表示剩下的口罩的总重量。第二行一个整数N（1<N<=100），表示这批
口罩有多少张。接下来N行，每行一个整数Wi（1<=Wi<=1000），表示每一张口罩的重量。

 

输出

如果无解，则输出“0”；如果有多解，则输出“-1”；否则，按照升序输出丢失的口罩的编号，相邻两个数之间用一个空格隔开。

 

样例输入

270
4
100
110
170
200

 

样例输出

2 4

题解：

其实当我开始遇见这道题时，我就这样思考，我们可以将剩下的口罩的总重量看做背包的容量，而口罩就是物品，但是我们不能用动态规划来直接求出状态。所以我们可以用01背包方案总数来求解——（dp[i]+=dp[j-a[i]]，i为物品编号，j为当前的容量）。而我们也可以用一个结构体来存储放入背包的物品编号数，最后加上当前物品就可以了。

源代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],dp[100005];
bool v[105];
struct node {int num[105],len;
} p[100005];
int main() {scanf("%d%d",&n,&m);for(int i=1; i<=m; i++) scanf("%d",&a[i]);dp[0]=1;for(int i=1; i<=m; i++) for(int j=n; j>=a[i]; j--) {if(dp[j-a[i]]>0) {memcpy(p[j].num,p[j-a[i]].num,sizeof p[j-a[i]].num);p[j].len=p[j-a[i]].len;p[j].len++;p[j].num[p[j].len]=i;dp[j]+=dp[j-a[i]];if(dp[j]>=2&&j==n) {printf("-1");return 0;}}}if(dp[n]==0) {printf("0");return 0;}for(int i=1; i<=p[n].len; i++) v[p[n].num[i]]=1;for(int i=1; i<=m; i++) if(!v[i]) printf("%d ",i);return 0;
}

寻找疫苗

 

题目描述

     

小王梦见疫苗在一个神迹里，为了寻找疫苗，他出发了。
如下图，神迹的城堡是一个树形的结构，共有n间屋子。每间屋子都有一把锁，并且每间屋子最多可以到另外的两
个屋子里（它是一棵二叉树）。在城堡的每个房间都存在着不同的宝藏。现在小王站在城堡的大门口（1号屋子门
口）拥有k把万能钥匙，可 以打开任意一把锁，但每把钥匙只能用一次，钥匙是拔不出来的。
问题哪有那么简单……小王还有一个传送门，可以在任何时候带他去任何一间屋子，但传送门也只能 使用一次。
地图上画出了宝藏的分布，只有获得最大价值的宝藏，小王的目的才能实现。

 

 

 

输入

第一行：两个数n和k。为城堡的屋子总数和你拥有的万能钥匙数。 第二行到第n行：每行两个数x1和x2，为树上
的n-1条边。（树保证以1为根节点）。 第n+1行：n个数，第i个数为房间i的宝藏价值vi 

 

输出

一个数，为最大宝藏价值maxv。

 

 

样例输入

8 4 
1 2 
1 3 
2 4 
2 5 
3 6 
3 7 
6 8 
2 5 1 4 6 1 1 10

 

样例输出

27

 

数据范围：

n<=20

题解：

用钥匙依次开1 2 4 5 号房间，再用传送门去8号房间，27=2+5+6+4+10。

利用树形dp思想,dfs遍历树。
现在的问题是传送门如何解决:把传送门看成不需钥匙直接到某个点的路径.因此可建立一个超级根,一边与原根节点相连,另一边与用传送门到的点相连。Idea很棒!
代码其实可以用记忆化优化……(不想写了，Code中见)

源代码：

#include<bits/stdc++.h>
using namespace std;
struct node {int ans,sum,ans1,sum1;
};
node a[25];
int f[25][25],n,k;
int dp(int x,int key) {if(x==0) return 0;if(key==1) return a[x].sum1;if(f[x][key]>0) return f[x][key];for(int i=0; i<=key-1; i++) f[x][key]=max(f[x][key],dp(a[x].ans,i)+dp(a[x].sum,key-1-i)+a[x].sum1);return f[x][key];
}
int main() {scanf("%d%d",&n,&k);for(int i=1; i<=n-1; i++) {int x,y;scanf("%d%d",&x,&y);a[y].ans1=x;if(a[x].ans==0)a[x].ans=y;else a[x].sum=y;}for(int i=1; i<=n; i++) {scanf("%d",&a[i].sum1);}a[n+1].ans=1;int ans=0;for(int i=2; i<=n; i++) {memset(f,0,sizeof(f));bool flag=0;a[n+1].sum=i;if(a[a[i].ans1].ans==i) {a[a[i].ans1].ans=0;flag=0;} else {a[a[i].ans1].sum=0;flag=1;}ans=max(dp(n+1,k+2),ans);if(flag==0) a[a[i].ans1].ans=i;else a[a[i].ans1].sum=i;}printf("%d\n",ans);return 0;
}

口罩运输问题

题目描述

WH市有m个仓库和n个医院。第i个仓库有ai个单位的口罩；第j个医院需要bj个单位的口罩。口罩供需平衡，即m个
仓库口罩和等于n个医院所需口罩 。从第i个仓库运送每单位口罩到第j个医院的费用为Cij 。试设计一个将仓库
中所有货物运送到医院的运输方案，使总运输费用最少。

 

输入

第1行有2个正整数m和n，分别表示仓库数和医院数。接下来的一行中有m个正整数ai ，表示第i个仓库有ai个单位
的口罩。再接下来的一行中有 n个正整数bj ，表示第j个医院需要  bj个单位的口罩。接下来的m行，每行有n个
整数，表示从第 i个仓库运送每单位口罩到第  j个医院的费用Cij 。

 

输出

两行分别输出最小运输费用和最大运输费用。

 

样例输入

2 3
220 280
170 120 210
77 39 105
150 186 122

 

样例输出

48500
69140

 

数据范围

1<=n,m<=100

题解：

1、从S向每个Xi连一条容量为仓库中货物数量ai，费用为0的有向边。
2、从每个Yi向T连一条容量为商店所需货物数量bi，费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大，费用为cij的有向边。

求最小费用最大流，最小费用流就是最少运费，求最大费用最大流，最大费用流就是最多运费。

源代码：

#include<bits/stdc++.h>
#define inf 0x7fffffff
#define T 2001
using namespace std;
int m,n,head[2005],q[2005],dis[2005],from[2005],a[2005],b[2005],cnt,ans;
int c[2005][2005];
bool inq[2005];
struct data {int from,to,next,v,c;
} e[1000001];
void ins(int u,int v,int w,int c) {cnt++;e[cnt].from=u;e[cnt].to=v;e[cnt].v=w;e[cnt].c=c;e[cnt].next=head[u];head[u]=cnt;
}
void ppo(int u,int v,int w,int c) {ins(u,v,w,c);ins(v,u,0,-c);
}
void opp(int k) {cnt=1;memset(head,0,sizeof(head));for(int i=1; i<=m; i++) ppo(0,i,a[i],0);for(int i=1; i<=n; i++) ppo(m+i,T,b[i],0);for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) ppo(i,m+j,inf,k*c[i][j]);
}
bool po() {for(int i=0; i<=T; i++)dis[i]=inf;int t=0,w=1,i,now;dis[0]=q[0]=0;inq[0]=1;while(t!=w) {now=q[t];t++;if(t==200)t=0;for(int i=head[now]; i; i=e[i].next) {if(e[i].v&&dis[e[i].to]>dis[now]+e[i].c) {from[e[i].to]=i;dis[e[i].to]=dis[now]+e[i].c;if(!inq[e[i].to]) {inq[e[i].to]=1;q[w++]=e[i].to;if(w==200)w=0;}}}inq[now]=0;}if(dis[T]==inf)return 0;return 1;
}
void op() {int i,x=inf;i=from[T];while(i) {x=min(e[i].v,x);i=from[e[i].from];}i=from[T];while(i) {e[i].v-=x;e[i^1].v+=x;ans+=x*e[i].c;i=from[e[i].from];}
}
int main() {scanf("%d%d",&m,&n);for(int i=1; i<=m; i++) scanf("%d",&a[i]);for(int i=1; i<=n; i++) scanf("%d",&b[i]);for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) scanf("%d",&c[i][j]);opp(1);while(po()) op();printf("%d\n",ans);ans=0;opp(-1);while(po()) op();printf("%d\n",-ans);return 0;
}

AC

希望疫情早日治好！