欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

HDU多校四

程序员文章站 2022-09-17 08:00:32
总结:上次队内任务分配不好,这次分两组开题。比上次好多了,出了两道题,再接再厉!!!这里写目录标题一级目录题意思路代码一级目录题意思路代码一级目录题意思路代码一级目录题意思路代码一级目录题意思路代码一级目录题意思路代码一级目录题意思路代码一级目录题意思路代码一级目录题意思路代码一级目录题意思路代码......

总结:
上次队内任务分配不好,这次分两组开题。比上次好多了,出了两道题,再接再厉!!!

1002

题意

给你n种枪,然后给你n把枪的伤害和换弹时间,然后父亲和儿子(父慈子孝)随机选一种枪来对射。先把最优的武器选出来,花最少时间能打死对面那种(不止一个),父亲想赢的话就只有赌中这些最优的武器概率为cnt/n,选出来了也只有1/2的概率赢,最后我赢的概率就是父亲输的概率 ,1-cnt/2n。

思路

先把最优的武器选出来,花最少时间能打死对面那种(不止一个),父亲想赢的话就只有赌中这些最优的武器概率为cnt/n,选出来了也只有1/2的概率赢,最后我赢的概率就是父亲输的概率 ,1-cnt/2n。

代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const int maxn=1005;
struct aa{
    int x,y;
    int t;
}a[maxn];
bool cmp(aa a,aa b){
    return a.t<b.t;
}
int main(){
    int te;
    cin>>te;
    while(te--){
        int n;
        cin>>n;
        for(int i=0;i<n;++i){
            cin>>a[i].x>>a[i].y;
            int c=100-a[i].x;
            int cc=0;
            if(c>0){
                cc=c/a[i].x;
                if((c%a[i].x)!=0)
                 cc++;
            }
            a[i].t=cc*a[i].y;
        }
        double ans=0;
        sort(a,a+n,cmp);    
        int cc=a[0].t;
        int c=1;
        while(a[c].t==cc&&c<n)
             c++;
        ans=1-c*1.0/(2.0*n);
        printf("%.6lf\n",ans);
    } 
    return 0;
} 




1005

题意

给你一张无向联通图,图中的结点属于三种类型中的一种,这三种类型分别为M,L,R。从L/R结点到R/L结点要多花费x的时间,求从s点到t点最少要花费多少时间。

思路

把每个点拆成两个点,左点拆成两个左点,右点拆成两个右点,中间点拆成一左一右两个点,然后跑dijsktra

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+10;
const ll inf=1e18;
int n,m,s,t,cost;
string ss;
struct node {
    int u;
    int v;
    int w;
    int next;
}edge[maxn*8];
int head[maxn*3];
int tol=0;
void addedge (int u,int v,int w) {
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol].w=w;
    edge[tol].next=head[u];
    head[u]=tol++;
    
    edge[tol].u=v;
    edge[tol].v=u;
    edge[tol].w=w;
    edge[tol].next=head[v];
    head[v]=tol++;
}
ll d[maxn];
int visit[maxn];
char wjm[maxn];
struct qnode {
    int v;
    ll w;
    bool operator < (const qnode &r) const {
        return w>r.w;
    }
};
void dij (int s) {
    memset(visit,0,sizeof(visit));
    for (int i=1;i<=2*n;i++) d[i]=inf;
    priority_queue<qnode> q;
    d[s]=0;
    q.push({s,0});
    qnode tmp;
    while (!q.empty()) {
        tmp=q.top();
        q.pop();
        int u=tmp.v;
        if (visit[u]) continue;
        visit[u]=1;
        for (int i=head[u];i!=-1;i=edge[i].next) {
            int v=edge[i].v;
            int tt;
            if (wjm[u]==wjm[v])
                tt=0;
            else
                tt=1;
            if (!visit[v]&&d[v]>d[u]+edge[i].w+tt*cost) {
                d[v]=d[u]+edge[i].w+tt*cost;
                //if (!visit[v]) {
                    q.push({v,d[v]});
                    //visit[v]=1;
                //}
            }
        }
    } 
}
int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d%d%d%d",&n,&m,&s,&t,&cost);
        for (int i=1;i<=n*2;i++) head[i]=-1;
        cin>>ss;

        for (int i=1;i<=n;i++) {
            if (ss[i-1]=='L') {
                wjm[i]='L';
                wjm[i+n]='L';
            }
            else if (ss[i-1]=='R') {
                wjm[i]='R';
                wjm[i+n]='R';
            }
            else {
                wjm[i]='L';
                wjm[i+n]='R';
            }
        } 
        tol=0;
        for (int i=0;i<m;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(u+n,v,w);
            addedge(u+n,v+n,w);
            addedge(u,v+n,w);
        }
        ll ans=1e18;
        dij(s);
        ans=min(ans,d[t]);
        ans=min(ans,d[t+n]);
        dij(s+n);
        ans=min(ans,d[t]);
        ans=min(ans,d[t+n]); 
        printf("%lld\n",ans);
    }
    return 0;
}

1011

题意

给出两点距离以及时间,求之后的距离。

思路

对距离影响很小,直接输出距离即可,精确度范围内。

代码

#include<bits/stdc++.h>
#define pb(a) push_back(a)
#define ms(x,y) memset(x,y,sizeof(x))
#define sci(a) scanf("%d",&a) 
#define scl(a) scanf("%lld",&a)
#define scd(a) scanf("%lf",&a) 
#define ll long long 
using namespace std;
/* --------------- fast io --------------- */ // begin
namespace Fread{
const int SIZE=1<<20;
char buf[SIZE],*S,*T;
inline char getchar(){
    if(S==T){
        T=(S=buf)+fread(buf,1,SIZE,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}
}//namespace Fread
namespace Fwrite{
const int SIZE=1<<20;
char buf[SIZE],*S=buf,*T=buf+SIZE;
inline void flush(){
    fwrite(buf,1,S-buf,stdout);
    S=buf;
}
inline void putchar(char c){
    *S++=c;
    if(S==T)flush();
}
struct _{
    ~_(){flush();}
}__;
}//namespace Fwrite

#ifdef ONLINE_JUDGE
    #define getchar Fread::getchar
    #define putchar Fwrite::putchar
#endif

template<typename T>inline void read(T& x){
    x=0;int f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+(c-'0'),c=getchar();
    x*=f;
}
template<typename T>inline void write(T x,bool _enter=0,bool _space=0){
    if (!x)putchar('0');else{
        if(x<0)putchar('-'),x=-x;
        static char dig[41];
        int top=0;
        while(x)dig[++top]=(x%10)+'0',x/=10;
        while(top)putchar(dig[top--]);
    }
    if(_enter)putchar('\n');
    if(_space)putchar(' ');
}

namespace Fastio{
struct reader{
    template<typename T>reader& operator>>(T& x){::read(x);return *this;}
    reader& operator>>(char& c){
        c=getchar();
        while(c=='\n'||c==' ')c=getchar();
        return *this;
    }
    reader& operator>>(char* str){
        int len=0;
        char c=getchar();
        while(c=='\n'||c==' ')c=getchar();
        while(c!='\n'&&c!=' ')str[len++]=c,c=getchar();
        str[len]='\0';
        return *this;
    }
}cin;
const char endl='\n';
struct writer{
    template<typename T>writer& operator<<(T x){::write(x,0,0);return *this;}
    writer& operator<<(char c){putchar(c);return *this;}
    writer& operator<<(const char* str){
        int cur=0;
        while(str[cur])putchar(str[cur++]);
        return *this;
    }
}cout;
}//namespace Fastio
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
/* --------------- fast io --------------- */ // end

int main(){
    int te;
    cin>>te;
    while(te--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        cout<<c<<endl;
        
    } 
    return 0;
} 

本文地址:https://blog.csdn.net/weixin_43912188/article/details/107897135