AiRomance

Notes of Lecture 23: Computational Complexityvideo link P,EXP,RP = {problems solvable in at most(<=) polynomial time} EXP = {problems solvable in exponential(2^$n^c$) time} R = {problems solvable in finite time} The axis is computational difficulty. Most problems uncomputableExamples: negative-weight cycle detection (P) NxN Chess (EXP&!P) Tetris (EXP, don’t know whether is P) halting problem: given program, does it ever halt/stop? (not in R) Most decision problems are uncomputable...

Multiple Knapsack Problemproblem link The Meaning of the problemYou have three kinds of coins. Their face values are 1,2 and 5. Of cause you only have a limited number of coins. You need to find the minimum value that you can’t represent exactly with these coins. SolutionThere are lots of people solve this problem using Generating function. That way is too hard to understand. We just need to think of this problem as a multiple knapsack problem. I learned from this blog dp[j] = 1 means that...

Constructing Roads In JGShining’s Kingdomproblem link The meaning of the problemSo why this is longest increasing subsequence Problem ? Look at the picture below: As the problem described, we can’t have crossed lines. Each line has two endpoints. One is the “rich” endpoint above and the other is the “poor” endpoint below. The rich endpoints’ number of the lines we finally pick up should be monotonically increasing. The corresponding poor endpoints should be monotonically increasing too....

细心和智慧并存的解答题目链接 题的大致意思是能不能从起点经过T时间精准到达终点，图中有一些障碍不能走，走过的格子也不能再走。 其中数据是最大7*7的迷宫，最多50个迷宫。 智慧之处——精准的剪枝类似全排列的深搜时间复杂度是O(n!)，7*7的数据是过不去的。 首先就是普通地剪枝： 如果时间已经大于T，就不用再走了 如果已经有正确答案，要及时地退出搜索 然后是奇偶剪枝，这里参考了其他博客 这里我重新画了一张图，如下： 图中的S可以代表任何你走到的位置，不一定是起点。就如图中的红色和蓝色路径，这两条路径是最少需要的时间。如果剩余时间少于最短路径长度，那么是一定不能到达终点的。 既然时间不够一定不能到达，时间刚好和剩余最少时间相等也能到达，那么还剩一种情况，就是时间大于剩余最少时间。这也应该是大概率会遇到的情况。根据题意我们只能在第T秒精准到达终点，我们时间多出来的怎么办呢？——我们需要在终点周围“徘徊”。 如图中的绿色和黄色箭头所示，你比最短路径多走出来的路径，一定是先“出去”，再“回来”。多走的路径是“对称的”，那多出来的路径长度一定是偶数。 ...

一道经典的分治题目链接 题意是套圈游戏要设计一款尺寸最大的圆环，满足圆环不会一次套中两个物品。每个物品有一个摆放坐标。我们要求的是这些物品中相邻最近的两个物品之间的距离，这个距离就是我们要求的圆环的直径。 这个类型网上常称为寻找最近点对问题。 ...

这是力扣上一道非常简单的问题，是经典的解决括号匹配问题。当然做法是用一个栈即可解决问题。有效的括号 这是我的代码：123456789101112131415161718192021222324class Solution { public boolean isValid(String s) { Stack<Character> st = new Stack(); boolean flag = true; for(int i=0;i<s.length();i++){ Character nowC = s.charAt(i); if(nowC=='('||nowC=='{'||nowC=='['){ st.push(nowC); }else { ...

博客的免费图床方案（Cloudflare R2 + PicGo）参考博客 这个博客写的已经非常详细清楚了，这里不再赘述实现步骤。 这里记录一下我是怎么发现这篇博客的。 在一个很无聊的时间段，我打开了Inoreader看RSS订阅的博客列表有没有更新，其中有一篇少数派的博客吸引了我，是这个博客。 这里博主提到了他的推特账号。其中很近的时间里他发布了上面提到的免费图床方案的博文。 这篇博客解决了我正在苦恼的问题，那就是博文中图片的插入。如果是只有一个github pages的静态网站还好说，直接传在相对文件夹里即可。但是如果面对多平台，比如我还想在csdn中发布，那就变得很麻烦，因为markdown里写的相对路径将不可用，最直接的办法就是更改每个图片链接。 然而如果是有自己的图床就很方便了，不用担心网络上的图片会突然失效，多平台发布也不用更改自己的截图路径。上方的图片就是用我自己实现的图库。 ...

正则表达式To the book page Regexp golf注意这里如果写对的话，应该什么都不会输出。 正则表达式中的\b是单词边界的标志，它用来匹配一个单词的边界。 123456789101112131415161718192021222324252627282930313233343536373839404142// Fill in the regular expressions// 正则表达式应该匹配“car”和“cat”，但不匹配其他字符串。verify(/ca[rt]/, ["my car", "bad cats"], ["camper", "high art"]);// 正则表达式应该匹配“pop”和“prop”，但不匹配其他字符串。verify(/pr?op/, ["pop culture", "mad props"], ["plop",...

使用高德SDK实现导航功能参考博客 Github仓库直达 这是今天企业实训的一个小作业，实际上我从昨天就开始尝试申请key然后下载官方Demo开始实验。本来是要做flutter项目，但是高德官方里flutter教程只有显示地图和定位功能，没有导航功能，导航功能官方只有Android的教程。今天也是用Android原生进行编写的。至于怎么整合到flutter项目里目前还不知道。。。 1. 官网下载SDK我也尝试过直接gradle引入包的操作，但是直接引入的会缺少AmapNaviParams。官网也一直强调有个什么东西开源了所以提供的包里移除了一些东西（不知道到底是什么）。 官网SDK下载地址 我下载的是导航合包： 2. 创建项目直接Android Studio创建一个java，Groovy的项目即可。 设置里需要设置生成所有Gradle Task： 这样你就可以靠点击这里直接获得你项目的SHA1的值，申请key的时候需要这个。 点击上图位置你就可以在终端看见你的SHA1值。在我这里release和debug的SHA1的值是一样的。 ...

错误To the book page Retry大概率触发MultiplicatorUnitFailure错误，承接直到运行成功并返回结果。 1234567891011121314151617181920212223242526272829class MultiplicatorUnitFailure extends Error {}function primitiveMultiply(a, b) { if (Math.random() < 0.2) { return a * b; } else { throw new MultiplicatorUnitFailure("Klunk"); }}function reliableMultiply(a, b) { // Your code here. for(;;){ try{ var ans = primitiveMultiply(a,b); ...

robotTo the book page代码解释由AI生成。 总代码数据结构和图的构建首先定义了村庄中各个地点之间的道路： 123456789const roads = [ "Alice's House-Bob's House", "Alice's House-Cabin", "Alice's House-Post Office", "Bob's House-Town Hall", "Daria's House-Ernie's House", "Daria's House-Town Hall", "Ernie's House-Grete's House", "Grete's House-Farm", "Grete's...

对象To the book page A vector type封装一个类，实现坐标的加减法，以及get属性的length返回坐标离原点的距离。 12345678910111213141516171819202122// Your code here.class Vec{ constructor(x,y){ this.x = x; this.y = y; } plus(other){ return new Vec(this.x+other.x,this.y+other.y); } minus(other){ return new Vec(this.x-other.x,this.y-other.y); } get length(){ return Math.sqrt(this.x**2+this.y**2); }}console.log(new Vec(1,...

高阶函数记录一下这本书的习题的答案，这是第五章的练习。 To the book page Flattening将包含数组的数组展开，即只有一对中括号的数组。 1234567let arrays = [[1, 2, 3], [4, 5], [6]];// Your code here.let combineArrays = arrays.reduce((accumulator,currentArray)=>{ return accumulator.concat(currentArray);},[])console.log(combineArrays);// → [1, 2, 3, 4, 5, 6] Your own loop如果不能满足条件（testAct）就不能继续循环。下一次循环要用新的值（updateAct），每次循环需要执行一定的操作（bodyAct）。 123456789101112// Your code here.function loop(value, testAct, updateAct,bodyAct){ ...

用Github Desktop简化你的推送流程Github Desktop官方网站 1. 第三方仓库克隆选择file->clone repository, 通过URL克隆你的仓库选择URL，里面填你的第三方仓库的https克隆链接，注意要填写公网地址而不是内网地址。 注意选择你保存仓库的本地位置 点击clone后应该会弹出让你输入用户名和密码，如果是gitlab，直接输入你登录gitlab的用户名和密码。 到此为止应该是可以克隆仓库到本地了。之后的操作，和一般的git操作是一致的，不过是有了图形化的界面，不用输入繁琐的命令。 2. add 和 commit直接到app界面，一旦仓库有文件更改，app界面会罗列出你更新文件的内容，需要你进行commit操作。 3. push处理完所有的commit后就可以进行推送了，直接点击界面右边的push origin 即可。

Chess For Three这是Codeforces Round 945 (Div. 2) 第一题。 题目链接 题意三个人玩游戏，每局两个人玩。赢得人得2分，输的人得0分。平局每个人得1分。会给你三个人的最终得分，问最多平局多少局。 重点记录这里题确实不难，但是有一个样例因为没有给怎么算的导致我一直以为样例给错了。。。 123 4 56 3分4分5分，最大平局数是6。 我最一开始想的是a和b平局3次，b还剩一局和c平局，这是4次。a和c平局3次，b和c平局2次，这是5次。但是样例给的是6次。 6次的情况应该是c和a平局2次，c和b平局3次，a和b平局1次，这样就是6次。这真的是太amazing了。 题解可以直接暴力枚举a和b，a和c，b和c平局次数，然后判断分数是否合法。除去平局的分数，剩下的分数应该left%2==0。 但是还有结论， min((p1+p2+p3)/2,p1+p2)，这里保证p1<=p2<=p3。 先考虑合不合法，三个数加一起如果是偶数就一定合法。 ...

Prison Escape这是codechef starter 134 div4的第六题。题目链接 题目大意NxM的01矩阵，0代表罪犯，1代表守卫者。罪犯可以上下左右移动，计算罪犯最少需要经过几个守卫者才能逃出这个矩阵。我们要求出这些罪犯里边经过最少守卫者数量的最大值。数据范围：T 1000，N和M...

3out1in题目链接 题目大意这是codechef starter 134 div4的第五题。 给你一个数组B，里面包含M个数字，其中M必定为奇数。操作是选出三个数字a,b,c, 这三个数字从数组里剔除，数组中重新加入成员a+b-c。可以看出来每一次操作会让数组少两个元素，问最后剩下一个元素的最大值是多少。其中有多个询问，询问内容是如果只有前k个元素，剩下的最后一个元素最大值是多少。 赛时回顾我在第一次做这道题的时候就直接考虑到了用优先队列。显然最优解是每次选两个最大值，然后减去最小值。原数组我用数组a存储，每次将前k个元素送入优先队列和数组b中，数组b进行排序用来获得最小值，优先队列获取最大值。成功拿到30分的部分分，其他测试会超时。 正解官方题解思路让我恍然大悟。永远记得可以用空间换取时间。既然可以用一个优先队列，那么我们就可以用两个优先队列。虽然我们不知道给出的qurey里k的值是多少，但是我们可以用ans数组记录所有对应k值的答案。 ...

Codeforces Round 944 (Div. 4) 回顾比赛回顾赛中是AC了前四题，E答案错误，F超时。可以说是做到了最后五分钟，排名是6000多。 比赛链接 官方题解链接 题目分析AB就直接跳过了，纯签到。 C. Clock and StringsC题意思是给出表中两对数字，看每对数字连接的线是否相交。我的思路是只要一条线的一个端点在另一条线的区间内，切另一端在区间外即可断定这两条线是相交的。 为了更好的进行区分，我进行了排序，其中满足a<c a<b c<d。 我觉得不能直接去写，表上的数字是1到12，对于一条线，一个端点是1，另一个端点是10，其中11和12其实是在线的包围内的，所以我给所有小于6的数字加了12，区间变成了6到17，然后判断是否c在a和b之间,d在a和b之外。但是我今天才发现我的判断语句竟然是这样的： 12if((a<c&&c<b)||(a<d&&d<b)) cout<<"YES"<<endl; else...