枚举
important
- 搞清楚枚举什么
- 看看能否能够去除不可能的情况缩小枚举的规模
- 二进制枚举
eg.生理周期
image.png
image.png
//问题分析
//枚举什么：
/*
从第d+1天开始，枚举日子
*/
//能不能减小枚举的规模，（不是递增1的请历遍每一天）
/*
显然假如d+i 是体力高峰，那么d+i+j(0<j<23)的日子都不是体力高峰
即，体力情商双高峰，一定出现在d+i+23*k（0<= k ,k in N）的日子里,记为m
体力、情商、智商三高峰，一定出现在 m+(23*28)k的日子里
*/
//代码
# include<iostream>
using namespace std;
int solve(int p,int e,int j ,int d){
int i = d+1;
while((i-p)%23 != 0 && i<=21252){
i++;
}
while((i-e)%28 != 0 && i<=21252){
i += 23;
}
while((i-j)%33 != 0 && i<=21252){
i += 23*28;
}
if((i-p)%23==0 && (i-e)%28 == 0 && (i-j)%33==0){
return i;
}else{
return 21252;
}
}
int main(){
int p,e,i,d;
cin >> p >> e >> i >> d;
cout << "The next triple peak occurs in " << solve(p,e,i,d) << "days" << endl;
}
eg.假币问题
image.png
image.png
image.png
// 模拟实验
/*
用这些字母的含义：
标识硬币，不做重量区分
*/
//枚举什么
/*
第i枚硬币是假币————轻；重
*/
//减小规模：
/*
去除天平两边相等的所有硬币
*/
# include <iostream>
# include <cstring>
using namespace std;
char Right[3][7];//天平左边
char Left[3][7];//天平右边
char Result[3][7];//结果
bool isFake(char c,bool light){
//为了避免复制粘贴
for(int i = 0;i<3;i++) {
char *leftPoint, *rightPoint;
if (light) {
leftPoint = Left[i];
rightPoint = Right[i];
} else {
leftPoint = Right[i];
rightPoint = Left[i];
}
switch (Result[i][0])
{
case 'e':
if (!(strchr(rightPoint, c) == NULL && strchr(leftPoint, c) == NULL)) {
return false;
}
break;
case 'u':
if (strchr(rightPoint, c)== NULL) {
return false;
}
break;
case 'd':
if (strchr(leftPoint, c) == NULL) {
return false;
}
break;
}
}
return true;
}
int main(){
//读入三次称量结果
for(int i = 0;i<3;i++){
cin >> Left[i] >> Right[i] >> Result[i];
}
//历遍判断如果有一种称量结果是even 则排除这两变的所有硬币
int flag=-1;
for(int i = 0;i<3;i++){
if(Result[i][0] == 'e'){
flag = i;
break;
}
}
if(flag != -1){
char sign[12];
strcpy(sign,Right[flag]);
strcat(sign,Left[flag]);
//cout << sign << "*" << endl;
for(char c='A';c<'L';c++){
if(strchr(sign,c) == NULL){
if(isFake(c,true)){
cout << c << " is the counterfeit coin and it is light" << endl;
}else if(isFake(c,false)){
cout << c << " is the counterfeit coin and it is heavy" << endl;
}
}else{
continue;
}
}
}
//那么问题来了，如果没有even的情况，就要历遍所有。
else{
for(char c = 'A';c<'L';c++){
if(isFake(c,true)){
cout << c << " is the counterfeit coin and it is light" << endl;
}else if(isFake(c,false)){
cout << c << " is the counterfeit coin and it is heavy" << endl;
}
}
}
}
上面算法没有去除两组都是even的情况
# include <iostream>
# include <cstring>
using namespace std;
char Right[3][7];//天平左边
char Left[3][7];//天平右边
char Result[3][7];//结果
bool isFake(char c,bool light){
//为了避免复制粘贴
for(int i = 0;i<3;i++) {
char *leftPoint, *rightPoint;
if (light) {
leftPoint = Left[i];
rightPoint = Right[i];
} else {
leftPoint = Right[i];
rightPoint = Left[i];
}
switch (Result[i][0])
{
case 'e':
if (!(strchr(rightPoint, c) == NULL && strchr(leftPoint, c) == NULL)) {
return false;
}
break;
case 'u':
if (strchr(rightPoint, c)== NULL) {
return false;
}
break;
case 'd':
if (strchr(leftPoint, c) == NULL) {
return false;
}
break;
}
}
return true;
}
int main(){
//读入三次称量结果
for(int i = 0;i<3;i++){
cin >> Left[i] >> Right[i] >> Result[i];
}
//历遍判断如果有一种称量结果是even 则排除这两变的所有硬币
int flag[3]={-1,-1,-1};
int k = 0;
for(int i = 0;i<3;i++){
if(Result[i][0] == 'e'){
flag[i] = i;
k = 1;
}
}
if(k){
char sign[12];
int ord;
for(int i = 0;i<3;i++){
if(flag[i] != -1) {
strcpy(sign, Left[i]);
strcat(sign, Right[i]);
ord = i;
break;
}
}
//当有多组even的情况
for(int j = ord+1;j<3;j++){
if(flag[j] != -1){
char budget[12];
int i = 0;
while(sign[i] != '\0'){
budget[sign[i]-'A'] = sign[i];
i++;
}
i = 0;
while(Right[j][i] != '\0' ){
budget[Right[j][i]-'A'] = Right[j][i];
i++;
}
i = 0;
while(Left[j][i] != '\0' ){
budget[Left[j][i]-'A'] = Left[j][i];
i++;
}
int sign_i =0;
for(int order = 0;order <12;order++){
if (budget[order] != '\0'){
sign[sign_i] = budget[order];
sign_i++;
}
}
sign[sign_i] ='\0';
}
}
//cout << sign << "*" << endl;
for(char c='A';c<'L';c++){
if(strchr(sign,c) == NULL){
if(isFake(c,true)){
cout << c << " is the counterfeit coin and it is light" << endl;
}else if(isFake(c,false)){
cout << c << " is the counterfeit coin and it is heavy" << endl;
}
}else{
continue;
}
}
}
//那么问题来了，如果没有even的情况，就要历遍所有。
else{
for(char c = 'A';c<'L';c++){
if(isFake(c,true)){
cout << c << " is the counterfeit coin and it is light" << endl;
}else if(isFake(c,false)){
cout << c << " is the counterfeit coin and it is heavy" << endl;
}
}
}
}
7a0dbdc5e82d8fec.png
