DFS | 位运算 | 位运算优化N皇后问题
借 LeetCode 的每日一题 51. N 皇后 - 力扣(LeetCode) 学了一下使用位运算优化 N 皇后问题的方法,不由得感叹位运算真是个神奇的东西,整理一下:
题目按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
text123输入:n = 4输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释:如上图所示,4 皇后问题存在两个不同的解法。
提示:1 <= n <= 9
DFS + 位运算优化首先基本的 DFS 解法就不多赘述了, ...
关于vector的小测试
今天突然发现自己是个大杀软。。。
起因在LeetCode上写题,想了半天毫无头绪,遂翻题解,恍然大悟,直呼妙哉😆
按照题解思路快速完成代码并提交,击败了50%多点的选手🤨
然而点开击败了99%选手的提交代码,发现和题解也是一样思路,遂百思不得其解😕
发现99%代码还使用了我认为奇慢无比的下标直接访问vector元素!?
想当年我了解到使用iterator遍历vector后便为这种看起来很高大上的方法所折服并沿用至今,面对着“三观”尽碎的可能,上网查资料得知:下标直接访问的确比iterator更快!!
但是。。。毕竟实践是检验真理的唯一标准,我决定再自己试试(临死挣扎)。。。
测试分成3组:
直接用下标index
迭代器iterator
C++11中的新特性foreach
网上查阅资料得知,iterator访问有几种优化方法:
使用后自增
常量迭代器
提取vector.end()
首先是代码:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 ...
分治 | 二分 | 寻找正序数组的中位数
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/median-of-two-sorted-arrays
Description给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
Input两个 vector<int>,表示两个正序的数组
Output两个数组合并后的中位数(double 类型)
Sample Input12示例1: nums1=[1,3], nums2=[2]示例2: nums1=[1,2], nums2=[3,4]
Sample Output12示例1: 2示例2: 2.5
Hintnums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000$-10^6\leq nums1[i],\;nums2[i]\leq 10^6$
分析做完这个题才知道自己OI ...
暑期“毕设” -- Contest Killer
暑期 “毕设” ——Contest KillerContest Killer初学WPF,写了这个OI离线测评器
可以把它看成是CCR-Plus的换皮版(毕竟评测器部分的源代码都是照搬的…………)
因为UI字体普遍比较大,适合较大大屏幕的玩家使用
已开源,
Github:Yan2u/Contest_Killer: An offline judger for Olympiad in Informatics (github.com)
记录断断续续写了两个月……不断重复发现问题 + 上网查资料 + 现场学习 + 解决问题,纯面向问题编程了
虽然用了viewmodel和command,但是感觉自己还不是很懂MVVM,感觉用绑定事件来写也差不多
下一目标:用ASP.NET搭建自己的博客
加油:)
一些截图
Deepin 初体验
Deepin 初体验家里的古董笔记本好像带不动最新的 Windows10 了,最近使用体验比较差,但平时又不怎么用它……
那么,何不拿这台笔记本搞点事儿呢??
想起以前在网上看到基于 Linux 的 Deepin OS 的时候,被它高端大气上档次的界面吸引了(然后尝试用VMWare装但是失败……),于是这次我打算动真格,直接在笔记本上安装 Deepin OS!
安装 Deepin首先 Deepin 官网本身的下载链接速度奇慢,这里推荐使用清华的镜像源下载:Deepin-CD
打开之后选择 Deepin-15.11-amd64.iso 下载镜像文件
之后就是用 UltraISO 烧录启动盘,然后开机 F2 进入 Boot 界面,选择 USB-HDD 启动
启动之后成功进入安装界面,按照提示操作一波之后,安装成功
图是网上找的:)
配置 Deepin进入桌面,发现 Deepin 已经自带了 Chrome,WPS Office,搜狗输入法,和虽然是上古版本的 QQ,感觉比安装 Manjaro 的时候一个个手动 sudo pacman -S ... 方便了许多(最蛋疼的是输入法配置)
...
Neumorphism UI: 新拟态设计
新拟态设计:Neumorphism UINeumorphism UI
新拟态设计(Neumorphism UI)是 2020 年 UI 设计的主要趋势之一,你可以在 dribbble 上看到很多作品,新拟态是基于New+Skeuomorphism 英文单词的拼写。它是一种使用对象阴影的模糊、角度和强度来突显出对象的样式。由于其柔和的阴影和整体的外观,使该设计看起来更加的逼真、未来、现代、真实、有吸引力。
拟态,在生物学中指的是一种生物模拟另一种生物或模拟环境中的其他物体从而获得好处的现象,用在 UI 设计上,即是让 UI 元素模拟生活中的物体的形状与特征(就像桌面的垃圾桶图标那样),从而让 UI 元素具有生活中物体的层次感和辨识度
新拟态结合目前比较流行的扁平化设计和卡片式设计和拟态的设计风格,起源于一套在 dribbble 上走红的设计方案:
设计师 alexplyuto 发表了这套设计方案,获得数千点赞,之后类似风格的新拟态设计大量出现,可以说他的作品开创了 UI 设计的一个新趋势
个人感觉这套设计方案很有现代感,简洁的同时有富含层次感,可以感觉到每一个元素仿佛都是雕刻在了背 ...
LrcEditor开发记(一)api接口
前言项目地址:Github
前一段时间将我写的歌词编辑器 LRCEditor 完善了一下,添加了一个搜索歌词的功能,但是仅限于网易云(因为网易云音乐的API是最好搞的),有一些网易云上面没有版权的歌曲自然就搜不到歌词,非常影响体验
于是就想到将另外两家音乐软件:QQ音乐和酷狗音乐的 API 也搞过来,添加到搜索功能里面去,这样基本上就不用担心搜不到歌词了:)
然后就花了整整一天时间研究他们的 API……
这里将 QQ 音乐和酷狗音乐的 API 接口使用整理一下,看到这篇文章并且有需要的小伙伴就可以直接拿去用了:)
P.S.1 整理的时间是 2020 年 2 月,有些接口过了一段时间可能就被更换了,所以看完还请自己先验证一波……
P.S.2 本文中接口网址返回的数据均为 JSON 字符串
P.S.3 有关网易云接口的整理在另一篇博文里,链接:VB.NET | 在线获取歌词方法的小小总结
1. QQ 音乐部分搜索歌曲网址格式:https://c.y.qq.com/soso/fcgi-bin/client_search_cp?aggr=1&cr=1&flag_qc=0&am ...
动态规划 | 线段树 | 0/1分数规划 \ | 图论 | 201901031考试:解题报告
题目限制一览
题目
时间限制
空间限制
1. array
1000 MS
128 MB
2. bus
2000 MS
128 MB
3. team
3000 MS
256 MB
1. 逆序数对列(array.cpp)Description对于一个数列{ai},如果有iaj,那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的
数列,可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个?
Input第一行为两个整数n,k。
Output写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对10000求余数后的结果。
Sample Input14 1
Sample Output13
Hint样例说明:
下列3个数列逆序对数都为1;分别是1 2 4 3 ;1 3 2 4 ;2 1 3 4;
100%的数据 n<=1000,k<=1000
分析
正统解法
设 $f[i][j]$ 表示 $1\rightarrow i$ 的排列中逆序对数为 $j$ 个的方案数
那么一些边界的情况就可以 ...
动态规划 | 贪心 | 图论 | 201901025考试 :解题报告
题目限制一览
题目
时间限制
空间限制
1. trapped
1000 MS
128 MB
2. array
1000 MS
128 MB
3. travel
1000 MS
128 MB
1. 陷阱(trapped.cpp)DescriptionFJ将N(1<=N<=100000)堆干草放在了一条平直的公路上。第j堆干草的大小为Sj,坐标为Pj。奶牛贝茜位于一个没有干草堆的点B。
奶牛Bessie可以在路上自由移动,甚至可以走到某个干草堆上,但是不能穿过去。如果她朝同一个方向跑了D个单位的距离,那么她就有足够大的速度去击碎任何大小严格小于D的干草堆。当然,在这之后她就可以获得了更大的活动空间,以尝试击碎更多干草堆。
约翰可以指定某堆干草,并增大它的大小,他想知道他最少需要 增大多少,才能把奶牛贝茜困住(即在第一堆干草和最后一堆干草之间),或者根本不可能。
Input第一行两个整数,分别表示N和B
接下来N行,每行两个整数S,J ,描述了干草堆的大小和坐标
Output输出一个整数,表示FJ需要增加的最小值。如果不可能阻止Bessie ...
数论 | 同余 | 字符串 | 动态规划 \ | 树链剖分 | 201901024考试:解题报告
题目限制一览
题目
时间限制
空间限制
1. math
1000 MS
128 MB
2. path
1000 MS
128 MB
3. city
1000 MS
128 MB
1. 数学题(xorarray.cpp)Description一道数学题,表达式为:(B+E+S+S+I+E)(G+O+E+S)(M+O+O),该表达式共有7个变量,每个变量最多有500个可能的候选取值,问有多少种方式能使上面的表达式成为7的倍数?
Input第一行一个整数N
接下来N行,每行包含一个变量和其可能的一个值。输入数据保证同一个变量可能的取值各不相同,且都在-10^5 到 10^5之间
Output一个整数,表示方案数。
Sample Input123456789101110B 2E 5S 7I 10O 16M 19B 3G 1I 9M 2
Sample Output12
Hint12345The two possible assignments are(B,E,S,I,G,O,M) = (2, 5, 7, 9, 1, 16, 19) -> 51,765 ...