这场好毒瘤啊。。。A 和 B 题面长,C 开始不会做。。。

1501A – Alexey and Train

题意

这题很多人读题存在障碍…

某人从起点站(姑且可以认为其编号为 0)坐火车在时刻 0 出发,沿线依次经过 n 个编号从 1n 的火车站。列车的时刻表用 n 个数对 (a_i,b_i) 表示,描述了本来列车应该在 a_i 时刻到达第 i 个站并在 b_i 时刻离开。

由于天气影响,列车无法按照时刻表运行,他算出了 n 个整数 tm_i,描述了从第 i – 1 个站到第 i 个站需要多走的时间,实际上,从第 i – 1 个站到第 i 个站需要的时间即为 a_i – b_{i – 1} + tm_i

列车从第 i 个站出发需要同时满足:

  • 时刻大于等于 b_i
  • 在该站停留的时间大于等于 \lceil\frac{b_i – a_i}{2}\rceil

利用以上信息计算列车到达第 n 个站的时间。

题解

难点是读懂题,读懂题后直接模拟就可以了,注意离站的条件即可。

#include <cstdio>
#include <cctype>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

int read()
{
    int s = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

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

const int maxn = 105;
int a[maxn], b[maxn], tm[maxn], n;

int calc(int b, int a)
{
    int ret = b - a;
    return (ret & 1) ? ((b - a) >> 1) + 1 : ((b - a) >> 1);
}

int main()
{
    int T = read();
    while (T--)
    {
        n = read();
        FOR(i, 1, n)
            a[i] = read(), b[i] = read();
        FOR(i, 1, n) tm[i] = read();
        int now = 0;
        FOR(i, 1, n)
        {
            now += a[i] - b[i - 1] + tm[i];
            if (i == n) break;
            now = max(now, max(now + calc(b[i], a[i]), b[i]));
        }
        printf("%d\n", now);
    }
    return 0;
}

1501B – Napoleon Cake

题意

制作拿破仑蛋糕时需要依次叠放 n 个干的层,给定 \lbrace a_n\rbrace,描述了在叠放第 i 层之后需要加的奶油量,加了量为 x 的奶油会使得最顶层的 x 层变湿。

对于每一层求最后的干湿状态。

题解

不难发现其就是一个线段覆盖问题,可以使用差分进行求解。加到 i 层的时候把 d_{\max\lbrace0, i – a_i + 1\rbrace}:= 1d_{i + 1}:= -1 即可,最后把前缀和累加回来就能得到答案。

注意多测清空。

#include <cstdio>
#include <cctype>
#include <cstring>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

int read()
{
    int s = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

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

const int maxn = 2e5 + 5;
int stk[maxn], n;

int main()
{
    int T = read();
    while (T--)
    {
        n = read();
        FOR(i, 1, n)
        {
            int a = read();
            if (!a) continue;
            int low = max(0, i - a + 1), up = i;
            ++stk[low], --stk[up + 1];
        }
        FOR(i, 1, n) stk[i] += stk[i - 1];
        FOR(i, 1, n) printf("%d ", stk[i] ? 1 : 0), stk[i] = 0;
        stk[n + 1] = stk[0] = 0;
        puts("");
    }
    return 0;
}

1500A – Going Home

题意

给定 \lbrace a_n\rbrace,满足 4\le n\le 2\times10^5 并且 \forall i\in[1,n],1\le a_i\le 2.5\times10^6,求四个不同的下标 x,y,z,w 使得 a_x + a_y = a_z + a_w

有解则打印解,无解输出 \texttt{NO}

题解

注意到我们的和 a_i + a_j\le 5\times 10^6,这个是解决问题的关键。

所以我们直接大力枚举 S = a_i + a_j,记录一下加出来的这个 S,如果同样的 S 出现了第二次则直接输出答案就好。根据鸽巢原理,我们如果枚举的次数超过了值域,那么就肯定不存在解。

#include <cstdio>
#include <cctype>
#include <algorithm>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

int read()
{
    int s = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

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

const int maxn = 2e5 + 5, maxs = 5e6 + 5;

struct node
{
    int id, val;
    bool operator<(const node &b) const
    {
        if (val == b.val) return id < b.id;
        else return val < b.val;
    }
} a[maxn], ans[maxs];

int n;

int main()
{
    n = read();
    FOR(i, 1, n) a[i].val = read(), a[i].id = i;
    std::sort(a + 1, a + n + 1);
    int cnt = 0;
    FOR(i, 1, n)
        FOR(j, i + 1, n)
        {
            int s = a[i].val + a[j].val;
            if (ans[s].id + ans[s].val && ans[s].id != a[i].id && ans[s].id != a[j].id && ans[s].val != a[i].id && ans[s].val != a[j].id)
            {
                printf("YES\n%d %d %d %d", a[i].id, a[j].id, ans[s].id, ans[s].val);
                return 0;
            }
            else if (!ans[s].id)
                ans[s].id = a[i].id, ans[s].val = a[j].id, ++cnt;
            if (cnt >= 5e6)
            {
                puts("NO");
                return 0;
            }
        }
    puts("NO");
    return 0;
}
最后修改日期: 2021年3月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。