【暴力剪枝】CF1708D

暴力剪枝】CF1708D"/>

【暴力剪枝】CF1708D

题意

思路

这样的操作下，数列减的速度是非常快的，也就是说，易出现很多的0，0的操作没啥意义，所以我们要找到第一个 >0 的数对其后的序列进行排序，就能大大减少复杂度 

这道题告诉我们实在没思路可以猜个暴力剪枝的做法

Code：

#include <bits/stdc++.h>#define int long longconstexpr int N = 2e5 + 10;
constexpr int mod = 998244353;int n;
int a[N];void solve() {std::cin >> n;for (int i = 1; i <= n; i ++) {std::cin >> a[i];}int pos = 0;for (int i = 1; i <= n; i ++) {if (a[i]) {pos = i - 1;break;}}while(n > 1) {for (int i = std::max(pos, 1ll); i <= n; i ++) {a[i] = a[i + 1] - a[i];}n --;std::sort(a + pos, a + 1 + n);pos = std::upper_bound(a + 1, a + 1 + n, 0) - a - 1;if (pos == n - 1) break;}std::cout << a[n] << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}