爆搜出奇迹,就是TLE,实际上所有的题都可以枚举所有结果选择额,但是实际上因为过程太多,很多题直接枚举会TLE,因此需要一定的技巧。
题目0:统计方形(数据加强版)
实际上这道题考的是递推,但是也可以转化为枚举的方式。
我们将矩阵视作由m个长度为1的长和n个长度为1的宽,他们连接为一条直线,那么就分别会有m+1个顶点和n+1个点,这样以后我们只需要在m+1个顶点选择两个和n+1的定点选择两个就可以构成一个矩形,故采用组合数公式C2,m+1*C2,n+1即为答案,代码如下。
#include<iostream>
using namespace std;
int main() {
long long n, m, Rectangle = 0, Square = 0;
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (i == j) Square += (n - i) * (m - j);
else Rectangle += (n - i) * (m - j);
}
cout << Square << " " << Rectangle << endl;
return 0;
}
题目1:烤鸡
按照题目要求从美味值递减然后层数递增的方式来递归进行答案计算,存储在ans_memo数组中最后一齐输出,通过能够显著减少代码量。
#include<stdio.h>
int ans_memo[15][10005];
int ans = 0;
int temp_ans[15];
void dfs(int d, int step) {
if (d < 0 || step>10) return;
if (d == 0 && step == 10) {
ans++;
for (int i = 0; i < 10; i++) ans_memo[i][ans - 1] = temp_ans[i];
return;
}
for (int i = 1; i <= 3; i++) {
if ((9 - step) * 3 + i < d) continue;
if ((9 - step) + i > d) return;
temp_ans[step] = i;
dfs(d - i, step + 1);
}
}
int main() {
int d;
scanf("%d", &d);
if (d > 30 || d < 10) return 0 * printf("0");
else {
dfs(d, 0);
printf("%d\n", ans);
for (int i = 0; i < ans; i++) {
for (int j = 0; j < 10; j++)
printf("%d ", ans_memo[j][i]);
printf("\n");
}
}
return 0;
}
题目2:三连击(升级版)
按照题目要求从123开始枚举,直到987(因为不能有重复数字,所以122及之前都会有重复,100-109含有0不能选)。
#include<stdio.h>
#define min(a,b) (((a) < (b)) ? (a) : (b))
int main() {
int a, b, c, tem1 = 0, tem2 = 0, flag = 0;
scanf("%d%d%d", &a, &b, &c);
for (int i = (123 / a + min(123 % a, 1)) * a; i <= 987 / a * a; i += a) {
tem1 = i / a * b, tem2 = i / a * c;
if (tem1 >= 100 && tem1 <= 999 && tem2 >= 100 && tem2 <= 999) {
int book[10], sum = 0, mul = 1;
book[1] = i % 10, book[2] = i / 10 % 10, book[3] = i / 100;
book[4] = tem1 % 10, book[5] = tem1 / 10 % 10, book[6] = tem1 / 100;
book[7] = tem2 % 10, book[8] = tem2 / 10 % 10, book[9] = tem2 / 100;
for (int k = 1; k < 10; k++) sum += book[k], mul *= book[k];
if (sum == 45 && mul == 362880) {//因为九个数字都需要使用。
flag = 1;
printf("%d %d %d\n", i, tem1, tem2);
}
}
}
if (flag == 0) printf("No!!!");
return 0;
}
题目3:选数
从0位置开始枚举,直到选到k个,判断是否为素数,是则加一否则不加,然后递归进行。
#pragma warning(disable:4996)
#include<stdio.h>
int n, k, memo[25], ans;
int isPrime(int n) {
for (int i = 2; i * i <= n; i++) if (n % i == 0) return 0;
return 1;
}
void dfs(int step, int st, int temp_ans) {
if (step == k) {
ans += isPrime(temp_ans);
return;
}
for (int i = st; i < n; i++)
dfs(step + 1, i + 1, temp_ans + memo[i]);
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &memo[i]);
dfs(0, 0, 0);
return 0 * printf("%d\n", ans);
}
题目4:组合的输出
和上面一道题一样,只不过不需要判断素数。
#include<stdio.h>
int n, r, memo[25], cnt = 1, ans_memo[25];
void dfs(int step, int st) {
if (step == r) {
for (int i = 0; i < r; i++) printf("%3d",ans_memo[i]);
printf("\n");
return;
}
for (int i = st; i < n; i++) {
ans_memo[step] = memo[i];
dfs(step + 1, i + 1);
}
}
int main() {
for (int i = 0; i < 25; i++) memo[i] = cnt++;
scanf("%d%d", &n, &r);
dfs(0, 0);
return 0;
}
题目5:全排列问题
使用book数组标记是否使用,其余和组合一致。
#include<stdio.h>
int n, book[15], ans[15];
void dfs(int k){
if (k == n) {
for (int i = 1; i <= n; i++) printf("%5d", ans[i]);
printf("\n");
return;
}
for (int i = 1; i <= n; i++){
if (!book[i]){
book[i] = 1, ans[k + 1] = i;
dfs(k + 1);
book[i] = 0;
}
}
}
int main(){
scanf("%d", &n);
dfs(0);
return 0;
}
题目6:火星人
就是查找当前排列的下字典序的第n个排列,当然可以使用stl的next_permutation(这道题在官方眼里就是熟练使用这个函数的)。
当然如果你知道康托展开,那么这道题直接实现一遍康托展开然后改小部分即可(如果不知道可以自行去了解,大概就是求解某个排列是在他非排列状态下的第几个的方法)。
//普通方式
#include<algorithm>
#include<stdio.h>
using namespace std;
int memo[10005], n, m;
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%d", &memo[i]);
while (m--) next_permutation(memo, memo + n);
for (int i = 0; i < n - 1; i++) printf("%d ", memo[i]);
return 0 * printf("%d", memo[n - 1]);
}
//方法2,来自于yummy大佬
#include<stdio.h>
#include<string.h>
int memo[10005], book[10005], m, n;
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++){
scanf("%d", &memo[i]);
int x = memo[i];
for (int j = 1; j <= memo[i]; j++) x -= book[j];
book[memo[i]] = 1;
memo[i] = x - 1;
}
memo[n] += m;
for (int i = n; i > 0; i--)
memo[i - 1] += memo[i] / (n - i + 1), memo[i] %= n - i + 1;
memset(book, 0, sizeof(book));
for (int i = 1; i <= n; i++){
for (int j = 0; j <= memo[i]; j++) if (book[j]) memo[i]++;
printf("%d ", memo[i]+1);
book[memo[i]] = 1;
}
return 0;
}
题目7:涂国旗
这道题就是枚举白的蓝的和红的的行数,然后维护一个最小值,这里分享一个在VS里跑是对的但是上交是错的代码。
//sp
#pragma warning(disable:4996)
#include<stdio.h>
char map[55][55];
int min(int x, int y) { return x < y ? x : y; }
int main(){
int m, n, ans = 1e9 + 1;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
char temp = getchar();
for (int j = 0; j < m; j++) {
temp = getchar();
map[i][j] = temp;
}
}
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int temp_ans = 0;
for (int k = 0; k <= i; k++)
for (int l = 0; l < m; l++)
if (map[k][l] != 'W') temp_ans++;
for (int k = i + 1; k <= j; k++)
for (int l = 0; l < m; l++)
if (map[k][l] != 'B') temp_ans++;
for (int k = j + 1; k < n; k++)
for (int l = 0; l < m; l++)
if (map[k][l] != 'R') temp_ans++;
ans = min(ans, temp_ans);
}
}
return 0 * printf("%d\n", ans);
}
//true
#pragma warning(disable:4996)
#include<stdio.h>
#include<iostream>
using namespace std;
char map[55][55];
int min(int x, int y) { return x < y ? x : y; }
int main(){
int m, n, ans = 1e9 + 1;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> map[i][j];
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int temp_ans = 0;
for (int k = 0; k <= i; k++)
for (int l = 0; l < m; l++)
if (map[k][l] != 'W') temp_ans++;
for (int k = i + 1; k <= j; k++)
for (int l = 0; l < m; l++)
if (map[k][l] != 'B') temp_ans++;
for (int k = j + 1; k < n; k++)
for (int l = 0; l < m; l++)
if (map[k][l] != 'R') temp_ans++;
ans = min(ans, temp_ans);
}
}
return 0 * printf("%d\n", ans);
}
题目8:First Step ファーストステップ
有一说一我也是个拉拉人,看到这个题我直接喷了2333(btw,停电是一定会停的)。
这道题就是类似于找横着的和竖着的连通块,所以需要使用dfsemmm就是一个搜索的方式。
#include <iostream>
using namespace std;
int dx[2] = { 0,1 }, dy[2] = { 1,0 };
char map[105][105];
int n, m, r, ans;
void dfs(int x, int y, int k, int person){
if (person - 1 == r) {
ans++;
return;
}
if (map[x][y] != '.' || x < 0 || y < 0 || x >= n || y >= m) return;
dfs(x + dx[k], y + dy[k], k, person + 1);
}
int main(){
cin >> n >> m >> r;
for (int i = 0; i < n; i++)
cin >> map[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
if (map[i][j] == '.') {
for (int k = 0; k < 2; k++)
dfs(i, j, k, 1);//[i,j]点站一个人开始,按照dx[k],dy[k]的方向进行dfs
}
}
if (r == 1) ans /= 2;//特判,因为重复计算了
cout << ans << endl;
return 0;
}
题目9:[USACO1.5]回文质数 Prime Palindromes
原题,直接略过。
题目10:火柴棒等式
提前打表记住每个数字需要的火柴棍即可
#include<stdio.h>
int memo[10] = { 6,2,5,5,4,5,6,3,7,6 }, ans, num;
int sticks_sum(int n) {
int sticks = 0, bits = 0;
do{
bits = n % 10;
sticks += memo[bits];
n /= 10;
} while (n);
return sticks;
}
int main() {
scanf("%d", &num);
for (int i = 0; i < 1111; i++)
for (int j = 0; j < 1111; j++)
if (sticks_sum(i) + sticks_sum(j) + sticks_sum(i + j) == num - 4) ans++;
return 0 * printf("%d", ans);
}
题目11:妖梦拼木棒
首先如果要用四个木棒拼成一个等边三角形,必然会需要两条相等边,且两条相等边必然为最大的边(记边长为l),假设这条边有m个,那么我们就可以有C2,m个取这个的方案;
那么接下来是第三条边,第三条边有两种,一个是两条l/2长的短边,另一种为i+j=l/2的边,此时假设l/2有p条,i有n条,j有q条,则我们分别由C2,p和C1,n*C1,q种方案;
最后由乘法原理,上述的三个组合数相乘即为答案。
另外由于计算过程中可能爆ans,需要不停的在中间取模。
#pragma warning(disable:4996)
#include<stdio.h>
const int MOD = 1000000007;
int book[5011];
int main(){
int n, temp, ans = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &temp);
book[temp]++;
}
for (int i = 1; i <= 5000; ++i){
for (int j = i; j <= 5000; ++j){
if (i + j > 5000) break;
if (i == j) {
if (book[i] >= 2 && book[i << 1] >= 2)
ans = (ans + (book[i] * (book[i] - 1) / 2 % MOD * (book[i << 1] * (book[i << 1] - 1) / 2) % MOD)) % MOD;
}
else {
if (book[i] >= 1 && book[j] >= 1 && book[i + j] >= 2)
ans = (ans + (book[i] * book[j] % MOD * (book[i + j] * (book[i + j] - 1) / 2) % MOD)) % MOD;
}
}
}
printf("%d\n", ans);
return 0;
}
题目12:kkksc03考前临时抱佛脚
题目的意思是,将某个集合划分为两个子集,其两个子集的和的差值最小。
首先先考虑贪心,我们将一个最大和一个最小形成一对,然后分别加到左右脑,若为奇数则剩余加到当前较小的一半,但是这样的话在会WA(比如1 1 2 2 59 98 98 99);
那么换种来贪心,我们将当前比较左右脑,如果左脑大,那么右脑加当前最大,否则左脑加当前最小,来换取平衡(但是还是WA)。
实际上正解是01背包,将其放入左脑和右脑可以看做划分为要或者不要,且由于最优情况每个学科的总时间一定是n/2(这样差值即为0),所以我们转化为在这些商品(题)中,选择最多的物品使得背包(做题时间)的物体(时间)尽可能的多(长),最后通过sum-求出来的最大时间就是我们需要的最大时间了。详情见代码。
#include<iostream>
#include<cstring>
using namespace std;
int subject[5], ans, ques[25], dp[1300];
int max(int x, int y) { return x > y ? x : y; }
int main() {
for (int i = 1; i <= 4; i++) cin >> subject[i];
for (int i = 1; i <= 4; i++) {
int sum = 0;
for (int j = 1; j <= subject[i]; j++){
cin >> ques[j];
sum += ques[j];
}
for (int j = 1; j <= subject[i]; j++)
for (int k = sum / 2; k >= ques[j]; k--)//这里是01背包的基本优化,从后往前即可将二维背包转化为一维
dp[k] = max(dp[k], dp[k - ques[j]] + ques[j]);
ans += sum - dp[sum / 2];
memset(dp, 0, sizeof(dp));
}
cout << ans << endl;
return 0;
}
题目13:[COCI2008-2009#2] PERKET
实际上就是枚举每一个组合的酸度乘积和甜度和,然后abs比较即可,注意区分清水。
还有注意一点(我在这里wa了两次),就是由于酸度是乘积,所以dfs的第二个量是要从1开始的。
#include<stdio.h>
int sour[15], sweet[15], ans = 1e9 + 5, n;
int min(int x, int y) { return x > y ? y : x; }
int abs(int x) { return x > 0 ? x : -x; }
void dfs(int i, int sour_ratio, int sweet_ratio) {
if (i == n) {
if (sour_ratio == 1 && sweet_ratio == 0) return;
ans = min(abs(sour_ratio - sweet_ratio), ans);
return;
}
dfs(i + 1, sour_ratio * sour[i], sweet_ratio + sweet[i]);
dfs(i + 1, sour_ratio, sweet_ratio);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d%d", &sour[i], &sweet[i]);
dfs(0, 1, 0);
return 0 * printf("%d\n", ans);
}
题目14:吃奶酪
首先最小距离我们会先想到贪心,即每次都贪当前的最小距离,但是局部最优不一定全局最优,比如有一个奶酪在一个圆心,然后奶酪分别在这个圆上彼此距离大于此圆半径的情况下,无法得到正确答案。
所以这道题我们依旧需要使用dp的方法,但是,由于数据点十分小只有16,因此直接枚举所有和也可以获得最小值(当然需要合理剪枝,比如当前的距离已经比已经算过的最小距离还要大的时候直接停掉就行了)。
而对于dp,对于此题来说,我们设定某一位的值为1说明该点的奶酪没被吃,否则被吃了,更多信息看代码,
//枚举
#include<stdio.h>
#include<math.h>
#include<algorithm>
int n, book[1000];
double x[30], y[30], dis[30][30], ans = 1e10 + 5;
void dfs(int cheese, int now, double sum) {
if (sum > ans) return;
if (cheese == n){
ans = std::min(ans, sum);
return;
}
for (int i = 1; i <= n; i++)
if (book[i] == 0) {
book[i] = 1;
dfs(cheese + 1, i, sum + dis[now][i]);
book[i] = 0;
}
}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
dis[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
dfs(0, 0, 0.0);
return 0 * printf("%.2f", ans);
}
//状压dp
#pragma warning(disable:4996)
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
double x[20], y[20], dp[20][35000];
double dis(int a, int b) { return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b])); }
int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
memset(dp, 127, sizeof(dp)); //初始化
for (int s = 1; s <= (1 << n) - 1; s++)//枚举每一个状态
for (int i = 1; i <= n; i++){
if ((s & (1 << (i - 1))) == 0) continue; //说明当前状态下已经被吃掉了,所以跳过
if (s == (1 << (i - 1))) { //说明当前还没被吃掉
dp[i][s] = 0; //故需要对dp进行初始化,并且从该点开始枚举每一个点
continue;
}
for (int j = 1; j <= n; j++){
if ((s & (1 << (j - 1))) == 0 || i == j) continue;//说明自己吃自己,跳过
dp[i][s] = std::min(dp[i][s], dp[j][s - (1 << (i - 1))] + dis(i, j));//更新当前所需要花费的最小值
}
}
double ans = -1;
for (int i = 1; i <= n; i++){//枚举每一个点到对应顺序点的和的最小值
double s = dp[i][(1 << n) - 1] + dis(i, 0);
if (ans == -1 || ans > s) ans = s;//get最小值
}
printf("%.2lf\n", ans);
return 0;
}
好了以上就是枚举的全部题,题目都不是特别难,就是有些会有点繁琐,另外最后一题的枚举最后一个点会TLE,原因是因为0,0点也有奶酪导致死循环(自己改)。
另外直接抄答案的可能会RE哦(滑稽)。