【Codeforces Global Round 1 E】Magic Stones
Codeforces round global Magic
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
```cpp d[i] = c[i+1]-c[i]; (1<=i<=n-1) change c[i]
c[i]' = c[i+1]+c[i-1]-c[i];
d[i-1] = c[i]'-c[i-1];
= c[i+1]+c[i-1]-c[i]-c[i-1] == c[i+1]-c[i] = d[i];
d[i] = c[i+1]-c[i]'
= c[i+1]-c[i+1]-c[i-1]+c[i]
= c[i] - c[i-1];
= d[i-1];
也就是说对2..n-1进行操作的话
就是把相邻的d的值交换一下
显然这样的交换能让d变成任意顺序
因此,只要c[1]==d[1]并且c[n]==d[n]
然后排序后的c和排序后的d相同的话,就ok.
这里必须要用Integer的equals方法比较才不会超时。。
直接用int的a[i]!=b[i]会超时>_<
</font>
<font color = black size = 6> 【代码】</font>
```cpp
import java.io.*;
import java.util.*;
//code start from here
/*
d[i] = c[i+1]-c[i]; (1<=i<=n-1)
change c[i]
c[i]' = c[i+1]+c[i-1]-c[i];
d[i-1] = c[i]'-c[i-1];
= c[i+1]+c[i-1]-c[i]-c[i-1] == c[i+1]-c[i] = d[i];
d[i] = c[i+1]-c[i]'
= c[i+1]-c[i+1]-c[i-1]+c[i]
= c[i] - c[i-1];
= d[i-1];
*/
public class Main {
final static int N = (int)1e5;
static InputReader in;
static PrintWriter out;
static int n;
static Integer c[],t[],d1[],d2[];
public static void main(String[] args) throws IOException{
in = new InputReader();
//out = new PrintWriter(System.out);
c = new Integer[N+10];t = new Integer[N+10];
d1 = new Integer[N+10]; d2 = new Integer[N+10];
n = in.nextInt();
for (int i = 1;i <= n;i++) c[i] = in.nextInt();
for (int i = 1;i <= n;i++) t[i] = in.nextInt();
if (!c[1].equals(t[1]) || !c[n].equals(t[n])){
System.out.println("No");
return;
}
for (int i = 1;i <= n-1;i++) d1[i] = c[i+1]-c[i];
for (int i = 1;i <= n-1;i++) d2[i] = t[i+1]-t[i];
Arrays.sort(d1, 1,n);
Arrays.sort(d2, 1,n);
for (int i = 1;i <= n-1;i++)
if (!d1[i].equals(d2[i])) {
System.out.println("No");
return;
}
System.out.println("Yes");
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader() {
br = new BufferedReader(new InputStreamReader(System.in),32768);
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
相关文章
- 【Codeforces 1327E】Count The Blocks
- 【Codeforces Global Round 7 D1】Prefix-Suffix Palindrome (Easy version)
- 【Codeforces Global Round 9 C】Element Extermination
- 【Codeforces Round #493 (Div. 2) B】Cutting
- 【Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) C】
- 【Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) B】Weakened Common Divisor
- 【Codeforces Round #452 (Div. 2) D】Shovel Sale
- 【Codeforces Round #299 (Div. 2) B】Tavas and SaDDas
- 【21.67%】【codeforces 727B】Bill Total Value
- 【codeforces 791C】Bear and Different Names
- 【codeforces 777B】Game of Credit Cards
- 【codeforces 723F】st-Spanning Tree
- Codeforces Round #256 (Div. 2) B. Suffix Structures
- Codeforces Round #437 (Div. 2, based on MemSQL Start[c]UP 3.0 - Round 2)
- Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2) 一夜回到小学生
- VP记录:Codeforces Round 857 (Div. 2) A~D