- 博客(50)
- 收藏
- 关注
RSS订阅原创 Leetcode440. 字典序的第K小数字
没想到这道题竟然这么难。对于我这道题的难点就是分清字典序的标号和本身节点所代表的数值大小两个红色下标所代指的就是两个节点前缀之差即为一颗子树在字典序中有多少个点，这一点明白以后，大致在外部函数计算子树大小时就没有这么多疑惑了。下面最重要的就是分清下标和数值大小。#include<bits/stdc++.h>using namespace std;typedef long long ll ;class Solution {public: ll cal(ll x , ll
2021-06-04 20:48:37
190
原创 如何理解协方差矩阵（散布矩阵）
这学期开了模式识别的学习课程，经常提到概率论与数理统计的一个概念：协方差矩阵（在模式识别中又叫散布矩阵）。理解这个矩阵严格意义上来说其实不需要太多先导知识，我们只需要了解一些线性代数基本的概念。但是你如果不了解协方差矩阵，听模式识别的课程就会云里雾里（就像我一样）。那么在学习协方差矩阵之前首先你需要知道一些统计学的基本概念1.均值：2.样本标准差：均值很好理解，是描述样本集合中的中间点，是所有信息的平均。而标准差描述的是一种散布度，比如[0,10,11]和[6,7,8]的均值是一样的都是7，但
2021-04-01 21:41:54
1646
原创 POJ 2505 A multiplication game
题目链接题意：乘法博弈，每个人可以从1开始乘，大于等于n的胜题解：sg函数打表找规律发现和18有关。sg函数打表代码：#include<cstdio>using namespace std;const int N = 1e4+10;typedef long long ll;ll n ;int SG(ll x){ if(x >= n) return 0; for(ll i = 2;i <= 9 ;i ++){ if(!SG(x
2020-12-03 16:19:58
119
原创 POJ 2975 Nim
题目链接：https://vjudge.net/problem/POJ-2975题意：严格意义来说其实并不是博弈论。有多少种方法可以产生必胜态（也就是让对手为必败态），也就是异或值为0的方式题解：模拟，前缀异或和后缀异或即可。坑点：不能等于#include<cstdio>using namespace std;const int N = 1e4+10;typedef long long ll;ll a[N];ll pre[N] , suf[N];int _ , n ;
2020-12-03 16:14:56
102
原创 HOJ 4388 Stone Game II
链接：vj链接分类：类签到题题意：一堆可以拆成k和k xor n堆（两者同时得小于n）题解：完全就是最简单的奇数偶数博弈，因为拆位只能在已有位中拆，所以就是每个数的位数-1相加判奇数偶数。#include<bits/stdc++.h>using namespace std;const int N = 55;int a[N];int _ , n ;int main(){ int T = 0; for(scanf("%d" , &_) ; _ ; _ -
2020-12-03 16:10:04
91
原创 Codeforces Round #680 D Divide and Sum
题目链接：链接题目大意：2n的序列分成两部分p和q，p递增，q递减，对于每一个下标i求一下abs(p[i] - q[i])的值，p和q都是任意分开的。题目思路：首先提出一个结论：对于任意的p序列和q序列，他们的差值和都是一定的。下面我们思考如何证明：1.先将2n的序列排序，并将它们分成两部分，我们假设左半部分是L，右半部分是R，他们的长度均为n2.假设我们在L部分任意拿出了x个数给p序列，那么右半部分一定拿出n-x个数，于是剩下的数就全部属于q序列p：L中x个数，R中n-x个数q：R中x个数
2020-11-27 17:57:04
79
原创 SG函数 《算法竞赛进阶指南》总结与练习 Acwing235 魔法珠
题目链接：链接题目大意：中文=-=题目思路：和2020ccpc网络赛的题目有点像，但简单了不少，考验你SG函数的理解。这一题纯凭自己理解手打的，如有不对之处请大佬指正。1.首先基础之处便是对这个公平组合游戏的判断，必胜态必败态，公平，相同规则下几个条件都满足。肯定是个sg函数的题目2.每个数有自己对应的sg值，这个sg值是什么得根据题目的限定条件来决定，因为是分解成他的约数，从SG定理中可以知道，肯定是各个约数sg异或之和，而由于每个数都可能被删除一次，那么将每一次的异或值算出来，根据sg定理，可以
2020-11-21 14:21:25
185
原创 ccpc 2020江西省赛 博弈论 J Split Game
题目链接：J蓝书链接：蓝书题题目大意：和蓝书上的有向图剪纸游戏博弈除了获胜方式不一样，其他几乎是一样，给你一个n×m的纸片，每一次可以将纸片剪成两部分，谁先剪出1×1的格子就必败。题解思路：其他所有地方都几乎和蓝书上的模板题目相同，主要是如何处理必败态，训练赛中wa的点就是处理的时候简单的把1×1的状态也就是在sg[1][1]中表示的状态简单的划归为必胜态，这是完全不对的，其实稍加思考会发现sg搜索的过程中他是不会枚举1×1的状态的，因为这种状态对于参与游戏的两个人是必败状态，他们是不会主动去选择这种
2020-11-21 12:18:22
851
1
原创 博弈刷题小集锦，码
POJ 2234 Matches GameHOJ 4388 Stone Game IIPOJ 2975 NimHOJ 1367 A Stone GamePOJ 2505 A multiplication gameZJU 3057 beans gamePOJ 1067 取石子游戏POJ 2484 A Funny GamePOJ 2425 A Chess GamePOJ 2960 S-NimPOJ 1704 Georgia and BobPOJ 1740 A New Stone Game
2020-09-22 14:55:45
105
原创 SG函数之POJ2311Cutting Game && AcWing219 剪纸游戏
题目链接：链接Cutting Game思路：1.1×X 或 X * 1的纸张一定是必胜态，然而他们必须经过2×2，2×3，3×2的局面，而这些局面为必败态，由此推出了在我前一篇博客中讲到的公平组合游戏四要素1.2人的公平游戏2.交替操作3.操作方法一样4.无法操作的时候为负（在这里便有所涉及）接下来就是如何写SG函数了，如下：#include<bits/stdc++.h>using namespace std;const int N = 210;int n , m;int
2020-09-22 14:54:26
168
原创 SG函数详解
SG函数详解关于概念必胜点和必败点必胜点和必败点的性质组合游戏SG函数的分析与推导取石子问题Sprague-Grundy定理（SG定理）：SG函数小习题简介：sg函数和sg定理是公平组合游戏中的重要组成部分，这篇文章是结合博客（末尾会贴博客链接）和我之前写博弈论题目的总结与反思，因为之前并没有系统的学习sg函数，所以做博弈论的题目可谓是一波三折，可以说学习sg函数的相关内容加深了我对博弈论的理解，让我对博弈论题目有了一个系统的思考。这篇博客是一篇小小的总结，以后提高最重要的方法还是需要多刷题。关于概念
2020-09-22 14:42:56
2668
原创 [NOIP2010]关押罪犯
快乐水题，不用调bug题目链接：https://vjudge.net/contest/369847#problem/A思路：二分+二分图判定，很快乐，萌新必备题。总结：这种转化成图的思路还是很有参考价值的，再加上学会用二分转化，真的很受用，学到了。题虽水，而解精妙#define _CRT_SECURE_NO_WARNINGS 1#pragma GCC optimize(2)#include<bits/stdc++.h>#include<iostream>#includ
2020-08-25 11:05:06
99
原创 2020 Multi-University Training Contest 3 HDU 6798 Triangle Collision
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6798题外话：发现即使是程序竞赛的几何题也像是小时候做的那些几何题一样，（当然肯定会难一些）需要你去构造或者说做一些辅助线来进行，这道题目真的让人有些思考（还是我太菜了）对于这种几何题，你可能应该有一些自己学会构造的思想蕴含在其中。这一题真是太典型了，二分+计算几何，确实是好题啊！题目思路：构造多个三角形对于当前方向上的路径利用时间进行二分，判断穿过的边的个数很棒的题！#define _CRT_SEC
2020-08-23 15:33:40
130
1
原创 POJ2230 Watchcow
https://www.acwing.com/problem/content/368/简单题就来打个卡，顺便提醒一下，欧拉图判定条件，无向图为欧拉图，当且仅当无向图连通，并且每个点的度数都是偶数。#define _CRT_SECURE_NO_WARNINGS 1#pragma GCC optimize(2)#include<iostream>#include<stdio.h>#include<algorithm>#include<vector>
2020-08-23 11:58:50
100
原创 POJ2942 Knights of the Round Table
亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求： 1、相互憎恨的两个骑士不能坐在直接相邻的2个位置； 2、出席会议的骑士数必须是奇数， 这是为了让投票表决议题时都能有结果。如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个
2020-08-21 16:09:08
133
原创 POJ 3649 Network
太痛苦了原谅我开头就宣泄负能量，但是一个极low的模板题式的题目花了我两天时间调bug，调的真的是昏天黑地啊。既然这么痛苦就好好写写这个博客吧。题目链接：https://www.acwing.com/problem/content/description/366/题意：中文题解：point1 ：求出边双连通分量，并缩点得到一棵树point2：对于每一条加入的边在缩点后的树上，他的两个节点对应树中节点，树上两个节点路径上的桥全部标记并在答案中减掉（在之前已经标记过的桥不用减）这个在之前写的时候真没
2020-08-20 11:42:18
107
原创 BZOJ1123 & Acwing 363
《算法竞赛进阶指南》签到题，ps：快点写博客啊！！！https://www.acwing.com/activity/content/problem/content/679/1/题意：中文思路：需要理解的是对于一个点的子节点是相对是割点的子节点集合t1,t2…ts，那么对于当前节点的答案贡献为sz[t] * (n-sz[t]),对于剩下的点直接加上（sum+1）*（n-sum-1）（此为所有相对割点sz大小之和）#include<bits/stdc++.h>using namespace
2020-08-12 15:43:33
88
原创 Codeforces Round #652 (Div. 2) A~E
链接：题目赛后总结Codeforces Round #652 (Div. 2)A.FashionabLeeB.AccurateLeeC. RationalLeeD. TediousLeeE. DeadLee小总结Codeforces Round #652 (Div. 2)A.FashionabLee题意：能不能构造多边形和x轴，y轴同时平行思路：边数得是偶数的同时，同时满足(n-2)/2为奇数int main(){ int _; for(scanf("%d" , &_);
2020-06-25 15:14:41
171
原创 K MUV LUV UNLIMITED Gym 102361K（树上博弈详解！）
链接题意：两人轮流取叶子，取到根的人获胜参考博客本题其实花了很长时间去理解去看，之前真的不是完全明白为什么这样，看了上面的那篇参考博客，我想我应该对博弈题有一点浅薄的认知了。而我自己写的这一篇博客相当于我理解的一个过程，我觉得是写的更加详细了一点，仅供大家参考，说的内容还是很详实的。思路：打这场训练的时候当时就根据题意推了很久，用的非常笨的方法，利用已知必胜态必败态推导未知必胜态和必败态，草稿纸上推演了很长时间，就是想尽办法把必败态转化。失败了。因为太过于复杂。下面介绍博客链接的方法，我认为这个
2020-06-16 14:25:25
673
原创 CH#56C 异象石
一道贼可怕的题目，这能想到就想到，不能想到就等着被算法题目（日常）揍吧。另外这道题有参考别人代码之嫌，实属弟弟行为，下次一定不。题目链接：良心网站acwing题意：中文题啊=_=思路：LCA+set维护，首先你得要理解时间戳的概念，对于出现的异象石你可以发现一个规律叫做按照时间戳排序，异象石的节点连成一个圈，并且累加相邻的节点，最后得到的结果恰好是路径和的两倍，这是本题最为可怕的地方，因为你根本想不到竟然还可以这样累加，我下次该怎么想这种题目？手画样例？还是默默的把这种结论记下来？很难考到这么奇怪的
2020-06-14 15:22:28
156
原创 Educational Codeforces Round 89 (Rated for Div. 2)重点：D. Two Divisors
链接虽然因为菜造成了这么慢的写完，但至少策略上没有什么问题，既然卡题那就做下一题，再卡就再换，虽然最后的时间都不够做这道D题了A、Shovels and Swords题意简单不表菜是原罪，比赛的时候尝试了各种手段，各种方法首先要求出x+y的最大值可以列出等式x + 2y <= a;2x + y <= b;由此可知3x+3y <= (a+b)因此x+y <= (a+b)/3到了这步我就不会了，感觉不是充要条件，当然事后题解是和a,b再取个最小值，但我当时真懵了，
2020-06-14 15:06:06
188
原创 Codeforces Round #485 (Div. 2)重点：D - Fair多源最短路
链接A - Infinity Gauntletmapint n;int a[N];int main(){ map<string,int>mp; string a[8]; mp["purple"] = 1; a[1] = "Power"; mp["green"] = 2; a[2] = "Time"; mp["blue"] = 3; a[3] = "Space"; mp["orange"] = 4; a[4
2020-06-13 11:10:21
128
原创 Codeforces Round #646 (Div. 2) url：E.Tree Shuffling
646 div2复盘：本场签到题AB写的略慢，B甚至没把思路考虑清楚，就开始动键盘，E题也没把思路考虑完整清楚。之前自身出现的问题是不懂一个思路遇到挫折就换一个思路，现在是没把思路考虑完整，结合样例考虑（正式比赛中还需要这样自己想样例的能力）。A.Odd Selection思路：我的思路统计奇数偶数个数的情况，只有奇数个奇数才能满足此题条件，但是在这个条件的基础上还需要满足他的个数符合要求，标程写的还是也还挺好的，但是像我就是会考虑个数的关系，其实没有利用好计算机的特点；int a[N]; in
2020-06-03 12:15:14
106
原创 Codeforces Round #645 (Div. 2) 重点：D：The Best Vacation
题目链接：点这里D. The Best Vacation题意：一年有n个月，每个月有di天，给你len天假期，如果在每个月的第j天拜访他人就会获得j个拥抱，让你最大化拥抱。解题思路：主流思路叫做双指针，但是不是双指针的那种典型的写法，首先做这道题之前需要证明一下，假期选择天数的结尾一定是每个月的结尾天数...
2020-06-02 11:53:18
121
原创 Codeforces Round #581 (Div. 2) 重点：C.Anna, Svyatoslav and Maps
啥也不多说了，重拾坚持题解，不写题解不是人，做一题写一题，不转不是中国人（最后一句纯玩梗，瓜众散了散了题目链接：在这里A.BowWow and the Timetable题意：快A题，主要是注意审题int main(){ string a; while(cin >>a){ int f = 0; for(int i = SZ(a)-1;i >=1 ;i --){ if(a[i]=='1')f = 1;
2020-05-28 00:58:49
130
原创 尺取法Codeforces 985E Pencils and Boxes （复习一下尺取法）再次开启咕咕咕之旅
去吧皮卡丘Educational Codeforces Round 44 (Rated for Div. 2)题意：给定n，k，d，表示给你n支铅笔，每支有一个权值v。现在让你把n支笔放入一些盒子中（盒子数量可以无穷大），每个盒子中至少有k支笔，而且每个盒子中的最大笔的值与最小笔的值不超过d。问你能否找到一个合法的放法，可以输出"YES"，否则输出"NO"。思路：排序是不可能的啦，这辈子都不...
2020-05-07 23:57:20
118
原创 线段树解题报告
H Moving Points题目链接：https://vjudge.net/contest/358745#problem/H思路：树状数组维护，类似于树状数组求逆序对+思维（思维量很小）#include<bits/stdc++.h>using namespace std;const int N = 2e5+9;typedef long long ll;struct no...
2020-03-01 00:10:39
2708
原创 hrbust寒假训练第一场
题目链接：https://vjudge.net/contest/348944#overviewA：CodeForces 1255C题意：给你n-2个打乱顺序的三元组序列，让你排出原序列。思路：哇，这题思路很明显啊，不过说实话代码好难敲呀。首先找出现一次的，然后在其中确定出现两次的出现三次的，把他们都标记一下，再以这两个去确定剩下的那个未被标记元素，找到n个就结束了。我的代码蛮丑的，不知道咋优...
2020-01-18 13:15:30
280
原创 hrbust寒假训练第二场
链接：https://vjudge.net/contest/348951A：CodeForces 1256D题意：通过给你的不超过k次交换，使字典序尽量小。思路：这题还是比较清晰的，把0往前移就是了，主要代码实现上需要简洁一点，自我认为代码实现还算简洁。哦对，要注意k的longlong的问题，因为这个还wa了一次，太傻了。#include<bits/stdc++.h>usin...
2020-01-17 13:24:14
1762
原创 Good Bye 2019前四题ABCD
题目链接：http://codeforces.com/contest/1270 good bye 2019A:最大的谁大谁赢B:小小思维题，，，相邻两个绝对值大于等于2就输出那俩#include<bits/stdc++.h>using namespace std;const int maxn = 2e5+9;const int inf=0x3f3f3f3f;int a[m...
2020-01-13 23:04:21
296
原创 算法竞赛进阶指南 线性dp
1.poj2279思路：线性dp，但过不了poj上的样例，会爆内存，，实验只能去Acwing上实验。最后一个last元素可以尝试每一排，但是有个界限状态的要点我觉得应该把初始状态设为dp[1][0][0][0][0]=1应该比dp00000更好理解个人认为。。要开Long Long #include<bits/stdc++.h>using namespace std;type...
2020-01-13 22:44:18
299
原创 hrbust2460.三维空间的移动方式
题目链接：http://acm.hrbust.edu.cn/index.php？m=ProblemSet&a=showProblem&problem_id=2460题意不表题目感想：虽然是简单题吧，但是由于是算法思维和代码能力的练习，所以把它补了，这题的思维真的类似于数字三角形那题，就是逆推dp思想，逆推逆推！校赛两道题都是这个思想，也是一个教训，而且对于每一个算法的理解基础真...
2019-12-09 10:43:54
301
原创 Codeforces Round #511 (Div. 2)
题目链接：http://codeforces.com/contest/1047A Little C Loves 3 I#include<iostream>#include<cstdio>using namespace std;int n;int main(){ cin>>n; if(n%3==0){ cout<&l...
2019-12-04 19:33:08
116
原创 Codeforces Round #600 (Div. 2)D. Harmonious Graph
题目链接：https://codeforces.com/contest/1253/problem/D题意：若某个节点编号到大于他的编号的节点，那么他们之间的任意一个点也要可达。题目思路：开始的时候想的是一个加权并查集，权维护的是最远的点，这和后来的正解做法思路确实是反了，直接把父亲节点当做是当前节点的最远节点即可。要说有什么教训，我感觉太多了，思路出来以后，一定要思考他的正确性，千万别吊死在...
2019-11-19 13:51:14
145
原创 Educational Codeforces Round 76 (Rated for Div. 2) D - Yet Another Monster Killing Problem
题目链接：http://codeforces.com/contest/1257/problem/D题目大意：有n个怪兽，对应n个攻击力，m个奥特曼（大雾），每个奥特曼有一个攻击力和攻击天数（他们可以任意派出和使用），怪兽必须按顺序打败，问最少多少个奥特曼可以击败所有怪兽，若击败不了所有怪兽，输出-1从这篇题解中真的学到很多，写这种思维题的时候，我没有学会用整体的思维去考虑问题，应该像当初写高...
2019-11-15 20:15:11
234
原创 POJ3126 Prime Path
POJ3126 Prime Path题意：只能通过素数到达想要的那个数，问你最短的路径；解题思路：拥有所有素数，bfs复盘过程：虽然是个基本的bfs的题，但想用dfs做，本来想借助dfs搞清楚他的迭代过程，结果搜索的分支十分混乱，不对，应该说迭代的太深了，想想dfs先序遍历的原理就知道不能如此，于是最后向bfs低头。明显基础题。。基础不牢，地动山摇！#include<stdio.h&...
2019-11-13 18:52:45
136
原创 poj1182食物链，最经典的加权并查集
题目链接添加链接描述题意：中文题不表解题思路：太经典了，说实话其中的向量偏移的思想减少了好多好多的代码量，不然可能需要使用16个if来判断，实际上，其中的findx函数使用的思想就是同向直接相加的感觉。很多博文写的很好代码参考博客百度推荐第一条博客向量偏移，再加上递归加权的思想。有点菜，不过加油。#include<stdio.h>using namespace std;...
2019-10-31 17:21:27
172
原创 2019icpc银川站总结
对，没错，就是这一场被称为史上最水icpc的这场比赛，我们还打铁了回来以后，训练的时候，不小心听到对面学长的窃窃私语，什么谁去谁去都能拿金，，，真的很难受，一场史上最水的icpc，被我们打成这样，真的巨难受，也算是时隔那么多天还是写了总结的契机吧。真的经验实在是太少了，感觉实在是太可惜，太可惜，越可惜，其实就越难受。。回来还有其他队的人和我说什么：我也想去打银川站，，，很丧。回来也甚至没有和教...
2019-10-30 16:54:32
1355
3
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人