求助

P4168 [Violet] 蒲公英

Mobius_LCA @ 2023-10-17 18:41:12

这里是代码:

#include <bits/stdc++.h>
using namespace std ; 
const int N = 40010 , T = 35 ; 
int n , m , a[N] , L , R ; 
int ssum , sum , len ;  //ssum 离散化 , sum 端点个数(原来) 
int c[N] , b[N] , rb[N] , rsum ; 
int cnt[80][80][N] , mm[80][80] , kin[80][80] , d[N] ; 
int rec[N] ; 

int Query(int l , int r ) {
    int x1 = lower_bound(rb +1 , rb + rsum + 1 , l ) - rb , 
    x2 = upper_bound(rb + 1 , rb + rsum + 1 , r) - rb - 1 ; 
    L = rb[x1] , R = rb[x2] ; 
//  cout << "x1:" << x1 << endl ; 
//  cout << L << ' ' << R << endl  ; 
    if(L >= R) { //brufe
        int nm = 0 , rkin = 0 ; 
        for ( int i = l ; i <= r ; ++i ) {
            int rf = lower_bound(d + 1 , d + ssum + 1, a[i]) - d ; 
            rec[rf] ++ ; 
            if(nm < rec[rf]) nm = rec[rf] , rkin = a[i] ; 
            else if(nm == rec[rf]) {
                if(rkin == 0 || rkin > a[i]) rkin = a[i] ; 
            }
//          cout << "nm : " << nm << endl ; 
//          cout << "rkin:" << rkin << endl ; 
        }
        for ( int i = l ; i <= r ; ++i ) {
            int rf = lower_bound(d + 1 , d + ssum + 1, a[i]) - d ; 
            rec[rf] -- ; 
        }   
        return rkin ;   
    }
//  cout << "LR" << ' ' << L << ' ' << R << endl ; 
    int ma1 = mm[x1][x2] , nm = 0 , k1 = kin[x1][x2] ; 
//  cout <<"k1" <<' ' << k1 << endl ; 
//  cout << "ma1:" << ma1 << endl ; 
    int rkin = 0 ; 
    for (int i = l ; i < L ; ++ i ) {
        int rf = lower_bound(d + 1 , d + ssum + 1 , a[i]) - d ;
//      cout << rf << endl ; 
        cnt[x1][x2][rf] ++ ; 
//      cout << cnt[x1][x2][rf] << endl ; 
            if(nm < cnt[x1][x2][rf]) cnt[x1][x2][rf] , rkin = a[i] ; 
            else if(nm == cnt[x1][x2][rf] ) {
                if(rkin == 0 || rkin > a[i]) rkin = a[i] ; 
            }
    }
    for (int i = R + 1 ; i <= r ; ++ i ) {
        int rf = lower_bound(d + 1 , d + ssum + 1 , a[i]) - d ;
        cnt[x1][x2][rf] ++ ; 
            if(nm < cnt[x1][x2][rf]) cnt[x1][x2][rf] , rkin = a[i] ; 
            else if(nm == cnt[x1][x2][rf] ) {
                if(rkin == 0 || rkin > a[i]) rkin = a[i] ; 
            }
    }
    int fim = max(ma1 , nm ) ; 
    for (int i = l ; i < L ; ++ i ) {
        int rf = lower_bound(d + 1 , d + ssum + 1 , a[i]) - d ;
        cnt[x1][x2][rf]-- ; 
    }
    for (int i = R + 1 ;  i <= r ; ++ i ) {
        int rf = lower_bound(d + 1 , d + ssum + 1 , a[i]) - d ;
        cnt[x1][x2][rf]-- ; 
    }   
    if(ma1 == nm ) {
        return min(k1 , rkin) ; 
    }
    if(fim == ma1) return k1 ; 
    else return rkin ; 
}
int main() {
    freopen("P4168_1.in","r",stdin);
    freopen("P4168_1.ans","w",stdout) ; 
    cin >> n >> m ;  len = n / T ;  
    for ( int i = 1 ; i <= n ; ++i ) cin >>a[i]  , c[i] = a[i] ; 
    sort(c + 1, c + n + 1) ; 
    for ( int i = 1 ; i <= n ; ++i ) 
        if( i == 1 || c[i] != c[i - 1] ) d[++ssum] = c[i] ; 
    for ( int i = 1 ; i <= T ; ++i ) 
        b[++sum] = (i - 1) * len + 1 , b[++sum] = i * len ; 
    if( b[sum] < n ) {
        sum++ , b[sum] = b[sum - 1] + 1 ;
        sum++ , b[sum] = n ;  
    }
    sort(b + 1 , b + sum + 1) ; 
    for ( int i = 1 ; i <= sum ; ++i ) 
        if(i == 1 || b[i] != b[i - 1] ) rb[++rsum] = b[i] ; 
//  for ( int i = 1 ; i <= rsum ; ++i ) {
//      cout << "rb" << i << ":" << rb[i] << endl ;  
//  }
    for ( int i  = 1 ; i <= rsum ; ++i ) 
        for (int j = i ; j <= rsum ; ++j ) {
            int lmax = 0 , lkind = 0 ; 
            for( int k = rb[i] ; k <= rb[j] ; ++k ) {
                int rf = lower_bound(d + 1 , d + ssum + 1 , a[k]) - d ; 
                cnt[i][j][rf] ++ ; 
            if(lmax < cnt[i][j][rf]) lmax = cnt[i][j][rf] , lkind = a[k] ; 
            else if(lmax == cnt[i][j][rf] ) {
                if(lkind == 0 || lkind > a[k]) lkind = a[k] ; 
            }
            }  
            mm[i][j] = lmax , kin[i][j] = lkind ; 
        }
    int lq = 0 , l0 , r0 ; 
    for( int i = 1 ; i <= m ; ++i ) {
        cin >> l0 >> r0 ; 
        int l = (l0 + lq  - 1) % n + 1  ; 
        int r = (r0 + lq - 1 ) % n  + 1 ; 
//      int l = l0 , r = r0 ; 
        if( l > r) swap( l , r) ; 
//      cout << "lr:" << l << ' ' << r << endl ; 
        int res = Query( l , r ) ;
        cout << res << endl ; 
        lq = res ;  
    }
    return 0 ; 
}

目前调了 20 多次 , 一直 WA 0 pts,大样例第一个对了一些,真的找不出来问题了,救救孩子【哭】


by Mobius_LCA @ 2023-10-17 18:42:41

P.S. 这个做法是 lyd 书上的第一个做法


|