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 可以给你飙到
by AfterFullStop @ 2024-07-24 01:02:36
优化的话可以再
(感觉抄过来好麻烦,就直接减下来了)
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