2020杭电多校第四场
1002 Blow up the Enemy
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6803
题意：
给出一系列武器，每个武器有两个属性，伤害A和延迟D，张三和father的选择互不干扰，每个武器被选中的概率都是一样的，当他们的同时击败对方时，均有50%的可能性获胜。他们的血量HP最开始都为100，问张三击败father的最大概率。
题解：
其实就是计算出每个武器清空对方血槽所需的时间，而张三就是挑出时间消耗最少的武器时，此时的概率最大，遍历farther的选择就行了。
注意：
并不需要考虑张三的每一种情况，直接假设拿到最好的武器就好了。（我就是想多了，，，）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
struct node{
int A;
int D;
int time;
}Weapon[1005];
bool cmp(node a,node b)
{
return a.time<b.time;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);//武器个数
memset(Weapon,0,sizeof(Weapon));
for(int i=1;i<=n;i++)
{
scanf("%d%d",&Weapon[i].A,&Weapon[i].D);//伤害和延迟
Weapon[i].time=100/Weapon[i].A;
if(100%Weapon[i].A==0)Weapon[i].time--;
Weapon[i].time*=Weapon[i].D;//消灭对手所需的时间；
}
sort(Weapon+1,Weapon+n+1,cmp);
double pro;
int x=Weapon[1].time,num=1;
for(int i=2;i<=n;i++)
{
if(Weapon[i].time!=x){break;}
else num++;
}
pro=1.0*num/n*0.5+(n-num)*1.0/n;
printf("%lf\n",pro);
}
return 0;
}1004 Deliver the Cake
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6805
题意：
张三同学从s到达t，同时手提蛋糕，在路上会切换左右手，但是某些路会规定左右手，必须使用对应的左右手，而每切换一次就需要x秒的时间，问张三最快需要消耗多少秒的时间
题解：
先分别统计左右手， (如：u,v,w u0,u1,v0,v1,若他们的下标不同则需要加上x )再直接Dijkstra算法统计整个的路径就好了。
代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf=9999999;
const int maxn=100005,maxv=2*maxn;
ll dis[maxv][2];
char str[maxv];
struct Edge{int v,w;};
struct node{
ll d;
int u,t;
bool operator<(const node &n)const{return d>n.d;}//按照d从大到小排序
};
priority_queue<node> pq;//这样的排序就是按照d从小到大来排
vector<Edge>edge[maxv];
int main()
{
int T,n,m,s,t,x,u,v,w;
for(scanf("%d",&T);T--;)
{
scanf("%d%d%d%d%d",&n,&m,&s,&t,&x);
scanf("%s",str+1);//从1开始存
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
edge[u].push_back(Edge{v,w});
edge[v].push_back(Edge{u,w});//同时进行存储
}
for(int i=1;i<=n;i++)
dis[i][0]=dis[i][1]=1e18;
if(str[s]!='L')pq.push({dis[s][1]=0,s,1});//走左边
if(str[s]!='R')pq.push({dis[s][0]=0,s,0});//走右边
while(!pq.empty())
{
node d=pq.top();pq.pop();
if(dis[d.u][d.t]<d.d)continue;//dis表示的就是已经记录了最短路径表示从s->d.u，不需要这条路
if(d.u==t)break;//已经到达了终点
for(const Edge &e:edge[d.u])//vector的迭代器//d.u->对应的多个终点
{
ll w=e.w+d.d;//
int t=str[e.v]=='R'?1:(str[e.v]=='L'?0:d.t);
if(t==d.t&&w<dis[e.v][t])//不换手
pq.push(node{dis[e.v][t]=w,e.v,t});
w+=x;
if(str[e.v]=='M')t=!t;
if(t!=d.t&&w<dis[e.v][t])
pq.push(node{dis[e.v][t]=w,e.v,t});
}
}
printf("%lld\n",min(dis[t][0],dis[t][1]));
while(!pq.empty())pq.pop();
for (int i = 1; i <= n; i++) edge[i].clear();
}
return 0;
} 1005 Equal Sentences
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6806
题意：
就是给定一连串个单词，相邻<=1的两个不相同的单词可以进行交换(自身和自身交换也行)，问一共有多少组交换方法
题解：
运用递推，比如说1,2 交换 1个；2,3交换 1个；3,4交换 就有2个（加上1,2的那个）
f[i]=f[i-1]+f[i-2]->斐波那契数列
注意：
注意自己和自己交换的情况，也就是初始的即为1.
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005,mod=1e9+7;
int f[N];string str[N];
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>str[i];
}
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=n;i++)
{
f[i]=f[i-1];
if(str[i]!=str[i-1]&&i>=2)
{
f[i]=(f[i-2]+f[i])%mod;
}
}
printf("%d\n",f[n]);
}
return 0;
}
1011 Kindergarten Physics
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6812
题意：
两个小球同时下落，求他们之间的距离
题解：
cin,cout
注意：人类迷惑行为，是在下输了。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int a,b,d,t;
scanf("%d%d%d%d",&a,&b,&d,&t);
printf("%d\n",d);
}
return 0;
}
投递亚信科技（中国）有限公司等公司6个岗位
