[高精度][二分]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)
blank

相关推荐

  • kworker进程_线程池队列类型

    kworker进程_线程池队列类型工作队列是另一种将工作推后执行的形式,它可以把工作交给一个内核线程去执行,这个下半部是在进程上下文中执行的,因此,它可以重新调度还有睡眠。    区分使用软中断/tasklet还是工作队列比较简单,如果推后的工作不需要睡眠,那么就选择软中断或tasklet,但如果需要一个可以重新调度,可以睡眠,可以获取内存,可以获取信号量,可以执行阻塞式I/O操作时,那么,请选择工作队列吧!    在老的

  • 数据分析法、数据分析方法论总结

    数据分析法、数据分析方法论总结数据分析方法论1、5W2H分析法2、PEST分析法3、逻辑树分析法4、4P营销理论5、用户使用行为理论数据分析法数据分析方法论主要用来指导数据分析师进行一次完整的数据分析,它更多的是指数据分析思路,比如从哪几方面开展数据分析,各方面包含什么内容和指标。 数据分析方法论主要从宏观角度指导如何进行数据分析,它就像一个数据分析前期的规划,指导着后期数据分析工作的开展。 数据分析法则是指具体的分析方法,如常见的对比分析、交叉分析、相关分析、回归分析、聚类分析等数据分析法。数据分析法.

  • ListView中实现部分刷新的两种方法

    ListView中实现部分刷新的两种方法ListView在开发中用到的地方非常多,我们经常是全部刷新来更新数据,如果只需要更新某一条数据,该怎么实现呢?我在项目中使用过以下两种方法:1.通过点击的位置,获取需要刷新那一列对应的控件,然后在控

  • 【永久一次性解决】github访问慢[通俗易懂]

    【永久一次性解决】github访问慢[通俗易懂]一次性解决

  • linux防火墙配置命令_linux防火墙规则设置

    linux防火墙配置命令_linux防火墙规则设置一、实验要求1.不允许外网不经过防火墙与内网进行通信2.允许内网用户通过防火墙访问外部HTTP、HTTPS服务器3.允许内网用户通过防火墙访问外部FTP服务器二、实验环境1.使用两台Linux虚拟机和一台win10物理机。一台Linux主机作为网关(需要双网卡),另一台Linux主机作为内网,使用物理机作为外网。2.我使用的是RedHat6.5版本。RedHat7及…

  • 机器人手眼标定Ax=xB(eye to hand和eye in hand)及平面九点法标定[通俗易懂]

    机器人手眼标定Ax=xB(eye to hand和eye in hand)及平面九点法标定[通俗易懂]一、背景Calibration是机器人开发者永远的痛。虽然说方法说起来几十年前就有,但每一个要用摄像头的人都还是要经过一番痛苦的踩坑,没有轻轻松松拿来就效果好的包。机器人视觉应用中,手眼标定是一个非常基础且关键的问题。简单来说手眼标定的目的就是获取机器人坐标系和相机坐标系的关系,最后将视觉识别的结果转移到机器人坐标系下。手眼标定行业内分为两种形式,根据相机固定的地方不同,如果相机和机器…

发表回复

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

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