第十七届浙江大学宁波理工学院程序设计大赛（重现赛）C题

题目链接：https://ac.nowcoder.com/acm/contest/10934分析题目，发现可以用搜索来做。搜索空间就是1~n。每次折纸以后，搜索空间被分成了1~a和a~n，两部分。思路：每次折纸后，依次搜索折痕的两边，同时看是否满足搜索条件，继而看是否达到折纸要求。具体看代码以及注释#include <iostream>#include <bits/stdc++.

aianswer3

146人浏览 · 2021-03-18 11:03:12

aianswer3 · 2021-03-18 11:03:12 发布

题目链接：https://ac.nowcoder.com/acm/contest/10934

分析题目，发现可以用搜索来做。搜索空间就是1~n。

每次折纸以后，搜索空间被分成了1~a和a~n，两部分。

思路：

每次折纸后，依次搜索折痕的两边，同时看是否满足搜索条件，继而看是否达到折纸要求。

具体看代码以及注释

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int a, n, flag=0;
int step[1000005]; //保存达到折痕所需要的次数，下标为折痕。

void dfs(int mid)
{
    if(mid==a)
    {
        //flag=1;
        return;
    }
    else
    {
        if((!(mid%2)) && (!step[mid/2])) //判断1~a区间是否进行折纸操作，判断即将形成的折痕是否重复
        {
            if((mid/2==a) && (mid%2==0))//判断此次折纸是否满足要求，递归结束标志
            {
                step[mid/2]=step[mid]+1;
                //flag=1;
                return;
            }
            else
            {
                step[mid/2]=step[mid]+1; //更新折纸次数
                //cout<<0<<" "<<mid/2<<" "<<step[mid/2]<<endl;
                dfs(mid/2);//继续折纸
            }
        }
        if((!((n-mid)%2)) && (!step[(n+mid)/2])) //判断a~n区间，其余操作相似
        {
            if((mid/2==a) && (mid%2==0))
            {
                step[mid/2]=step[mid]+1;
                //flag=1;
                return;
            }
            else
            {
                step[(n+mid)/2]=max(step[n], step[mid])+1;
                //cout<<1<<" "<<(n+mid)/2<<" "<<step[(n+mid)/2]<<endl;
                dfs((n+mid)/2);
            }
        }
    }
}

int main()
{
    cin>>n>>a;
    memset(step, 0, sizeof(step));
    dfs(n);

    if(step[a]==0 && a!=0)// 判断最终是否可以达到目标
        cout<<-1<<endl;
    else
        cout<<step[a]<<endl;
    return 0;
}