1002 Blow up the Enemy

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6803
题意：
给出一系列武器，每个武器有两个属性，伤害A和延迟D，张三和father的选择互不干扰，每个武器被选中的概率都是一样的，当他们的同时击败对方时，均有50%的可能性获胜。他们的血量HP最开始都为100，问张三击败father的最大概率。
思路:
儿子肯定直接选价值最大的武器（即为最小次数打出100伤害），张三如果不选相同次数即可打出100伤害的武器就会输，所以我们统计武器中最快打出100伤害的武器的个数k，k/2n即为儿子输的概率，求儿子赢的概念为1−k/2
代码：

#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn=1010;
int a[maxn],d[maxn];
int main()
{
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        int cnt,ans;
        cnt=ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i]>>d[i];
            if(a[i]>=100)cnt++;
        }
        if(cnt)
        {
            double x=cnt*1.0/n*0.5;
            cout<<1-x<<endl;
            continue;
        }
        int mint=100/a[1]*d[1];
        for (int i=1;i<=n;i++)
        {
            int k;
            if(100%a[i]==0)k=(100/a[i]-1)*d[i];
            else k=100/a[i]*d[i];
            if(mint>k) {
                mint = k;
            }
        }
        for(int j=1;j<=n;j++)
        {
            int kk=(mint/d[j]+1)*a[j];
            if(kk>=100)
            {
                ans++;
            }
        }
        double xx=ans*1.0/n*0.5;
        cout<<1-xx<<endl;
    }
    return 0;
}

1004 Deliver the Cake

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6805
题意：
张三同学从s到达t，同时手提蛋糕，在路上会切换左右手，但是某些路会规定左右手，必须使用对应的左右手，而每切换一次就需要x秒的时间，问张三最快需要消耗多少秒的时间
思路：
L和R可以考虑将换手造成的时间消耗放在边权上，对于M可以考虑将M分成L和R两条路（默认优先L）
然后自己跑Dijkstra就行，如果起点或者终点为M，需要创建边权为0的虚拟点代替
代码：

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define P pair<ll,int>
#define INF 0x3f3f3f3f
using namespace std;
const int N=2e5+10, M=2e6+10;

int T,n,m,s,t,x;
int to[M],nxt[M],val[M],head[N],idx;
char c[N];
ll dis[N];
bool st[N];

inline void add(int a,int b,int c)
{
    to[idx]=b,nxt[idx]=head[a],val[idx]=c,head[a]=idx++;
}

void dijkstra()
{
    memset(st,false,sizeof st);
    memset(dis,INF,sizeof dis);
    priority_queue<P,vector<P>,greater<P>> heap;
    if(c[s]=='M') heap.push({0,0}), dis[0]=0;
    else heap.push({0,s}), dis[s]=0;

    while(heap.size())
    {
        P t=heap.top();
        heap.pop();

        int id=t.second;
        if(st[id]) continue;
        st[id]=true;

        for(int i=head[id];~i;i=nxt[i])
        {
            int j=to[i];
            if(dis[j]>dis[id]+val[i])
            {
                dis[j]=dis[id]+val[i];
                heap.push({dis[j],j});
            }
        }
    }
}

void solve(){
    idx=0;
    memset(head,-1,sizeof head);   

    scanf("%d%d%d%d%d",&n,&m,&s,&t,&x);
    scanf("%s",c+1);
    if(c[s]=='M')
        add(0,s,0), add(s,0,0), add(0,s+n,0), add(s+n,0,0);
    if(c[t]=='M')
        add(2*n+1,t,0), add(t,2*n+1,0), add(2*n+1,t+n,0), add(t+n,2*n+1,0);
    int u, v, val;
    for(int i=0; i<m; i++){
        cin>>u>>v>>val;
        if(c[u]==c[v] && (c[u]=='R'||c[u]=='L'))
            add(u,v,val), add(v,u,val);
        else if(c[u]==c[v] && c[u]=='M')
            add(u,v,val), add(v,u,val), add(u+n,v,val+x), add(v,u+n,val+x), add(u,v+n,val+x), add(v+n,u,val+x), add(u+n, v+n, val), add(v+n, u+n, val);
        else if((c[u]=='L' && c[v]=='R')||(c[u]=='R'&&c[v]=='L'))
            add(u,v,val+x), add(v,u,val+x);
        else if(c[u]=='L' && c[v]=='M')
            add(u,v,val), add(v,u,val), add(u,v+n,val+x), add(v+n, u, val+x);
        else if(c[u]=='R' && c[v]=='M')
            add(u,v,val+x), add(v,u,val+x), add(u,v+n,val), add(v+n, u, val);
        else if(c[u]=='M' && c[v]=='L')
            add(u,v,val), add(v,u,val), add(u+n,v,val+x), add(v, u+n, val+x);
        else if(c[u]=='M' && c[v]=='R')
            add(u,v,val+x), add(v,u,val+x), add(u+n,v,val), add(v, u+n, val);
    }
    dijkstra();
    if(c[t]=='M')   cout<<dis[2*n+1];
    else            cout<<dis[t];
    cout<<endl;
}

int main()
{
    scanf("%d",&T);
    while(T--)  solve();
    return 0;
}

1005 Equal Sentences

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6806
题意：
就是给定一连串个单词，相邻<=1的两个不相同的单词可以进行交换(自身和自身交换也行)，问一共有多少组交换方法
思路：
因为位置之差不大于1，所以考虑交换相邻的两个单词来构造“几乎相等”（包括其本身）
在交换时，注意相同的单词不能交换，不能连着交换一个单词两次（例a, b, c不能交换成b,c,a）
其中dp[i]为前 i 个单词组成的“几乎相等”字符串的个数，所以dp[0]=dp[1]=1;
相邻两个单词相等，则不交换为dp[i]=dp[i-1];
不等交换，为dp[i]=(dp[i-1]+dp[i-2])%mod;
代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 100005, mod = 1e9 + 7;
int f[N], n;
string s[N];

int solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> s[i];
    }
    fill(f, f + n + 1, 0);
    f[0] = 1;
    for (int i = 1; i <= n; i ++) {
        f[i] = f[i - 1];
        if (i >= 2 && s[i] != s[i - 1]) { 
            f[i] = (f[i] + f[i - 2]) % mod;
        }
    }
    return f[n];
}

int main() {
    int Test;
    cin >> Test;
    for (int Case = 1; Case <= Test; Case ++) {
        printf("%d\n", solve());
    }
    return 0;
}

1011 Kindergarten Physics

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6812
题意：
两个小球同时下落，求他们之间的距离
思路：
一个理解题意的题，有两个重a，bkg的个，初始时候相距d距离，在只受重力影响的情况下，试问一段时间后他们之间的距离。根据初中知识，距离不变，所以我们只需要直接输出即可（这题就离谱）。
代码

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

本次比赛AC两道，排名754，继续努力