ZR#955 折纸

悠悠 2024-04-20 10:29 1阅读 0赞

##  ##

ZR\#955 折纸

### 解法: ###

> 可以发现折纸之后被折到上面的部分实际上是没有用的，因为他和下面对应位置一定是一样的，而影响答案的只有每个位置的颜色和最底层的坐标范围。因此，我们只需要考虑最底层即可，即我们可以把折纸等效为裁纸，每次去掉较小的那一部分。  
> 用哈希维护每一列和每一行的极大回文子串，记录一下行与列的最大值相乘即可。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long const int N = 2e6 + 50; char s[N],tt[N]; string p[N]; int HL[N],WL[N],m,n; int HR[N],WR[N],t[N],f[N]; int manacher(int *p, char *ss, int Len) { int len = 0; s[0] = '('; for(int i = 1 ; i <= Len ; ++ i) { s[++ len] = '#'; s[++ len] = ss[i]; } s[++ len] = '#', s[++ len] = ')'; int mx = 0, id = 0; for(int i = 1 ; i < len ; ++ i) { if(i < mx) p[i] = min(mx - i, p[2 * id - i]); else p[i] = 1; while(s[i + p[i]] == s[i - p[i]]) ++ p[i]; if(i + p[i] > mx) mx = i + p[i], id = i; } return len; } int main() { scanf("%d%d",&n,&m); for(int i = 1 ; i < n ; i++) HL[i] = HR[i] = 1; for(int i = 1 ; i < m ; i++) WL[i] = WR[i] = 1; for(int i = 1 ; i <= n ; i++) cin >> p[i]; for(int i = 1 ; i <= n ; i++) { int len = m; for(int j = 1 ; j <= len ; j++) tt[j] = p[i][j - 1]; int Len = manacher(t, tt, m) - 3; int mx = 1; for(int j = 3 ; j <= Len ; j += 2) { if(j - t[j] + 1 <= mx) mx = j; else WL[j >> 1] = 0; } int mn = Len + 2; for(int j = Len ; j >= 3 ; j -= 2) { if(j + t[j] - 1 >= mn) mn = j; else WR[j >> 1] = 0; } } LL ansW = 0; int sum = 0; WL[0] = 1, WR[m] = 1; for(int i = 0 ; i <= m ; i++) sum += WR[i]; for(int i = 0 ; i <= m ; i++) { if(WR[i]) -- sum; if(WL[i]) ansW += sum; } swap(n, m); for(int i = 1 ; i <= n ; i++) { int len = m; for(int j = 1 ; j <= len ; j++) tt[j] = p[j][i - 1]; int Len = manacher(t, tt, m) - 3; int mx = 1; for(int j = 3 ; j <= Len ; j += 2) { if(j - t[j] + 1 <= mx) mx = j; else HL[j >> 1] = 0; } int mn = Len + 2; for(int j = Len ; j >= 3 ; j -= 2) { if(j + t[j] - 1 >= mn) mn = j; else HR[j >> 1] = 0; } } LL ansH = 0; sum = 0; HL[0] = 1, HR[m] = 1; for(int i = 0 ; i <= m ; i++) sum += HR[i]; for(int i = 0 ; i <= m ; i++) { if(HR[i]) -- sum; if(HL[i]) ansH += sum; } printf("%lld\n", ansW * ansH); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11448968.html