Educational Codeforces Round 101 (Rated for Div. 2)D. Ceil Divisions

D. Ceil Divisions

题意

给你n个数，每次可以这样操作 ( x ≢ y , a x = ⌈ a y / a x ⌉ ) (x\not\equiv y,a_x = \lceil{a_y/a_x}\rceil) (x​≡y,ax​=⌈ay​/ax​⌉)，问你最多操作n+5次使最后变为一个2和n-1个1

思路

首先考虑时间复杂度 3 ≤ ∑ n ≤ 2 ∗ 1 0 5 3 \leq \sum n \leq 2*10^5 3≤∑n≤2∗105我们发现必须在$O(nlogn)$以为来解决这个问题，然后通过找规律我们发现要使其在n+5次操作内完成，那我们必须有一个急速降幂过程，然后我们以极限数据$2e5$为例来推，发现 2 e 5 − > ( 2 e 5 ) − > 21.147 − > 4.598 − > 2.144 − > 1.464 2e5->\sqrt(2e5)->21.147->4.598->2.144->1.464 2e5−>( ​2e5)−>21.147−>4.598−>2.144−>1.464共进行了5次的操作，那么我们猜测这个问题的解决方法就是通过开根号上取整作为分界点来处理数据的。

#include
using namespace std;
const int N = 2e5 + 100;
typedef long long LL;
//#define int long long void solve() {int n; cin >> n;vector<pair<int,int>>ans;int t = n;while (1) {if (t <= 2) break;int x = sqrt(t);if (x * x < t) ++x;for (int i = x + 1; i < t; ++i)ans.push_back({i, t});ans.push_back({t, x});ans.push_back({t, x});t = x;}cout << ans.size() << endl;for (auto it : ans) {cout << it.first << " " << it.second << endl;}
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！