1.枚举

1.1 完美立方

形如a3>= b3 + c3+ d3的等式被称为完美立方等式。例如123= 63 + 83+ 103。编写一个程序，对任给的正整数N(N≤100)，寻找所有的四元组(a，b，c，d)，使得a3=b3 + c3+ d3，其中a,b,c,d 大于1，小于等于N，且b<=c<=d。

输入

一个正整数N (N≤100)。

输出

每行输出一个完美立方。输出格式为:

Cube = a，Triple = (b,c, d)，

其中a,b,c,d所在位置分别用实际求出四元组值代入。

请按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则b值小的优先输出、仍相同则c值小的优先输出、再相同则d值小的先输出。

  • 解题思路：

    四重循环枚举a,b,c,d，a在最外层，d在最里层，每一层都是从小到大枚举

    a枚举范围[2,N]
    b范围[2, a-1]

  • #include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int N;
    scanf("%d", &N);
    for (int a = 2; a <= N; ++a)
        for (int b = 2; b < a; ++b)
            for (int c = b; c < a; ++c)
                for (int d = c; d < a; ++d)
                    if (a * a * a == b * b * b + c * c * c + d * d * d)
                        printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);
    return 0;
}

1.2 生理周期

人有体力、情商、智商的高峰日子，它们分别每隔23天、28天和33天出现一次。对于每个人，我们想知道何时三个高峰落在同一天。给定三个高峰出现的日子p,e和i (不一定是第一次高峰出现的日子)，再给定另一个指定的日子d，你的任务是输出日子d之后，下一次三个高峰落在同一天的日子(用距离d的天数表示)。例如:给定日子为10，下次出现三个高峰同一天的日子是12，则输出2。

输入

四个整数: p，e，i和d。p， e，i分别表示体力、情感和
智力高峰出现的日子。d是给定的日子，可能小于p，e或i。所有给定日子是非负的并且小于或等于365，所求的日子小于或等于21252。

输出

从给定日子起，下一次三个高峰同一天的日子的天数)。

  • 解题思路

从d+1天开始，一直试到第21252天，对其中每个日期k,看是否满足(k-p)%23 ==0&&(k-e)%28 ==0 &&(k-i)%33== 0

如何试得更快?

找到一个周期后，寻找下一个周期每次枚举增加的天数为已找到的周期（的最小公倍数）。

  • #include <iostream>
#include <cstdio>
using namespace std;
#define N 21252
int main()
{
    int p, e, i, d, caseNo = 0;
    while (cin >> p >> e >> i >> d && p != -1)
    {
        ++caseNo;
        int k;
        for (k = d + 1; (k - p) % 23; ++k);
        for (; (k - e) % 28; k += 23);
        for (; (k - i) % 33; k += 23 * 28);
        cout << "Case "<< caseNo <<" : the next triple peak occurs in "<< k-d <<"";
    }
    return 0;
}

1.3 称硬币

有12枚硬币。其中有11枚真币和1枚假币。假币和真币重量不同，但不知道假币比真币轻还是重。现在,用一架天平称了这些币三次，告诉你称的结果，请你找出假币并且确定假币是轻是重(数据保证一定能找出来)。

输入

1 注意:天平左右的硬币数总是相等的,这里的up/down指右边翘起/下沉

ABCD EFGH even

ABCI EFJK up

ABIJ EFGH even

输出

K is the counterfeit coin and it is light.

  • 解题思路
    对于每一枚硬币先假设它是轻的，看这样是否符合，称量结果。如果符合，问题即解决。如果不符合，就假设它是重的，看是否符合称量结果。把所有硬币都试一遍，一定能找到特殊硬币。

    如何判断一个假设结果为真？

  • #include <iostream>
#include <cstring>
using namespace std;
char Left[3][7];   //天 平左边硬币
char Right[3][7];  //天 平右边硬币
char result[3][7]; //结果
bool IsFake(char c, bool light);
//light为真表示假设假币为轻，否则表示假设假币为重

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        for (int i = 0; i < 3; ++i)
            cin >> Left[i] >> Right[i] >> result[i];
        for (char C = 'A'; C <= 'L'; C++)
        {
            if (IsFake(C, true))
            {
                cout << C << " is the counterfeit coin and it is light.\n";
                break;
            }
            else if (IsFake(C, false))
            {
                cout << C < < < " is the counterfeit coin and it is heavy. \n";
                break;
            }
        }
    }
}

bool IsFake(char c, bool light)
//light为真表示假设假币为轻，否则表示假设假币为重
{
    for (int i = 0; i < 3; ++i)
    {
        char *
            pLeft,
            *pRight; //指向天平两边的字符串
        if (light)
        {
            pLeft = Left[i];
            pRight = Right[i];
        }

        else
        { // 如果假设假币是重的，则把称量结果左右对换
            pLeft = Right[i];
            pRight = Left[i];
        }
        switch (result[i][0])
        { //天平右边的情况
        case 'u':
            if (strchr(pRight, c) == NULL)//天平右边翘起说明为轻的假币在右边
                return false;
            break;
        case 'e':
            if (strchr(pLeft, c) == strchr(pRight, c))//天平平衡翘起说明为轻的假币左右两边都不能在
                return false;
            break;
        case 'd':
            if (strchr(pLeft, c) == NULL)//天平右边下沉说明为轻的假币在左边
                return false;
            break;
        }
    }
    return true;
}

1.4 熄灯问题(一)

有一个由按钮组成的矩阵，其中每行有6个按钮，共5行每个按钮的位置上有一盏灯
当按下一个按钮后，该按钮以及周围位置(上边，下边,左边，右边)的灯都会改变状态

-如果灯原来是点亮的，就会被熄灭

-如果灯原来是熄灭的，则会被点亮

在矩阵角上的按钮改变3盏灯的状态

在矩阵边上的按钮改变4盏灯的状态.

其他的按钮改变5盏灯的状态

与一盏灯毗邻的多个按钮被按下时,一个操作会抵消另一次操作的结果给定矩阵中每盏灯的初始状态，求一种按按钮方案，使得所有的灯都熄灭。

输入

-第一行是一个正整数N,表示需要解决的案例数

-每个案例由5行组成，每一行包括6个数字

-这些数字以空格隔开，可以是0或1

-0表示灯的初始状态是熄灭的

-1表示灯的初始状态是点亮的

输出

-对每个案例，首先输出一行,输出字符串“PUZZLE #m”,其中m是该案例的序号

-接着按照该案例的输入格式输出5行

-1表示需要把对应的按钮按下

-0表示不需要按对应的按钮

-每个数字以一个空格隔开

  • 解题思路

    第2次按下同一个按钮时,将抵消第1次按下时所产生的结果→每个按钮最多只需要按下一次

    第一想法:枚举所有可能的按钮(开关)状态，对每个状态计算一下最后灯的情况，看是否都熄灭，每个按钮有两种状态(按下或不按下)，一共有30个开关，那么状态数是230,太多，会超时。

    如何减少枚举的状态数目呢?

    基本思路:如果存在某个局部，一旦这个局部的状态被确定，那么剩余其他部分的状态只能是确定的一种，或者不多的n种，那么就只需枚举这个局部的状态即可。

    经过观察，发现第1行就是这样的一个“ 局部”
    -因为第1行的各开关状态确定的情况下，这些开关作用过后，将导致第1行某些灯是亮的，某些灯是灭的
    -要熄灭第1行某个亮着的灯(假设位于第i列)，那么唯一的办法就是按下第2行第i列的开关
    (因为第1行的开关已经用过了，而第3行及其后的开关不会影响到第1行)

    -为了使第1行的灯全部熄灭，第2行的合理开关状态就是唯一-的

    有没有状态数更少的做法？

    枚举第一列，状态数是2的5次方=32

    #include <memory>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
char oriLights[5];
char lights[5] ;
char result[5] ;
int GetBit (char c,int i){//取c的第i位
    return(c>>i)&1;
}
void SetBit(char &c,int i ,int v){//c的第i位置为v
    if(v)c|=(1<<i);
    else c&=~(1<<i);
}
void FlipBit(char &c,int i){//c的第i位反转
    c^=(1<<i);
}
void OutputResult(int t,char result[]){
    cout<<"PUZZLE #"<<t<<endl;
    for(int i=0;i<5;++i){
        for(int j;j<6;++j){
            cout<<GetBit(result[i],j);
            if(j<5)cout<<" ";
            else cout<<endl;
        }
    }
}
int main(){
    int T;
    for(int t=1;t<=T;++t){
        for(int i=0;i<5;++i)
            for(int j=0;j<6;++j){
                int s;
                cin>>s;
                SetBit(oriLights[i],j,s);
        }
        for(int n=0;n<64;++n){
            int switchs=n;
            memcpy(lights,oriLights,sizeof(oriLights));
            fot(int i=0;i<5;++i){
                result[i]=switchs;//第i行的状态存进result
                for(j=0;j<6;++j){
                    if(GetBit(switchs,j)){
                        if(j>0)FlipBit(Lighis[i],j-1);
                        FlipBit(lights[i],j);
                        if(j<5)FlipBit(lights[i],j+1);
                    }
                }
                if(i<5)
                    lights[i+1]^=switchs;//下一行的灯的状态用异或即可确定
                switchs=lights[i];
            }
            if(lights[4]==0){//最后一行全被熄灭表示成功
                OutputResult(t,result);
                break;
            }
        }
    }
    return 0;
}