求助,这种删除方法为什么会WA
查看原帖
求助,这种删除方法为什么会WA
54047
兮水XiShui丶楼主2018/8/1 22:06

我是枚举删除的位置(设为mid),然后用 1 - mid-1的位置的hash值去乘mid+1 - l 的hash值来统计删除某一位之后的hash值,但是这样只有30分,改成题解中的方式后就A了,求解为什么

下面是代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ull unsigned long long

using namespace std;

const int M = 205;
const int N = 30005;
const ull base = 233;

int n , l , s , ans;
char c[N][M];
ull hs[N][M] , p[N] , num[N];

ull cal_kid ( int mid , int sign ) {
    int hash_left = 0 , hash_right = 0;
    if ( mid == 1 ) // l = 2 r = l l-1 = 1  
     return hs[sign][l] - hs[sign][1] * p[l - 2 + 1];
    if ( mid == l ) // l = 1 r = l-1 l-1 = 0
     return hs[sign][l - 1] - hs[sign][0] * p[l - 2 + 1];
    hash_left = hs[sign][mid - 1] - hs[sign][0] * p[mid - 2 + 1];
    hash_right = hs[sign][l] - hs[sign][mid] * p[l - mid + 1 - 1];
    return hash_left * hash_right;
}

int main ( void ) {
    scanf ( "%d%d%d" , &n , &l , &s );
    p[0] = 1;
    for ( int i = 1 ; i <= l ; i++ ) 
        p[i] = p[i - 1] * base; 
    for ( int i = 1 ; i <= n ; i++ ) {
        scanf ( "%s" , c[i] + 1 );
        for ( int j = 1 ; j <= l ; j++ )
         hs[i][j] = hs[i][j - 1] * base + c[i][j];
    } 
    for ( int mid = 1 ; mid <= l ; mid++ ) {
        memset ( num , 0 , sizeof ( num ) );
        int hc = 1;
        for ( int j = 1 ; j <= n ; j++ ) 
         num[j] = cal_kid ( mid , j ); 
        sort ( num + 1 , num + 1 + n );
        for ( int j = 1 ; j <= n ; j++ )
         if ( num[j] == num[j + 1] ) 
          hc++;
         else  {
         	ans += hc * ( hc -1 ) / 2;
         	hc = 1;
         } 
        ans += hc * ( hc - 1 ) / 2;  
    }
    printf ( "%d\n" , ans ); 
    return 0;
} 
2018/8/1 22:06
加载中...