分类 Luogu 下的文章

这题真的是太火辣

题目

题目背景

DJL为了避免成为一只咸鱼,来找srwudi学习压代码的技巧。

题目描述

Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多,srwudi改造了一个跳楼机,使得访客可以更方便的上楼。

经过改造,srwudi的跳楼机可以采用以下四种方式移动:

  1. 向上移动x层;
  2. 向上移动y层;
  3. 向上移动z层;
  4. 回到第一层。

一个月黑风高的大中午,DJL来到了srwudi的家,现在他在srwudi家的第一层,碰巧跳楼机也在第一层。DJL想知道,他可以乘坐跳楼机前往的楼层数。

输入输出格式

输入格式:

第一行一个整数h,表示摩天大楼的层数。

第二行三个正整数,分别表示题目中的x, y, z。

输出格式:

一行一个整数,表示DJL可以到达的楼层数。

输入输出样例

输入样例#1:

15 4 7 9

输出样例#1:

9

输入样例#2:

33333333333 99005 99002 100000

输出样例#2:

33302114671

说明

可以到达的楼层有:1,5,8,9,10,12,13,14,15

想不出来不要死磕这一题,先看看第三题。。。。

1<=h<=2^63-1

1<=x, y, z<=100000


题解

首先看到 2^{63} -1这个数据范围,就应该想到复杂度是跟h无关或是log

聪明的我果然没有想到

这题可以说是一个套路:模后求各种东西

正解为:

首先考虑只用y和z跳,把能跳到的楼层记录下来。

然后再跳x,那么只需再y和z跳的基础上加上x即可,但是我们想y和z跳多了没有用,于是我们把y和z可以跳到的楼层都%x,模掉的部分由x来跳,那么就会想万一剩下的部分x跳不到怎么办,于是我们可以吧模型转化一下,所有y和z可以跳到的节点%x,然后边权设为y或者z,那么又可以表示高度也可以使用上面讲的东西,设从1到高度%x为i的最小高度为f[i], 那么从当前高度%x可以到达的层数为(h-f[i])/x+1,至于f[i]当然是要求最小的。

还有Dijkstra不是道为什么莫名只有70分(不是T)


代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define File(s) freopen(#s".in", "r", stdin); freopen(#s".out", "w", stdout)
#define gi get_int()
#define for_edge(i, x) for (int i = Head[x]; i != -1; i = Edges[i].Next)
#define _ 200000
long long get_int()
{
    long long x = 0, y = 1; char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-')
        ch = getchar();
    if (ch == '-') y = -1, ch = getchar();
    while (ch <= '9' && ch >= '0') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * y;
}

class Edge
{
public:
    int Next, To, Value;
}Edges[_];
int Head[_], E_num;
void Add_edge(int From, int To, int Value)
{
    Edges[E_num] = (Edge){Head[From], To, Value};
    Head[From] = E_num++;
}

long long Dist[_], h, x, y, z;
bool Vis[_];
void SPFA()
{
    memset(Dist, 0x3f, sizeof(Dist));
    memset(Vis, 0, sizeof(Vis));
    std::queue<int> Q;
    Q.push(1 % x);
    Vis[1 % x] = true;
    Dist[1 % x] = 1;
    while (!Q.empty()) {
        int Now = Q.front();Q.pop();
        for_edge(i, Now) {
            int To = Edges[i].To, Value = Edges[i].Value;
            if (Dist[To] <= Dist[Now] + Value) continue;
            Dist[To] = Dist[Now] + Value;
            if (Vis[To] == false) {
                Vis[To] = true;
                Q.push(To);
            }
        }
        Vis[Now] = false;
    }
}

int main()
{
    File(code);
    memset(Head, -1, sizeof(Head));
    h = gi, x = gi, y = gi, z = gi;
    for (int i = 0; i < x; i++) {
        Add_edge(i, (i + y) % x, y);
        Add_edge(i, (i + z) % x, z);
    }
    SPFA();
    long long Ans = 0;
    for (int i = 0; i < x; i++)
        if (Dist[i] <= h) Ans += (h - Dist[i]) / x + 1;
    printf("%lld", Ans);
    return 0;
}

第一次写这种东西写的是真的烂

题目

题目描述

墨墨突然对等式很感兴趣,他正在研究,problem1存在非负整数解的条件,他要求你编写一个程序,给定N、{an}、以及B的取值范围,求出有多少B可以使等式存在非负整数解。

输入输出格式

输入格式:

输入的第一行包含3个正整数,problem2​分别表示数列的长度、B的下界、B的上界。

输入的第二行包含N个整数,即数列{an}的值。

输出格式:

输出一个整数,表示有多少b可以使等式存在非负整数解。

输入输出样例

输入样例#1:

2 5 10 3 5

输出样例#1:

5

说明

对于20%的数据,20pts

对于40%的数据,40pts

对于100%的数据,100pts


题解

对我来说这是道神仙题

这题和Luogu2403跳楼机很像,只不过跳楼机只有x,y,z,而这题有很多个a[i],考虑只用除了a[0]的其他数加,那么所加出来的数%a[0],然后再记录一下%之前的数,那么求出每个0 ~ (a[0]-1)需要加的最小的数,然后统计答案(如何统计参考Luogu3403跳楼机),最后用Bmax统计出来的答案-Bmin统计出来的答案,就是本题的答案了


代码

  • 注意一下这题对我这种数组乱开的人有点卡空间,试了好几次数组的大小才过
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define File(s) freopen(#s".in", "r", stdin); freopen(#s".out", "w", stdout)
#define gi get_int()
#define _ 4000005
#define for_edge(i, x) for (int i = Head[x]; i != -1; i = Edges[i].Next)
#define INF 0x3f3f3f3f
long long get_int()
{
    long long x = 0, y = 1; char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-')
        ch = getchar();
    if (ch == '-') y = -1, ch = getchar();
    while (ch <= '9' && ch >= '0') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * y;
}

class Edge
{
    public:
        int Next, To, Value;
}Edges[_];
int Head[_], E_num;
void Add_edge(int From, int To, int Value)
{
    Edges[E_num] = (Edge){Head[From], To, Value};
    Head[From] = E_num++;
}

long long Dist[_], Vis[_], Num[_];

void SPFA()
{
    memset(Dist, 0x3f, sizeof(Dist));
    memset(Vis, 0, sizeof(Vis));
    std::queue<int> Q;
    Q.push(0);
    Dist[0] = 0;
    Vis[0] = true;
    while (!Q.empty()) {
        int Now = Q.front();Q.pop();
        for_edge(i, Now) {
            int To = Edges[i].To, Value = Edges[i].Value;
            if (Dist[To] <= Dist[Now] + Value) continue;
            Dist[To] = Dist[Now] + Value;
            if (Vis[To] == false) {
                Vis[To] = true;
                Q.push(To);
            }
        }
        Vis[Now] = false;
    }
}

int main()
{
    memset(Head, -1, sizeof(Head));
    int n = gi;
    long long Bmin = gi - 1, Bmax = gi, Min = INF;
    for (int i = 0; i < n; i++) {
        Num[i] = gi;
        Min = std::min(Min, Num[i]);
    }
    std::sort(Num, Num + n);
    for (int i = 0; i < Min; i++)
        for (int j = 1; j < n; j++)
            Add_edge(i, (i + Num[j]) % Min, Num[j]);
    SPFA();
    long long Ans = 0;
    for (int i = 0; i < Min; i++) {
        if (Dist[i] <= Bmin) Ans -= (Bmin - Dist[i]) / Min + 1;
        if (Dist[i] <= Bmax) Ans += (Bmax - Dist[i]) / Min + 1;
    }
    printf("%lld", Ans);
    return 0;
}