[高精度][二分]JZOJ 1207 遥控车

[高精度][二分]JZOJ 1207 遥控车

Description

平平带着韵韵来到了游乐园,看到了n辆漂亮的遥控车,每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s的遥控车。可是韵韵毕竟还小,她想象的名字可能是一辆车名字的前缀(也就是说能确定一个i,使s是name[i]的前缀),这时她就能玩第i辆车;或者是一个无中生有的名字,即s不是任何一辆车名字的前缀,这时候她什么也不能玩。

你需要完成下面的任务:

1.韵韵想了m个她想要的名字,请告诉她能玩多少次。

2.由于管理员粗心的操作,导致每辆车的摆放位置都可能出现微小的差错,原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个(第1辆车的位置不可能是0,第n辆车的位置不可能是n+1)。请你计算出共有多少种可能的排列。

注:数据保证当s是name[i]的前缀时,i是唯一确定的。一辆车可以玩多次。

 

Input

第一行是2个正整数n、m。

接下来n行,每行1个字符串name[i],表示第i辆车的名字。

接下来m行,每行1个字符串s,表示韵韵想要的名字。

Output

第一行输出韵韵能玩的次数。

第二行输出共有多少种可能的排列。

 

Sample Input

4 4
Abcd
DeF
AAa
aBccc
Ab
AA
AbC
aBcc

Sample Output

3
5

 

Data Constraint

 

 

Hint

【数据规模和约定】

对于题目涉及到的字符串严格区分大小写,且长度小于255。

对于20%的数据 n≤10,m≤10;

对于40%的数据 n≤1000,m≤1000;

对于100%的数据 n≤10000,m≤10000。

分析

关于着前缀,我本想用字典树的

结果MLE。。。无奈,就用了stupid的二分法

然后第二问打波表发现是斐波那契,加高精度即可

 

[高精度][二分]JZOJ 1207 遥控车
[高精度][二分]JZOJ 1207 遥控车

#pragma GCC optimize(2)
#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
string s[10001];
int cnt;
int n,m;

bool Bin_Search(string a) {
    int l=1,r=n;
    while (l<=r) {
        int mid=l+r>>1;
        if (s[mid]>a) r=mid-1;
        else l=mid+1;
    }
    return !s[l].find(a,0);
}

int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) cin>>s[i];
    int ans1=0;
    sort(s+1,s+n+1);
    for (int i=1;i<=m;i++) {
        string a;
        cin>>a;
        ans1+=Bin_Search(a);
    }
    printf("%d\n",ans1);
    int a[10001],b[10001],c[10001];
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    memset(c,0,sizeof c);
    a[1]=1;b[1]=2;b[0]=1;
    if (n<=3) printf("%d",n==1?1:(n==2?1:2));
    for (int i=1;i<=n-2;i++) {
        for (int j=1;j<=b[0];j++) {
            c[j]=a[j]+b[j]+c[j];
            c[j+1]=c[j]/10;
            c[j]%=10;
        }
        if (c[b[0]+1]>0) ++b[0];
        for (int j=1;j<=b[0];j++) {
            a[j]=b[j]; b[j]=c[j];c[j]=0;
        }
    }
    for (int i=b[0];i;i--)
        printf("%d",b[i]);
}

View Code

 

转载于:https://www.cnblogs.com/mastervan/p/9699165.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101401.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java class类文件「建议收藏」

    java class类文件「建议收藏」根据 Java 虚拟机规范,类文件由单个 ClassFile 结构组成:ClassFile { u4 magic; //Class 文件的标志 u2 minor_version;//Class 的小版本号 u2 major_version;//Class 的大版本号 u2 constant_pool_count;//常量池的数量 cp_info consta

  • 慧荣SM2246XT主控的固态硬盘修复开卡不识别怎么短接方法

    慧荣SM2246XT主控的固态硬盘修复开卡不识别怎么短接方法一块坏了的240G的固态硬盘,电脑完全不认盘了,所以想修复一下,拆开看到主控是慧荣的SM2246XT,幸好此主控是有开卡软件的,下载也比较方便,最新的SM2246XT_MP_EnhancePageMode_MPQ1102A_DBQ0412_FWR1212A.rar修复成功率很高,但跟U盘量产不同,固态硬盘开卡是需要短接的,但很多人不知道SM2246XT的固态硬盘该怎么短接,这里就教大家。如图拆开ssd外壳后可以看到板子上有ROMMODE的字样,那里就是短接的位置了,这里的4个短接点,我们是需要用镊子两两短

  • E667: Fsync failed

    E667: Fsync failed通过vim编辑文件/proc/sys/kernel/core_pattern,保存时报错E667:Fsyncfailed通过以下方式:echo“core-%e-%p-%t”|sudoddof=/proc/sys/kernel/core_pattern参考:https://askubuntu.com/questions/167819/im-getting-fsync-failed-…

  • CreatePipe()等函数创建管道来操纵控制台

    CreatePipe()等函数创建管道来操纵控制台#include  #include    #define BUFSIZE 4096   HANDLE hChildStdinRd, hChildStdinWr, hChildStdinWrDup,    hChildStdoutRd, hChildStdoutWr, hChildStdoutRdDup,    hInputFile, hStdout;   BO

  • navicate 15 激活码 在线[在线序列号]「建议收藏」

    navicate 15 激活码 在线[在线序列号],https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 局部变量和全局变量,以及作用范围的区别_外部变量和全局变量区别

    局部变量和全局变量,以及作用范围的区别_外部变量和全局变量区别    在写工程文件的时候,犯了一个基础性的错误,基础不牢,地动山摇。所以通过查阅资料回顾了一些相关知识,并记录下来。防止以后再发生这种惨案。变量按存储区域分:全局变量、静态全局变量和静态局部变量都存放在内存的静态存储区域,局部变量存放在内存的栈区。变量按作用域分:  全局变量:在整个工程文件内都有效;“在函数外定义的变量”,即从定义变量的位置到本源文件结束都有效。由于同一文…

    2022年10月28日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号