【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

题解

$【2016常州一中夏令营Day4】$ 表示最后一步向左走到达第i个格，它上一格不能是从右边走得到，易得 $【2016常州一中夏令营Day4】$
$【2016常州一中夏令营Day4】$ 表示最后一步向右走到达第i个格，它上一格不能是从左边走得到的，易得 $【2016常州一中夏令营Day4】$
$【2016常州一中夏令营Day4】$ 表示最后一步先上走到达第i个格，易得 $【2016常州一中夏令营Day4】$

$【2016常州一中夏令营Day4】$ $【2016常州一中夏令营Day4】$ $【2016常州一中夏令营Day4】$

所以 $【2016常州一中夏令营Day4】$ 套上高精度即可

#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 需要计算机大神你的帮助！
【2016常州一中夏令营Day4】

上天为了撮合小 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\n",t);

        else printf("%d. false\n",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)