【SinGuLaRiTy-1016】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

对于所有的题目：Time Limit：1s  |  Memory：256 MB

第一题：路径

题目描述

有n个点，m条无向边，有A,B两个人，初始时刻A在点1，B在点2，他们要走到点n去。A每走一条边，要消耗B单位能量，B每走一条边，要消耗E单位能量。如果A,B相伴走，则只消耗P单位的能量。请问A,B走到点n，最少要消耗多少能量?

输入数据保证1和n，2和n连通。

输入

第一行包含整数B,E,P,N和M，所有的整数都不超过40000，N>=3。

接下来M行，每行两个整数，表示该无向边连接的两个顶点。

输出

一个整数，表示最小要消耗的能量。

样例数据

4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8

STD Code

题目分析

第二题：magic

题目描述

小魔仙为了拯救她的好朋友芭比兔，千方百计的弄到了关押芭比兔的迷宫的地图。迷宫的入口在点1处，关押芭比兔的地点在点n处。在迷宫中，小魔仙只能沿着水平方向或竖直方向移动，否则就会碰壁。迷宫中的墙是无形的，幸好地图中已经给出了小魔仙的所有必经地点，她必须严格按照地图中给出的顺序访问这些必经点，才能达到点n处。小魔仙走路的速度很慢，每秒种只能走一个单位距离。但是小魔仙可以施展魔法，这样她可以瞬间跳过其中若干点，时间消耗几乎为0。但是她的魔法最多只能让她跳过k个点（注意：她不能跳过起点和终点，即点1和点n）。她想以最快的速度救出芭比兔，请问她最少需要多少时间。地图的行经路线可能会多次经过同一个坐标。小魔仙跳过的k个点是指在行经路线中的点，如果某个点被跳过多次，则每一次都要消耗魔法。

输入

第一行包含N，K.(N<=500,K<=N)接下来N行包含两个整数x，y,表示需要访问的顶点坐标。（-1000<=x<=1000,-1000<=y<=1000）

输出

小魔仙最少需要的时间。

样例数据

STD Code

题目分析

第三题：公路

题目描述

有一条单向的高速公路，只有一条车道，有n（1<=n<=100000）辆车在车高速路上行驶。他们的车速可能不同。但因为只有一条车道，所以不存在超车的可能。如果一辆车追上了前车，它就只能减速，与前车以同样的速度行驶，这样它们可以成为一个group。这些汽车的体积可以忽略不计。问经过T单位时间，高速公路上一共有多少个group。（当T时刻时，所有位置相同的汽车称为一个group）。

输入

第一行两个整数N,T(1<=T<=1000000000)

接下来N行，每行包含两个整数，分别表示一辆车的初始位置和初始速度。

输出

一个整数，表示T时刻后有多少个group。

样例数据

STD Code

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>

#define LL long long

using namespace std;

int n,k,sum;

struct node
{
    LL  x,l,f;
};

node a[100010];

bool cmp(node a,node b)
{
    return a.f<b.f;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d%I64d",&a[i].x,&a[i].l);
        a[i].f=a[i].x;
        a[i].x+=a[i].l*k;
    }
    sort(a+1,a+1+n,cmp);
    LL  p=a[n].x;
    for(int i=n-1;i>=1;i--)
    {
        if(a[i].x>=p)
            sum++;
        else
            p=a[i].x;
    }
    printf("%d",n-sum);
    return 0;
}

题目分析

Time ： 2017-04-08

[SinGuLaRiTy] 2017-04-08 综合性测试

原文：http://www.cnblogs.com/SinGuLaRiTy2001/p/6681978.html