首页 > 其他分享 >luogu P2371 [国家集训队] 墨墨的等式 题解

luogu P2371 [国家集训队] 墨墨的等式 题解

时间:2024-07-29 21:18:26浏览次数:20  
标签:LF int 题解 LL P2371 que luogu pi dis

luogu P2371 [国家集训队] 墨墨的等式

题目传送门

思路

同余最短路

同余最短路

同余最短路与差分约束有异曲同工之妙,都将约束条件转化为边,每种状态转化为点。把本来与图论毫不相干的问题抽象到具体的图上,通过拓扑排序,最短路等基础算法获得最小状态,从而解决问题。

在本题中,以 \(0\) 到 \(a_1 - 1\) 为节点,对于节点 \(v\) ,遍历 \(a\) ,将 \(v\) 和 \((v + a_j) \bmod a_1\) 连权值为 \(a_j\) 的边。

把图建完之后,就形成了一个有向图,跑最短路后 \(dis_v\) 的值即为用题目给出的数能获得的最小的,对 \(a_1\) 取模为 \(v\) 的值。

\(\forall v\) ,\(1\) 到 \(n\) 中有 \(\dfrac{n - dis_v}{a_1} + 1\) 数是可以用题目给出的数到达,所以答案为 \(\sum_i^{a_1 - 1} \dfrac{r - dis_v}{a_1} - \dfrac{l - 1 - dis_v}{a_1}\)

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
typedef long long LL;

using namespace std;

const int N = 15, M = 5e5 + 5;
const LL inf = 1e18;

#define pb push_back
#define pi pair<LL, LL>
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)

priority_queue< pi, vector< pi >, greater< pi >> que;
vector< pi > g[M];
LL n, Min = 1e9;
LL l, r, dis[M], ans;
bool vis[M];
LL a[N];

void dijkstra() {
    dis[0] = 0;
    que.push({0, 0});

    while (que.size()) {
        int u = que.top().second;
        que.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto to : g[u]) {
            int v = to.first, w = to.second;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                que.push({dis[v], v});
            }
        }
    }
}

int main() {
    scanf("%lld%lld%lld", &n, &l, &r);
    
    LF(i, 1, n) {
        scanf("%lld", &a[i]);
        Min = min(Min, a[i]);
    }

    if (Min == 1) {
        printf("%lld\n", r - l + 1);
        return 0;
    }

    LF(i, 0, a[1] - 1) {
        LF(j, 1, n) g[i].pb({(i + a[j]) % a[1], a[j]});
        dis[i] = inf;
    }

    dijkstra();
    LF(i, 0, a[1] - 1) if (r >= dis[i]) ans += (r - dis[i]) / a[1] + 1;
    LF(i, 0, a[1] - 1) if (l - 1 >= dis[i]) ans -= (l - 1 - dis[i]) / a[1] + 1;
    printf("%lld", ans);
    return 0;
}

Und verloren sei uns der Tag, wo nicht ein Mal getanzt wurde!
每个不曾起舞的日子,都是对生命的一种辜负。
——《查拉图斯特拉如是说》

标签:LF,int,题解,LL,P2371,que,luogu,pi,dis
From: https://www.cnblogs.com/faruzan/p/18331104

相关文章

  • vue3中使用keepAlive缓存路由组件不生效的问题解决
    在Vue3中使用keep-alive缓存路由组件时,可能会遇到一些问题导致缓存不生效。以下是一些常见的问题及其解决方案:keep-alive写法错误:在Vue3中,使用keep-alive需要将router-view包裹在keep-alive中,并通过插槽传递组件。例如:<template><router-viewv-slot="{Co......
  • CF1523D Love-Hate 题解
    CF1523DLove-Hate题解传送门题目大意:给定\(m\)和\(n\)个集合,而且这\(n\)个集合的元素都是\(1\)~\(m\)中的数且没有重复,而且大小都不超过\(15\)。求一个最大的集合,使得这个集合是至少\(\left\lceil\frac{n}{2}\right\rceil\)个集合的子集。先想一个问题:题目是让......
  • CF1523E Crypto Lights 题解
    CF1523ECryptoLights题解传送门。题目大意:有\(n\)个台灯,初始时都是暗的,每次随机点亮一个暗台灯,若点亮后存在一个长度为\(k\)的连续段有大于一个台灯被点亮则立刻停止,求期望点亮多少台灯。(就是直接把原题翻译搬过来了)很明显的期望dp,状态定义也很明显,设\(f_i\)表示......
  • P8347 「Wdoi-6」另一侧的月 题解
    P8347「Wdoi-6」另一侧的月题解第一次自己思考出来紫题,题解纪念一下。下面为大家讲解如何一步步推到最终结论:首先,原树没有根,不妨设它的根为\(1\),将它转化成有根的,便于操作。为了方便描述,我们称将一个非根节点的点的父亲删去,保留含这个点的连通块这个操作为截取操作(就是......
  • CF538G Berserk Robot 题解
    Description有一个机器人,第\(0\)秒时在\((0,0)\)位置。机器人会循环执行一个长度为\(l\)的指令序列,每秒执行一个指令。指令有ULDR四种,分别代表向上/左/下/右移动一格。你不知道这个指令序列具体是什么,但是你知道\(n\)条信息,第\(i\)条信息为「第\(t_i\)秒时机器......
  • CF1634F Fibonacci Additions 题解
    CF1634FFibonacciAdditions题解传送门。题目大意:给定两个序列\(A\)和\(B\),每次一个可以选一个区间,并在区间的第\(i\)个数加上\(F_i\),其中\(F\)是斐波那契数列,你需要在每次询问结束时输出两个序列是否相等。可以先求一个序列\(C\)表示\(A\)和\(B\)每个位置的......
  • 剑指Offer题解合集
    剑指Offer题单及题解题目顺序为牛客上剑指Offer专题JZ3、数组中重复的数字分析可以直接对数组进行排序,通过判断首末数字大小来判断数字越界情况,注意数组为空的情况。发现\(0\leqnums[i]\leqn-1\),因此直接开一个数组判断是否有重复数字即可,返回第一个重复数字。代码......
  • 力扣题解2-两数相加
    问题的描述如下:分析过程:为了解决这个问题,我们需要逐位相加两个链表对应位置的值,并处理进位问题。具体步骤如下:初始化一个新的链表,用于存储结果。使用两个指针遍历两个输入链表,逐位相加,同时考虑进位。如果一个链表比另一个短,则将其视为0进行计算。处理最后可能存在的进位......
  • curl发送get和post请求时遇到&截断的问题解决
    get的parameter里带&被截断处理第一种是双引号括住 第二种是加反斜杠转义 post请求的body里有参数的value带了&curl-XPOSThttp://qa-ci.fuxi.netease.com:36800/job/xxxxx/xxxx--userxxxx:xxxxx-d token=popo -d"msg=cd/ssd/deployment_bash&&bashkill.b......
  • P10812 【MX-S2-T3】跳 题解
    题目分析考虑DP。显然当没有\(i\)连向\(i+1\)的边时,整个图是一个DAG,可以直接DP。所以我们DP要解决的唯一问题,就是考虑上\(i\)到\(i+1\)的边。考虑从\(n\)走到\(1\)的过程。当我们从\(i\)向前跳到\(j\)后,此时我们要么向前跳,要么往回走。又因为不能经过重复......