纪中17日T1 2321. 方程

(File IO): input:cti.in output:cti.out

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

Goto ProblemSet

题目描述

输入

输出

样例输入

样例输出

数据范围限制

提示

吐槽

这些图片太模糊了吧……

还有那吓人的 mod 998244353

都使得我们对这道题的恐惧感叠加了998244353层……

没想到……只有三种答案！（三进制呵呵哒）

Solution

（约定：用line[i]表示第i个输入的数据，man[i]表示在第i位是否为男生（i from 1 to n））

step1

先对line[1]进行判断：

　　若line[1]==0

　　　　直接dfs

　　若line[1]==1

　　　　进行两遍dfs，其中一遍man[1]=1，另一边man[2]=1；

　　若line[1]==2

　　　　一遍dfs，man[1]=man[2]=1；

if(line[]==){

    man[]=;

    dfs();

    memset(man,,sizeof(man));

    man[]=;

    dfs();

    }

if(line[]==) dfs();

if(line[]==){

    man[]=man[]=;

    dfs();

}

处理完在边缘位置的line[1]后，接下来就好操作了。

step2

写dfs

int t,n,ans,line[];

bool man[];

IL void dfs(int depth)

{

    int now=;

    if(depth>) now+=man[depth-];

    if(depth<n) now+=man[depth+];

    now+=man[depth];

    if(now!=line[depth]) return;

    if(depth==n){

        ans++;

        return;

    }

    man[depth+]=;

    dfs(depth+);

    man[depth+]=;

    dfs(depth+);

}

step3

按照题目的意思

怎么看上去像打了马赛克呢……

这个快读是专门给line的！

IL int read()

{

    char ch=getchar();

    while(ch<''||ch>'')

    {

        ch=getchar();

    }

    return (int)ch^;

}

for(int i=;i<=n;i++)

            line[i]=read();

step4

输出答案

printf("%d\n",ans/);

别问我为什么要除以2

自己去推到dfs的结果吧。

我已经被接下来的问题折磨疯了……

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#define IL inline

using namespace std;

int t,n,ans,line[];

bool man[];

IL void dfs(int depth)

{

    int now=;

    if(depth>) now+=man[depth-];

    if(depth<n) now+=man[depth+];

    now+=man[depth];

    if(now!=line[depth]) return;

    if(depth==n){

        ans++;

        return;

    }

    man[depth+]=;

    dfs(depth+);

    man[depth+]=;

    dfs(depth+);

}

IL int read()

{

    char ch=getchar();

    while(ch<''||ch>'')

    {

        ch=getchar();

    }

    return (int)ch^;

}

int main()

{

//    freopen("cti.in","r",stdin);

//    freopen("cti.out","w",stdout);

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        ans=;

        memset(man,,sizeof(man));

        for(int i=;i<=n;i++)

            line[i]=read();

        if(line[]==){

            man[]=;

            dfs();

            memset(man,,sizeof(man));

            man[]=;

            dfs();

        }

        if(line[]==) dfs();

        if(line[]==){

            man[]=man[]=;

            dfs();

        }

        printf("%d\n",ans/);

    }

    return ;

}

Problem

我不能通过#9！

运行时错误？

我又调试了很久很久……

发现了一个叫“段错误”的东西

program received signal SIGSEGV,segmentation fault

有些内存是内核占用的或者是其他程序正在使用，为了保证系统正常工作，所以会受到系统的保护，而不能任意访问。

或者时数组越界……

老师正在看另一个老师打游戏，不想理我……

哼唧……

巴特西

纪中17日T1 2321. 方程

纪中17日T1 2321. 方程

题目描述

输入

输出

样例输入

样例输出

数据范围限制

提示

吐槽

Solution

step1

step2

step3

step4

Code

Problem

最新文章

热门文章