hust Little Sheep and a paper
hust Little Sheep and a paper
用户1624346
发布于 2018-04-17 16:12:05
发布于 2018-04-17 16:12:05
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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-03-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读