闲谈:搜索是个神奇的东西,我也不知道为什么2^50能过.可能只是因为最坏是2^50左右吧QAQ.这题思路是很简单的,对于每个点,我们有两个选择.一是放到上升序列中去,二是放到下降序列中去,假如都不能放,那么就要自己重新开一个.然后直接搜索递归即可.基于最优解肯定是要放到最近的序列连续.然后第一次找到了位子就是最优的了.下面是代码: #include <bits/stdc++.h> using namespace std; const int N=55; int a[N],n,up[N],down[N]; bool dfs(int dep,int u,int xu,int xd)//...

闲谈:这题首先得于处理所有可行的路线,然后路线中应当优先选取最大覆盖的路线.题目有几个细节.1.枚举的时候应当按组合数,就是枚举了一个方案,下次起点设为它自己.2.然后就是剩下可以枚举的层数和剩下的bus数量一定得满足剩下的bus数量<=我当前的层数所有bus数量*剩下层数.2.然后首项一定小于公差,因为下表是从0~59.然后剩下的就是代码实现了. #include <bits/stdc++.h> using namespace std; typedef pair<int,int> pi; const int N=60; int n,bus[N]; vector&...

闲谈:写搜索真的心累,复杂复杂.代码又长,又难调.幸好蓝书搜索并不是很短,且y总大部分都做了视频,且有辛格大佬不然我估计写不下去了.言归正传,讲讲这个题目怎么做.题目是你可以移动且只能移动n次,使得屏幕的方块全部消掉.移动就是左移和右移,然后假如你移动方向有方块你就交换.没有方块就就掉落呗.然后消了之后也会掉落,一旦相同连续颜色的方块>=3就可以消了.答案优先级是按照x为第一关健字,y为第二关健字,1优先于-1,1表示向右移动,-1表示向左移动.做法就是模拟上面描述的过程,搜索的剪枝有2个.1.一旦有种方块数量<3.那么直接return false就可以了.2.由于向右移动的优先级...

闲谈:1.这个题就是给你一个N进制数和N位,给出A和B的固定格式,以及C且C的格式,且A+B=C且不能进位.要你求A、B、C中每个字符所代表的每个数字.2.这题我们由于最后不能进位可知最后一位进位必定return.3.然后从第一位开始判断是否合法即可.代码: #include <bits/stdc++.h> using namespace std; const int N=30; int n; char an[3][N]; bool st[N]; int path[N]; int q[N]; bool ck() { for (int i=n-1,t=0;i>=0;i--...

闲谈:和数独规则差不多--然后可以直接按数独1的方法进行就好了..数独1没写题解吧...这里补下QAQ.1.首先观察计数,我们观察层数会发现,假如我们下标从0开始,那么在我们填一个数(x,y)时,付出的代价是min(min(8-x,x),min(8-y,y))+6;那么假设我们填的数是val,那么得分就是val*min(min(8-x,x),min(8-y,y))+6;2.和数独1一样,我们可以预先处理出两个数组,一个ones,一个mp.第一个判断二进制数中有几个1,第二个用来判断一个二进制数是2的几次方.为什么要这两个预处理呢?第一个ones我们是用来,在对于每次选择分支少的进行剪枝的,第二...

acwing182-破坏正方形算法:IDA*时间复杂度:(指数)题目描述&数据范围:下图左侧显示了一个用24根火柴棍构成的完整3×3网格。所有火柴的长度都是1。您可以在网格中找到许多不同大小的正方形。在左图所示的网格中，有9个边长为1的正方形，4个边长为2的正方形和1个边长为3的正方形。组成完整网格的每一根火柴都有唯一编号，该编号从上到下，从左到右，从1开始按顺序分配。如果你将一些火柴棍从完整网格中取出，形成一个不完整的网格，则一部分正方形将被破坏。右图为移除编号12,17和23的三个火柴棍后的不完整的3×3网格。这次移除破坏了5个边长为1的正方形，3个边长为2的正方形和1个边长为3的...

直接IDA*即可 /* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 */ #include <bits/stdc++.h> using namespace std; int a[25]; int cnt[4]; int path[100]; int b[8]={6,7,8,12,17,16,15,11};//检测答案 int c[8][7]={ {0,2,6,11,15,20,22}, ...

#include <bits/stdc++.h> using namespace std; int main() { string a,b; cin>>a>>b;int flag=0; int len1=a.size(),len2=b.size(); for(int i=0;i<len1;i++)//枚举每个b从a串开始的位子 { int j=0;int k=i; while(j<len2&&a[k]==b[j]) k++,j++; if(j=...

IDA类似剪枝--当成一个剪枝就好了QAQ.给定n本书，编号为1-n。在初始状态下，书是任意排列的。在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。我们的目标状态是把书按照1-n的顺序依次排列。求最少需要多少次操作。输入格式第一行包含整数T，表示共有T组测试数据。每组数据包含两行，第一行为整数n，表示书的数量。第二行为n个整数，表示1-n的一种任意排列.同行数之间用空格隔开。输出格式每组数据输出一个最少操作次数。如果最少操作次数大于或等于5次，则输出”5 or more”。每个结果占一行。数据范围1≤n≤15emm,数据这么小,xjb搜一下就完事QAQ.注意用IDA剪枝一下...

什么是A算法,A算法又叫启发式搜索,通过堆优化+估价函数对搜索进行优化的一种算法,运用于正权图(我只知道这个,负权图算法还没学QAQ).通过启发函数可以让搜索复杂度大大降低.如下图:但是对于终点第一次出队并非一定是最小值,就比方说这个图,下面的第三个点,由于前面的估计函数都是0,所以我们肯定先出队的距离为4,而后才有2.A算法的证明就类似dij算法,贪心想想就是了.这就是A算法,是不是感觉也不是很难呢?下面讲解两个题目吧~题目描述&数据范围:给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。注意： 每条最短路中至少要包含一条边...

题目解释&数据范围给定一张NM的地图，地图中有1个男孩，1个女孩和2个鬼。字符“.”表示道路，字符“X”表示墙，字符“M”表示男孩的位置，字符“G”表示女孩的位置，字符“Z”表示鬼的位置。男孩每秒可以移动3个单位距离，女孩每秒可以移动1个单位距离，男孩和女孩只能朝上下左右四个方向移动。每个鬼占据的区域每秒可以向四周扩张2个单位距离，并且无视墙的阻挡，也就是在第k秒后所有与鬼的曼哈顿距离不超过2k的位置都会被鬼占领。注意： 每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。输入格式第一行包含整数T，表示共有T组...

题目描述&数据范围:有N个城市（编号0、1…N-1）和M条道路，构成一张无向图。在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。现在你需要回答不超过100个问题，在每个问题中，请计算出一架油箱容量为C的车子，从起点城市S开到终点城市E至少要花多少油钱？注意： 假定车子初始时油箱是空的。输入格式第一行包含两个整数N和M。第二行包含N个整数，代表N个城市的单位油价，第i个数即为第i个城市的油价pi。接下来M行，每行包括三个整数u,v,d，表示城市u与城市v之间存在道路，且车子从u到v需要消耗的油量为d。接下来一行包含一个整数q，代表问题数量。接下来q行，每行包含三个整数C、S、...

博客将更新进阶指南的题解.每天任务数是8.困难=3.中等=2.简单=1.明天开始实行.严格完成任务QAQ.175/412还差237题可能进阶指南不止这么多.emm先更完再说.y总没做视频的,或许之后我会在直播平台做视频QAQ加油~

题目:有6个箱子A-F，每个箱子里有一把钥匙，拿到钥匙i就能打开箱子i。现在我们强行打开1,2箱子，取出里面的钥匙，然后用这些钥匙打开其他箱子……最后问有几种可能打开所有箱子。(小学题解法:我们用f[i]表示可以打开i个箱子的放置数,首先推首项f[2]=2,因为1,2和2,1都是一样可以打开的,我们从n开始考虑第n个箱子的钥匙一定不能放在它自己的身上,因为这样必定无解,那么它就一定放置在1,2...n-1个箱子之中,我们把第n个箱子所放的钥匙和位于其他箱子之中有n的钥匙的箱子互换一下,然后把n号箱子删除,那么方案数就是f[n]=f[n-1](n-1);所以方程就是f[i]=f[i-1](i-1...