分类 搜索 下的文章

BZOJ 4878: [Lydsy1705月赛]挑战NP-Hard

Solution对整个无向图求一个 DFS 树,如果最大深度 > k,就可以输出一条路径,如果 <= k,就可以以深度作为染色方案。有一点点卡常,数组不要开太大。Code#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> using namespace std; const int N = 1001; const int M = 20001; inline ch- 阅读剩余部分 -

BZOJ 1054: [HAOI2008]移动玩具

Solution直接搜索就可以了。可以状压一下方便判重。Code#include <cstdio> #include <algorithm> #include <queue> using namespace std; int s, t; int a[10][10]; int toNum() { int x = 0; for(int i=1; i<=4; i++) for(int j=1; j<=4; j++) { x <<= 1; x |= a[i][j]; - 阅读剩余部分 -

BZOJ 1085: [SCOI2005]骑士精神

Solution迭代加深搜索Code#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> using namespace std; int a[5][5], now[5][5]; int go[8][2] = { {2, -1}, {-1, 2}, {-2, 1}, {1, -2}, {-1, -2}, {-2, -1}, {2, 1}, {1, 2} }; int target[5][5] =- 阅读剩余部分 -

BZOJ 3109: [cqoi2013]新数独

Solution按照题意搜索就行了。Code#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> using namespace std; const int N = 30; int a[N][N][5]; int bel[N][N]; int l1[N][N]; int l2[N][N]; int used[N][N]; int ans[N][N]; void dfs(int x, int y) { if(y >- 阅读剩余部分 -

BZOJ 3299: [USACO2011 Open]Corn Maze玉米迷宫

Description今年秋天,约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子,有些格子种了玉 米,种宥玉米的格子无法通行。 迷宫的四条边界上都是种了玉米的格子,其屮只有一个格子 没种,那就是出口。 在这个迷宫里,有一些神奇的传送点6每个传送点由一对点组成,一旦 走入传送点的某个结点, 机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的,如果你定到了另一头,机器也会把你送回来。 奶牛在一个单位的时间内只能向相邻的四个方向移动一格,不过传送机传送是瞬间完成 的。 现在W西在迷宫里迷路了,她只知道目前的位罝在哪里,请你帮助她用最短的时间走出 迷宫吧。Input第- 阅读剩余部分 -

BZOJ 3393: [Usaco2009 Jan]Laserphones 激光通讯

DescriptionInput第1行输入w和H,之后W行H列输入地图,图上符号意义如题目描述.Output最少的对角镜数量.Sample Input7 8 ....... ......C ......* *****.* ....*.. ....*.. .C..*.. .......Sample Output3Solution搜索,类似于最短路,不过要加一维方向,整体类似于 SPFACode#include <bits/stdc++.h> #define long long long using namespace std; inline void read(i- 阅读剩余部分 -

BZOJ 1673: [Usaco2005 Dec]Scales 天平

Description约翰有一架用来称牛的体重的天平.与之配套的是N(1≤N≤1000)个已知质量的砝码(所有砝码质量的数值都在31位二进制内).每次称牛时,他都把某头奶牛安置在天平的某一边,然后往天平另一边加砝码,直到天平平衡,于是此时砝码的总质量就是牛的质量(约翰不能把砝码放到奶牛的那边,因为奶牛不喜欢称体重,每当约翰把砝码放到她的蹄子底下,她就会尝试把砝码踢到约翰脸上).天平能承受的物体的质量不是无限的,当天平某一边物体的质量大于C(1≤C<230)时,天平就会被损坏. 砝码按照它们质量的大小被排成一行.并且,这一行中从第3个砝码开始,每个砝码的质量至少等- 阅读剩余部分 -

BZOJ 3432: [Usaco2014 Jan]Cross Country Skiing

DescriptionN*M的格子,每个格子都有一个分值v,有的格子一定要经过.两个格子i,j可以互相到达,当且仅当它们有一条边重复(即上下左右方向),且abs(vi-vj)<=D.现在请求出最小的D的值。InputLine 1: The integers M and N.Lines 2..1+M: Each of these M lines contains N integer elevations.Lines 2+M..1+2M: Each of these M lines contains N values that are either 0 or 1, wit- 阅读剩余部分 -

BZOJ 1024: [SCOI2009]生日快乐

Descriptionwindy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。windy主刀,每一切只能平行于一块蛋糕的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N 块蛋糕,windy必须切 N-1 次。为了使得每块蛋糕看起来漂亮,我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么?Input包含三个整数,X Y N。1 <= X,Y <= 10000 ; 1 <= N <= 1- 阅读剩余部分 -

BZOJ 1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

DescriptionFarmer John新买的干草打包机的内部结构大概算世界上最混乱的了,它不象普通的机器一样有明确的内部传动装置,而是,N (2 <= N <= 1050)个齿轮互相作用,每个齿轮都可能驱动着多个齿轮。 FJ记录了对于每个齿轮i,记录了它的3个参数:X_i,Y_i表示齿轮中心的位置坐标(-5000 <= X_i <= 5000; -5000 <= Y_i <= 5000);R_i表示该齿轮的半径(3 <= R_i <= 800)。驱动齿轮的位置为0,0,并且FJ也知道最终的工作齿轮位于X_t,Y_t。 驱- 阅读剩余部分 -

BZOJ 1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场

Description农夫JOHN的农夫上有很多小山丘,他想要在那里布置一些保镖(……)去保卫他的那些相当值钱的奶牛们。 他想知道如果在一座小山丘上布置一名保镖的话,他总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行(1 < N < = 100)和M列( 1 < M < = 70) 。矩阵中的每个元素都有一个值H_ij(0 < = H_ij < =10,000)来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。 小山丘的定义是:若地图中一个元素所邻接的所有元素都比这个元素高度要小(或它邻接- 阅读剩余部分 -

BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨

题目描述去年偶们湖南遭受N年不遇到冰冻灾害,现在芙蓉哥哥则听说另一个骇人听闻的消息: 一场流星雨即将袭击整个霸中,由于流星体积过大,它们无法在撞击到地面前燃烧殆尽, 届时将会对它撞到的一切东西造成毁灭性的打击。很自然地,芙蓉哥哥开始担心自己的 安全问题。以霸中至In型男名誉起誓,他一定要在被流星砸到前,到达一个安全的地方 (也就是说,一块不会被任何流星砸到的土地)。如果将霸中放入一个直角坐标系中, 芙蓉哥哥现在的位置是原点,并且,芙蓉哥哥不能踏上一块被流星砸过的土地。根据预 报,一共有M颗流星(1 <= M <= 50,000)会坠落在霸中上,其中第i颗流星会在- 阅读剩余部分 -

【NOIP模拟赛】Nim 游戏·改、聚会、历史

前言又是一个模拟赛,再一次爆炸。T1 Nim 游戏·改(nim.c/cpp/pas)题目描述众所周知的 Nim 游戏是这样的:有 n 堆石子,小 A 和小 B 轮流取石子,小 A 先操作,每次选择一堆石子,在这堆中取走任意多个石子,最后没有石子可取的人输。现在为了加强Nim 游戏难度,每堆非空石子有一次额外的特殊机会,即耗掉这个机会,然后什么也不拿走,而其他条件都不变。当然,如果你将一堆本来有额外机会的石子拿空,那么这次额外机会也就没有了。现在假设小 A 和小 B 都绝顶聪明,他们将进行 T 轮游戏。每轮游戏若小 A 必胜,输出“A”,否则输出“B”。输入格式第一行为一个整- 阅读剩余部分 -