当前位置： 首页 > article >正文

派对灯 Party Lamps [USACO 2.2]

article 2024/11/29 21:36:48

 有的时候，思路远比代码更重要！！！

题目

5. K10855 派对灯 Party Lamps [USACO 2.2]

题目描述

在 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)上的数值和经过若干操作后某些灯的状态.写一个程序去找出所有灯最后可能的与所给出信息相符的状态,并且没有重复.

输入格式

不会有灯会在输入中出现两次.

第一行: N.(10<=N<=100)

第二行: C 最后显示的数值.(0<=C<=10000)

第三行: 最后若干亮着的灯的编号,用一个空格分开,以-1 为结束.

第四行: 最后若干关着的灯的编号,用一个空格分开,以-1 为结束.

输出格式

每一行是所有灯可能的最后状态(没有重复).

每一行有 N 个字符,第 1 个字符表示 1 号灯,最后一个字符表示 N 号灯。0 表示关闭,1 表示亮着.这些行必须从小到大排列（看作是二进制数）.

如果没有可能的状态,则输出一行'IMPOSSIBLE'.

输入输出样例
输入样例1：复制
10
1
-1
7 -1
输出样例1：复制
0000000000
0101010101
0110110110
说明
【样例说明】

在这个样例中，有三种可能的状态：

一、所有灯都关着

二、1,4,7,10号灯关着，2,3,5,6,8,9亮着。

三、1,3,5,7,9号灯关着，2, 4, 6, 8, 10亮着。

【耗时限制】1000ms 【内存限制】128MB

 思路

 解这道题思路很重要。

想法1：枚举每次按下按键

 每一次按下按键，要么是按下了按键1，要么是按键2，要么是按键3，要么是按键4。

可以写出下面的伪代码：

for(i = 1---->4){//第一次按下的按键

        for(j = 1------>4){//第二次

                for(k = 1-------->4){//第三次

                        .

                        .

                        .

                        for(x = 1-------->4){//第C次

                                算出按完后的状态

                                判断状态是否合法

                                合法的存入set中去//不知道set的去“这里”

                        }

                        .

                        .

                        .

                }

        }

}

一共C层循环，每层4次一共是4^C,0<=C<=10000，4的一万次方？？？

。。。。。。

死的真惨！

pass

 想法2：枚举所有灯按过C次后的状态

 C太big了，n可就小得多了，枚举所有灯按过C次后的状态，再补过程行不行？

伪代码实现一下：

long long T[2^100+5][100+5];

for(i1 = 0------->1){

        for(i2 = 0------->1){

                for(i3 = 0------->1){

                        for(i4 = 0------->1){

                                .

                                .

                                .

                                for(in = 0------->1){

                                        T[i]={i1,i2,i3,i4,...,in};

                                }

                        }

                }

        }

}

判断T[i]是否合法以及是否可以实现。

2^100 TLE超时

2^100*100 MLE超空间

呃。。。

死得更惨呜呜呜。。。

pass

 最终答案：分析一下

 先来康康每个按钮按下啊造成的影响：

1按钮：

灯的编号  ：1   2   3   4   5

原来         ：1   1   1   1   1

第1次按下：0   0   0   0   0

第2次按下：1   1   1   1   1

第3次按下：0   0   0   0   0

可以很轻松的发现 第2次按下会还原成原来的 第3次按下和第1次按下一模一样。

也就是说：其实1按钮只有2种状态 按下或不按。

2按钮：

灯的编号  ：1   2   3   4   5

原来         ：1   1   1   1   1

第1次按下：0   1   0   1   0

第2次按下：1   1   1   1   1

第3次按下：0   1   0   1   0

2按钮也只有2种状态：按下或不按。

3按钮：

灯的编号  ：1   2   3   4   5

原来         ：1   1   1   1   1

第1次按下：1   0   1   0   1

第2次按下：1   1   1   1   1

第3次按下：1   0   1   0   1

4按钮：

灯的编号  ：1   2   3   4   5

原来         ：1   1   1   1   1

第1次按下：0   1   1   0   1

第2次按下：1   1   1   1   1

第3次按下：0   1   1   0   1

一模一样

写一下伪代码：

for(LL i=0;i<=1;i++){//1按钮
        for(LL j=0;j<=1;j++){//2按钮
            for(LL k=0;k<=1;k++){//3按钮
                for(LL l=0;l<=1;l++){//4按钮
                    判断是否可以按出。
                    模拟现在的状态。
                    判断是否符合要求。
                    合法的存入set中去。
                }
            }
        }
    }

问题来了，i+j+k+l最大也才4，C可是有一万呢！！！怎么判断是否可以按出？

先来列张表！

 让我们补一下伪代码：

for(LL i=0;i<=1;i++){//1按钮
        for(LL j=0;j<=1;j++){//2按钮
            for(LL k=0;k<=1;k++){//3按钮
                for(LL l=0;l<=1;l++){//4按钮
                   if((i+j+k+l)%2!=c%2||i+j+k+l>c) continue;
                    模拟现在的状态。
                    判断是否符合要求。
                    合法的存入set中去。
                }
            }
        }
    }

下一步：模拟现在的状态。

这一步比较简单，标记一下就行了，注意记得清零。

for(LL x=1;x<=n;x++) f[x]=true;
if(i) for(LL x=1;x<=n;x+=1) f[x]=!f[x];
if(j) for(LL x=1;x<=n;x+=2) f[x]=!f[x];
if(k) for(LL x=2;x<=n;x+=2) f[x]=!f[x];
if(l) for(LL x=1;x<=n;x+=3) f[x]=!f[x];

 那么， 如何判断是否符合要求。

首先，用open[]和close[]标记开关，再依次判断，顺便存一下答案

再用insert()存入set中去。

现在，代码变成了这样：

 scanf("%lld%lld",&n,&c);
    while(cin>>x&&x!=-1) open[x]=true;
    while(cin>>x&&x!=-1) close[x]=true;
    for(LL i=0;i<=1;i++){
        for(LL j=0;j<=1;j++){
            for(LL k=0;k<=1;k++){
                for(LL l=0;l<=1;l++){
                    if((i+j+k+l)%2!=c%2||i+j+k+l>c) continue;
                    for(LL x=1;x<=n;x++) f[x]=true;
                    if(i) for(LL x=1;x<=n;x+=1) f[x]=!f[x];
                    if(j) for(LL x=1;x<=n;x+=2) f[x]=!f[x];
                    if(k) for(LL x=2;x<=n;x+=2) f[x]=!f[x];
                    if(l) for(LL x=1;x<=n;x+=3) f[x]=!f[x];
                    bool ok=true;
                    string ans="";
                    for(LL x=1;x<=n;x++){
                        if(open[x]&&!f[x]||close[x]&&f[x]) ok=false;
                        ans.push_back(f[x]+'0');
                    }
                    if(ok) se.insert(ans);
                }
            }
        }
    }

时间复杂度是O(1600),根本不存在TLE的问题。

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,c,x;
bool open[110],close[110],f[110];
set<string> se;
set<string>::iterator it;
int main(){
	scanf("%lld%lld",&n,&c);
	while(cin>>x&&x!=-1) open[x]=true;
	while(cin>>x&&x!=-1) close[x]=true;
	for(LL i=0;i<=1;i++){
		for(LL j=0;j<=1;j++){
			for(LL k=0;k<=1;k++){
				for(LL l=0;l<=1;l++){
					if((i+j+k+l)%2!=c%2||i+j+k+l>c) continue;
					for(LL x=1;x<=n;x++) f[x]=true;
					if(i) for(LL x=1;x<=n;x+=1) f[x]=!f[x];
					if(j) for(LL x=1;x<=n;x+=2) f[x]=!f[x];
					if(k) for(LL x=2;x<=n;x+=2) f[x]=!f[x];
					if(l) for(LL x=1;x<=n;x+=3) f[x]=!f[x];
					bool ok=true;
					string ans="";
					for(LL x=1;x<=n;x++){
						if(open[x]&&!f[x]||close[x]&&f[x]) ok=false;
						ans.push_back(f[x]+'0');
					}
					if(ok) se.insert(ans);
				}
			}
		}
	}
	if(se.empty()) printf("IMPOSSIBLE");
	else{
		for(it=se.begin();it!=se.end();it++) cout<<*it<<endl;
	}
	return 0;
}

评测记录

 

 创作不易，点个赞再走吧🥰🥰🥰


http://www.kler.cn/a/414723.html

相关文章：

  • linux内核读写硬盘文件 kernel_writekernel_read
  • 【爬虫框架：feapder，管理系统 feaplat】
  • Linux 内核 调用堆栈打印函数
  • 如何在Python中进行数学建模？
  • unity 绿幕抠图
  • 多输入多输出 | Matlab实现TCN-LSTM时间卷积神经网络结合长短期记忆神经网络多输入多输出预测
  • DVWA 在 Windows 环境下的部署指南
  • C++设计模式行为模式———状态模式
  • npm库xss依赖的使用方法和vue3 中Web富文本编辑器 wangeditor 使用xss库解决 XSS 攻击的方法
  • ASP.NET Core 入门
  • Linux：文件管理（二）——文件缓冲区
  • DVWA靶场——File Inclusion
  • Linux笔记--基于OCRmyPDF将扫描件PDF转换为可搜索的PDF
  • 大语言模型LLM的微调中 QA 转换的小工具 xlsx2json.py
  • C++语法·叭
  • 气膜建筑：打造全天候安全作业空间，提升工程建设效率—轻空间
  • BERT的中文问答系统46网页页面
  • Spring Boot教程之九：创建基本应用程序及Hello Word示例
  • MIG IP核详解（二）
  • 【菜笔cf刷题日常-1400】C. Johnny and Another Rating Drop（位运算，数学）
  • 【Git】Git 完全指南：从入门到精通
  • 记录QT5迁移到QT6.8上的一些问题
  • vscode配置
  • 淘宝商品信息获取：Python爬虫技术的实际应用
  • Spring Boot的理解
  • 适用于学校、医院等低压用电场所的智能安全配电装置