首页 > 其他分享 >洛谷P1219 [USACO1.5] 八皇后 Checker Challenge

洛谷P1219 [USACO1.5] 八皇后 Checker Challenge

时间:2023-07-15 22:57:46浏览次数:46  
标签:洛谷 USACO1.5 int Challenge 30 棋子 对角线 15 sum

写在前面

我又回来了!
偷了几天懒,还认识我吗?甭管认识不认识,还是要自我介绍一番:本人是初学c++的初中生,还是个蒟蒻,最要命的是没有脑子。今天,还请允许我浪费您一点时间,叨叨上几句。
本题目来自于洛谷,网址https://www.luogu.com.cn/problem/P1219,建议在洛谷上看一下。
本题解非盈利,无恶意,目的明确:分享经验,打发时间,同时,让更多的人被我带偏。因此,题解中可能有的侵权行为还希望您与我联系联系。
毕竟作者是个蒟蒻,一点水平都没有,因此欢迎对错误的批评指正!

题面(复制于洛谷)

[USACO1.5] 八皇后 Checker Challenge

题目描述

一个如下的 \(6 \times 6\) 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列 \(2\ 4\ 6\ 1\ 3\ 5\) 来描述,第 \(i\) 个数字表示在第 \(i\) 行的相应位置有一个棋子,如下:

行号 \(1\ 2\ 3\ 4\ 5\ 6\)

列号 \(2\ 4\ 6\ 1\ 3\ 5\)

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 \(3\) 个解。最后一行是解的总个数。

输入格式

一行一个正整数 \(n\),表示棋盘是 \(n \times n\) 大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

样例 #1

样例输入 #1

6

样例输出 #1

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

提示

【数据范围】
对于 \(100\%\) 的数据,\(6 \le n \le 13\)。

题目翻译来自NOCOW。

USACO Training Section 1.5

题目解释

原题中有个不错的例子:

题目是个什么意思呢?
就是说,一个棋子,横着,竖着,斜着,都不会有其他棋子,这就对了。(可以看看上面哦)
那怎么办到?
在这里,我采用大法师DFS。按横行枚举每个棋子,将竖列与对角线标起来,即可。
另外,对角线上的点坐标有规律:左上-右下者,同一线上差相等(i-j);右上-左下者,同一线上和相等(i+j)

代码实现

首先,依然是准备工作

int a[15],b[15],c[30],d[30];//a,b,c,d分别代表横行纵坐标、竖列占用情况、右上-左下对角线占用情况、左上-右下对角线占用情况。 
int n,sum;//n意义见题面,sum为方案数记录

DFS输出代码

if(i==n+1)//搜索到棋盘之外,说明完成搜索 
	{
		if(sum<3)//方案数小于3 
		{
			for (int k=1;k<=n;k++)
				cout<<a[k]<<" ";//输出方案 
			cout<<endl;
		}
		sum++;//方案数自增 
	}

DFS作业代码

for(int j=1;j<=n;j++)//搜索该横行每一竖列 
		if(!b[j] && !c[i+j] && !d[i-j+n-1])//该位置上下、对角线均无棋子,即符合要求 
		{
			a[i]=j;//记录纵坐标 
			b[j]=1;//竖列标记 
			c[i+j]=1;//对角线之一标记 
			d[i-j+n-1]=1;//对角线之二标记(+n防止i-j<1造成数组越界) 
			dfs(i+1);//搜索下一行 
			b[j]=0;//消除全部标记以供再次使用 
			c[i+j]=0;
			d[i-j+n-1]=0;
		}

主函数(不必多解释了吧)

int main()
{
	cin>>n;
	dfs(1);
	cout<<sum<<endl;
	return 0;
}

完整代码

#include<iostream>
#include<cstdio>
using namespace std;
int a[15],b[15],c[30],d[30];
int n,sum;
void dfs(int i) 
{
	if(i==n+1) 
	{
		if(sum<3)
		{
			for (int k=1;k<=n;k++)
				cout<<a[k]<<" ";
			cout<<endl;
		}
		sum++;
	}
	for(int j=1;j<=n;j++)
		if(!b[j] && !c[i+j] && !d[i-j+n-1])
		{
			a[i]=j; 
			b[j]=1; 
			c[i+j]=1;
			d[i-j+n-1]=1; 
			dfs(i+1);
			b[j]=0;
			c[i+j]=0;
			d[i-j+n-1]=0;
		}
}
int main()
{
	cin>>n;
	dfs(1);
	cout<<sum<<endl;
	return 0;
}

请注意

  • 在进行左上-右下的对角线的标记时一定记得+n,否则会造成数组越界哦~
  • 完成搜索要回溯,也就是清楚标记
  • 对角线:i+j表示右上-左下对角线,而i-j+n-1表示左上-右下对角线!成功把你绕晕了吗?哈哈~

时间复杂度

最大值是13,循环次数为4674890次。数据规模偏小,因此虽然时间复杂度高,但也绝对没问题。
洛谷运行结果如下:

深搜这样我就挺满意了(~ ̄▽ ̄)~

写在最后

回归是不是挺惊喜?没有?我伤心了。
就不再重申开头了。
这次写题解的速度突破了1小时呢!你为我感到自豪,快说!
明天见喽~

THE END~

标签:洛谷,USACO1.5,int,Challenge,30,棋子,对角线,15,sum
From: https://www.cnblogs.com/httony/p/17557143.html

相关文章

  • 洛谷 P4931 [MtOI2018] 情侣?给我烧了!(加强版)
    洛谷传送门设\(f_i\)为\(i\)对情侣完全错位的方案数,那么答案为:\[\binom{n}{k}\frac{n!}{(n-k)!}2^kf_{n-k}\]分别代表选择\(k\)对情侣,选择它们的位置,情侣可以换位。\(f_i\)有递推公式:\[f_i=4i(i-1)(f_{i-1}+2(i-1)f_{i-2})\]考虑选出两个人,另外......
  • How to ak 【LGR-145-Div.4】洛谷入门赛 #14?
    A数字判断#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/hash_policy.hpp>#definereregister#definelll__int128#definegcgetchar#defineptputchar#definei......
  • 洛谷 P6667 [清华集训2016] 如何优雅地求和
    洛谷传送门点值不好搞。考虑把它搞成系数一类的东西。由二项式反演,\(f(x)=\sum\limits_{i=0}^x\binom{x}{i}b_i\Leftrightarrowb_i=\sum\limits_{j=0}^i\binom{i}{j}(-1)^{i-j}f(j)\)。然后我们要求:\[\sum\limits_{k=0}^n\sum\limits_{i=0}^ms_i\bino......
  • [已过万次测试] MIT 6.5840 2023 Lab 4 Shard KV Server TaskA, TaskB, Challenge 通
    MIT6.58402023Lab4ShardKVServerTaskA,TaskB,Challenge前言这波是终于写完了MIT6.5840的所有lab了。lab均是独立完成,没有任何参考,哈哈,还是挺有成就感的。lab4其实在上周就已经写完了,不过比较懒,拖了一周才开始写总结。本次lab4,在所有lab中,个人认为难度仅次于lab2,也......
  • 洛谷 P3372 【模板】线段树 1
    题目传送门题目描述如题,已知一个数列,你需要进行下面两种操作:1.将某一个数加上x2.求出某区间每一个数的和输入格式第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。接下来M行每行包含3......
  • P1216 [USACO1.5] [IOI1994]数字三角形
    自己的思想:要用逆序,但是某个未知的位置可能存在一个非常大的数,因此不知道如何dp看题解之后:对于倒数第二行的数,可以算出它们的最优解,依次往上推,第一个数就是整体的最优解,其实本质上可以用隔离意识来看,在搞最后一排时,将前面所有排隔离掉,在处理中间的每一排时,又将其他排隔离掉接下......
  • 线段树模板 洛谷P3374 【模板】树状数组 1
    题目传送门题目描述如题,已知一个数列,你需要进行下面两种操作:1.将某一个数加上x2.求出某区间每一个数的和输入格式第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。接下来M行每行包含3......
  • 洛谷 P6892 [ICPC2014 WF] Baggage
    洛谷传送门感觉这题递归的思想挺值得借鉴的。特判\(n=3\)。首先根据样例不难猜测最小次数为\(n\)。事实上最小次数下界为\(n\),因为设\(x\)为当前相邻元素相同对数,不难发现除第一次操作外\(x\)最多增加\(2\),而终态中\(x=2n-2\)。我们尝试构造能达到下界的方案。......
  • 洛谷 P4869 albus就是要第一个出场 题解
    洛谷P4869albus就是要第一个出场题意给定一个长度为\(n\)的序列\(A\),设可重集合\(S=\left\{\operatorname{xor}_{i=1}^nA_ix_i\midx_i\in\{0,1\}\right\}\),即\(S\)为\(A\)的所有子集的异或和构成的集合。给定一个数\(k\),求\(k\)在\(S\)中的排名。如果\(S\)中......
  • 洛谷 P6109 - [Ynoi2009] rprmq1
    首先将修改操作差分为\(l_1\)时刻给\([l_2,r_2]\)中的值\(+v\),\(r_1+1\)时刻给\([l_2,r_2]\)中的值\(-v\)。这样第\(i\)行的状态相当于执行\(1\simi\)时刻的操作后的状态。猫树分治,把一个询问挂在线段树上满足\(l\lel_1\lemid\ler_1\ler\)的区间\([l,r]\)......