[USACO]Party Lamps

事实上,每个开关按偶数次的时候,相当于没按。整道题的思路就是按照这个来的。


/*
ID :
LANG: C++11
TASK: lamps
 */

#include iostream
#include algorithm
#include cstring
#include cstdio
#include cstdlib
#include string
#include set

using namespace std;

int N, C;

int lampsTarget[110] = {}, lamps[110] = {};
int switchEffect[4][110] = {};
setstring lampsAns;

//初始化,分别初始化每个开关作用的灯,将目标状态置为-1,意思是灯开或者关无所谓
void init(){
    for (int i = 1; i = N; i ++){
        switchEffect[0][i] = 1;
    }
    for (int i = 0; i  (N + 1) / 2; i ++){
        switchEffect[1][2 * i + 1] = 1;
    }
    for (int i = 1; i = N / 2; i ++){
        switchEffect[2][2 * i] = 1;
    }
    for (int i = 0; i  (N + 2) / 3; i ++){
        switchEffect[3][3 * i + 1] = 1;
    }
    for (int i = 1; i = N; i ++){
        lampsTarget[i] = -1;
    }
}

//灯状态是否与要求一致
bool fit(){
    for (int i = 1; i = N; i ++){
        if (lampsTarget[i] == -1)
            continue;
        if (lampsTarget[i] != lamps[i])
            return false;
    }
    return true;
}

//设置灯全亮
void setlamps(){
    for (int i = 1; i = N; i ++)
        lamps[i] = 1;
}

//按下开关s
inline void pressSwitch(int s){
    for (int i = 1; i = N; i ++){
        lamps[i] = (lamps[i] + switchEffect[s][i]) % 2;
    }
}

//将结果变成string
inline string itos(){
    char c[110] = {};
    for (int i = 0; i  N; i ++){
        c[i] = lamps[i + 1] + '0';
    }
    return string(c);
}

//枚举开关的状态
void switches(){
    if ((C - 1) % 2 == 0){  //奇数个开关次数
        if (C = 1) {   //枚举,某个开关按了一次的情况
            for (int i = 0; i  4; i++) {
                setlamps();
                pressSwitch(i);
                if (fit()) {
                    lampsAns.insert(itos());
                }
            }
        }
        if (C = 3){    //枚举,某三个开关按了一次的情况
            for (int i = 0; i  4; i ++){
                setlamps();
                for (int j = 0; j  4; j ++){
                    if (j == i)
                        continue;
                    pressSwitch(j);
                }
                if (fit()){
                    lampsAns.insert(itos());
                }
            }
        }
    }
    if (C % 2 == 0){    //开关次数是偶数
        //全部开关都开合了偶数次,即相当于未改变灯的状态的情况
        setlamps();
        if (fit())
            lampsAns.insert(itos());
        if (C = 2) {   //按了两个开关
            for (int i = 0; i  3; i++) {
                for (int j = i + 1; j  4; j++) {
                    setlamps();
                    pressSwitch(i);
                    pressSwitch(j);
                    if (fit()) {
                        lampsAns.insert(itos());
                    }
                }
            }
        }
        if (C = 4){    //按了四个开关
            setlamps();
            for (int i = 0; i  4; i ++){
                pressSwitch(i);
            }
            if (fit()){
                lampsAns.insert(itos());
            }
        }
    }
}

int main()
{
    freopen("lamps.in", "r", stdin);
    freopen("lamps.out", "w", stdout);

    cin  N  C;

    init();
    int t;
    while (cin  t){
        if (t != -1)
            lampsTarget[t] = 1;
        else
            break;
    }
    while (cin  t){
        if (t != -1)
            lampsTarget[t] = 0;
        else
            break;
    }

    switches();

    setstring::iterator it;
    for (it = lampsAns.begin(); it != lampsAns.end(); it ++){
        cout  *it  endl;
    }
    if (lampsAns.empty()){
        cout  "IMPOSSIBLE"  endl;
    }
    return 0;
}

最新回复(0)
/jishumS8qC4il0JWDIwom3nqNB8ED7zN8_2FbnSQvemtFXOuTU_3D4858416
8 简首页