ACM入门教程-枚举_acm枚举

写在前面

枚举是最为入门的一种算法，其思想是把所有状态都列举一遍然后寻找想要的答案，这种算法利用了计算机高速计算的特点，也就是我们也常常把枚举称为暴力算法，它的正确性显而易见，后续的其余算法常常是基于暴力枚举上的优化，如：前缀和、二分等。所以掌握枚举的思维对于入门的新手来说是至关重要的。

半平面交

Problem Description

所谓半平面就是一个二元一次不等式，形如：ax+by<c。或者是大于、小于等于、大于等于。
给定2个一元二次不等式：
ax+by<c
dx+ey>f
求范围x,y∈[0,1000]范围内有多少组（x,y）满足上面两个不等式。（x,y都是整数）

Input

输入多组测试数据，每行是6个整数分别表示a,b,c,d,e,f。范围均在-1000-1000之间。输入多组测试数据，每行是6个整数分别表示a,b,c,d,e,f。

Output

每组测试数据输出一个整数表示答案。

SampleInput

1 1 100 5 5 0
1 1 2001 5 5 -1

SampleOutput

5049
1002001

思路分析

这道题目给定了6个常数然后再给定条件，唯一变化的量x，y也给出了范围，直观上我们就会尝试每个（x，y）进行判断，直到遍历完所有组合后我们就可以得到答案，这种算法的核心就是两重循环进行（x，y）的枚举，时间复杂度为O（n²）时间上可行。

#include<stdio.h>
int main()
{
    int a,b,c,d,e,f,x,y,ans;
    while(~scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f))
    {
        ans=0;
        for(x=0;x<=1000;x++)
            for (y=0;y<=1000;y++)
                if(a*x+b*y<c&&d*x+e*y>f)ans++;
        printf("%d\n",ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

水仙花数

Problem Description

春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的：
“水仙花数”是指一个三位数，它的各位数字的立方和等于其本身，比如：153=1³⁺⁵3+3^3。
现在要求输出所有在m和n范围内的水仙花数。

Input

输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999）。

Output

对于每个测试实例，要求输出所有在给定范围内的水仙花数，就是说，输出的水仙花数必须大于等于m,并且小于等于n，如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开;
如果给定的范围内不存在水仙花数，则输出no;
每个测试实例的输出占一行。

SampleInput

100 120
300 380

SampleOutput

no
370 371
no
370 371

思路分析

这题主要考察大家懂不懂得怎么分离一个数字得每一位数，掌握好这个知识点即可。

# include<stdio.h>
int main()
{
    int a,b,c,d,e,f,m,n;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        m=0,n=0;
        for(c=a;c<=b;c++)
        {
            d=c%10;
            e=c/10%10;
            f=c/100%10;
            if(d*d*d+e*e*e+f*f*f==c)
            {
                if((m++)==0)printf("%d",c);
                else printf(" %d",c);
            }
        }
        if (m>0) printf("\n");
        else if (m==0) printf("no\n");

    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Help Pupil

Problem Description

你家有个熊孩子，他上小学了！但是他不会做这样的题目，让你帮帮忙！！！！！！（太熊了，还是别帮了吧）

如下图：

在方块内填入1-9这9个数字（每个数字最多用一次），使得每行，每列，每对角线的和等于给定的数字。

Input

输入6个整数r1, r2, c1, c2, d1, d2  (1 ≤ r1, r2, c1, c2, d1, d2 ≤ 20).意义如下图所示

Output

输出方格内的四个数字。如果没有答案输出"-1"

如果有多种结果，输出任意一种

SampleInput

3 7
4 6
5 5

SampleOutput

1 2
3 4

思路分析

我们将格子从左到右从上到下依次标号为num1-4，显然对于每一行，每一列与每一个对角线都有限制条件，这也意味着，当第一个格子数确定后对于格子2也确定答案了，它的值必须为r1-num1同理我们可以得到 num3=c1-r1 num4=d1-r1，所以我们可以发现对于每一个num1，其它三个格子都是唯一确定的，那么我们就判断这三个格子的数能否满足其它条件，以及判断数字是否重复使用 即可。

#include<bits/stdc++.h>
using namespace std;
int num[3][3],book[15];//book数组标记数字是否被使用过。
int main()
{
    int r1,r2,c1,c2,d1,d2;
    cin>>r1>>r2>>c1>>c2>>d1>>d2;
    int flag=0;
    for(int i=1;i<=9;i++)
    {
        memset(book,0,sizeof(book));
        book[i]=1;
        num[1][1]=i;
       if(r1-i>=1&&r1-i<=9&&book[r1-i]==0)num[1][2]=r1-i,book[r1-i]=1;
       else continue;
       if(c1-i>=1&&c1-i<=9&&book[c1-i]==0)num[2][1]=c1-i,book[c1-i]=1;
       else continue;
       if(r2-num[2][1]>=1&&r2-num[2][1]<=9&&book[r2-num[2][1]]==0)num[2][2]=r2-num[2][1],book[r2-num[2][1]]=1;
       else continue;

       if(c2==num[2][2]+num[1][2]&&d1==num[1][1]+num[2][2]&&d2==num[1][2]+num[2][1])
       {
           flag=1;
           break;
       }
    }
    if(flag)
        for(int i=1;i<3;i++)
    {
         for(int j=1;j<3;j++)
            cout<<num[i][j]<<" ";
         cout<<endl;
    }
    else cout<<-1<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

区间回文数

Problem Description

给两个长度为9的数字l和r，求l和r之间的回文数的个数有多少。

Input

多组输入。每组输入两个长度为9的数字l和r 1e8<=l<=r<1e9

Output

每组输出区间回文数的个数

SampleInput

100000000 100000011

SampleOutput

1
hint:区间只有一个回文数100000001

思路分析

常见的枚举有两种思路，一是枚举范围，二是构造可行解，上面我们用到的方法都是方法一，这一题显然用方法一算法正确性是可行的，只需要根据回文串的特点来判断每一个数字是不是回文数字即可，但是由于题目的数据范围最大会到9e8级别，显然会超时，这道题目的数据很有意思的一点是1e8<=l<=r<1e9，这也意味着它是一个9位数，既然如此我们可以尝试构造答案，当第一位为a时显然第九位也要为a，同理我们可以得到这样一个结构abcdedcba，我们发现只要枚举前面五个数字就可以确定一个可行的回文数字，只要判断它的大小是否在m和n之间即可，在时间复杂度上对于第一位来说取值有9种（不能为0）其它四个数字有10种（910101010）=1e5显然可行。

#include<stdio.h>
#include<math.h>
int main()
{
	long long n,m;
	long long sum;
	while(~scanf("%lld %lld",&n,&m))
	{
		int cnt=0;
		for(int a=1;a<=9;a++)
			for(int b=0;b<=9;b++)
				for(int c=0;c<=9;c++)
					for(int d=0;d<=9;d++)
						for(int e=0;e<=9;e++)
						{
							sum=a*100000000+b*10000000+c*1000000+d*100000+e*10000+d*1000+c*100+b*10+a;
							if(sum>=n&&sum<=m)  
							{
								cnt++;
							}
						}
	printf("%d\n",cnt);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

AC的故事大结局喜剧版（上）

Problem Description

预知前两季故事请回顾第一季剧情，第二季剧情)

上集说到小C被强行劫走，小A被打晕在路边（PS：不知道是罪犯以为小A挂了没有补刀，还是罪犯胆子太小不敢）。

第二天，小A在医院里醒来，原来是有人看见他并报了警。小A想，自己手无寸铁，对这个事情也毫无头绪，只好求助于警方。

警方通过调查监控发现劫走小C的人是开着一辆面包车，冲散了他们俩，然后劫走小C的。之后跟踪面包车，发现他们进入了一栋大楼，大楼足足有9层楼高！随后调出电梯的画面，发现他们正是坐电梯上楼去的！

然而电梯的显示楼层的LED屏幕居然坏掉了！LED由7个小灯组合而成，如下图：

其中的部分小灯坏掉了，监控画面只能看到亮了的部分小灯，并不能确定具体是哪个楼层。

虽然也可以逐层排查，但是为了避免打草惊蛇，必须一发命中，直接冲进去抓人，不然犯人恐怕有所察觉，那就大事不妙了！
小A心急如焚，可否帮忙确认犯人可能到了哪些楼层？

已知图中某些位置的小灯是点亮着的，请在1~9中筛选出犯人可能去的楼层。
每个数字的显示方式如图：

Input

先输入一个整数t（<=1000000），表示有t组数据

每组数据，有n个灯一定亮（0<=n<=7）

接着有n个整数，表示具体哪些条形灯亮着（编号）

Output

对于每组数据，从小到大输出每种可能的数字

SampleInput

2
5
1 3 4 5 7
7
1 2 3 4 5 6 7

SampleOutput

2 8
8

思路分析

这道题的难点在于状态的表示上，但是这道题的状态显然是有限的，并且我们可以知道1-9的的表示方法，那就先手敲（也称之为打表），然后再依次判断就可以了

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int num[10][10] = { {0,0,1,0,0,1,0},{1,0,1,1,1,0,1},{1,0,1,1,0,1,1},{0,1,1,1,0,1,0},{1,1,0,1,0,1,1},{1,1,0,1,1,1,1,},{1,0,1,0,0,1,0},{1,1,1,1,1,1,1,},{1,1,1,1,0,1,1} };
int book[8];
int main()
{   
	int t;
	cin >> t;
	while (t--)
	{   
		int n,ans;
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> book[i];
		for (int i =0; i <= 8; i++)
		{
			ans = 1;
			for (int j = 1; j <= n; j++)
			{
				if (num[i][book[j] - 1] == 0)
				{
					ans = 0;
					break;
				}
			}
			if (ans)cout << i + 1 << " ";
		}
		cout << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33