1 条题解
-
0
A 星际通讯 (telecom) 题解
题目大意
- 一次按键:选择一个整数
x ≥ 0- 立即传输
10^x字节 - 花费
2^x秒
- 立即传输
- 给定一个需传输的字节数
r (1 ≤ r ≤ 10¹⁸),求最少需要多少秒。 - 共有
T (1 ≤ T ≤ 5 × 10⁴)次独立查询。
Solution
本题考察模拟,同一位的块数绝不会 ,这就意味着正好就是 的十进制展开。
进一步分析,如果第 位()有 ()个块,那么它们所产生的总时间是 。
整体最少时间 即 ,其中 只需要到 ,原因是 是给定的上界。
算法
- 读入
r按字符串处理,方便取得每一位的十进制数字。 - 从最低位(个位)开始向高位遍历:
- 当前位置下标记为
i,数字为d。 - 累加
ans += d × (1LL << i)。
- 当前位置下标记为
- 输出
ans。
i ≤ 18,因此1LL << i不会溢出 64 位。- 每个
r最多 19 位,总运算量T × 19,约 95 万次,非常快。
Code
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; if (!(cin >> T)) return 0; while (T--) { string r; cin >> r; long long ans = 0; int len = r.size(); // 从最低位开始处理:r[len-1] 是个位 for (int i = 0; i < len; ++i) { int digit = r[len - 1 - i] - '0'; ans += 1LL * digit * (1LL << i); // digit × 2^i } cout << ans << '\n'; } return 0; }B 禁忌的联盟 (lol) 题解
Step 1: 忽略 颜色限制,只处理 不互质
定义DP状态
定义一个DP状态:
f[p],表示以质因数 为最后一位因子的最长子序列长度。转移方式
观察到,如果两个数 有公共质因数 ,那么它们之间可以相连。
对于每个 ,我们枚举它所有的质因数 ,找到所有 中的最大值 ,然后令当前元素作为结尾的子序列长度为 ;然后反向更新所有这些质因数的 。
这个部分的复杂度是 ,因为对每个 做质因数分解。
Step 2: 引入 不同的限制(颜色限制)
每个质因数 下,维护两个记录:
f[p].max1:最大的子序列长度,以及对应的f[p].max2:第二大的子序列长度(必须与max1的 不同)
转移逻辑
对于当前元素 ,设 的所有质因数集合为 ,我们尝试从这些质因数对应的最长记录中转移:
$$dp[i] = \max_{p \in P} \begin{cases} f[p].\text{max1}.\text{value} & \text{if } f[p].\text{max1}.\text{color} \neq a_i \\ f[p].\text{max2}.\text{value} & \text{if } f[p].\text{max1}.\text{color} = a_i \end{cases}$$然后将 更新回所有 的
f[p]中对应的位置。总复杂度:,其中
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <cstring> #include <cmath> #include <set> #include <map> #include <unordered_map> using namespace std; #define int long long using pii = pair<int, int>; using ull = unsigned long long; // #define debug(x) cout << #x << ":" << x << endl constexpr int M = 5e5 + 2; int col[M], a[M]; int pri[M]; int prime[M]; int n, cnt, ans; struct node { int len, c; }; node max1[M], max2[M]; void ols(int n) { int i, j; for (i = 2; i <= n; i++) { if (!pri[i]) { pri[i] = i; prime[cnt++] = i; } for (j = 0; i * prime[j] <= n; j++) { pri[i * prime[j]] = prime[j]; if (i % prime[j] == 0) { break; } } } } vector<int> f(int x) { vector<int> t; while (x > 1) { int p = pri[x]; t.push_back(p); while (x % p == 0) x /= p; } return t; } void solve() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i] >> col[i]; ols(5e5); for (int i = 1; i <= n; i++) { auto v = f(a[i]); int curmax = 0; cerr<<i<<":"<<curmax<<endl; for (auto &ele : v) { cerr<<ele<<"ssss"<<endl; if (max1[ele].c == col[i]) curmax = max(curmax, max2[ele].len); else curmax = max(curmax, max1[ele].len); } curmax++; ans = max(ans, curmax); for (auto &ele : v) { if (max1[ele].c == col[i]) max1[ele].len = max(max1[ele].len, curmax); else { if (curmax > max1[ele].len) { max2[ele] = max1[ele]; max1[ele] = {curmax, col[i]}; } else if (curmax > max2[ele].len) { max2[ele] = {curmax, col[i]}; } } } } cout << ans << endl; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; }C 神秘合金 (medal)
首先,定义
dp[sum, u]表示从节点 1 到节点 的路径中,经过的所有边的 总和为sum时,路径的 总和的最小值。我们的目标是从节点 1 到节点 ,找到使性能值最小的路径,性能值为:在这个过程中,状态转移的关键是根据边的属性 更新状态。
具体地,如果当前在节点 ,通过一条边 转移到节点 ,并且该边的 和 分别为 和 ,那么状态转移方程可以表示为:
$$dp[\text{sum} + a][v] = \min(dp[\text{sum} + a][v], dp[\text{sum}][u] + b)$$说明:
- 其中 表示当前路径的 总和。
- 通过边 ,新的路径的 总和为 ,路径的 总和为 。
这个方程的含义是:当我们从节点 转移到节点 时,如果当前路径的 总和为
sum,我们就将这个新的路径的 总和 和新的 总和 更新到状态 。注意到 时,状态相同的情况之间没有转移:
由于题目中规定 ,即每条边的 值都是正整数。因此,当前路径的 总和会随着每一次转移而增加,不能减少。
- 假设某条路径经过了节点 和节点 ,且路径的 。
- 当我们通过边 转移时,新的路径的 会变为 (因为 ),而 一定会增加。
- 因为 增加,且每个状态的 之间是严格递增的,所以在计算 时,如果某个状态的 已经确定了一个值,那么我们就可以直接从小的 值开始枚举,从而避免不必要的重复计算。
因此,状态之间不可能相同的情况会导致我们不需要转移到相同的 值。换句话说,路径的 总和的变化是单调递增的,因此状态间不会有相同的 值进行转移。
时间复杂度为
- 一次按键:选择一个整数
- 1
信息
- ID
- 217
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者