C求优化

学术版

Special_Tony @ 2024-07-24 00:46:01

rt,其它应该没啥问题,但是1ll<<use会爆炸,求优化QAQ

# pragma GCC optimize("Ofast,no-stack-protector")

# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

# define I return

# define AK 0

# define IOI ;

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

int t, n, sum, x, lst, use;

bool flag;

int main () {

    ios::sync_with_stdio (0);

    cin.tie (0);

    cout.tie (0);

    cin >> t;

    while (t --) {

        cin >> n >> lst, sum = use = 0, flag = 0;

        for (int i = 1; i < n; ++ i) {

            cin >> x;

            if (lst != 1 && x == 1)
                flag = 1;

            if (flag)
                continue ;

            use = ceil (log2 (max (1.0, ceil (log2 (lst) / log2 (x) * (1ll << use)))));
//          cerr << use << ' ';
            sum += use;

            lst = x;

        }

        cout << (flag ? -1 : sum) << '\n';

    }

    I AK IOI

}
/*
1
9
16 2 4 2 256 2 4 2 8
*/

by Special_Tony @ 2024-07-24 00:48:58

下了,回复记得踢我喵


by FstAutoMaton @ 2024-07-24 00:50:56

@Special_Tony 你这个题做法完全错了吧。。。


by Special_Tony @ 2024-07-24 00:51:42

@FstAutoMaton WA#5


by AfterFullStop @ 2024-07-24 00:54:13

@Special_Tony 1<<use 肯定寄了啊,use 可以给你飙到 O(n) 的。


by AfterFullStop @ 2024-07-24 01:02:36

优化的话可以再 \log 一下。

(感觉抄过来好麻烦,就直接减下来了)


by 红黑树 @ 2024-07-24 01:58:36

草,我还以为只有我一个暴力两次对数(


by Special_Tony @ 2024-07-24 08:35:54

@AfterFullStop

@Special_Tony 1<<use 肯定寄了啊,use 可以给你飙到 O(n) 的。

我知道吖,但是我不会优化QAQ


by AfterFullStop @ 2024-07-24 08:43:09

@Special_Tony

优化可以这样:

然后细说一下那个恶心的取整:

事情是这样的,我写完之后测了一下样例,发现倒数第二个样例寄了,然后我输出了一下,发现 2 被他向上取整到了 3,于是我加判了一下 eps,然后就过了。


by Special_Tony @ 2024-07-24 08:44:18

@AfterFullStop 啊啊我也倒数第二个阳历寄过


by Special_Tony @ 2024-07-24 08:47:13

@AfterFullStop eps多少比较好啊qaq


| 下一页