CF1110E Magic Stones

川长思鸟来 2021-12-20 10:29 234阅读 0赞

[CF1110E Magic Stones][]

> 给定长度为 \\(n\\) 的两个数组 \\(c,\\ t\\)
> 
> 一次操作可以选择 \\(1<i<n\\) ，使 \\(c\_i\\) 变为 \\(c\_i'=c\_\{i+1\}+c\_\{i-1\}-c\_i\\)
> 
> 能否做若干次操作使得 \\(c\_i=t\_i(1\\leq i\\leq n)\\)
> 
> \\(1<n\\leq10^5,\\ c\_i,\\ t\_i\\in\[0,\\ 2\\times10^9\]\\)

差分

--------------------

令 \\(c\\) 的差分数组为 \\(d\\)

一次操作后 \\(d\_i=c\_\{i+1\}-c\_i,\\ d\_\{i+1\}=c\_i-c\_\{i-1\}\\) ，可以发现这就是交换了 \\(d\_i,\\ d\_\{i+1\}\\)

因此再将 \\(t\\) 差分，比较 \\(d\\) 在 \\(\[2,\\ n\]\\) 中的每个数是否都在 \\(t\\) 的差分数组中出现过，出现过则为 Yes

注意要特判 \\(c\_1=t\_1,\\ c\_n=t\_n\\)

时间复杂度 \\(O(n\\log n)\\)

代码

#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; int n, c[maxn], d[maxn], t[maxn]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", c + i); } for (int i = 1; i <= n; i++) { scanf("%d", t + i); } if (c[1] != t[1] || c[n] != t[n]) { return puts("No"), 0; } for (int i = n; i; i--) { d[i] = c[i] - c[i - 1]; t[i] -= t[i - 1]; } sort(d + 2, d + n + 1); sort(t + 2, t + n + 1); for (int i = 2; i <= n; i++) { if (d[i] != t[i]) { return puts("No"), 0; } } puts("Yes"); return 0; }

转载于:https://www.cnblogs.com/Juanzhang/p/10986179.html

[CF1110E Magic Stones]: http://codeforces.com/problemset/problem/1110/E

发表评论取消回复

表情：

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

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

相关阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 88 阅读

相关【构造】CF1734 E

[Problem - 1734E - Codeforces][] 题意： ![434e61d374814555abe1a965962475f0.png][] 思路： !

超、凢脫俗/ 2024年03月23日 22:45/ 0 赞/ 76 阅读

相关 CF891E Lust

CF891E Lust -------------------- 鸽子更博了 Orz Itst 神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去

迈不过友情╰/ 2023年08月17日 17:29/ 0 赞/ 134 阅读

相关 CF1110D Jongmah

题意给出\\(n\\)个在\\(1\\)到\\(m\\)范围内的数\\(a\_i\\)，定义一个三元组为\\((x,x,x)\\)或者\\((x,x+1,x+2)\\)

深藏阁楼爱情的钟/ 2022年01月12日 09:29/ 0 赞/ 222 阅读

相关 CF1110G Tree-Tac-Toe（博弈论）

题面 [传送门][Link 1] 题解博弈论的前提是双方都是绝顶聪明的人所以这种题目显然不是我应该做的 [题解][Link 2] //minam

一时失言乱红尘/ 2021年12月23日 05:43/ 0 赞/ 267 阅读

相关 CF1163E Magical Permutation

题意：给定集合，求一个最大的x，使得存在一个0 ~ 2x \- 1的排列，满足每相邻的两个数的异或值都在S中出现过。Si <= 2e5 解：若有a，b，c，令S1 = a ^

亦凉/ 2021年12月22日 16:45/ 0 赞/ 188 阅读

相关 [CF1111E]Tree

题目大意：给一棵$n(n\\leqslant10^5)$个点的树，有$q(q\\leqslant10^5)$次询问，每次询问给出$k,m,r$表示把以下$k$个点分成不超过$m

素颜马尾好姑娘i/ 2021年12月22日 04:15/ 0 赞/ 226 阅读

相关 CF1110E Magic Stones

[CF1110E Magic Stones][] > 给定长度为 \\(n\\) 的两个数组 \\(c,\\ t\\) > > 一次操作可以选择 \\(1<i<n\\) ，

川长思鸟来/ 2021年12月20日 10:29/ 0 赞/ 235 阅读

相关 CF 166E Tetrahedron

E. Tetrahedron time limit per test 2 seconds memory limit per test 256 megabytes in

蔚落/ 2021年12月19日 14:35/ 0 赞/ 224 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 288 阅读