【2016常州一中夏令营Day4】-白红宇

【2016常州一中夏令营Day4】

阅读量：5308 次

发布时间：2019-06-14

本文共 3335 字，大约阅读时间需要 11 分钟。

小 W 走迷宫

【问题描述】

小 W 被小 M 困在了一个方格矩阵迷宫里，矩阵边界在无穷远处，我们做出如下的

假设：

a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；

b. 走过的格子立即塌陷无法再走第二次；

c. 只能向北、东、西三个方向走。

小 W 走了没多久就累坏了，他很想知道如果允许在方格矩阵上走 N 步，共有多少种不同的方案。（开始时小 W 就在方格矩阵上的任意位置， 2 种走法只要有一步不一样，即被认为是不同的方案）

【输入格式】

一行输入 N。

【输出格式】

一行输出方案个数。

【输入输出样例】

game.in

game.out

【数据规模】

对于 30%的数据：N<=20

对于 100%的数据：N<=100

题解

$a[i]$ 表示最后一步向左走到达第i个格，它上一格不能是从右边走得到，易得 $a[i]=a[i-1]+c[i-1]$

$b[i]$ 表示最后一步向右走到达第i个格，它上一格不能是从左边走得到的，易得 $b[i]=b[i-1]+c[i-1]$

$c[i]$ 表示最后一步先上走到达第i个格，易得 $c[i]=a[i-1]+b[i-1]+c[i-1]$

$f[i]=a[i]+b[i]+c[i]$ $=2*a[i-1]+2*b[i-1]+3*c[i-1]$ $=2*f[i-1]+f[i-2]$

所以 $f[i]=2*f[i-1]+f[i-2]$ 套上高精度即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n;struct hh{ int n,a[105];};hh a,b,ans;hh sum(hh a,hh b){ int i; hh c; c.n=max(a.n,b.n); memset(c.a,0,sizeof(c.a)); for(i=1;i<=c.n;i++) { c.a[i]+=a.a[i]+b.a[i]; if(c.a[i]>=10) { c.a[i+1]+=c.a[i]/10; c.a[i]=c.a[i]%10; } } while(c.a[c.n+1]) { ++c.n; if(c.a[c.n]>9) { c.a[c.n+1]+=c.a[c.n]/10; c.a[c.n]=c.a[c.n]%10; } } return c;}hh mul(hh a,int k){ int i,j; hh c; c=a; for(i=1;i<=c.n;i++) c.a[i]*=k; for(i=1;i<=c.n;i++) if(c.a[i]>9) { c.a[i+1]+=c.a[i]/10; c.a[i]=c.a[i]%10; } while(c.a[c.n+1]) { c.n++; if(c.a[c.n]>=10) { c.a[c.n+1]+=c.a[c.n]/10; c.a[c.n]=c.a[c.n]%10; } } return c;}int main(){ int i,j; hh temp; freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d",&n); a.n=b.n=1;a.a[1]=1; for(i=1;i<=n-1;i++) { b=sum(a,b);a=sum(a,b); temp=a; a=b; b=temp; } ans=sum(mul(a,3),mul(b,2)); for(i=ans.n;i;i--) printf("%d",ans.a[i]); fclose(stdin); fclose(stdout); return 0;}

小 W 砍大树

【问题描述】

小 W 走出了迷宫，发现小 M 正等着他出城约会。不妙的的是，一棵大树挡在他们面前。这是一棵奇怪的树（当然是计算机领域的树，而且不一定是二叉树），所有叶子节点都是 True 或者 False。对于从上往下奇数层的非叶子节点是 and，偶数层非叶子节点为 or。

树上每个节点的值是所有孩子节点的值进行该节点的运算操作。砍树的方法就藏在树根的值里！小 W 需要计算机大神你的帮助！

上天为了撮合小 W 和小 M，大树以简单的括号序列给出：上图可以描述为((A(BC))(DE))

【输入格式】

数据包括若干组，每组数据包含一行一个字符串。输入()表示结束。

【输出格式】

每组数据输出一行，包含：数据编号，点，空格，true 或 false。

【输入输出样例】
form.in

((F(TF))(TF))

(TFT)

((TFT)T)

()

form.out

1. false

2. false

3. true

【数据规模】

对于 10%的数据：每行只包含一对括号；

对于 30%的数据：只有嵌套的括号，没有并列的括号

题解

用栈维护即可

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int len,top,cnt,t;int s[50005];char str[50005];int main(){ int i,now; freopen("form.in","r",stdin); freopen("form.out","w",stdout); while(true) { scanf("%s",str+1); len=strlen(str+1); if(len==2&&str[1]=='('&&str[2]==')') break; cnt=top=1; s[top]='('; for(i=2;i<=len;i++) { if(str[i]=='T'){s[++top]=1;continue;} if(str[i]=='F'){s[++top]=0;continue;} if(str[i]=='('){s[++top]=2;cnt++;continue;} if(cnt&1) now=1; else now=0; while(s[top]==1||s[top]==0) { if(cnt&1) now=now&s[top]; else now=now|s[top]; top--; } s[top]=now; cnt--; } t++; if(s[1]) printf("%d. true\n",t); else printf("%d. false\n",t); } return 0;}