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) 未归档(72) 算法(1) 背包问题(1)

/ 注册

全部文章（共109篇）

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

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

2017-08-20

0 807

【POJ2449】Remmarguts' Date （A* k短路）

题目链接：http://poj.org/problem?id=2449 题解： A*求k短路模板题… 反向SPFA，dis数组为估价函数，当目标点的更新次数达到k时，就求出了广义上的k短路 //by sdfzchy #include<cstdio> #include<cst...

2017-08-20

0 425

【NOIP模拟8.13】

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

2017-08-14

0 458

【NOIP模拟8.12】

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

2017-08-12

0 348

【NOIP模拟8.9】

T1 fuction 题意：求给定a,b,c,求ax+by=c的正整数解个数题解：扩展欧几里得求出最小正整数解，然后通过 <nobr> x=x0−k×bgcd(a,b) </nobr>, <nobr> y=y0+k×agcd(a,b)...

2017-08-09

0 406

【NOIP模拟8.8】

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

2017-08-08

0 364

【NOIP模拟8.7】

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

2017-08-08

0 363

【NOIP模拟8.6】

T1 gift Solution：题目描述显然就是一个背包，然而就是不知道怎么拿背包做QAQ 爆搜+剪枝三十分正解的确是01背包首先将 <nobr> w </nobr>从小到大排序，题意可以转化为买其中若干物品后，剩余钱数小于所有剩余物...

2017-08-06

0 398

【洛谷1801】黑匣子

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

2017-08-04

0 507

【NOIP模拟8.4】

T1 打工 PS：本人比较懒就不发原题了（orz），网上查就有想到了是DP但是转移有一点问题（雾…），然后只好特判+爆搜水过20分题解： 30分做法：首先我们发现得到的序列有一个性质，即 <nobr> a[i]<=max(a[j])+1　(j<i) ...

2017-08-04

0 414