Tag Archives: 枚举

CF 287A(IQ Test-枚举3个字符相等的矩阵)

Posted on by
A. IQ Test
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

In the city of Ultima Thule job applicants are often offered an IQ test.

The test is as follows: the person gets a piece of squared paper with a 4 × 4 square painted on it. Some of the square's cells are painted black and others are painted
white. Your task is to repaint at most one cell the other color so that the picture has a 2 × 2 square,
completely consisting of cells of the same color. If the initial picture already has such a square, the person should just say so and the test will be completed.

Your task is to write a program that determines whether it is possible to pass the test. You cannot pass the test if either repainting any cell or no action doesn't result in a 2 × 2 square,
consisting of cells of the same color.

Input

Four lines contain four characters each: the j-th character of the i-th
line equals "." if the cell in the i-th row and the j-th
column of the square is painted white, and "#", if the cell is black.

Output

Print "YES" (without the quotes), if the test can be passed and "NO"
(without the quotes) otherwise.

Sample test(s)
input
####
.#..
####
....
output
YES
input
####
....
####
....
output
NO
Note

In the first test sample it is enough to repaint the first cell in the second row. After such repainting the required 2 × 2 square is on the intersection of the 1-st
and 2-nd row with the 1-st and 2-nd
column.

枚举看是否有一个矩形有3个字符相等
一开始居然把4个判断打错了？《上午也是……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
using namespace std;
#define MAXLen (4+10)
char a[MAXLen][MAXLen];
bool flag=0;
int main()
{
	for (int i=1;i<=4;i++) scanf("%s",a[i]+1);
	for (int i=1;i<4;i++)
		for (int j=1;j<4;j++)
		{
			if (a[i][j]==a[i][j+1]&&a[i][j]==a[i+1][j]) flag=1;
			if (a[i][j]==a[i][j+1]&&a[i][j]==a[i+1][j+1]) flag=1;
			if (a[i][j]==a[i+1][j]&&a[i][j]==a[i+1][j+1]) flag=1;
			if (a[i+1][j]==a[i][j+1]&&a[i+1][j]==a[i+1][j+1]) flag=1;

		}
	if (flag) printf("YESn");
	else printf("NOn");
	return 0;
}

fzu_noip 1039(盖楼-线段树)

Posted on by

盖楼

时限：1s内存：32M

★问题描述:

S举办了一场盖楼比赛，有n位选手参赛，将这n位选手编号为1到n。比赛刚开始时第i位选手的房子的初始高度为Ai，每过一天该选手的房子高度增加Bi。S想知道比赛开始后T天编号为L到R的选手中，造的最高的房子高度为多少。

★数据输入：

输入数据的第一行为两个整数N，Q。(1<=N，Q<=30000)。接下来N行，表示每个选手的初始房子高度和房子每天增长高度，每行两个数Ai,Bi（1<=Ai,Bi<=10^9）。接下来Q行，表示Q个询问，每行3个数Li，Ri，Ti(1<=Li<=Ri<=N,0<=Ti<=1000000)。所有输入都是整数。

★结果输出:

对于每个询问输出一行一个整数,表示比赛开始后Ti天编号为Li到Ri的选手中造的房子的最大高度。

 

输入示例

输出示例

5 4

4 1

3 5

6 2

3 5

6 5

1 5 2

1 3 5

1 1 0

1 5 0

16

28

4

6

5 4

6 1

5 1

2 5

4 3

6 1

2 4 1

3 4 5

1 4 5

1 2 0

7

27

27

6

 

本来是半平面交+线段树合并（归并合并），暴力居然能过


const
   maxn=30000;
var
   n,q,i,j,l,r,p,t:longint;
   a,b:array[1..maxn] of longint;
begin
   read(n,q);
   for i:=1 to n do read(a[i],b[i]);
   for i:=1 to q do
   begin
      read(l,r,t);
      p:=b[l]*t+a[l];
      for j:=l+1 to r do
         if (p<b[j]*t+a[j]) then p:=b[j]*t+a[j];
      writeln(p);
   end;
end.

BZOJ 1028（n小于100时的枚举）

Posted on by

1028: [JSOI2007]麻将

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 330  Solved: 141
[Submit][Status][Discuss]

Description

麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌（共有东、南、西、北、中、发、白七种）和序数牌（分为条子、饼子、万子三种花色，每种花色各有一到九的九种牌），每种牌各四张。在麻将中，通常情况下一组和了的牌（即完成的牌）由十四张牌组成。十四张牌中的两张组成对子（即完全相同的两张牌），剩余的十二张组成三张一组的四组，每一组须为顺子（即同花色且序数相连的序数牌，例如条子的三、四、五）或者是刻子（即完全相同的三张牌）。一组听牌的牌是指一组十三张牌，且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。 　　
在这里，我们考虑一种特殊的麻将。在这种特殊的麻将里，没有字牌，花色也只有一种。但是，序数不被限制在一到九的范围内，而是在1到n的范围内。同时，也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成，其中两张组成对子，其余3m张组成三张一组的m组，每组须为顺子或刻子。现给出一组3m + 1张的牌，要求判断该组牌是否为听牌（即还差一张就可以和牌）。如果是的话，输出所有可能的等待牌。

Input

包含两行。 第一行包含两个由空格隔开整数n, m (9<=n<=400, 4<=m<=1000)。第二行包含3m + 1个由空格隔开整数，每个数均在范围1到n之内。这些数代表要求判断听牌的牌的序数。

Output

输出为一行。 如果该组牌为听牌，则输出所有的可能的等待牌的序数，数字之间用一个空格隔开。所有的序数必须按从小到大的顺序输出。如果该组牌不是听牌，则输出"NO"。

Sample Input

9 4

1 1 2 2 3 3 5 5 5 7 8 8 8



Sample Output

6 7 9

HINT

Source

解决方案
先枚举等待牌，再枚举对子，最后计数所有的3个1组
显然如果一个结点开始有3个顺子
--------------X3
那么它等价于


X3    X3    X3
所以只要向后枚举（优先贪前面的），知道有取不尽（即需要多取导致-1的）跳出即可。

Program majiang;
const
   maxn=410;
   maxm=1010;
var
   n,m,i,j,k,p:longint;
   a:array[1..maxn] of longint;
   a2:array[1..maxn] of longint;
   flag:boolean;
function check(x:longint):boolean;
var
   i,j:longint;
begin
   fillchar(a2,sizeof(a2),0);
   for i:=1 to n do a2[i]:=a[i];
   for i:=1 to n do
   begin
      if (a2[i]>=2) then
      begin
         dec(a2[i],2);
         for j:=1 to n+2 do
         begin
            if a2[j]<0 then break;
            if a2[j]=0 then continue;
            a2[j]:=a2[j] mod 3;
            if a2[j]>0 then
            begin
               dec(a2[j+1],a2[j]);
               dec(a2[j+2],a2[j]);
               a2[j]:=0;
            end;
         end;
         if (a2[j]=0) and (j=n+2) then exit(true);

         fillchar(a2,sizeof(a2),0);
         for j:=1 to n do a2[j]:=a[j];

      end;
   end;
   exit(false);
end;
begin
   read(n,m);
   fillchar(a,sizeof(a),0);
   for i:=1 to 3*m+1 do
   begin
      read(p);
      inc(a[p]);
   end;
   flag:=false;
   for i:=1 to n do
   begin
      inc(a[i]);

      if check(i) then
      begin
         if flag then write(' ') else flag:=true;
         write(i);
      end;

      dec(a[i]);
   end;

   if not(flag) then write('NO');
   writeln;

end.