CodeForces1208A

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

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

完美解决.

CodeForces1208B

由于\(A\)实在太水了,所以我打算这两道题放在一起.

不得不承认,这题也吓到我了,这直接导致我滚回去做\(A\)了.

其实也并不难,这题一般都能想到二分区间长度,然后枚举左端点,把这一部分硬拆出来判断,用桶记录就行了.

但是这题的症结在于开桶的话空间是负担不起的.

但我们发现,尽管值域很广,但是不同的数字地个数并不会超过\(n\),而\(n\)的数量级是\(10^3\)级别的,所以我们直接离散化就好了.

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #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
                
                 #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 ;}