欢迎来到Doc100.Net免费学习资源知识分享平台!
您的位置:首页 > 程序异常 >

usaco training section 2.2 party lamps - 山中竹笋

更新时间: 2015-05-04 00:00:00 责任编辑: Author_N15

 

英文原题  中文题译 
题目大意:
一组灯,几个按钮,按一个按钮可以改变若干灯的开关状态。给定按按钮的计数次数和最终状态中若干个灯的状态,要求求出所有可能状态。

每个灯只有两个状态:开/关。每个按钮如果按两次就会恢复原样。因此,按钮计数器C实际上只有最多4次有效。对C>4,枚举每个按钮的开关状态,一共2^4=16个状态,检查是否与目标状态吻合,即可得解。

需要注意之处:枚举按钮动作之后判断是否符合计数器要求用两个条件,一是按键次数二是奇偶性。

调试时发现一个错:memset( lamps, 1, sizeof(int)*n_lamp );试图把lamps初始化为1,但结果是0x01010101,因为memset是按byte操作的而lamps是整数值。另外,对静态二维数组排序,需要用指针排,或者,将内部一维数组声明成结构,不过不用指针排的话copy操作耗时(在这里倒是可以忽略不计)。


/*
ID: blackco3
TASK: lamps
LANG: C++
*/
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
#define _max_ 100
int lamps[_max_], final[_max_], possible[16][_max_] ;
int n_lamp, n_act, n_possible=0 ;

bool p_psb_comp( int *lamps_1, int *lamps_2 ) {
	for( int i=0; i<n_lamp; i++ )
		if( lamps_1[i] < lamps_2[i] )
			return true ;
		else if ( lamps_1[i] > lamps_2[i] )
			return false ;
	return false ;
}
void check_lamps() {
	for( int i=0 ; i<n_lamp ; i++ )
		if( final[i]!=-1 && final[i]!=lamps[i] ) 
			return ;
	memcpy( possible[n_possible++], lamps, sizeof(lamps) );
}
inline void turn_lamps( int but ) {
	for( int i=0; i<n_lamp ; i++ )
		if( !but || ( but==1 && i&1 ) || ( but==2 && !(i&1) ) || ( but==3 && !(i%3) ) )
			lamps[i] = 1-lamps[i] ;
}
void check_acts(int cur_act, int button)
{
	if( button==4 ){
		if( cur_act<=n_act && (cur_act&1)==(n_act&1) )
			check_lamps();
		return ;
	}
	check_acts(cur_act,button+1) ;
	turn_lamps( button ) ;	
	check_acts(cur_act+1,button+1);
	turn_lamps( button ) ;
}

int main() {	
	freopen("lamps.in", "r", stdin);
	freopen("lamps.out", "w", stdout);	
	cin >> n_lamp >> n_act ;
	memset( final, -1, sizeof(int)*n_lamp );
	for( int cur=-1, icount=0 ; icount<2 ; ){
		cin >> cur ;
		if( cur==-1 )
			icount++ ;
		else
			final[cur-1]=1-icount ;
	}
	for( int i=0; i<n_lamp; i++ )
		lamps[i]=1 ;
	check_acts(0,0);
	if( !n_possible )
		cout << "IMPOSSIBLE" << endl ;
	else {
		int *p_psb[16] ;
		for( int i=0; i<n_possible; i++ )
			p_psb[i]=possible[i] ;
		sort( p_psb, p_psb+n_possible, p_psb_comp );
		for( int i=0; i<n_possible; i++ ){
			for( int j=0; j<n_lamp; j++ )
				cout << p_psb[i][j] ;
			cout << endl ;
		}
	}
	return 0;
}
上一篇:上一篇
下一篇:下一篇

 

随机推荐程序问答结果

 

 

如对文章有任何疑问请提交到问题反馈,或者您对内容不满意,请您反馈给我们DOC100.NET论坛发贴求解。
DOC100.NET资源网,机器学习分类整理更新日期::2015-05-04 00:00:00
如需转载,请注明文章出处和来源网址:http://www.doc100.net/bugs/t/1773713/
本文WWW.DOC100.NET DOC100.NET版权所有。