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

题目链接

链接

翻译

定义一个数组 \(a_i = i\)

你每次可以选择两个下标 \(i\) 和 \(j\)，让你用 \(a_i\) 去除 \(a_j\) (向上取整)。

希望最后 \(n\) 个数字中剩下 \(n-1\) 个 \(1\) 以及 \(1\) 个 \(2\)。

且操作的次数不能超过 \(n+5\) 次。

题解

思路是这样的，对于 \(1\) 的产生，只需用 \(i\) 去除 \(i+1\) 即可。

看样子我们只需要进行 \((i,i+1)\) 就能完成这个任务，但是有一个问题，最大的 \(n\) 没有 \(n+1\) 让他进行除了。

想法是留一个比较小的数字 \(x\)，让 \(n\) 一直去除 \(x\)。

\(x\) 为 \(2\) 的话，太小了，要除的次数太多了。

所以就一直试这个数字 \(x\)，发现 \(x=64\) 时是合适的。

那么就用 \((i,i+1)\) 这样的操作把除了 \(2,64,n\) 这三个数字之外的数字都变成 \(1\)。

然后用 \(n\) 不断除 \(64\),因为 \(64^3\) 就大于 \(2*10^5\) 了，所以只需三次操作。

而 \(64\) 变成 \(1\) 则需要除 \(2\) 六次。

再加上 \((i,i+1)\) 的 \(3..63\) 以及 \(65..n-1\) 的 \(n-4\) 次。

那么最多的操作次数就为 \(n-4+6+3=n+5\) 次操作。

对于 \(n\) 小于等于 \(64\) 的情况，就直接保留 \(n\) 和 \(2\) ，然后用 \(n\) 除 \(2\) 就行了。

代码

#include 
#define LL long long
using namespace std;const int N = 2e5;int T, n,tot;
int x[2*N + 10], y[2*N + 10];void addOpe(int i, int j) {x[++tot] = i;y[tot] = j;
}void outAnswer() {cout << tot << endl;for (int i = 1; i <= tot; i++) {cout << x[i] << " " << y[i] << endl;}
}int main() {#ifdef LOCAL_DEFINEfreopen("in.txt", "r", stdin);#endif // LOCAL_DEFINEios::sync_with_stdio(0), cin.tie(0);cin >> T;while(T--){tot = 0;cin >> n;if (n <= 64) {for (int i = 3; i <= n - 1; i++) {addOpe(i, i + 1);}//a[3..n-1]=1int an = n;while (an != 1) {addOpe(n, 2);an = ceil(1.0 * an / 2.0);}}else {const int mid = 64;//n>100for (int i = 3; i <= mid-1; i++) {addOpe(i, i + 1);}//a[3..mid-1] = 1for (int i = mid+1; i <= n - 1; i++) {addOpe(i, i + 1);}//a[mid+1..n-1]=1int an = n;while (an != 1) {addOpe(n, mid);an = ceil(1.0 * an / mid);}int amid = mid;while (amid != 1) {addOpe(mid, 2);amid = ceil(1.0 * amid / 2);}}outAnswer();}return 0;
}

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