【2016常州一中夏令营Day4】

小 W 走迷宫
【问题描述】
小 W 被小 M 困在了一个方格矩阵迷宫里，矩阵边界在无穷远处，我们做出如下的
假设：
a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b. 走过的格子立即塌陷无法再走第二次；
c. 只能向北、东、西三个方向走。
小 W 走了没多久就累坏了，他很想知道如果允许在方格矩阵上走 N 步，共有多少种不同的方案。（开始时小 W 就在方格矩阵上的任意位置， 2 种走法只要有一步不一样，即被认为是不同的方案）
【输入格式】
一行输入 N。
【输出格式】
一行输出方案个数。
【输入输出样例】
game.in
2

game.out
7

【数据规模】
对于 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<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
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<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
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
",t);
        else printf("%d. false
",t);
    }
    return 0;
}

小 W 数线段
【问题描述】
小 W 和小 M 终于携手走到了城市门前，却发现门上刻了一个 N*M 的点阵，相邻两点距离
为 1，点阵里任取两点可连成线段。门上标注了：我问你 T 次，每次给你一个 L，你要答出
有多少对线段长度是 L。答都对了你才可以进门。
【输入格式】
第一行三个整数：N,M,T。
第二行为 T 个整数,即每个 L。
【输出格式】
一行 T 个整数，表示 T 个询问的答案。
只有整数间存在空格。
【输入输出样例】
dist1.in
3 3 3
1 2 3
dist1.out
12 6 9
dist2.in 4 5 1
5
dist2.out 2
【数据规模】
对于 20%的数据：N,M<=20，T<=10
对于 40%的数据：N,M<=1000，T<=100
对于 60%的数据：N,M<=100000
对于 100%的数据：N,M<=1000000000,T<=1000，L<=2*MAX(N,M)