首页 > 其他分享 >[ABC334C] Socks 2 题解

[ABC334C] Socks 2 题解

时间:2023-12-29 23:34:10浏览次数:33  
标签:pre ... Min 题解 sum args Socks ans ABC334C

题目传送门

一道贪心题。

数量为 \(2\) 的袜子不用考虑,因为最好的情况就是相同颜色的配一对。

我们只需要考虑那 \(k\) 种只有 \(1\) 个的袜子,如果 \(k\) 为偶数,答案为相邻两数之差之和;如果 \(k\) 为奇数,就枚举删掉一个数,让剩下的数按照 \(k\) 为偶数的情况做,最后取一个最小值。这个过程可以使用前缀和维护。

Code

#include <bits/stdc++.h>

const long long IMX = 1ll << 30;
const long long LMX = 1ll << 60;
const long long MOD = 998244353;

using ll = long long;
using i128 = __int128;
using ld = long double;
using f128 = __float128;

namespace xvl_ { 
	#define SP(n, x) std :: setprecision(n) << std :: fixed << x
	#define REP(i, l, r) for (auto i = (l); i <= (r); i++)
	#define PER(i, r, l) for (auto i = (r); i >= (l); i--)
	#define DEBUG(x) std :: cerr << #x << " = " << x << '\n'
	#define SZ(x) (x.size())
	#define fst first
	#define snd second
	template <typename T> T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
	template <typename T> T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;
ll n, k, ans;
ll a[200005], sum[200005], pre[200005];
int main() {
	// freopen("InName.in", "r", stdin);
	// freopen("OutName.out", "w", stdout);
	ios :: sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> n >> k;
	REP(i, 1, k) {
		cin >> a[i];
		if (i & 1) sum[i] = sum[i - 1] - a[i];
		else sum[i] = sum[i - 1] + a[i];
	}
	PER(i, k, 1) {
		if (i & 1) pre[i] = pre[i + 1] - a[i];
		else pre[i] = pre[i + 1] + a[i];
	}
	if (k & 1) {
		ans = LMX;
		REP(i, 1, k) ans = Min(ans, sum[i - 1] - pre[i + 1]);
	}
	else {
		for (int i = 2; i <= n; i += 2) ans += a[i] - a[i - 1];
	}
	cout << ans;
	return 0;
}

标签:pre,...,Min,题解,sum,args,Socks,ans,ABC334C
From: https://www.cnblogs.com/xvl-/p/17935869.html

相关文章

  • [ABC334E] Christmas Color Grid 1 题解
    题目传送门一道dfs题。先统计出绿连通块数量,然后对于每个红色方块统计涂成绿色方块后会变成多少个连通块。正常涂成绿色后应该会增加一个大小为\(1\)的绿连通块,但若是有不同的绿连通块与其相邻,答案又会减少\(1\)。Code#include<bits/stdc++.h>constlonglongIMX=1......
  • CF1917F Construct Tree 题解
    Description给你一个数组\(l_1,l_2,\dots.l_n\)和一个数字\(d\)。问你是否能够构造一棵树满足以下条件:这棵树有\(n+1\)个点。第\(i\)条边的长度是\(l_i\)。树的直径是\(d\)。只需要判断是否有解即可。\(2\len\le2000,1\led\le2000,1\lel_i\led\)。Solutio......
  • 【题解】BZOJ 4403序列统计
    tg.BZOJ4403序列统计pj.BZOJ4403序列统计没啥用的题解\(QWQ\)——无脑思考首先要想怎么求单调不上升序列的个数,因为可能会有重复的数,所以不能直接用排列组合。那这道题怎么打呀?我不知道啊\(\dots\)\((~:\)因为原来是单调不下降序列,将第\(i\)位上的数加\(i\),于是......
  • CF1806F GCD Master 题解
    题目链接EasyversionHardversion题目解法参考DeaphetS的题解很有意思的题,感觉\(F1\)不到\(*2900\),\(F2\)超过\(*2900\)F1简化题目中的操作:把\(n\)个数放到\(n-k\)组中,求\(\max(\sum\)每组\(a_i\)的\(\gcd)\)首先考虑所有数互不相同的情况结论1:把\(k+......
  • [CF30E] Tricky and Clever Password 题解
    [CF30E]TrickyandCleverPassword题解注意到一个合法字符串首尾相同,考虑用S的反转和S跑KMP。对于只有一个串,暴力manacher即可。匹配到某一位置\((i,j)\)时,查询区间最长的奇回文串长度,用二分+ST表解决,因为回文串不能超过区间长度。//Problem:TrickyandCle......
  • P9994 [Ynoi Easy Round 2024] TEST_132 题解
    题解怎么都是用暴力日过去的啊。思路考虑根号分治,设阈值为\(B\)。对于第二维出现次数超过\(B\)的,我们可以在修改时暴力更改,这部分复杂度为\(O(\frac{nm}{B})\)。对于第二维出现次数小于\(B\)的,我们可以在修改是打标记,查询时遍历一遍,这部分的复杂度为\(O(mb)\)。大多数......
  • P9995 [Ynoi2000] rspcn 题解
    思路比较典的ODT题目。发现排序是一个非常有性质的操作。它对区间的更改与颜色段均摊差不多。那么我们可以想到用ODT来维护这一整个序列。具体的,区间排序操作可以用ODT维护每次排序产生的段,每段用线段树维护排序后的结果。每次修改就可以进行线段树的分裂与合并。如......
  • P9991 [Ynoi Easy Round 2023] TEST_107 题解
    思路题目即要求删除区间中的一个或多个颜色。考虑假如枚举删除颜色\(k\)。那么在\(l,r\)中的答案为:\[\max_{i=1}^{m+1}a_i-a_{i-1}\]其中\(a_i\)为颜色\(k\)在\(l\simr\)中的出现位置,\(a_{0}=l,a_{m+1}=r\)。可以分类讨论。答案为\(a_1-l\),那么只需要维护\(......
  • AT_abc020_c 题解
    链接(atcoder)链接(luogu)简单算法组合(?算法一爆搜,时间复杂度\(O(2^{n\timesm}\timest)\),不能通过此题。算法二考虑二分\(t\),然后暴搜,时间复杂度\(O(2^{n\timesm}\timeslog2(t))\),不能通过此题。算法三考虑二分\(t\),然后暴记忆化搜索,时间复杂度\(O(n\timesm......
  • CF1234F 题解
    blog。小清新题,下文\(V=20\)即值域。反转操作,本质就是选两个不相交连续段拼起来。显然合法的最终串长度一定\(\leV\)。将这些合法串预处理出来,那么每个串都对应一个「字母集合」。随便DP一下,求出所有集合中,的最大的合法「字母集合」大小。\(dp_{\smallU}\)就是只选一......