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

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操