1469D - Ceil Divisions （思维）

淩亂°似流年 2021-07-16 16:32 278阅读 0赞

[题目][Link 1]

思路：首先对于1 2 3 4 . . . 2e5 我想啊，让 i=3 到 2e5-1的数全部 i/2e5 那么这些数就全为1了，1 2 1 1 1 … 1 1 2e5 ，我们这时操作次数还剩下8次(1,2,2e5没用掉)，但2e5/2 8次不够用啊，所以接着我想留出一个10来现在操作次数剩下9次，2e5/10 用掉了6次，10/2又要用掉4次，比9次多了一次.那么我想这让2e5/a 用掉5次，a/2还是用4次就可以了。将a最大化16，16/2用4次，2e5/16用5次，那不就解决了嘛。但n<=16还需特殊对待。

Code:

#include<iostream>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    
    int main()
    { 
        FAST;
        int t;cin >> t;
        while (t--)
        { 
            int n;cin >> n;
            cout << n + 5 << endl;
            if (n <= 16)
            { 
                for (int i = 3;i <= n - 1;i++) cout << i << " " << n << endl;
                for (int i = 1;i <= 8;i++)cout << n << " " << 2 << endl;
            }
            else
            { 
                for (int i = 3;i <= 15;i++)cout << i << " " << n << endl;
                for (int i = 17;i <= n - 1;i++)cout << i << " " << n << endl;
                for (int i = 1;i <= 5;i++)cout << n << " " << 16 << endl;
                for (int i = 1;i <= 4;i++)cout << 16 << " " << 2 << endl;
            }
        }
    }

[Link 1]: https://codeforc.es/problemset/problem/1469/D

发表评论取消回复

表情：

评论列表（有 0 条评论，278人围观）

还没有评论，来说两句吧...

相关阅读

相关 D1. Equalizing by Division（hard 1600）————暴力+贪心

题目连接][Link 1] /***** 该题是用最少的操作，产生k个相等的数字思路：直接暴力，因为每个数大小2e5 ， 2的18次方2e5多，所以每...

ゞ浴缸里的玫瑰/ 2024年04月18日 14:06/ 0 赞/ 55 阅读

相关【筛法】ABC170 D - Not Divisible

太久没写ABC了，不会！ [D - Not Divisible (atcoder.jp)][D - Not Divisible _atcoder.jp] 题意： ![1b

桃扇骨/ 2024年03月22日 14:35/ 0 赞/ 39 阅读

相关思维+贪心——cf1042D

/ 首先考虑从后往前计算lis，显然0的在很多情况下的贡献要大于1 如果遇上0，那么lis++，如果遇上1，那么cnt1++，并且用cnt1更新lis

一时失言乱红尘/ 2023年10月11日 09:09/ 0 赞/ 36 阅读

相关 Integer Division

Integer Division Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述判

我就是我/ 2022年08月14日 05:49/ 0 赞/ 177 阅读

相关 Division

[Division][] <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000MS

布满荆棘的人生/ 2022年08月03日 15:59/ 0 赞/ 161 阅读

相关 mysql函数ceil和ceiling

CEILING(X) 或 CEIL(X) 该函数返回的最小整数值，但不能小于X。 SELECT CEILING(3.46);4 SELECT

拼搏现实的明天。/ 2022年05月19日 05:42/ 0 赞/ 228 阅读

相关 D. Divide and Summarize(思维)

[题目][Link 1] 思路：其实想一想不难看出我们只需要将所有的情况得到的值存储起来，然后在之后的问询阶段判断是否有这个值就可以了。然后注意一下当值都相同时进行特殊判

「爱情、让人受尽委屈。」/ 2021年07月16日 18:07/ 0 赞/ 388 阅读

相关 1469D - Ceil Divisions （思维）

[题目][Link 1] 思路：首先对于1 2 3 4 . . . 2e5 我想啊，让 i=3 到 2e5-1的数全部 i/2e5 那么这些数就全为1了，1 2 1 1

淩亂°似流年/ 2021年07月16日 16:32/ 0 赞/ 279 阅读

相关 E1. Square-free division (easy version) (数论、思维)

[题目][Link 1] 思路：首先贪心的想一想，我让每一段尽可能长，则最后的段数就可能越少。再来看什么时候一个数是平方数，将一个数质因数分解 X=a^x1

末蓝、/ 2021年07月16日 15:21/ 0 赞/ 379 阅读

相关 1199D - Welfare State（思维）

[题目][Link 1] 题意：对于n个公民，我们知道其一开始的各自的金钱。现在我们有两种操作：1.直接将各个钱数小于k的公民的钱数转变为k。2.将第p个人的钱数抓变为k

我就是我/ 2021年07月16日 15:04/ 0 赞/ 489 阅读