【NOIP模拟】Grid(字符串哈希)

时间:2021-10-10 01:17:26

题目背景

SOURCE:NOIP2016-RZZ-1 T3

题目描述

有一个 2×N 的矩阵,矩阵的每个位置上都是一个英文小写字符。

现在需要从某一个位置开始,每次可以移动到一个没有到过的相邻位置,即从 (i,j) 可以移动到 (i-1,j)(i+1,j)(i,j-1)(i,j+1) (要求该位置在矩阵上且之前没有到过)。

从选取的起点开始,经过 2N-1 次移动后,将会走过矩阵的每一个位置,将移动经过的格子依次取出来就得到了一个长度为 2N 的串。

可以任意选择起点和终点,任意选择移动方案,求能得到多少种不同的串。

输入格式

输入第一行,一个正整数 N 。
接下来两行,每行一个由英文小写字符组成的字符串,描述这个矩阵。

输出格式

输出一行一个整数,表示能得到的串的总数。

样例数据 1

输入



a

输出

1

样例数据 2

输入


dab 
abd

输出

8

样例数据 3

输入


ababa 
babab

输出

2

备注

【样例2说明】

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAJ0AAABECAYAAACbFzcxAAAM5ElEQVR4nO2dC3BU1RnH//e19+472bwgDxJCxCAGWgQqBhTFR1sstlq1Wjutthar7VQ7dkZGp1VrhXE6jmhVaqkzPmpRsTV2VFSsoCkPEwgxCGN4k0BCyGPDPrKP++g5d0MMbVQI7t096f0Nw97dDeT77vnOd75zzne+yxkE2NhYCJ9pAWz+/xCHvxkYGIDt+Gy+bDiOg6Io5itlyOii0ShqamoQDAahqQmAUePjeAG8IMLQdehaMtPijBpekIguPNFBJbpomRZndBAjE0QJPp8fW7ZsQSAQMD8eMjrq4To7O03jg+g0/wFzUJGTRH5DTb13uMh1RiUaHVSPRHDwmjSR5GBTD0MH1DCxqQHoxAkc54ThVSQRHi97ce3jLVC8XrDWwRweoHVtHdY/ehMmzvkOLr5rJRKRTEt16lA91i77KfZteAUX/OIpTL74CiTCmZbq1CADDuLhMFbdVkPsKjE0tFLEE3/UMD2cK6cIil+Brlos6WlC+gtkd655LTgUuIk7Fx0ZFmoUUD1EIr95TfQx9ZAyLNQpwhPLEkT3iCOmOMLPmzGdlmTP6GgIdzyOozEdvWQxrKMyG4PDEdWHRT3olMCcG4yAvWRiYzm20dlYjm10NpaTOaPj2FyVGQtwfGbv/YgTifRDokzdgE4sj7Mtz2LIfVdTqxSZuvfWezrq4fQIQrvewu6N6xGzPZ51kPts9Ldg33sv4mhnNww+tQ5tNdYZHTe4diPBXCwMfrwKW15+FKEYMqP5KKFD03E96CtLHYbKrvXUo/nlB3Do0GFwyqAegrV6WDO8Um9GBtNE6BhUMqwqYsx07Rp1cwxt79CGMZJxxGNh6JpBjM4JyekGzzOyVU1l5B1IJoiVIY5kuA/xsE4+chM9lJR+FuiRfqOjnkGPoq/5OTT89REc7jVQMuMyuLRe0miFzDg5TjCgBXfjwDuPoHnt6whHVDgD5+LMq36NqvNmwSXwNEzNfjgRgqih+98rUP96Izp3d0CpugrTrvstKs4cb26FGvoX/zenQ3qHV2JRgqDh2M5VWP/g7ejoC2Bi7XwY+5/FzvfeJO5eZGZ4kpQBHHpjGTa88Dz4kqsx87rb4RFb0LByCXZs3QPBmWkJTw46wnD8ERyoX42wew6q5i9EfP9qvL/sThxu6yKKpj/aSaun44gX18Kd6NzwFHqVcsy+YzWm1uQisncB+KXXo1NX2RiWaCsQWbUBAeOn34rqW+5CcX4CvsQn6Fv1NiI9fdAHg/JsV4dmE+mahvx592PeDxcjkMNh4hn3Yc2K5di7/SaMK10AOc3eLr1GR1pBjR5E8OB2KBX3orJmPHHtgK/0fJTPWYjOBkZSJ4glJRNulHzrDvDN76L91bvR2rMNva0tiOiT4ZAFcNlubUPoxPAqUD7rQuQUOUnoA+SfOQey+ykkBkisqqcmHOkkvTEdMTotEUWkjwdf5IEwGHDTpETd7EqutP76Lw3iscWBXdj6jyXY/v4muIqqMG7mlagIyEg2dEGPZWjtYdSQyY+USlsxm4GmsKTb0oaR1t9EFZJc5QiUVCDeXo/eoGbqlgx1oX9/S7p//ZcGXRqJdbXiaHMDXGctxkUPrMH5N9yC4uJJMMIDgwutmZbyZCGyYieO7t6JWITamoFoezPUgRhkxW22T7qddlo9HTU60VOAgq/WItm4GhuffQyzL5qOnk2Po7lpP5wlBhuNZS41OMkwOoB4bwvpMAeR6HkD29b+HaGQm8R0BxEKT4Ob56GleeZ3uphxpxHH3hfvht/DobQ0hJ1P/BFRfAPlNdOgyOT7eHplSO/wShpAl3worF2COe1d2Lz2QfxrswSJKJZXdQ75rsBcmMx29CQgl87ApLlXoPvl11C/9DJwrkrkn3E5SsUP0LG1DntmzsWMaQFosUxL+wUIXsj+YvjEGHbX/QqtyRjUWA1m3nY/SssKyTDEuKejGCpH9JyA6u+vRPH8HYiS+EcJVMDjd5MeJ0IS078udNrQhETkoWzRcgRm/RLhvjAc+USHvDwYkR7E4wLk3Bwk0uwhThd6n4XiRfj67y4GnfnEu9vIEBuHXDQJnkCAhq7QLWgLS3YkqLK8Mxe5VbXIweCWy+Cwykp2Mp0AcaIP3glfgads2LaRUgqaWE51ZGL5R3BA8ady+BVvLnxGag5hym9R57csy8RUivv0mkVMHegFx64OZoLP8I7OfXp4ziqsTW1iwROcDGNFD0oGdGFjzcJmTGEbnY3l2EZnYzkjxnS86DCT+5hYuB1GKiExpRKtA0LfC4wdUqaY955P+QOqD4t60F0c/jNOuv+X0aWy+GL9XWR25mVmOeM4GpE3EelPXSdiiPbRJMUMCzUKqB5UfgrVx9QjlGGhThFqdIlweHCt6cTvuONFESORCMrKytDXF4Qou5jzciYcXQ7QoCVjgx5CzrREo8NMlIibFZsESSENKDA5Y6Yiq7Eo/H4f9uzZg7y8PPPzz1gyoekvDFqdMfSXmTfGbK09A8NkJ3owkZI8EiPLfYLRack4eNmDq8dA1aaKry0aE1Wb5v7sSearNlG7Go5dtSkLsas2MYRdtSl7sKs22WQVttHZWI5tdDaWYxvdKcCN4borFp7LsY3u5KHnRXXozK6ZfQ6GnqrkZBG20Z0MtDSG2okjjatxoLkJqsDYicPPg+7i9DVh7/pX0RPsh2GBbhmp2kT35HmGzN2s1BTfh71vP4SP69+F5hhWtYkhPYZDqy8cbw+jrwHb/nYvDu1rN8uHpdvqrKvaZGhIhEJQk0kSF8kQnW6IDoGdtG9OhKZKZHhNQk+GMdAbgy4okFweCAJb6etmybBYBMnYADiHGwJvQEtyMMgQa4UHt6RqExLH0N34NLa9+jQ6OrpJD6tE+YKbcdbl1yPgl9g40EIUERQZsbZ6bHtsEw5t3IyErxrV312KKfPOhVviLTlJdbpQD6d2fICWl5Zhx4eNUCZegsopLiR1P+k81mzfpH1wECQDkf112PSHe3Ckfwpqrl6CyppctNbdgw/q1hBvwcqMUIAoxxDc/R7aDqgou+QHyHW1YdsTt+KjtRugO7M/zjNrDce2o+HhW9C0vhF5s69BkWcbdrz2DKLBIGkra/ba0l7LhI47RlyHu+h8VP58BSZPBqK7ShDeeQN6O9rp2V6wkoCkxY9BLL0U5/xkJSZP9SP6SS3WPfwjHGiqQ9UFc0kDEi+SzVuHpD2ONb2AA22tmHDNCzjvikVwCt0IPHkZNr8TgWbRzDy9RkePuyV5uCctxNSbRLRvXYaNb7Wiv20jjvYo8J4tMzR9VqElAsivnIuSqQVmf/JPmA5v8UR0x/qzf2/UXGM0cGzf20jIl6BixoXw5pLunixBxbwb8NGHq6Cr1pwWT6/R0VmfFkbXluVYs+LPJCZyYxxx6eNmT4DIPYtQPNsHpOFQLyCT+YTLjIsMupfNC+RaBDMZllwckV7SeTg3JEeqvBlNX9NIjzEMhdilNTU+0upoUrOkILo/WgdNOhvn3duAixb/BtUzF0CIqmZyIhvxHEUiE6DDCHVuQbBdBU/Cn3j3Lgx0t0OSfUykHhmGjNyKmRBDO9B9uB0Jmi9pqOjf2wQ1FoZVhWUsmL1KpFfRhPlWBPfvQE/wKPa89XscPKxCyT2A3p4ECnNYeJ6pAd4hIbTpeTQ9Uw1j0Sx0vnIf9u3OwZSbv41AHulg2ZwwSu+vziF36nx48/6JplXL4BQXwxetx4Y31yIaH0dmr9Z4gPSWCiM9SXDlY3zt91DccBda/nQtPnb4oUyYhao5Mva1voGtG6/ENxdON4tEZ/XSCSdDchbDmdOB0K6/4N0HlpOJhRfll96HaQtqIcRokZ3sht5fseJa1F7fhnXPPYHGR9eRIVWFv7gcbr2ceGtrtlrSPpHQdBGeKTdi/tIL0X/4COAugKdoAiQjhhn9/eC8pebpp2yG1vpQlWpM//FLqLlRgxbuQ/hoF4Tc8fAUlkF28CQuyrSUJwHt2CRMKJh7JxZWLcSx3l5w7jL4C/KJrfFmzM0lxkCpMFNRzgGlYDLkvMmfPhPMcMHhDaRmuAwsqtLZg+T2pZ4Z4c2Fa1zlUDzK1FkS2h6CBHfpNLhKMNQeHJcqrDM2niNBOV4pyKxSzkD49hkY5kxv8A3LlZt080/G2sPaZTJWrW0kxoIuGdKBnbVZmzGDbXQ2lmMbnY3l2FWbshC7ahND2FWbsoeTrtpUVFRIXqP0MTdsPubcfB5rIvXgB/pWdrM5y6R6xAf31HgJnMTCNuH/YppWMgqnU8HBg23Iz883Px/ydNTICguLECS9KlUOgEEtQQ1NJkOSJ/X8sWzf6vgceMVHhljBLCthMLF6PjKCOwc+vx/8sEMxQ56OvgSDQXbLa9lkLdSh5eTkDI2eQ0ZnY2MV9pKJjeX8B8rPEzto6qETAAAAAElFTkSuQmCC" alt="" />

能得到的字符串有:abdbad, adabdb, badabd, bdbada, dababd, dabdba, dbabad, dbadab。

【数据规模与约定】

对于 20% 的数据,N≤5。
对于 60% 的数据,N≤50。
对于 100% 的数据,N≤600。

【题目分析】

没怎么做过字符串哈希的题目,这次就当是预习了。

因为题目中要求不能走已经走过的地方,并且要将整个矩阵走完,那么整个问题就有套路了。

走法都是固定的:

从某一点出发,向左或向右走到头,再拐回到同一列,然后从下一列开始可以选择走若干个蛇形(可以是$0$),然后迂回。

如下图所示:

【NOIP模拟】Grid(字符串哈希)

$........$

当然方向不止这几种,哈希时进行$4$次反转即可。

下面来看看哈希:

整个图形可以看成三部分:左边迂回的部分,中间蛇形的部分,右边迂回的部分。

我们可以将左边迂回部分的哈希值预处理出来,然后枚举右边迂回的部分,每次拼接一个蛇形,再拼接上左边的部分。

注意在将右边和蛇形与左边拼接时,因为已经预处理出了左边,所以只需将右边加蛇形的哈希值乘上$Powh[2 * (j - 1)]$再加上左边的哈希值(j的含义看代码,具体为什么乘以可以试着写写没有预处理时的计算式子)。

【CODE】

  下面是单哈希的代码。

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std; const int h = , H = ;
int n;
char s[][];
unsigned long long num[];
unsigned long long l[][];
unsigned long long Powh[];
unsigned long long now;
int fst[], nxt[], tot; inline void insert(unsigned long long x){
int i, y = x % H;
for(i = fst[y]; i; i = nxt[i])
if(num[i] == x) return;
num[++tot] = x;
nxt[tot] = fst[y];
fst[y] = tot;
} int main(){
int i, j;
for(Powh[] = i = ; i <= ; i++)
Powh[i] = Powh[i - ] * h;
scanf("%d", &n);
scanf("%s", s[] + );
scanf("%s", s[] + );
tot = ;
for(int T = ; T <= ; T++){
for(i = ; i <= n; i++){
l[][i] = l[][i] = ;
for(j = i; j >= ; j--) l[][i] = l[][i] * h + s[][j];
for(j = ; j <= i; j++) l[][i] = l[][i] * h + s[][j];
for(j = i; j >= ; j--) l[][i] = l[][i] * h + s[][j];
for(j = ; j <= i; j++) l[][i] = l[][i] * h + s[][j];
}
int k;
for(i = ; i <= n; i++){
now = ;
for(j = i; j <= n; j++) now = now * h + s[][j];
for(j = n; j >= i; j--) now = now * h + s[][j];
k = ;
for(j = i; j >= ; j--){
insert(l[k][j - ] + now * Powh[ * (j - )]);
now = now * h + s[k][j - ];
k = - k;
now = now * h + s[k][j - ];
}
} for(i = ; i <= n; i++) swap(s[][i], s[][i]);
if(T == ){
for(i = ; i <= n / ; i++){
swap(s[][n - i + ] , s[][i]);
swap(s[][n - i + ] , s[][i]);
}
}
}
cout<<tot<<endl;
return ;
}

【NOIP模拟】Grid(字符串哈希)的更多相关文章

  1. 【HHHOJ】NOIP模拟赛 玖 解题报告

    点此进入比赛 得分: \(100+20+100=220\)(还不错) 排名: \(Rank\ 16\) \(Rating\):\(+20\) \(T1\):[HHHOJ263]「NOIP模拟赛 玖」三 ...

  2. NOIP模拟赛20161022

    NOIP模拟赛2016-10-22 题目名 东风谷早苗 西行寺幽幽子 琪露诺 上白泽慧音 源文件 robot.cpp/c/pas spring.cpp/c/pas iceroad.cpp/c/pas ...

  3. cf&lowbar;514C&lpar;字符串哈希&rpar;

    题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=121897#problem/G Watto and Mechanism Time ...

  4. NOIP模拟赛-2018&period;11&period;5

    NOIP模拟赛 好像最近每天都会有模拟赛了.今天从高二逃考试跑到高一机房,然而高一也要考试,这回好像没有拒绝的理由了. 今天的模拟赛好像很有技术含量的感觉. T1:xgy断句. 好诡异的题目,首先给出 ...

  5. 2018&period;08&period;22 NOIP模拟 string(模拟)

    string [描述] 给定两个字符串 s,t,其中 s 只包含小写字母以及*,t 只包含小写字母. 你可以进行任意多次操作,每次选择 s 中的一个*,将它修改为任意多个(可以是 0 个)它的前一个字 ...

  6. NOIP模拟题汇总(加厚版)

    \(NOIP\)模拟题汇总(加厚版) T1 string 描述 有一个仅由 '0' 和 '1' 组成的字符串 \(A\),可以对其执行下列两个操作: 删除 \(A\)中的第一个字符: 若 \(A\)中 ...

  7. ELFhash - 优秀的字符串哈希算法

    ELFhash - 优秀的字符串哈希算法 2016年10月29日 22:12:37 阅读数:6440更多 个人分类: 算法杂论算法精讲数据结构 所属专栏: 算法与数据结构   版权声明:本文为博主原创 ...

  8. 2014-10-31 NOIP模拟赛

        10.30 NOIp  模拟赛   时间 空间 测试点 评测方式 挖掘机(dig.*) 1s 256M 10 传统 黑红树(brtree.*) 2s 256M 10 传统 藏宝图(treas. ...

  9. 8&period;1 NOIP模拟11

    8.1 NOIP模拟 11 今天上午返校之后,颓了一会,然后下午就开始考试,中午睡着了,然后刚开始考试的时候就困的一匹,我一看T1,woc,这不是之前线段树专题的题啊,和那道题差不多,所以我..... ...

随机推荐

  1. 【MSP是什么】MSP认证之成功的项目群管理

    同项目管理相比,项目群管理是为了实现项目群的战略目标与利益,而对一组项目进行的统一协调管理. 项目群管理 项目群管理是以项目管理为核心.单个项目上进行日常性的项目管理,项目群管理是对多个项目进行的总体 ...

  2. sql语句执行顺序

    首先来一张朋友传给我的图 FORM: 对FROM的左边的表和右边的表计算笛卡尔积.产生虚表VT1 ON: 对虚表VT1进行ON筛选,只有那些符合<join-condition>的行才会被记 ...

  3. &lpar;step 4&period;3&period;5&rpar;hdu 1035&lpar;Robot Motion——DFS&rpar;

    题目大意:输入三个整数n,m,k,分别表示在接下来有一个n行m列的地图.一个机器人从第一行的第k列进入.问机器人经过多少步才能出来.如果出现了循环 则输出循环的步数 解题思路:DFS 代码如下(有详细 ...

  4. iOS UICollectionView基础

    转载自:http://www.cnblogs.com/wayne23/p/4013522.html  初始化部分: UICollectionViewFlowLayout *flowLayout= [[ ...

  5. What is RandomCharacter&period;getRandomLowerCaseLetter&lpar;&rpar; &quest;&quest;&quest;&quest;&quest;

    今天在看书顺便打打书上的代码时,看到这么一个方法的调用RandomCharacter.getRandomLowerCaseLetter()! 年轻的我看到这一大串单词时还以为是JDK自带类里面方法Or ...

  6. 133、 Android 自动化测试(转载)

    Android 自动化测试--要点概括http://blog.csdn.net/vshuang/article/details/40595233 A/B测试与灰度发布http://blog.csdn. ...

  7. Js&lowbar;图片轮播

    <!DOCTYPE html> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <m ...

  8. libsvm使用说明

    http://www.hankcs.com/ml/libsvm-usage.html libsvm使用说明 码农场 > 机器学习 2016-02-18 阅读(345) 评论(0)  目录   l ...

  9. Yii 的session 实现返回上上页面

    学习session的页面:http://www.yiichina.com/doc/guide/2.0/runtime-sessions-cookies 关键摘要: $session = Yii::$a ...

  10. V4L2学习(一)整体说明

    1.概述 Video4Linux2是Linux内核中关于视频设备的内核驱动框架,为上层的访问底层的视频设备提供了统一的接口.凡是内核中的子系统都有抽象底层硬件的差异,为上层提供统一的接口和提取出公共代 ...