codeforces #313 div1 B

时间:2023-01-01 03:34:44

模拟判定就可以了

判定字符串是否相等用hash来判断

QAQ 值得一提的是一开始我交的时候T了

结果我将递归的顺序调整了一下就A了

(并不知道为什么

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std; typedef unsigned long long LL;
const int maxn=200010;
const int x=13331;
int n;
char s[maxn];
char p[maxn];
LL xp[maxn],hs[maxn],hp[maxn]; bool cmp(int a,int b,int c,int d){
return hs[a]-hs[b+1]*xp[b-a+1]==hp[c]-hp[d+1]*xp[d-c+1];
}
bool Solve(int a,int b,int c,int d){
if(cmp(a,b,c,d))return true;
if((b-a+1)&1)return false;
int e=(a+b)>>1;
int f=(c+d)>>1;
if(Solve(a,e,f+1,d)&&Solve(e+1,b,c,f))return true;
if(Solve(a,e,c,f)&&Solve(e+1,b,f+1,d))return true;
return false;
} int main(){
scanf("%s",s+1);scanf("%s",p+1);
n=strlen(s+1);
xp[0]=1;
for(int i=1;i<=n;++i)xp[i]=xp[i-1]*x;
hs[n+1]=0;hp[n+1]=0;
for(int i=n;i>=1;--i){
hs[i]=hs[i+1]*x+s[i]-'a';
hp[i]=hp[i+1]*x+p[i]-'a';
}
if(Solve(1,n,1,n))printf("YES\n");
else printf("NO\n");
return 0;
}

  

codeforces #313 div1 B的更多相关文章

  1. codeforces &num;313 div1 E

    首先我们要注意到一个事情 如果一个灯塔向左覆盖,那么比他小的某个灯塔如果向左覆盖的端点大于当前塔向左覆盖的端点,他一定向右覆盖 对于当前灯塔向右覆盖也是同理 那么我们只需要记录当前覆盖到的端点就可以完 ...

  2. codeforces &num;313 div1 D

    好神的题目! 首先我们运用pick定理A=S-B/2+1将要求的东西转化掉 之后分离变量,我们变成了求选取凸包面积的期望和求选取凸包在边界上的点的期望 我们先考虑求选取凸包面积的期望 如何计算凸多边形 ...

  3. codeforces &num;313 div1 C

    同BZOJ 3782 上学路线 QAQ 还比那个简单一点 把坐标(1,1)-(n,m)平移成(0,0)-(n-1,m-1) 设dp[i]表示从(1,1)出发第一次经过障碍且到达第i个障碍的方案数 首先 ...

  4. codeforces &num;313 div1 A

    捕获一只野生大水题! 首先我们知道边长为L的正三角形含有边长为1的小正三角形为L^2个 那么我们可以通过在六边形的正上,左下,右下补充正三角形使得原图形变成正三角形 然后再将补充的减去即可 #incl ...

  5. codeforces 407 div1 B题&lpar;Weird journey&rpar;

    codeforces 407 div1 B题(Weird journey) 传送门 题意: 给出一张图,n个点m条路径,一条好的路径定义为只有2条路径经过1次,m-2条路径经过2次,图中存在自环.问满 ...

  6. codeforces 407 div1 A题&lpar;Functions again&rpar;

    codeforces 407 div1 A题(Functions again) Something happened in Uzhlyandia again... There are riots on ...

  7. Codeforces Round 313&lpar;div1&rpar;

    A题: 题目大意: 给出内角全为120度的六边形的六条边的边长,求由多少边长为1的等边三角形构成. 解题思路: 将六边形补全为一个大的等边三角形,则大的等边三角形的边长为六边形的相邻三边之和,接着减去 ...

  8. codeforces &num;305 div1 done

    总算搞定了这一场比赛的题目,感觉收获蛮大 其中A,B,C都能通过自己的思考解决掉 D题思路好神,E题仔细想想也能想出来 以后坚持每两天或者一天做一场CF的div1的全套题目 除非有实在无法做出来的题目 ...

  9. Codeforces &num;254 div1 B&period; DZY Loves FFT 暴力乱搞

    B. DZY Loves FFT 题目连接: http://codeforces.com/contest/444/problem/B Description DZY loves Fast Fourie ...

随机推荐

  1. 使用css3 filter 实现移入背景变色效果

    <!doctype html><html lang="en"><head> <meta charset="UTF-8" ...

  2. C&plus;&plus;&lowbar;快速排序

    void quick_sort(int s[],int l,int r) { if(l<r) { int i=l,j=r,x=s[l]; while(i<j) { while( i< ...

  3. 产品经理学Python:条件控制

    条件控制其实就是if...else...(如果...条件是成立的,就做...:反之,就做...)的使用,其基本结构是: 具体看下面这个例子: def account_login(): # 定义函数 p ...

  4. Spring Security(三十二):10&period; Core Services

    Now that we have a high-level overview of the Spring Security architecture and its core classes, let ...

  5. hive 日常技巧

    --删除表中重复数据 delete from vitae a where (a.peopleId,a.seq) in (select peopleId,seq from vitae group by ...

  6. Ubuntu 16&period;04下vsftpd 安装配置实例

    从https://www.linuxidc.com/Linux/2017-06/144807.htm转载 第一步:安装VSFTPD sudo apt-get install vsftpd 安装完成后启 ...

  7. postgresql-distinct on理解

    PostgreSQL 的 distinct on 的理解 对于 select distinct on , 可以利用下面的例子来理解: create table a6(id integer, name ...

  8. 带你走进EJB--将EJB发布为Webservice&lpar;3&rpar;

    在上面文章中我们讲到,通过使用用JBoss5作为EJB容器的时候,调用Web服务出现了异常. 异常信息如下: *********************** CreateWeb Service Cli ...

  9. 使用phpExcel导出excel文件

    function export($log_list_export) { require "../include/phpexcel/PHPExcel.php"; require &q ...

  10. R语言绘图布局

    在R语言中,par 函数可以设置图形边距,其中oma 参数设置outer margin, mar 参数设置margin, 这些边距有什么不同呢,通过box函数可以直观的看到 box 默认在当前图形绘制 ...