英文原题 中文题译
题目大意:
一组灯,几个按钮,按一个按钮可以改变若干灯的开关状态。给定按按钮的计数次数和最终状态中若干个灯的状态,要求求出所有可能状态。
每个灯只有两个状态:开/关。每个按钮如果按两次就会恢复原样。因此,按钮计数器C实际上只有最多4次有效。对C>4,枚举每个按钮的开关状态,一共2^4=16个状态,检查是否与目标状态吻合,即可得解。
需要注意之处:枚举按钮动作之后判断是否符合计数器要求用两个条件,一是按键次数二是奇偶性。
调试时发现一个错:memset( lamps, 1, sizeof(int)*n_lamp );试图把lamps初始化为1,但结果是0x01010101,因为memset是按byte操作的而lamps是整数值。另外,对静态二维数组排序,需要用指针排,或者,将内部一维数组声明成结构,不过不用指针排的话copy操作耗时(在这里倒是可以忽略不计)。
题目大意:
一组灯,几个按钮,按一个按钮可以改变若干灯的开关状态。给定按按钮的计数次数和最终状态中若干个灯的状态,要求求出所有可能状态。
每个灯只有两个状态:开/关。每个按钮如果按两次就会恢复原样。因此,按钮计数器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; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 886英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1133英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1849郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1645英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1195英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 968英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1066英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1405英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 772英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 799英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 971英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1207英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 916英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1094英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 772英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1232英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1046英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 930英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1307英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 868英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ...
相关推荐
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
[USACO 1.1.4]破碎的项链.cpp
2.2 Section 2.2 2.3 Section 2.3 2.4 Section 2.4 3 Chapter3 3.1 Section 3.1 3.2 Section 3.2 3.3 Section 3.3 3.4 Section 3.4 4 Chapter4 4.1 Section 4.1 4.2 Section 4.2 4.3 Section 4.3 4.4 Section 4.4 5 ...
USACO全部译题 USACO Training Program Gateway
USACO_培训USACO_培训Ride.java-> Gift1.java->
USACO training 教程翻译合集(清晰明确)
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
One of the answer of the USACO training exercises.
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO题集及答案
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案