前言
在刷蓝桥杯国赛题目的时候刷到了这个神奇的东西。记录一下。现在放一下那道题。
最少的 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 的跳楼机可以采用以下四种方式移动：
- 向上移动 $x$ 层；
- 向上移动 $y$ 层；
- 向上移动 $z$ 层；
- 回到第一层。
一个月黑风高的大中午，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;
}
Comments NOTHING