E：出差
问题描述
A 国有 N 个城市, 编号为 1…N 。小明是编号为 1 的城市中一家公司的员 工, 今天突然接到了上级通知需要去编号为 N 的城市出差。
由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从 城市 1 到达城市 N, 需要通过其他城市进行陆路交通中转。小明通过交通信息 网, 查询到了 M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的 时间。
同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开 该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于 小明之前在城市 1 , 因此可以直接离开城市 1 , 不需要隔离）
由于上级要求, 小明希望能够尽快赶到城市 N, 因此他求助于你, 希望你 能帮他规划一条路线, 能够在最短时间内到达城市 N 。
输入格式
第 1 行: 两个正整数N,M,N 表示 A 国的城市数量, M 表示末关闭的路 线数量
第 2 行: N 个正整数, 第 i 个整数 Ci 表示到达编号为i 的城市后需要隔离 的时间
第 3 …M+2 行: 每行 3 个正整数,u,v,c, 表示有一条城市 uu 到城市 v的 双向路线仍然开通着, 通过该路线的时间为 c
输出格式
第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 N 的最短时间（到 达城市 N, 不需要计算城市 N 的隔离时间）
样例输入
4 4 5 7 3 4 1 2 4 1 3 5 2 4 3 3 4 5
样例输出
13
样例说明
评测用例规模与约定
对于 100% 的数据, 1≤N≤1000,1≤M≤10000,1≤Ci≤200,1≤u,v≤ N,,1≤c≤1000
运行限制
最大运行时间：1s
最大运行内存: 512M
最短路径采用Dijkstra算法会快一点；
#include <iostream> #include <cstring> #include <cmath> using namespace std; int n,m; //n个城市，m条路线 int geli[10005]; //到每个城市的隔离时间 int luxian[10005][10005]; int juli[10005]; //到一点的最短距离 bool vis[10005]; int dj(){ memset(juli,0x3f3f3f3f,sizeof(juli)); juli[1]=0; //距离起点为0 geli[1]=0; //出自己城市不隔离 geli[n]=0; //到达终点不需要隔离 for(int i=1;i<=n;i++){ //剔除n个 int s=-1; for(int j=1;j<=n;j++){ if(!vis[j]&&((s==-1)||(juli[j]<juli[s]))){ s=j; //第一次s为1，之后每一次寻找与前一个想通的城市 } } vis[s]=1; for(int j=1;j<=n;j++){ juli[j]=min(juli[j],juli[s]+luxian[s][j]+geli[s]); } } return juli[n]; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>geli[i]; } memset(luxian,0x3f3f3f3f,sizeof(luxian)); //无穷大 for(int i=1;i<=n;i++){ luxian[i][i]=0; //自己到自己为0 } for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; luxian[a][b]=luxian[b][a]=min(c,luxian[a][b]); } int ans=dj(); cout<<ans; return 0; }
F：费用报销
问题描述
小明在出差结束后返回了公司所在的城市, 在填写差旅报销申请时, 粗心 的小明发现自己弄丢了出差过程中的票据。
为了弥补小明的损失, 公司同意小明用别的票据进行报销, 但是公司财务 要求小明提交的票据中任意两张的日期差不小于 K 天, 且总金额不得超过实际 差旅费用 M 。
比如财务要求 K=7 时, 若小明提交了一张 1 月 8 日的票据, 小明就不能 提交 1 月 2 日至 1 月 14 日之间的其他票据, 1 月 1 日及之前和 1 月 15 日及之 后的票据则可以提交。
公司的同事们一起给小明凑了 N 张票据, 小明现在想要请你帮他整理一 下, 从中选取出符合财务要求的票据, 并使总金额尽可能接近 M 。
需要注意, 由于这些票据都是同一年的, 因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。
输入格式
第 1 行： 3 个整数, N,M,K
第 2…N+1 行: 每行 3 个整数 mi,di,vi, 第 i+1 行表示第 i 张票据时间 的月份 mi 和日期 di,vi 表示该票据的面值
输出格式
第 1 行: 1 个整数, 表示小明能够凑出的最大报销金额
样例输入
4 16 3 1 1 1 1 3 2 1 4 4 1 6 8
样例输出
10
样例说明
选择 1 月 3 日和 1 月 6 日的票据
评测用例规模与约定
对于 100% 的评测用例, 1≤N≤1000,1≤M≤5000,1≤K≤50,1≤mi≤ 12,,1≤di≤31,1≤vi≤400
日期保证合法。
运行限制
最大运行时间：1s
最大运行内存: 512M
动态规划问题， 先将n张票据以结构体保存下来，然后转化为数组，但是一天可能有好几张票据，因此我们要将一天票据进行比较。然后利用递推公式：
选i票据：ans[i] ans[i-k]+面值[i] 前提小于等于m'
不选i票据：ans[i] ans[i-1]
因此：ans[i]=max(ans[i-k]+面值[i],ans[i-1])
然后就是在于一天中每个票据挨个比较
#include <iostream> #include <vector> #include <cmath> using namespace std; int n,m,k; //n代表n个票据，m钱，k天 int piao1[400]; int ans[500]; vector<int> piao2[400]; int month12[12]={31,28,31,30,31,30,31,31,30,31,30,31}; struct piao{ int month; int day; int qian; }; piao a[1005]; int getday(int x,int y){ int ans=y; for(int i=0;i<x-1;i++){ ans+=month12[i]; } return ans; } int main(){ cin>>n>>m>>k; for(int i=1;i<=n;i++){ cin>>a[i].month>>a[i].day>>a[i].qian; } //输入结构体 int daymax=0; for(int i=1;i<=n;i++){ int day=getday(a[i].month,a[i].day); if(piao1[day]){ piao2[day].push_back(a[i].qian); }else{ piao1[day]=a[i].qian; } daymax=max(day,daymax); //全转为天数，重合的装在vector里 } for(int i=1;i<=daymax;i++){ //遍历每天的票据 if(piao1[i]==0) { ans[i]=ans[i-1]; //这一天没有票，等于上一天的值 }else{ if(piao2[i].size()==0){ //这一天只有一张票 if(ans[i-1]<=m){ ans[i]=ans[i-1]; } if(ans[i-k]+piao1[i]<=m){ ans[i]=max(ans[i],ans[i-k]+piao1[i]); } }else{ if(ans[i-1]<=m){ ans[i]=ans[i-1]; //这一天有多张票 } if(ans[i-k]+piao1[i]<=m){ ans[i]=max(ans[i],ans[i-k]+piao1[i]); } int len=piao2[i].size(); for(int j=0;j<len;j++){ if(ans[i-k]+piao2[i][j]<=m){ ans[i]=max(ans[i],ans[i-k]+piao2[i][j]); } } } } } cout<<ans[daymax]; return 0; }
G:故障
问题描述
在软件或系统开发中, 我们会遇到各种各样的故障。为了从故障现象反推 故障原因, 工程师们会总结一种叫做相关性矩阵的二维表格, 来表示故障原因 与故障现象之间的关系。比如:
其中每行表示一种故障原因, 每一列表示一种故障现象。该矩阵表示故障 原因 AA 可能产生故障现象 2、3、4, 故障原因 BB 可能产生故障现象 1、3。
在实际开发过程中, 如果出现了故障原因, 工程师就可以根据故障现象, 去计算每种故障原因产生的概率, 并按照概率大小对故障原因进行排查, 以达 到快速定位故障原因的目的。
现在, 我们假设系统开发中同一时间只会出现一种故障原因, 并且故障原 因引起各故障现象是独立事件。举个例子来说:
假设系统现在发生了故障原因 A, 有 1/3的概率出现故障现象 2 , 有 1/4 的概 率出现故障现象 3 , 有 1/2的概率出现故障现象 4。由于 3 种现象是独立发生的, 因此有 1/3*1/4*1/2 的概率同时出现故障 2、3、4。
约定若相关性矩阵中没有 ' x ' 记号, 则表示该故障原因一定不会产生某故 障现象, 比如故障原因 A, 一定不会产生故障现象 1。
根据历史经验数据, 我们统计得到了每一种故障原因出现的概率以及每一 种故障原因对应的故障现象产生概率。
现在已知系统出现的故障现象, 求问各个故障原因发生的概率。
输入格式
第 1 行: 2 个正整数 N,M,N 表示故障原因的个数（编号 1…N ), M 表 示故障现象的个数 (编号 1 1…M)
第 2 行: N 个整数, 第 i 个数表示故障原因 i 产生的概率 Pi.
第 3…N+2 行: 每行 M 个整数, 第 i+2 行第 j 个整数 Pij 表示故障原 因 i 出现故障现象 j 的概率 (百分比).
第 N+3 行: 1 个正整数 K, 表示目前出现的故障现象数量
第 N+4 行: K 个正整数, 依次为当前出现的故障现象编号, 不会重复
输出格式
第 1…N 行: 按概率从高到低输出每种故障原因及其可能的概率, 若出现 概率相同则优先输出编号小的故障原因。第 1 个数为故障原因编号, 第 2 个数 为故障概率 (百分比), 保留 2 位小数。
样例输入
3 5 30 20 50 0 50 33 25 0 30 0 35 0 0 0 0 0 25 60 1 3
样例输出
2 56.89 1 43.11 3 0.00
评测用例规模与约定
对于所有测试用例, 1≤N≤40,1≤M≤20,0≤Pi≤100,Σ(Pi)=100, 0≤Pij≤100，
运行限制
最大运行时间：1s
最大运行内存: 512M
这个题敢不敢再写得长一点，看题目半小时过去了，概率题；
就是这个算法，概率论的题，还好我们开过这门课，呜呜呜呜呜。
#include <iostream> #include <stdio.h> #include <algorithm> #include <cmath> using namespace std; int n,m; //n行，m列 int yuanyin[450]; int p1[450][450]; int k; int guzhang[4500]; int vis2[450]; int vis1[450]; double dange[450]; int id[450]; bool cmp(int a,int b){ if(fabs(dange[a]-dange[b])>1e-8){ return dange[a]>dange[b]; //当不相等时返回大的，否则返回id值小的 }else{ return a<b; } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>yuanyin[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>p1[i][j]; } } cin>>k; for(int i=1;i<=k;i++){ cin>>guzhang[i]; vis1[guzhang[i]]=1; //标记故障 } double num=0; for(int i=1;i<=n;i++){ dange[i]=1; //便于乘 for(int j=1;j<=m;j++){ if(vis1[j]){ //此点是故障点 dange[i]=(double)dange[i]*p1[i][j]/100.0; }else{ dange[i]=(double)dange[i]*(100-p1[i][j])/100.0; } } dange[i]=(double)dange[i]*yuanyin[i]/100.0; num+=dange[i]; } if(fabs(num)<1e-9){ for(int i = 1 ; i <= n ; i ++){ printf("%lld 0.00\n" , i) ; } return 0 ; } for(int i=1;i<=n;i++){ //很巧妙的排序，对id排序，然后输出 id[i]=i; dange[i]=dange[i]*100.0/num; } sort(id+1,id+1+n,cmp); //根据dange的值排id for(int i=1;i<=n;i++){ printf("%lld %0.2lf\n",id[i],dange[id[i]]); } return 0; }
