9.11 myl模拟赛

9.11 myl 模拟赛

100 + 100 + 0

第一题耗费了太多的时间，导致最后一题没有时间想，直接去写了暴力，而且出题人没有给暴力分。。。。

Problem 1. superman

【题目描述】

小可乐是要登上世界顶峰的男人！为了向他的妹子证明自己的能力，他决定去撒哈拉沙漠找到依米花送给他的妹子。

假设途中经过N个地区，编号为1~N，小可乐一开始在编号为1的地区，编号为N的地区代表撒哈拉沙漠，地区之间由于地形差别悬殊，并不是都可以直连的。同时由于不同经度存在时差，小可乐看了当地的地方时会以为出现了时间静止甚至倒流，所以我们假设两地区之间的穿行时间可以是负数或0，另外，由地区i到地区j的时间和由地区j到地区i的时间不一定是相同的。

小可乐在非洲的网友DDL被他感动了，决定去城市n迎接小可乐的到来，小可乐可以自己调整行动速度，为了不让DDL等得太着急，他想调整自己行动的速度，使得在每一条路上花费的时间都加或减一个整数，你的任务是调整小可乐的行动速度，找出一条用最短时间到达地区N的路径，并且保证这个最短时间的值大于或等于0。

【输入格式】

输入文件包含多组数据，第1个数为T，表示数据的数量。

对于每一组数据，输入第1行为两个正整数N，E，为地区的个数和地区间的路线数。然后E行，每行三个整数i，j和t（1≤i,j≤N，i≠j)，表示由地区i到地区j穿行的时间为t。由i到j最多只会有一条穿行线路。

【输出格式】

输出文件共T行，每组数据输出一行；

如果可以通过调节速度到达地区N，则输出一个非负整数，表示由地区1到地区N的最短时间。

如果不能由地区1到达地区N，则输出-1。

【输入样例】

4 5

1 2 1

1 3 1

2 3 -3

3 1 1

3 4 1

【输出样例】

【样例说明】

输入样例如图所示，其中节点标号表示相应地区，节点间数字表示所需时间。

如果设置控制速度的值为0，则有如下路径:1→2→3→1→2→……→3→4，使得投递的时间为负无穷大，显然是不符合要求的，所以应该把控制速度的值设为1,相当于每个时间值加1,得到的最短路径为1→2→3→4,所需时间为2+(-2)+2=2。

【说明】

Problem 2. market

【题目描述】

小可乐的妹子不在家，他只好自己去逛超市，小可乐最喜欢喝汽水，买到汽水会使小可乐开心起来，但是他也不愿意看到手里的毛毛变少，所以每买一瓶汽水也会有点难过，很显然他又遇到了很多麻烦。

现在小可乐面前有n瓶汽水，编号分别为1，2，3，……，n。他可以在这当中任意选择任意多瓶。其中第i瓶汽水有两个属性Wi和Ri，当他选择了第i瓶汽水后，就可以获得Wi的开心值；但是，他选择该汽水以后选择的所有汽水的开心值都会减少Ri。现在请你求出，该选择哪些汽水，并且该以什么样的顺序选取这些汽水，才能使得小可乐获得的开心值最大。

注意，开心值的减少是会叠加的。比如，选择了第i瓶汽水，那么就会获得Wi的开心值；然后又选择第j瓶汽水，又会获得了Wj-Ri开心值；之后又选择第k瓶汽水，又会获得Wk-Ri-Rj的开心值；那么他获得的开心值总和为Wi+(Wj-Ri)+(Wk-Ri-Rj)。

【输入格式】

第一行一个正整数n，表示汽水的瓶数。

接下来第2行到第n+1行，每行两个正整数Wi和Ri，含义如题目所述。

【输出格式】

输出仅一行，表示最大的开心值。

【输入样例】

5 2

3 5

【输出样例】

【说明】

20%的数据满足：n<=5，0<=Wi,Ri<=1000。

50%的数据满足：n<=15，0<=Wi,Ri<=1000。

100%的数据满足：n<=3000，0<=Wi,Ri<=200000。

样例解释：我们可以选择第1瓶汽水，获得了5点开心值；之后我们再选择第2瓶汽水，获得3-2=1点开心值。最后总的开心值为5+1=6。

Problem 3. Lemon_Soda

【题目描述】

小可乐惊喜的发现一瓶汽水中了再来一瓶，他去商店换汽水的时候，店主Lemon和Soda打算耍耍他，出了一个难题，而且做不出来就不给汽水喝

这题说的是：

使得达到或超过 n 位数字的最小正整数 x 是多少？

小可乐见了两位妹子紧张的不敢说话，快请你帮帮他解决这个难题吧

【输入格式】

一个正整数 n

【输出格式】

使得达到 n 位数字的最小正整数 x

【输入样例】

【输出样例】

【说明】

n<=2000000000

换底公式

T1 正向与反向建图两遍Dfs维护一下图的连通性，然后二分应该加的整数，用Spfa判负环检验。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <stack>

const int BUF = ; char Buf[BUF], *buf = Buf;

#define INF 1e7

inline void read (int &now)

{

    bool temp = false;

    for (now = ; !isdigit (*buf); ++ buf)

        if (*buf == '-') temp = true;

    for (; isdigit (*buf); now = now *  + *buf - '', ++ buf);

    if (temp) now = -now;

}

#define Max 120

struct E { E *n; int v, d; } *list[Max], *_list[Max], poor[Max * ], *Ta = poor;

bool is[Max], _is[Max], v[Max], F; int d[Max], c[Max], N;

void Can (int n) { is[n] = true; for (E *e = list[n]; e; e = e->n) if (!is[e->v]) Can (e->v); }

void Dfs (int n) { _is[n] = true; for (E *e = _list[n]; e; e = e->n) if (!_is[e->v]) Dfs (e->v); }

bool Spfa (int key)

{

    std :: stack <int> S; S.push (); c[] = , d[] = , v[] = true; E *e;

    for (int n, V; !S.empty (); )

    {

        n = S.top (); S.pop (); v[n] = false;

        for (e = list[n]; e; e = e->n)

        {

            V = e->v;

            if (!is[V] || !_is[V]) continue;

            if (d[V] > d[n] + e->d + key)

            {

                d[V] = d[n] + e->d + key;

                if (!v[V])

                {

                    v[V] = true, ++ c[V];

                    if (c[V] > N) return false;

                    S.push (V);

                }

            }

        }

    }

    return d[N] >= ;

}

int Main ()

{

    freopen ("superman.in", "r", stdin); freopen ("superman.out", "w", stdout);

    fread (buf, , BUF, stdin);    int M, x, y, Mid, l, r, res, Answer, Time; register int i, j; read (Time);

    for (; Time; -- Time)

    {

        read (N), read (M); Ta = poor; for (i = ; i <= N; ++ i) list[i] = _list[i] = NULL;

        for (i = ; i <= M; ++ i)

        {

            read (x), read (y), read (res);

            ++ Ta, Ta->v = y, Ta->n = list[x], list[x] = Ta, Ta->d = res;

            ++ Ta, Ta->v = x, Ta->n = _list[y], _list[y] = Ta, Ta->d = res;

        }

        memset (is, false, sizeof is); memset (_is, false, sizeof _is);

        Can (); if (is[N] == false) { printf ("-1\n"); continue; } Dfs (N);

        l = -, r = ;

        for (; l <= r; )

        {

            for (i = ; i <= N; ++ i) d[i] = INF, v[i] = false, c[i] = ;

            Mid = (l + r) / ;

            if (Spfa (Mid)) r = Mid - , Answer = d[N]; else l = Mid + ;

        }

        printf ("%d\n", Answer);

    }

    return ;

}

int ZlycerQan = Main (); int main (int argc, char *argv[]) { return ; }

T2 DP，f[i][j]表示前i个物品中选j个物品的最大价值，对原物品按照r值大小排个序后就可以dp了，方程为f[i][j] = max (f[i - 1][j], f[i - 1][j - 1] + q[i].w - q[i].c * (j - 1))

#include <cstdio>

#include <iostream>

#include <algorithm>

inline int max (int a, int b) { return a > b ? a : b; }

const int BUF = ; char Buf[BUF], *buf = Buf;

inline void read (int &now)

{

    for (now = ; !isdigit (*buf); ++ buf);

    for (; isdigit (*buf); now = now *  + *buf - '', ++ buf);

}

#define Max 3009

struct Q { int v, c; bool operator < (Q A) const { return c > A.c; } } q[Max];

int f[Max][Max];

int Main ()

{

    freopen ("market.in", "r", stdin); freopen ("market.out", "w", stdout);

    fread (buf, , BUF, stdin); int N, Answer = ; register int i, j; read (N);

    for (i = ; i <= N; ++ i) read (q[i].v), read (q[i].c);

    std :: sort (q + , q +  + N); f[][] = q[].v;

    for (i = ; i <= N; ++ i)

        for (j = ; j <= i; ++ j)

            f[i][j] = max (f[i - ][j], f[i - ][j - ] + q[i].v - q[i].c * (j - ));

    for (i = ; i <= N; ++ i) Answer = max (Answer, f[N][i]);

    printf ("%d", Answer);

    return ;

}

int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}

T3 一开始没时间做了，于是枚举了一下x，全TLE，

正解:

#include <cstdio>

#include <cmath>

#include <iostream>

inline void read (long long &now)

{

    register char c = getchar ();

    for (now = ; !isdigit (c); c = getchar ());

    for (; isdigit (c); now = now *  + c - '', c = getchar ()); -- now;

}

#define INF 1e17

#define flo double

int Main ()

{

    freopen ("Lemon_Soda.in", "r", stdin); freopen ("Lemon_Soda.out", "w", stdout);

    long long N; read (N); long long l = , r = INF, Mid, Answer;

    for (flo z = log (); l <= r; )

    {

        Mid = l + r >> ;

        if (Mid * log (Mid) / z >= N) r = Mid - , Answer = Mid; else l = Mid + ;

    }

    std :: cout << Answer;

    return ;

}

int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}

巴特西

9.11 myl模拟赛

100 + 100 + 0

第一题耗费了太多的时间，导致最后一题没有时间想，直接去写了暴力，而且出题人没有给暴力分。。。。

Problem 1. superman

Problem 2. market

Problem 3. Lemon_Soda

T1 正向与反向建图两遍Dfs维护一下图的连通性，然后二分应该加的整数，用Spfa判负环检验。

T2 DP，f[i][j]表示前i个物品中选j个物品的最大价值，对原物品按照r值大小排个序后就可以dp了，方程为f[i][j] = max (f[i - 1][j], f[i - 1][j - 1] + q[i].w - q[i].c * (j - 1))

T3 一开始没时间做了，于是枚举了一下x，全TLE，

正解:

最新文章

热门文章