CodeForces1208A

不得不承认,这题猛地一看吓到我了,吓得我直接看了\(B\)题,要不是\(B\)也吓到我了我就直接做\(B\)了.

打打表,找一找,你会发现,这玩意三个一循环,所以就只需要算\(f_0,f_1,f_2\)就完了,输出\(f_{n \% 3}\).

完美解决.

CodeForces1208B

由于\(A\)实在太水了,所以我打算这两道题放在一起.
不得不承认,这题也吓到我了,这直接导致我滚回去做\(A\)了.
其实也并不难,这题一般都能想到二分区间长度,然后枚举左端点,把这一部分硬拆出来判断,用桶记录就行了.
但是这题的症结在于开桶的话空间是负担不起的.
但我们发现,尽管值域很广,但是不同的数字地个数并不会超过\(n\),而\(n\)的数量级是\(10^3\)级别的,所以我们直接离散化就好了.

\(Code:\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back #define mid ( ( l + r ) >> 1 )   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 ; }