【暴力剪枝】CF1708D

柔光的暖阳◎ 2024-02-21 10:23 44阅读 0赞

[https://codeforces.com/contest/1708/problem/D][https_codeforces.com_contest_1708_problem_D]

题意

![0ec630f9d66249f5b4ddcf91021b3d13.png][]

思路

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

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

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr 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;
    }

[https_codeforces.com_contest_1708_problem_D]: https://codeforces.com/contest/1708/problem/D
[0ec630f9d66249f5b4ddcf91021b3d13.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/6dcdfa66972f4a9b8a2ddcd392096bbf.png

发表评论取消回复

表情：

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

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

相关阅读

相关 CF1214D

CF1214D 题意： > 给你一个 $ n \\times m $ 的矩阵，求最少用多少个障碍，将 $ (1,1) $ 到 $ (n,m) $ 的路径堵死...

た入场券/ 2024年04月20日 10:34/ 0 赞/ 97 阅读

相关 CF981D

CF981D 题意： > 给你n个数，要求你分成k堆。每堆的内部加和，每堆之间是相与。问最大的值。解法： > 二进制下最大的数的所有位一定是1，所...

缺乏、安全感/ 2024年04月20日 10:26/ 0 赞/ 90 阅读

相关 CF427D

CF427D > SA的奇技淫巧，其实就是板子。题意： > 给定两个字符串，求最短的满足各只出现一次的连续公共字串解析： > 一般情况下，SA...

素颜马尾好姑娘i/ 2024年04月20日 10:25/ 0 赞/ 90 阅读

相关 CF1208D

CF1208D 题意； > 给你一个数组，要求支持单点修改和单点查询解法： > 直接线段树搞一搞就没了。 CODE： includ...

系统管理员/ 2024年04月20日 10:24/ 0 赞/ 97 阅读

相关【暴力DP】CF1409 F

[Problem - F - Codeforces][] 题意： ![0b383875a1444f75b1163b33ac695a0b.png][] ![e01ceb20

骑猪看日落/ 2024年03月01日 07:49/ 0 赞/ 48 阅读

相关【暴力剪枝】CF1708D

[https://codeforces.com/contest/1708/problem/D][https_codeforces.com_contest_1708_proble

柔光的暖阳◎/ 2024年02月21日 10:23/ 0 赞/ 45 阅读

相关中位数+暴力——cf433C

/ 中位数到所有数的距离之和最小因为只能改一个数，所以我们找一个数，将其改为和其相邻的数的中位数，使答案最小先求一次原答案把每个数相邻的数用vector存下来，然

深碍√TFBOYSˉ_/ 2023年10月12日 08:22/ 0 赞/ 20 阅读

相关暴力——cf557c

//枚举高度[1,100000]，>l的全部割掉，<l的砍掉最小的 include<bits/stdc++.h> using namespace std

╰半橙微兮°/ 2023年10月12日 08:19/ 0 赞/ 20 阅读

相关暴力——cf1202C

直接去考虑细节很多，不如暴力做即在四个方向到达最远前向反方向走一步，答案肯定是从这四种情况+不多走里出的 include<bits/stdc++.h> u

谁借莪１个温暖的怀抱￠/ 2023年10月11日 09:09/ 0 赞/ 13 阅读

相关 First Blood（暴力加剪枝）

First Blood Time Limit: 1000 ms Memory Limit: 64 MB Total Submission: 79 Submissi

- 日理万妓/ 2022年08月01日 12:27/ 0 赞/ 94 阅读