警示,如果你 WA/MLE
查看原帖
警示,如果你 WA/MLE
507348
__vector__楼主2023/10/4 16:08

这虽然说的比较多,但不是讨论区题解。

对于 WA。

  • 注意是否满足,对于值相同的括号,左括号在前面。

  • 注意,如果你用的是将所有能使某些点的值相等的 K=xyK = \frac{x}{y} 求出来并排序,并且做法和第一篇题解相同(即按照 (a⋅xy,b)(a\cdot\frac{x}{y},b) 排序,并设 K=xyK = \frac{x}{y}。
    设从小到大排序后第 ii 位是 kik_i,若 K=ki=fK = k_i = f 等于某个定值时,三元组 a,b,c,d,e,⋯a,b,c,d,e,\cdots 的值相等,则按照第一条将这些数按照值相等进行贪心修改。但是按照第一条修改后,注意 KK 一旦超过 x/yx/y,本次修改即不再有效(因为 a,b,c,d,e,⋯a,b,c,d,e,\cdots 值不再一定仍然相等),应当进行还原,然后以 ki+1>K>xyk_{i+1} > K > \frac{x}{y} 重新修改,当然如果此时有括号的 a,ba,b 完全相等,仍然适用第一条。

  • 注意,如果你开了很多数组,并且运行时间很长(接近 TLE)
    我的解决方案是把局部变量换成全局变量(优化 2s),把 int 换成 short(空间变为原来 12)\frac{1}{2}),以上均为实测数据。

另外附上一些 testcase,由于我 WA 了 16 发,靠着对拍出来的数据改对,就发出来。

Testcase1:

  • input:
1
1
7 6 (
13 7 )
  • output:
YES

Testcase2:

  • input:
1
1
3 8 )
10 8 (
  • output:
NO

Testcase3:

  • input:
1
4
16 5 (
12 3 (
19 6 )
4 10 )
3 10 )
19 11 (
19 7 )
7 14 (
  • output:
NO

Testcase4

  • input:
1
2
2 5 )
4 3 )
4 4 (
2 5 (
  • output:
NO  

Testcase5

  • Input:
1
2
4 1 )
1 4 (
5 3 )
5 3 (  
  • Output:
YES

Testcase6

Input:

1
2
2 4 )
6 2 (
4 4 )
2 5 (

output:

YES

Testcase7

Input:

1
3
2 2 (
1 6 (
1 2 )
2 1 (
3 1 )
6 6 )  

Output:

YES  

Testcase9

input:

1
4
2 6 (
5 3 (
3 5 )
3 5 (
7 2 )
3 2 )
6 3 )
4 4 (

output:

YES  
2023/10/4 16:08
加载中...