house_cat

分类

ACM(110) JAVA(5) 其他(3) 文(1) 算法导论(2) 计算机图形学(4) 面试(2) 题解(2)

/ 注册

全部文章（共129篇）

Travelling Businessmen Problem

Travelling Businessmen Problem 先求出图的两个部分，可能只有一个部分然后用set模拟，得到不同部分差最小的 #include <bits/stdc++.h> using namespace std; typedef long long ll; ...

STL-set

2019-09-14

0 380

Random Access Iterator

Random Access Iterator 树型概率DP dp[u]代表以当前点作为根得到正确结果的概率将深度最深的几个点dp[u]很明显是1 然后很简单的转移有k次，但我们要先看一次的情况，然后再推到k次，k次中只要有一次就可以正确，所以求出k次全失败的概率，用1去减即可 #in...

概率树动态规划

2019-09-14

0 424

Complier

Complier [2019福建省赛] 模拟题应该有信心写，多出一些样例当/* 与// 在一起的时候总会出错，一旦出现了这些有效的应该把它删掉不对后面产生影响 #include<bits/stdc++.h> using namespace std; char s[1000...

模拟

2019-09-14

0 430

Review For Exam

Review For Exam [2019 福建省赛] 一个很简单的状态压缩DP，结果集体走偏如何解决连续几日的限制问题？这种东西普通的DP很难写 #include <bits/stdc++.h> #define ll long long using namespace std...

动态规划状态压缩

2019-09-14

0 365

Pipe Fitter and the Fierce Dogs

Pipe Fitter and the Fierce Dogs [JAG Asia 2016] 理解题意之后，就是一个非常傻的DP 然后难在理解题意，理解非法状态 #include <bits/stdc++.h> using namespace std; const int ...

动态规划

2019-09-14

0 456

Escape from the Hell

Escape from the Hell [JAG Asia 2016] 容易证明优先选择差值大的更优对于最后一瓶我们可以枚举枚举最后一瓶，然后在树状数组上消去它的影响，然后线段树check是否出现被追上的情况，即查询区间最小值。需要用到两个线段树，因为当二分找到的位置在最后一瓶后面...

树树状数组线段树

2019-09-14

0 431

We don't wanna work!

We don't wanna work! [JAG Asia 2016] 两个set，一个代表工作的，一个代表不工作的其实是一个很简单的模拟，但是我竟然排序之前标号。。。。检查代码的时候要从头开始检查。。 #include <bits/stdc++.h> using n...

STL-set

2019-09-14

0 351

[徐州网络赛]Longest subsequence

[徐州网络赛]Longest subsequence 可以分成两个部分，前面相同，然后下一个字符比对应位置上的大。枚举这个位置用序列自动机进行s字符串的下标转移注意最后一个字符 #include <bits/stdc++.h> const int maxn = 1e6 ...

序列自动机思维字符串

2019-09-13

0 420

[单调队列]XKC's basketball team

XKC's basketball team 题意：给定一个序列，从每一个数后面比它大至少 \(ｍ\) 的数中求出与它之间最大的距离。如果没有则为 \(-1\)。题解：从后向前维护一个递增的队列，从后往前遍历，若当前的数大于队尾就进队，否则从该队列中二分找最小的比自己大至少 \(ｍ...

单调栈

2019-09-13

0 377

XEN 3166

XEN 3166 这题原题是spj，校oj上只用判断yes no，不过也差不多题意分析之后就是求两个东西：字典序最小的长度为m的子序列同时这个字典序严格大于某个字符串用序列自动机先尽量相同，然后再考虑严格大于 #include <bits/stdc++.h&g...

序列自动机字符串

2019-09-13

0 437