专栏首页calmoundhust Little Sheep and a paper

hust Little Sheep and a paper

http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/H

题意:一张纸对折(向前翻),可以向左向右向上向下,经过几次对折,问起面向你的突出的折痕有多少个

分析1:经过折叠很容易清楚LR是一样的,UD是一样的。

         当该次折叠的是LR,则row[i]=row[i-1]*2;纵向折一次,那么前一次的横向就要翻倍

                                        col[i]=col[i-1]+face/2;前一次的纵向就会增加纸的厚度/2;

这里出现的问题就是对于face的取余,因为face必定是偶数,而取模后很难保证其face就一定是偶数,而且对于/2叶很难保证其正确性

 若其为奇数,/2会取证,所以我的思路就是舍弃其face/2这个步骤,直接记录其前一次的值

#include<stdio.h>
#include<string.h>
const int MN=1000010;
const long long MOD=100000009;

char str[MN];

int main()
{
long long row[2],col[2],face[2];
    int i,j;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",str);
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));
        int t=1;
        face[0]=1;
        face[1]=0;
        for(i=0;str[i];i++)
        {
            if(str[i]=='L' || str[i]=='R')
            {
                row[t]=(row[1-t]*2)%MOD;
                col[t]=(col[1-t]+face[t])%MOD;
            }
            else
            {
                row[t]=(row[1-t]+face[t])%MOD;
                col[t]=(col[1-t]*2)%MOD;
            }
            face[t]=(face[1-t]*2)%MOD;
            t=1-t;
        }
        t=1-t;
        printf("%lld\n",(row[t]+col[t])%MOD);
    }
    return 0;
}

分析2:看了别人的思路,试了他的代码,其时间效率整整比我少1000ms

           假设其只折叠LR,则其纵向的个数s1=(2^n1)-1,同理只折叠UD,其横向的个数s2=(2^n2)-1

           若交叉折叠的话,横向就是(s1+1)*s2,例如当纵向折叠一次,则横向*2 ,纵向折叠两次,则横向*4 纵向折叠三次,则横向*8

           当然,要排除掉第一次的折叠(无论第一次折叠式LR还是UD,对于其后的次数都没有影响,也就是说第一次的折叠应该忽略不计)

#include<stdio.h>
#include<string.h>
const int MN=1000010;
const long long MOD=100000009;

char str[MN];

long long pow_mod(long long a, long long n, long long m)
{
    if(n==0) return 1;
    if ( n == 1 ) return a % m;
    long long x = pow_mod(a, n / 2, m);
    long long  ans = x * x % m;
    if ( n % 2 == 1 ) ans = (ans * a) % m;
    return ans;
}

int main()
{
    long long row,col,s1,s2;
    int i,j,flag;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",str);
        row=col=0;
        for(i=0; str[i]; i++)
        {
            if(str[i]=='L' || str[i]=='R') col++;
            else row++;
        }
        if(str[0]=='L' || str[0]=='R') flag=1;
        else flag=0;
        if(!flag)
        {
            int tmp=col;
            col=row;
            row=tmp;
        }
        col--;
        s1=pow_mod(2,col,MOD);
        s2=pow_mod(2,row,MOD);
        printf("%lld\n",((s1-1)*s2%MOD+(s2-1)*s1%MOD)%MOD);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • sdut 1446 超级玛丽

    http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1446 题意:你...

    用户1624346
  • Where's Waldorf?

    题意:找相同字符窜首字母的地址 读题。。。。A word matches a straight, uninterrupted line of letters i...

    用户1624346
  • zoj ZOJ 3196 Give me the result

    http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=579#problem/D 题意:给出一段...

    用户1624346
  • JVM如何确定垃圾以及常用参数

    Java中,引用和对象是有关联的。如果要操作对象则必须引用进行。因此,简单的办法是通过引用计数来判断一个对象是否可以回收。简单的说,给对象中添加一个引用计数,每...

    万能青年
  • Vue中computed和watch的区别

    3.computed 属性值会默认走缓存,计算属性是基于它们的响应式依赖进行缓存的,也就是基于data中声明过的数据通过计算得到的

    TimothyJia
  • 剑指offer——平衡二叉树

    如果树为空,返回true。否则递归判断每个树节点的其左右子树高度之差的绝对值是否为0或者1,若是返回true,不是返回false。 注明:这里平衡二叉树不需...

    AI那点小事
  • 用Java代码实现一个在线聊天功能案例

    框架师
  • CCF认证 送货

    问题描述   为了增加公司收入,F公司新开设了物流业务。由于F公司在业界的良好口碑,物流业务一开通即受到了消费者的欢迎,物流业务马上遍及了城市的每条街道。然而...

    用户1148523
  • 内存屏障保证缓存一致性优化

     在前面内存系统重排序提到,“写缓存没有及时刷新到内存,导致不同处理器缓存的值不一样”,出现这种情况是糟糕的,所幸处理器遵循缓存一致性协议能够保证足够的可见性又...

    用户1174983
  • JavaWeb——会话技术之Session快速入门与验证码登录案例实战(Session实现原理、使用细节、快速入门、Session的特点)

    Session是服务器端会话技术,在一次会话的多次请求间共享数据,将数据保存在服务器端的对象中,HttpSession。

    Winter_world

扫码关注云+社区

领取腾讯云代金券