同余最短路

发布于 2023-05-24  189 次阅读


前言

在刷蓝桥杯国赛题目的时候刷到了这个神奇的东西。记录一下。现在放一下那道题。

最少的 1

问题描述

给定一个正整数 n, 找出所有 n 的倍数的二进制表示中最少有多少个 1 。

输入格式

输入一行包含一个整数 n 。

输出格式

输出一行包含一个整数表示答安。

样例输入

7

样例输出

3

样例说明

14 是 7 的倍数, 其二进制表示为 1110 , 有 3 个 1 。 也是 7 的倍数, 二进制表示中也有 3 个 1 。可以证明 7 的其他倍数的二进制表示不会具有更少的 1。

对于所有评测用例, $1≤n≤10^6$ 。

垃圾蓝桥网站题目显示有问题还有错字,我直接复制的(

题解

暴力+卡时能骗多少分我不知道,看数据强度吧

因为我们不知道n的倍数具体能到多少,我们开数组记录的话数组不知道要开多大,这里可以把所有数字模n。

我们开一个数组$dis[i], i \in (0, n-1)$表i的倍数中二进制中最少的1的数目, 因为所有整数都可以由1 通过×2和+1两种操作间接得到。

对于×2,相当于二进制所有数字右移一位,所以总数不变。

$$dis[(i \times 2)\mod n] = min(dis[(i \times 2)\mod n], dis[i]) $$

对于+1操作,如果当前数字是偶数的话,二进制最后一位肯定是0,所以加一相当于在当前结果上加一

$$dis[(i+1)\mod n] = min(dis[(i+1)\mod n], dis[i] + 1) $$

如果当前数字是奇数,暴力统计1的个数,并和当前结果比较即可。

这种形式是不是很想图论,其实本质上就是利用同余的性质去建了个图,跑个最短路求答案而已。

Code #1

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 1000005;
int n, dis[maxn];

inline int check(int x) // 对于奇数暴力统计
{
    int ans = 0;
    while (x)
    {
        if (x & 1)
            ans++;
        x >>= 1;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    memset(dis, 0x3f, sizeof(dis));
    cin >> n;
    dis[1] = 1;
    priority_queue<pair<int, int>> q;
    q.push({1, 1});
    while (!q.empty())
    {
        int now = q.top().second;
        q.pop();
        if (dis[now * 2 % n] > dis[now])
        {
            dis[now * 2 % n] = dis[now];
            q.push({-dis[now], now * 2 % n});
        }
        if (!(now & 1))
        {
            if (dis[(now + 1) % n] > dis[now] + 1)
            {
                dis[(now + 1) % n] = dis[now] + 1;
                q.push({-dis[(now + 1) % n], (now + 1) % n});
            }
        }
        else if (dis[(now + 1) % n] > check(now + 1))
        {
            dis[(now + 1) % n] = check(now + 1);
            q.push({-dis[(now + 1) % n], (now + 1) % n});
        }
    }
    cout << dis[0] << endl;
    return 0;
}

洛谷 P3403 跳楼机

题目背景

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

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

15
4 7 9

样例输出 #1

9

样例 #2

样例输入 #2

33333333333
99005 99002 100000

样例输出 #2

33302114671

提示

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

$1 \le h \le 2^{63}-1$,$1 \le x,y,z \le 10^5$。

题解

这题同样也是同余最短路,我们定义的一个$dis[i], i \in (0, x-1)$表示在模x意义下我们只使用2,3操作可以到达的楼层所用的最少步数。

$$dis[(now + y) \mod x] = \min(dis[(now + y) \mod x], dis[now] + y)$$

$$dis[(now + z) \mod x] = \min(dis[(now + z) \mod x], dis[now] + z)$$

这样我们就表示出了操作2,操作3的结果,只要用$\frac{h-dis[i]}{x} + 1$就可以得到最后的结果,因为我们开始是模的x,本质上压缩了dis数组的空间,现在除x就能得到压缩了多少次。

Code #2

#include <iostream>
#include <queue>
#include <cstring>
#define int long long
using namespace std;

const int maxn = 100005;
int h, x, y, z, dis[maxn];

void dijkstra() // 跑最短路
{
    dis[1] = 1;
    priority_queue<pair<int, int>> q;
    q.push({-1, 1});
    while (!q.empty())
    {
        int now = q.top().second;
        q.pop();
        if (dis[(now + y) % x] > dis[now] + y)
        {
            dis[(now + y) % x] = dis[now] + y;
            q.push({-dis[(now + y) % x], (now + y) % x});
        }
        if (dis[(now + z) % x] > dis[now] + z)
        {
            dis[(now + z) % x] = dis[now] + z;
            q.push({-dis[(now + z) % x], (now + z) % x});
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(dis, 0x3f, sizeof(dis));

    cin >> h >> x >> y >> z;
    if (x == 1 or y == 1 or z == 1) 
    // 特判,如果出现了1,一层一层的走肯定能表示全部的楼层
    {
        cout << h;
        return 0;
    }
    dijkstra();
    int ans = 0;
    for (int i = 0; i < x; i++)
        if (dis[i] <= h)
            ans += (h - dis[i]) / x + 1;
    cout << ans << endl;
    return 0;
}

$end$