3 条题解

  • 0
    @ 2025-7-19 20:51:46

    超时代码:

    #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
      @ 2025-7-19 20:40:53

      丑数双指针:

      #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
        @ 2024-8-25 11:04:15

        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
        上传者