USACO-Section2.2 Party Lamps【深度优先搜索】

2024-04-12 06:38

本文主要是介绍USACO-Section2.2 Party Lamps【深度优先搜索】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述:

在IOI98的节日宴会上,我们有N(10<=N<=100)盏彩色灯,他们分别从1到N被标上号码。 这些灯都连接到四个按钮:
按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。
按钮2:当按下此按钮,将改变所有奇数号的灯。
按钮3:当按下此按钮,将改变所有偶数号的灯。
按钮4:当按下此按钮,将改变所有序号是3*K+1(K>=0)的灯。例如:1,4,7…
一个计数器C记录按钮被按下的次数。当宴会开始,所有的灯都亮着,此时计数器C为0。
你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态,并且没有重复。(翻译来源:NOCOW)

INPUT FORMAT:

(file lamps.in)
不会有灯会在输入中出现两次。
第一行: N。
第二行: C最后显示的数值。
第三行: 最后亮着的一些灯,用一个空格分开,以-1为结束。
第四行: 最后关着的一些灯,用一个空格分开,以-1为结束。

OUTPUT FORMAT:

(file lamps.out)
每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符,第1个字符表示1号灯,最后一个字符表示N号灯。0表示关闭,1表示亮着。这些行必须从小到大排列(看作是二进制数)。
如果没有可能的状态,则输出一行’IMPOSSIBLE’。


SAMPLE INPUT

10
1
-1
7 -1
在这个样例中,有10盏灯,只有1个按钮被按下。最后7号灯是关着的。


SAMPLE OUTPUT

0000000000
0101010101
0110110110


解题思路:

这道题可以通过数学推理来进行各种优化。首先需要理解的是结果是以6个灯为一组重复,所以我们只需要判断6个灯的情况。所以我用的是深度优先搜索的方式,通过计算可以判断出c>4时可以实现所有可能的按法(根据按钮之间的联系来推),而c<=4则通过深搜来进行枚举。当然根据按钮之间的关系可以让枚举次数变得更少,但代码会不简洁和明晰。由于可能会有不同的按法出现相同的结果,所以加了去重。

/*
ID: huanshi
LANG: C
TASK: lamps
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int N,C,lamp=63,v[7],flag=0,vl[64];//lamp记录六盏灯的情况,v数组记录题目要求,flag判断是否有结果,vl用来去重
FILE *fout;
void judge(){//判断是否符合要求int i,temp=0;for(i=1;i<=6;i++){//如果与题目不符则returnif(v[i]==0&&(lamp&(int)pow(2,6-i)))return ;if(v[i]==1&&!(lamp&(int)pow(2,6-i))) return ;temp+=lamp&(int)pow(2,6-i);//将灯的情况转换为统一的数字来去重(位运算可能会出现负数)}if(vl[temp])return ;//如果情况已出现过则returnvl[temp]=1;flag=1;return ;
}
void dfs(int step){//深搜if(step>C){judge();return ;}int i;lamp=~lamp;dfs(step+1);lamp=~lamp;//按钮1(注意要回溯)lamp=lamp^42;dfs(step+1);lamp=lamp^42;//按钮2lamp=lamp^21;dfs(step+1);lamp=lamp^21;//按钮3lamp=lamp^36;dfs(step+1);lamp=lamp^36;//按钮4
}
int main(){FILE *fin  = fopen ("lamps.in", "r");fout = fopen ("lamps.out", "w");fscanf(fin,"%d",&N);fscanf(fin,"%d",&C);if(C>4)C=4;int i,j,temp;for(i=0;i<7;i++)v[i]=99999;while(fscanf(fin,"%d",&temp)!=EOF&&temp!=-1){//记录亮的灯if(temp%6==0)temp=6;else temp%=6;v[temp]=1;}while(fscanf(fin,"%d",&temp)!=EOF&&temp!=-1){//记录关的灯if(temp%6==0)temp=6;else temp%=6;v[temp]=0;}dfs(1);for(j=0;j<64;j++){//顺序输出结果if(vl[j]){for(i=1;i<N;i++){if(i%6==0)fprintf(fout,"%d",j&(int)pow(2,0)&&1);//6的倍数特殊处理else fprintf(fout,"%d",j&(int)pow(2,6-i%6)&&1);}if(i%6==0)fprintf(fout,"%d",j&(int)pow(2,0)&&1);else fprintf(fout,"%d\n",j&(int)pow(2,6-i%6)&&1);}} if(flag==0)fprintf(fout,"IMPOSSIBLE\n");//没有答案则输出impossibleexit(0);
}

这篇关于USACO-Section2.2 Party Lamps【深度优先搜索】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/896377

相关文章

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

SpringBoot开发中十大常见陷阱深度解析与避坑指南

《SpringBoot开发中十大常见陷阱深度解析与避坑指南》在SpringBoot的开发过程中,即使是经验丰富的开发者也难免会遇到各种棘手的问题,本文将针对SpringBoot开发中十大常见的“坑... 目录引言一、配置总出错?是不是同时用了.properties和.yml?二、换个位置配置就失效?搞清楚加

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Python中文件读取操作漏洞深度解析与防护指南

《Python中文件读取操作漏洞深度解析与防护指南》在Web应用开发中,文件操作是最基础也最危险的功能之一,这篇文章将全面剖析Python环境中常见的文件读取漏洞类型,成因及防护方案,感兴趣的小伙伴可... 目录引言一、静态资源处理中的路径穿越漏洞1.1 典型漏洞场景1.2 os.path.join()的陷

Spring Boot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)

《SpringBoot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)》:本文主要介绍SpringBoot拦截器Interceptor与过滤器Filter深度解析... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现与实

MyBatis分页插件PageHelper深度解析与实践指南

《MyBatis分页插件PageHelper深度解析与实践指南》在数据库操作中,分页查询是最常见的需求之一,传统的分页方式通常有两种内存分页和SQL分页,MyBatis作为优秀的ORM框架,本身并未提... 目录1. 为什么需要分页插件?2. PageHelper简介3. PageHelper集成与配置3.