Tag Archives: 枚举

POJ 2965-The Pilots Brothers' refrigerator

POJ 2965-The Pilots Brothers' refrigerator
The Pilots Brothers' refrigerator
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 19188 Accepted: 7358 Special Judge
Description
The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.
There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.
The task is to determine the minimum number of handle switching necessary to open the refrigerator.
Input
The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.
Output
The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.
Sample Input
-+--
----
----
-+--
Sample Output
6
1 1
1 3
1 4
4 1
4 3
4 4
Source
Northeastern Europe 2004, Western Subregion


这一题和之前做的POJ Problem 1753: Flip Game大同小异,只是这题要求记录搜索路径,并且翻转的时候是同行同列的所有格子都翻转,对之前那题的代码稍作修改即可。
这一题要求翻转的时候是翻转和(i,j)点同行同列的所有点,我们还是通过异或来完成。比如我们要对

-+--
----
----
-+--

的(0,0)(坐标从0开始)及其行列翻转,应该怎么办呢?
因为1^1=0,1^0=1,所以如果我们要改变某一位,只需要将该位异或1即可。又因为我们输入的时候是从左到右,从上到下的顺序,所以当我们要翻转第0行的时候,只需要异或0xf<<12,0xf<<12相当于把4个二进制1移到最左边(因为第0行在最左边),如果是翻转第i行,则异或0xf<<(4*(3-i));当我们要翻转某一列时,因为同一列的二进制位相差3个位置,所以异或值的形式为二进制0001000100010001,又因为(i,j)这个位置在行翻转的时候已经翻转过了,所以在列翻转时不能再翻转了,否则回到原状态了,所以根据行号的不同,我们可以得到不同的列异或值,分别是curr_xor=0x111,0x1011,0x1101,0x1110,列翻转的公式是next_p.val^=curr_xor<<(3-j);。这个问题用笔在纸上演算一下就会很明白了。
还有一个问题是怎样来记录搜索的路径,我的办法是开辟两个数组:

typedef struct P//翻转时的格子坐标
{
     int x,y;
};
P trace[MAX_STATUS];//trace[i]到达i状态值时翻转的某个格子坐标
int pre[MAX_STATUS];//pre[i]记录i状态的前一个状态值

pre[i]数组用来记录到达i状态时的前一个状态,而trace[i]则用来记录到达该状态时翻转的格子坐标。这样通过成功状态回溯到开始状态就可以找到所有路径了,具体实现请看下面的代码。
完整代码如下:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAX_STATUS=65536;//2^16=65536种,所以[0,65535]
const int ALL_1=65535;//全1
int visited[MAX_STATUS]={0};//访问标记
int XOR[4]={0x111,0x1011,0x1101,0x1110};//列异或值
typedef struct POS//position翻转位置
{
     int val;//当前翻转状态的值
     int step;//到当前状态共翻转了多少次
};
typedef struct P//翻转时的格子坐标
{
     int x,y;
};
P trace[MAX_STATUS];//trace[i]到达i状态值时翻转的某个格子坐标
int pre[MAX_STATUS];//pre[i]记录i状态的前一个状态值
//通过反向索引打印结果
void print_result(POS pos,int init_id)
{
     cout<<pos.step<<endl;
     vector<P> points;
     points.push_back(trace[pos.val]);
     int pre_val=pre[pos.val];
     while(pre_val!=init_id)//当没有追溯到初始状态时,一直循环
     {
          points.push_back(trace[pre_val]);
          pre_val=pre[pre_val];//追溯
     }
     int p_num=points.size();//顺着打印出来
     for(int i=p_num-1;i>=0;i--)
          cout<<points[i].x<<" "<<points[i].y<<endl;
}
//广度优先搜索
void BFS(int init_id)
{
     POS p,next_p;
     p.val=init_id;
     p.step=0;
     visited[p.val]=1;
     pre[p.val]=-1;//没有前一个状态
     queue<POS> Q_P;
     Q_P.push(p);
     while(!Q_P.empty())
     {
          p=Q_P.front();
          Q_P.pop();
          if(p.val==ALL_1)
          {
               print_result(p,init_id);
               return;
          }
          for(int i=0;i<4;i++)
          {
               int curr_xor=XOR[i];//i不同时,翻转异或的值也不同
               for(int j=0;j<4;j++)
               {
                    next_p.val=p.val;
                    next_p.val^=0xf<<(4*(3-i));//横向翻转
                    next_p.val^=curr_xor<<(3-j);//纵向翻转
                    if(visited[next_p.val]==0)
                    {
                         visited[next_p.val]=1;
                         next_p.step=p.step+1;
                         pre[next_p.val]=p.val;//记录前一个状态值
                         trace[next_p.val].x=i+1;//注意输出的坐标是从1开始到4
                         trace[next_p.val].y=j+1;//所以这里加1
                         Q_P.push(next_p);
                    }
               }
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     char c;
     int id=0;
     for(int i=0;i<4;i++)
     {
          for(int j=0;j<4;j++)
          {
               cin>>c;
               id<<=1;//id=id<<1;
               if(c=='-')//-:1;+:0
                    id+=1;
          }
     }
     BFS(id);
     return 0;
}

这个版本的代码如果以C++提交,则TLE,如果用G++提交则AC,用时625MS,内存1788K,不知道是什么原因。

POJ 1753-Flip Game

POJ 1753-Flip Game
Flip Game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 31655 Accepted: 13776
Description
Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
Choose any one of the 16 pieces.
Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
Input
The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.
Output
Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).
Sample Input
bwwb
bbwb
bwwb
bwww
Sample Output
4
Source
Northeastern Europe 2000


题意:翻动格子使得整个棋盘为全黑或者全白,求最少的翻动次数,翻动某一个格子,也会同时翻动其周围的四个格子(如果有的话)。因为某一个格子翻动2次的结果和不翻是一样的;翻动3次的结果和翻动1次的结果是一样的;多个也是一样,所以一个格子最多翻动1次,这样总的翻动次数最多为16次。每个格子有翻和不翻两种情况,所以总共有2^{16}种情况,可以暴力枚举。
但是一直没有想好用哪种方法,深度搜索还是广度搜索。后来想了想,这是求最优解(最少翻动次数)的题,所以用广度优先搜索的效率应该会高一些,但是在BFS的过程中曾有一个问题困扰了,后面再说。又因为棋盘正好是4*4=16的,可以用int的位运算来表示,b表示1,w表示0,这样棋盘的一个状态就可以用一个int数来表示,翻动格子也可以用位运算来表示,总共的状态数是2^{16},取值范围是[0,65535],当棋盘状态是0或者65535时,表示全白或者全黑,这时找到结果。
了解了这些,就可以写出BFS+位运算的代码了,这题我是参考了网上的题解

#include<iostream>
#include<queue>
using namespace std;
const int MAX_STATUS=65536;//2^16=65536种,所以[0,65535]
const int ALL_0=0;//全0
const int ALL_1=65535;//全1
int ans;
int visited[MAX_STATUS]={0};//访问标记
typedef struct POS//position翻转位置
{
     int val;//当前翻转状态的值
     int step;//到当前状态共翻转了多少次
};
//广搜
void BFS(int init_id)
{
     queue<POS> Q_P;
     POS s,next_p;
     //初始位置
     s.val=init_id;
     s.step=0;
     visited[s.val]=1;
     Q_P.push(s);
     while(!Q_P.empty())
     {
          s=Q_P.front();
          Q_P.pop();
          if(s.val==ALL_0||s.val==ALL_1)//找到结果
          {
               ans=s.step;
               return;
          }
          //尝试翻16个位置
          for(int i=0;i<4;i++)
          {
               for(int j=0;j<4;j++)
               {
                    next_p.val=s.val;
                    //测试i,翻转[i,j]上下位置的格子
                    if(i==0)
                         next_p.val^=1<<(11-4*i-j);
                    else if(i==3)
                         next_p.val^=1<<(19-4*i-j);
                    else
                    {
                         next_p.val^=1<<(11-4*i-j);
                         next_p.val^=1<<(19-4*i-j);
                    }
                    //测试j,翻转[i,j]左右位置的格子
                    if(j==0)
                         next_p.val^=3<<(14-4*i-j);
                    else if(j==3)
                         next_p.val^=3<<(15-4*i-j);
                    else
                         next_p.val^=7<<(14-4*i-j);
                    if(visited[next_p.val]==0)//如果没有访问
                    {
                         visited[next_p.val]=1;//访问
                         next_p.step=s.step+1;//翻转次数加1
                         Q_P.push(next_p);//并加入队列
                    }
               }
          }
     }
     ans=-1;//到这里还没有return,说明impossible
}
int main()
{
     //freopen("input.txt","r",stdin);
     char c;
     int id=0;
     //输入转换
  /*bwbw
     wwww
     bbwb
     bwwb
     排列成bwbw wwww bbwb bwwb,然后把b换成1,w换成0*/
     for(int i=0;i<4;i++)
     {
          for(int j=0;j<4;j++)
          {
               cin>>c;
               id<<=1;
               if(c=='b')//b=1;w=0
                    id+=1;
          }
     }
     BFS(id);
     if(ans==-1)
          cout<<"Impossible";
     else
          cout<<ans;
     return 0;
}

本代码提交AC,用时79MS,内存508K。
在每一次BFS的时候,我们都要尝试去翻所有16个格子,如果翻动之后达到了一个新的状态(也就是之前没有访问过),说明这个翻动是有效的,把它加入到队列中。在翻动的时候,怎样进行位运算大家可以把i=0,j=0代入到for循环里手算一遍,程序会根据i和j的不同,和不同的数进行异或运算。
之前我说有一个地方让我困惑,就是我之前:第一次BFS的时候肯定把所有格子都翻了一遍,也就是把(0,0)(0,1)...(3,3)翻动的结果都加入到队列中了,那么在第二次BFS的时候,把(0,0)出队,这个时候再来翻所有16个格子,这样不就相当于把所有格子又翻回到初始状态了吗?其实这种想法是不对的,说到底还是对BFS理解不够透彻。**我们在每次BFS的时候都是在队首元素的基础上翻转的,因为我们在while开头执行了s=Q_P.front();Q_P.pop();这么两句**,那么当我们把(0,0)翻转状态出队在去翻转的时候,是在(0,0)翻转状态的基础是再进行翻转的,而这个时候是只有(0,0)这一个格子翻了,其他15个格子都没有翻;同理当把(0,1)出队的时候,也是只有(0,1)翻了,其他15个都没有翻。所以这样BFS下去是能够搜索到所有状态的。
纵观所有BFS题目,套路都是一样的。

hihoCoder 1051-补提交卡

hihoCoder 1051-补提交卡
#1051 : 补提交卡
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho给自己定了一个宏伟的目标:连续100天每天坚持在hihoCoder上提交一个程序。100天过去了,小Ho查看自己的提交记录发现有N天因为贪玩忘记提交了。于是小Ho软磨硬泡、强忍着小Hi鄙视的眼神从小Hi那里要来M张"补提交卡"。每张"补提交卡"都可以补回一天的提交,将原本没有提交程序的一天变成有提交程序的一天。小Ho想知道通过利用这M张补提交卡,可以使自己的"最长连续提交天数"最多变成多少天。
输入
第一行是一个整数T(1 <= T <= 10),代表测试数据的组数。
每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, ... aN(1 <= a1 < a2 < ... < aN <= 100),表示第a1, a2, ... aN天小Ho没有提交程序。
输出
对于每组数据,输出通过使用补提交卡小Ho的最长连续提交天数最多变成多少。
样例输入
3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90
样例输出
76
59
100


这一题想到那个点上就不难了,题目要求将补提交卡插入空缺的某天中,使连续提交天数最长。要使连续提交天数最长,补提交卡插入的位置也一定要是连续的,而且很方便的是,题目中给出的空缺天数都是递增的,所以不需要重新排序了。
既然需要满足插入的位置也要连续,那么总的方案数就没有那么多了。比如n=5,m=2,有如下几种方案:

左边的红色数字表示不同方案标号,这个标号也正好是该方案中数组a中的第一个插空位置的下标。很容易得到总的方案数有n-m+1个,所以我们只需将i从0到n-m+1循环枚举每一种方案,求最长的连续提交天数。
对于某一种方案,如上所述,其插空的开始下标正好为i,因为要插m个空,所以结束下标为m+i-1。那么这两者之间总的连续提交天数怎么算呢?比如上图中的方案2,如果把第55和56天填上,那么实际的连续提交天数应该是从31~89.也就是要从i-1对应的那天的后一天(31)算起,到m+i-1-1对应的那天的前一天(89)结束,总共就是89-31+1,也就是a[m+i-1+1]-a[i-1]-1;如果遇到最后一个空,因为m+i-1+1可能超过数组a的范围,所以我们添加一个a[n]=101,俗称哨兵;如果i==0的话,没有i-1,所以分开讨论。
最终的代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     int t;
     cin>>t;
     int n,m;
     while(t--)
     {
          cin>>n>>m;
          vector<int> a(n+1);
          for(int i=0;i<n;i++)
               cin>>a[i];
          a[n]=101;//哨兵
          if(m>=n)
               cout<<100<<endl;
          else
          {
               int max_days=0;//最长连续提交天数
               int case_num=n-m+1;//总的枚举情况数
               for(int i=0;i<case_num;i++)
               {
                    int last_index=m+i-1;//该方案下最后一个下标
                    if(i==0)
                    {
                         if(a[last_index+1]-1>max_days)
                              max_days=a[last_index+1]-1;
                    }
                    else
                    {
                         if(a[last_index+1]-a[i-1]-1>max_days)
                              max_days=a[last_index+1]-a[i-1]-1;
                    }
               }
               cout<<max_days<<endl;
          }
     }
     return 0;
}

本代码提交AC,用时0MS,内存0MB。

POJ 2586-Y2K Accounting Bug

POJ 2586-Y2K Accounting Bug
Y2K Accounting Bug
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10647 Accepted: 5328
Description
Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc.
All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.
Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.
Input
Input is a sequence of lines, each containing two positive integers s and d.
Output
For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.
Sample Input
59 237
375 743
200000 849694
2500000 8000000
Sample Output
116
28
300612
Deficit
Source
Waterloo local 2000.01.29


这个题首先要读懂题意,其中的

ACM knows that each of these 8 postings reported a deficit

我一开始看不懂,不知道这个8代表什么意思,是怎么来的,看过别人的解释才知道,原来前面说每连续5个月会发布一次盈亏报告,而一年又12个月,总共可以发布8次,即:1-5,2-6,3-7,4-8,5-9,6-10,7-11,8-12。注意每次报告的月份和前后的报告的月份是有重叠的。
题目告诉我们这8次报告都是亏损,但是求这一年是否可以盈利,总的盈利最多是多少。这道题有点最优化的感觉,已知约束是8次报告都是亏损,求最优化总的盈利。
这道题可以有两种解法。
贪心
因为要求盈利最大化,所以可以先设12个月都是盈利的,然后再慢慢调整满足8次报告都是亏损的。一次报告是连续的5个月的总和,要保证一次报告是亏损,5个月里至少一个月是亏损的,亏损的月份放在5个月里的最后月份是最好的,因为这样可以和下一个报告重叠,使总的盈利最大。比如1-5使第5月份亏损,就能保证这个报告亏损,则2-6已经包含5月份了,当然这个报告肯定也亏损。这样1-5和2-6实际只有5月份是亏损的。但是如果1-5使第1月份亏损,虽然第一个报告是亏损的,但是2-6还是盈利的,又使第2月份亏损,则1-5和2-6实际有1月份和2月份是亏损的,这就亏损了两个月。
所以每次我们要亏损时,都从该报告的最后月份开始试探,一直往前试探,直到这个报告亏损。一直循环8个报告。最后求这一年总的盈亏。代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     int s,d;
     while(cin>>s>>d)
     {
          int surplus_num;//盈余的月份数
          vector<int> month(12,1);//初始的时候每个月都是surplus,1为surplus,0为deficit
          for(int i=0;i<8;i++)//8个‘连续5个月’
          {
               surplus_num=0;
               for(int j=0;j<5;j++)
                    surplus_num+=month[i+j];
               int k=0;
               while(surplus_num*s>=(5-surplus_num)*d)
               {
                    month[i+4-k]=0;//亏损的月份尽量放到后面,因为可以和下一个周期重叠,这样总的surplus会大一些
                    surplus_num=0;
                    for(int j=0;j<5;j++)
                         surplus_num+=month[i+j];
                    k++;
               }
          }
          surplus_num=0;
          for(int i=0;i<12;i++)
               surplus_num+=month[i];
          int rs=surplus_num*s-(12-surplus_num)*d;//这一年总的盈亏
          if(rs<0)
               cout<<"Deficit"<<endl;
          else
               cout<<rs<<endl;
     }
     return 0;
}

这个版本提交AC,用时32MS,内存216K。
枚举
因为这题只有12月份,每个报告只是连续5个月,要是每个报告都亏损,则可以在5个月里有1个月份亏损、2个月份亏损、3个月份亏损、4个月份亏损、5个月份亏损。前4种情况依次求解,直到既满足每个报告亏损,又使12个月总的是盈利。如果前4种都不行,那总的肯定是亏损。
这4种情况可以这样来表示,由于每5个月的报账都为亏损,所有连续的5个月里至少有1个月为亏损,则可能产生最优解的情况为如下4种

1 2 3 4 5 6 7 8 9 10 11 12
s s s s d s s s s d s s //每5个月里只有1个月亏损
s s s d d s s s d d s s //每5个月里只有2个月亏损
s s d d d s s d d d s s //每5个月里只有3个月亏损
s d d d d s d d d d s d //每5个月里只有4个月亏损

从上到下一次枚举四种情况,如果满足条件(每次报账都为亏损),则算出ans = (盈利的月数)*s - (亏损的月数)*d,若ans>0 则输出 否则输出Deficit;若上述4种情况都不满足,则直接输出Deficit.
代码如下:

#include<iostream>
using namespace std;
int main()
{
     int a,b;
     while(cin>>a>>b)
     {
          int ans = 0;
          if(4*a-b<0)
          {
               ans = 10*a-2*b;
          }
          else if(3*a-2*b<0)
          {
               ans = 8*a-4*b;
          }
          else if(2*a-3*b<0)
          {
               ans = 6*a-6*b;
          }
          else if(a-4*b<0)
          {
               ans = 3*a-9*b;
          }
          else
          {
               ans = -1;
          }
          if(ans>0)
               cout<<ans<<endl;
          else
               cout<<"Deficit"<<endl;
     }
     return 0;
}

这个版本提交AC,用时0MS,内存216K。
很显然,枚举速度更快,但是如果总共有1000个月份,每个报告20个月,共50个报告,或者数字更大时,枚举就很麻烦了,所以掌握第一种贪心的方法还是很有必要的。