Skip to main content

枚举

参考资料​

简介​

枚举（Enumerate）是基于已有知识来猜测答案的一种问题求解策略。

枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。

例题​

洛谷 P1217 [USACO1.5] 回文质数 Prime Palindromes

写一个程序来找出范围 [a,b][a,b] 间的所有回文质数。（5≤a<b≤100,000,0005 \le a < b \le 100,000,000）

Code (1)
#include <bits/stdc++.h>
using namespace std;

bool palindrome(int n)
{
	int x=0,y=n;
	while(n)
	{
		x=x*10+n%10;
		n/=10;
	}
	return x==y;
}
bool prime(int n)
{
	if(n<2)return 0;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)return 0;
	}
	return 1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int a,b;
	cin>>a>>b;
	for(int i=a|1;i<=b;i+=2)
	{
		if(palindrome(i)&&prime(i))cout<<i<<'\n';
	}
	return 0;
}
洛谷 P2241 统计方形（数据加强版）

有一个 n×mn \times m 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。（n≤5000,m≤5000n \leq 5000,m \leq 5000）

Code (2)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll n,m;
	cin>>n>>m;
	ll k=min(n,m),t=k*n*m-k*(k-1)/2*(n+m)+k*(k-1)*(k*2-1)/6;
	cout<<t<<' '<<n*(n+1)/2*m*(m+1)/2-t<<'\n';
	return 0;
}