3 条题解
-
0
超时代码:
#include <bits/stdc++.h> using namespace std; using ll = long long ; // priority_queue 默认是:大根堆 int main(){ ll a; int n; int x; while(cin>>a>>n){ priority_queue<ll,vector<ll>,greater<ll>> qq;//小根堆 unordered_set<ll> vis;//不排序的 ,去重 qq.push(a); for(int i=1;i<=n;i++) { x=qq.top(); qq.pop(); ll y1=2*x+1; ll y2=3*x+1; if(!vis.count(y1)) { vis.insert(y1); qq.push(y1); } if(!vis.count(y2)) { vis.insert(y2); qq.push(y2); } } cout<<x<<endl; } return 0; } -
0
丑数双指针:
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll a; int n; while (cin >> a >> n) { // 特判:第1个元素就是基 a if (n == 1) { cout << a << "\n"; continue; } // 用 vector 存前 n 个元素,0-based vector<ll> v(n); v[0] = a; // 两个指针 i2, i3 分别指向下一个参与生成 2*x+1 和 3*x+1 的位置 int i2 = 0, i3 = 0; // 从第2个位置开始填 for (int k = 1; k < n; k++) { ll next2 = 2 * v[i2] + 1; ll next3 = 3 * v[i3] + 1; // 下一个元素取两者中的较小者 ll nxt = min(next2, next3); v[k] = nxt; // 如果两者相等,就都要推进对应指针,避免重复 if (nxt == next2) i2++; if (nxt == next3) i3++; } // 最后 v[n-1] 就是第 n 个元素 cout << v[n-1] << "\n"; } return 0; } -
0
vector数组方式:
#include <bits/stdc++.h> using namespace std; int main() { int a, n; while (cin >> a >> n) { vector<int> que; que.push_back(a); // 使用 push_back 添加初始元素 int head1 = 0, head2 = 0; while (que.size() < n) { int x = que[head1] * 2 + 1; int y = que[head2] * 3 + 1; if (x < y) { que.push_back(x); head1++; } else if (x > y) { que.push_back(y); head2++; } else { que.push_back(x); head1++; head2++; } } cout << que.back() << endl; // 输出最后一个元素 } return 0; }
- 1
信息
- ID
- 811
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 52
- 已通过
- 7
- 上传者