Scorpioch

未归档

01分数规划(1) dp(4) gcd(2) NOIP膜你赛(1) OIer的刷题记录(25) poj(3) sgu(1) 【神奇的】模板(1) 二分(1) 动态规划 - 数位DP(1) 动态规划 - 概率DP(1) 动态规划 - 背包(2) 字符串 - KMP(1) 搜索(1) 数学(2) 数据结构 - 线段树(4) 数论(2) 算法(1) 背包问题(1)

/ 注册

全部文章 / 未归档（共55篇）

【BZOJ1085】【SCOI2005】骑士精神（IDA*）

题目链接：https://www.luogu.org/problem/show?pid=2324 题解：经典迭代加深搜索考虑到步数最大只有15步，用IDA*比较好，估价函数设为有几个点未到达目标位置，进行搜索即可 //by sdfzchy #include<iostream>...

2017-08-20

0 807

【NOIP模拟8.13】

T1Matrix 题解：直接做矩阵乘法肯定是要GG的考虑对于每个询问，我们需要查询的是相乘之后的一个子矩阵的元素和那么对于一个 <nobr> ∑x2i=x1∑y2j=y1c[i][j] </nobr>,可以由 <nobr> ∑...

2017-08-14

0 460

【NOIP模拟8.12】

T1 BRS 题意：求区间最大连续子段和题解： 60分做法：在每一段里贪心地做LIS，复杂度 <nobr> O(nm) </nobr> 100分做法：用线段树维护一个 lmax，rmax，max，sum，做区间合并即可 //by sdfzchy #i...

2017-08-12

0 349

【NOIP模拟8.8】

T1 expedition 离散化后记录每一种士兵的出现次数计算即可 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long...

2017-08-08

0 365

【NOIP模拟8.7】

T1 Maximum 题意：给出一个序列a，求其中任意两项进行与/或/异或运算后的最大值 30分解法：暴力枚举两个数，复杂度 <nobr> O(n2) </nobr> 60分解法：注意到有 <nobr> %30 </nobr...

2017-08-08

0 364

【洛谷1801】黑匣子

题目链接： https://www.luogu.org/problem/show?pid=1801 题解：堆的巧妙应（ru）用（men）由于所有询问第 <nobr> k </nobr>小值的k是不断递增的，所以考虑可以使用堆来维护建立一个大根堆和...

2017-08-04

0 511

【CodeForces617E】XOR and Favorite Number

题目链接： http://codeforces.com/problemset/problem/617/E 题解：莫队算法考虑如何进行转移，对于异或运算有一个性质，即 <nobr> a </nobr>^ <nobr> a &l...

2017-08-04

0 396

【POJ2157】Maze

题目链接：http://poj.org/problem?id=2157 题解： BFS爆搜建一个bool1数组表示一个门是否走过，一个bool2数组表示任意一个点是否走过每次走到一个钥匙，该钥匙数+1，如果这个钥匙对应的门曾经到过，而且钥匙数够了，把门放进队列里，没有到过就个普通的点一样...

2017-08-01

0 374

【HDU3853】LOOPS

题目链接：传送门题解：很容易想到用 <nobr> dp[i][j] </nobr>表示从 <nobr> (i,j) </nobr>走到 <nobr> (r,c) </nobr>的...

2017-07-28

0 416

【洛谷1291】百事世界杯之旅

题意：https://www.luogu.org/problem/show?pid=1291 题解：假设当前已经得到k个名字，得到第k+1个名字的期望为 <nobr> nn−k </nobr> , 所以易得从第一个名字到最后一个名字的平均次数就是 &l...

2017-07-27

0 404