深度搜索 - Page 6

「codecomb2094」还是N皇后
Description正如题目所说，这题是著名的N皇后问题。Input Format第一行有一个N。接下来有N行N列描述一个棋盘，“*”表示可放“.”表示不可放。Output Format输出方案总数。Sample Input4**.*************Sample Output1Data Limit对于30%的数据，N≤10;对于100%的数据，N≤14；题解裸的dfs不足以ac我发现n皇后可以用位运算加速参见http://blog.csdn.net/xadillax/article/details/6512318然后就能水过了。。...
02014年10月15日3,043深度搜索

「NOIP模拟赛」某种密码
关于某种密码有如下描述：某种密码的原文A是由N个数字组成，而密文B是一个长度为N的01数串，原文和密文的关联在于一个钥匙码KEY。若KEY=∑▒〖Ai*Bi〗，则密文就是原文的一组合法密码。现在有原文和钥匙码，请编一个程序来帮助他统计到底有多少个符合条件的密文。「输入数据」第一行两个数N，KEY，意义同题目描述；第二行N个数表示原文A，意义同题目描述。「输出数据」一个数ANS，表示对于原文A和KEY，有...
02014年10月4日3,287深度搜索
「BZOJ1098」[POI2007] 办公楼biu
DescriptionFGD开办了一家电话公司。他雇用了N个职员，给了每个职员一部手机。每个职员的手机里都存储有一些同事的电话号码。由于FGD的公司规模不断扩大，旧的办公楼已经显得十分狭窄，FGD决定将公司迁至一些新的办公楼。FGD希望职员被安置在尽量多的办公楼当中，这样对于每个职员来说都会有一个相对更好的工作环境。但是，为了联系方便起见，如果两个职员被安置在两个不同的办公楼之内，他们必须拥有彼此的电话号码...
02014年10月3日5,849链表,深度搜索,广度搜索
「BZOJ1770」[Usaco2009 Nov] lights 燈
Description貝希和她的閨密們在她們的牛棚中玩遊戲。但是天不從人願，突然，牛棚的電源跳閘了，所有的燈都被關閉了。貝希是一個很膽小的女生，在伸手不見拇指的無盡的黑暗中，她感到驚恐，痛苦與絕望。她希望您能夠幫幫她，把所有的燈都給重新開起來！她才能繼續快樂地跟她的閨密們繼續玩遊戲！牛棚中一共有N（1<=N<=35）盞燈，編號為1到N。這些燈被置於一個非常複雜的網絡之中。有M（1<=M<=595）條很神奇的無向...
32014年10月1日6,168深度搜索,高斯消元
「NOIP模拟赛」人偶师
「题目描述」n点m双向边的图，每个点有2个状态：开和关。每次操作改变一个点的状态，以及与其有边直接相连的点的状态。问开启所有点至少需要多少次操作。「输入格式」第一行2个整数n,m。第二行n个整数，第i个数表示第i点的状态，0为关，1为开。第3..m+2行，每行2个整数a,b，表示a和b直接相连，同一条边不会出现多次。「输出格式」第一行一个整数k表示最少的操作次数，所有数据保证至少有一组可行解。第二行k个整数，表示操作的点的...
02014年9月27日6,457深度搜索
「BZOJ3631」[JLOI2014] 松鼠的新家
Description松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以...
22014年9月25日5,289深度搜索,树形动规
「CF468B」Two Sets
LittleXhasndistinctintegers:p1, p2, ..., pn.HewantstodivideallofthemintotwosetsAandB.Thefollowingtwoconditionsmustbesatisfied:IfnumberxbelongstosetA,thennumbera - xmustalsobelongtosetA.IfnumberxbelongstosetB,thennumberb - xmustalsobelongtosetB.HelpLittleXdividethenumbersintotwosetsordeterminethatit'simpossible.InputThefirstlinecontainsthreespace-separatedintegersn, a, b(1...
02014年9月21日3,194深度搜索
「BZOJ3687」「FJ2014集训」简单题
「题目描述」小呆开始研究集合论了，他提出了关于一个数集四个问题：1.子集的异或和的算术和。2.子集的异或和的异或和。3.子集的算术和的算术和。4.子集的算术和的异或和。目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把这个问题交给你，未来的集训队队员来实现。「输入格式」从xor.in中输入数据第一行，一个整数n。第二行，n个正整数，表示a1,a2,...,an「输出格式」输出到xor.out中一行，包含一个整...
22014年9月14日6,284背包动规,深度搜索
「CF464B」Restore Cube
Peterhadacubewithnon-zerolengthofaside.Heputthecubeintothree-dimensionalspaceinsuchawaythatitsverticeslayatintegerpoints(itispossiblethatthecube'ssidesarenotparalleltothecoordinateaxes).Thenhetookapieceofpaperandwrotedowneightlines,eachcontainingthreeintegers—coordinatesofcube'svertex(asinglelinecontainscoordinatesofasinglevertex,eachvertexiswrittenexactlyonce),putthepaperonthetableandleft.Wh...
02014年9月8日3,342深度搜索
「BZOJ2719」[Violet 4] 银河之星
题解容易发现可以将平面的所有点分为9类012345678即同类棋子可以通过第三种移动到达相同位置而一个棋子跨过另一个，如0跨过4到达8，则可以视为0和4可以合成8，则问题转换为能不将所有点通过一系列合成得到一个和目标格子同类的点还要注意一下这种情况（1为棋子，0为目标，棋盘大小为3*3）1XXX0XXX1这种情况下是不能将0与8合成4的，除非将棋子移动到棋盘外所以还需要处理出在当前的棋盘大小内，哪些棋子可以相互合成，可以...
02014年9月6日3,848深度搜索
「BZOJ2783」[JLOI2012] 树
Description第一行是两个整数N和S，其中N是树的节点数。第二行是N个正整数，第i个整数表示节点i的正整数。接下来的N-1行每行是2个整数x和y，表示y是x的儿子。输出格式：输出路径节点总和为S的路径数量。输入样例：输出样例：3312312132 数据范围：对于30%数据，N≤100；对于60%数据，N≤1000；对于100%数据，N≤100000，所有权值以及S都不超过1000。======================================================...
02014年9月3日4,463STL,深度搜索
「BZOJ1024」生日快乐
Descriptionwindy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为X和Y的矩形蛋糕。现在包括windy，一共有N个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。windy主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成N块蛋糕，windy必须切N-1次。为了使得每块蛋糕看起来漂亮，我们要求N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么？I...
02014年9月1日3,678深度搜索