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;
}

参考：
https://blog.csdn.net/WAautomaton/article/details/107696587?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-3&spm=1001.2101.3001.4242

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;
}

2020杭电多校第四场

1002 Blow up the Enemy

1004 Deliver the Cake

1005 Equal Sentences

1011 Kindergarten Physics