CodeForces1208A
不得不承认,这题猛地一看吓到我了,吓得我直接看了$B$题,要不是$B$也吓到我了我就直接做$B$了.
打打表,找一找,你会发现,这玩意三个一循环,所以就只需要算$f_0,f_1,f_2$就完了,输出$f_{n \% 3}$.
完美解决.
CodeForces1208B
由于$A$实在太水了,所以我打算这两道题放在一起.
不得不承认,这题也吓到我了,这直接导致我滚回去做$A$了.
其实也并不难,这题一般都能想到二分区间长度,然后枚举左端点,把这一部分硬拆出来判断,用桶记录就行了.
但是这题的症结在于开桶的话空间是负担不起的.
但我们发现,尽管值域很广,但是不同的数字地个数并不会超过$n$,而$n$的数量级是$10^3$级别的,所以我们直接离散化就好了.
$Code:$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 2e3 + 100 ;
int n , l , r , ans = 0x3f3f3f3f , val[N] , idx ;
bool f , mk[N] ;
struct pairs { int data , pos ; } v[N] ;
inline bool check (int d) {
for (int i = 1 ; i <= n - d + 1 ; ++ i){
f = true ; MEM ( mk , 0 ) ;
for (int j = 1 ; j < i && f ; ++ j) if ( mk[val[j]] ) f = false ;
else mk[val[j]] = true ; if ( ! f ) continue ;
for (int j= i + d ; j <= n && f ; ++ j) if ( mk[val[j]] ) f = false ;
else mk[val[j]] = true ; if ( f ) return true ;
}
return false ;
}
inline bool cmp (pairs a , pairs b) {
if ( a.data != b.data ) return a.data < b.data ;
else return a.pos < b.pos ;
}
signed main () {
n = rint () ;
rep ( i , 1 , n ) { v[i].data = rint () ; v[i].pos = i ; } r = n - 1 ;
std::sort ( v + 1 , v + n + 1 , cmp ) ; idx = 0 ;
rep ( i , 1 , n )
if ( v[i].data != v[i-1].data ) val[v[i].pos] = ++ idx ;
else val[v[i].pos] = idx ;
while ( l <= r ) {
if ( check ( mid ) ) ans = mid , r = mid - 1 ;
else l = mid + 1 ;
}
printf ("%I64d\n" , ans ) ; // I64d是因为CF只支持这玩意儿,不支持lld
return 0 ;
}