ars4me-CSDN博客

原创【退役】

本以为一切都会难以言表实际上到了这一步才发现一切都很好说虽然被之前的博客疯狂打脸哈哈而且确实我从未入过役其实早就是预料好的结局只不过有些仓促与迷茫感谢这一路感谢那些人我未曾后悔更不会后悔或许与计算机还是差点缘分再见科技馆再见洛谷再见其他OJ 再见清北学堂再见csdn和博客园再见OI 再见c++ 再见这一切再见 AFO...

2018-06-17 20:49:41 299

原创 NOIP2017游记兼OI半程回忆录

前言一瞬间我感觉我好像挺惨的哪怕是同一个教室数月的同学也基本上都是从初中开始学的OI学的计算机语言最次的也都有些基本的了解而我在去年十月之前基本上连个屁都不知道也就会踢踢FIFA玩玩PES 只学了一年OI就要和这么多大佬同台竞争还是以一个高二的“老学长”的身份初心我的初中生活非常快乐现在回想起那段日子只能说是幸福吧虽然我不知道初中的同学们还会不会时常想起我但我我真的经

2017-11-12 21:10:26 1132

原创【数据结构】【C++STL】动态数组集合映射和优先队列

今天全都比较会了 2333

2017-09-27 21:08:17 385

原创 c++常用变量值的范围

int long longlong unsigned

2017-05-15 16:29:24 825

原创 hello

@TOChttps://kg.qq.com/node/play?s=L8Lh3VL9iAks0L72&shareuid=639e99812124328a32&topsource=a0_pn201001001_z11_u134449516_l0_t1558791527__

2019-05-25 22:15:00 141

原创走啦

最近做了很多题都没来得及补博客不管考的好不好以后都会补的放下包袱加油吧

2017-11-10 07:36:46 305

原创【模板】矩阵快速幂

就是求一个矩阵的幂快考试了时间太紧了没时间仔细搞代码来自Qiu.YF

2017-11-09 21:29:32 176

原创【模板】最长公共子序列

对于O(nlogn)搞一个最长上升子序列考虑一个数列5 2 3 1 4 首先把5加入答案序列中然后加2 发现2<5所以显然2替换5不会使结果更差那么答案序列就是{2} 然后加3 发现3>2 所以直接把3加到答案序列中 {2,3}

2017-11-09 21:27:15 199

原创【数据结构】[NOIP2013]火柴排队

要最小化 a[i]-b[i] 也就是说 a 序列第 k 大的元素必须和序列 b 中第kk 大的元素位置必须一样那么我们我们可以把a b离散化问题将转化为b序列要交换几次可以令其等于a 假设我们现在有离散化后的序列 a = {4, 3, 1, 2} b = {1, 3, 2, 4} 我们令 q[a[i]]=b[i] 相当于以a[i]为关键字对序列b[i]排序

2017-11-01 07:48:10 224

原创【动态规划】[AHOI2001]质数和分解

首先预处理200以内的质数我用了埃氏筛法然后就相当于完全背包求取方案数 fj+=fj−primeif_j+=f_{j-prime_i} 可以这么理解一个数要拆成若干素数和等同于拆成所有该数减去一个素数差的方案数之和但这么做需要初始化为0

2017-11-01 07:31:42 575

原创【动态规划】[luoguP1209 USACO1.3]修理牛棚 Barn Repair

可以用贪心但我还是想用dp去搞用f[i][j]表示前i个牛棚用j块木板的最优解所以 fij=min(fi−1j+ai−ai−1,fi−1j−1+1)f_{ij}=min(f_{i-1j}+a_i-a_{i-1},f_{i-1 j-1}+1) a[i]就是stall_number[i]

2017-11-01 07:21:03 286

原创【动态规划】[luoguP1791]线段覆盖

首先将读入的数据进行排序需要注意的是数据中线段的两个端点可能是逆序的在输入的时候需要交换位置然后就是DP的主要过程了设f[i]表示从排序后的第1条线段到第i条线段中可以选取（不重合）的最多线段数初始边界条件为f数组中的所有元素都是1 则状态转移方程为 fi=max(fi,fj+1)f_i = max(f_i , f_j + 1) 且必须满足第i条与第j条不重合

2017-10-31 07:48:04 417

原创【搜索】[luoguP1126]机器人搬重物

广搜题很生。 qx表示横坐标 qy表示纵坐标 qd表示方向其他的看代码吧

2017-10-31 07:34:12 935

原创【搜索】[luoguP1162]填涂颜色

题目一道很裸的搜索题我们可以一开始把所有的零赋值成2 然后从四条边界往里搜所有与边界相邻的2(能搜到的2)都赋值成0即可最后输出整个矩阵代码如下#include<iostream>#include<cstdio>#include<cctype> using namespace std; #define in = read(); typedef long long ll

2017-10-31 06:32:03 230

原创【动态规划】[NOIP2003]加分二叉树

题目感觉这个题挺难的啊毕竟dp很弱一个比较经典的树形dp 我们用f[i][j]表示区间i~j的最大加分 dp[i][j]表示区间i~j的最大加分时的根节点是什么所以初始化f[i][i] = a[i] dp[i][i] = i 然后就是循环枚举区间然后在每个区间中在枚举根节点如果发现当前区间的左子树的加分×右子树的加分＋根的分数大于当前的f[i][j]就更新最后还要输出一个前

2017-10-29 19:58:23 428

原创【图论】[luoguP1364]医院设置

n很小虽然我们知道它一定是个树但是。有什么用么我不清楚当成一个普通的图先floyd跑最短路然后n^2枚举把每一个点建医院的价值最后取最优的

2017-10-29 16:47:58 286

原创【数据结构】[NOIP2004]FBI树

就是感觉很像线段树那样建树然后统计01就行了

2017-10-29 16:36:34 581

原创【图论】[luoguP1330]封锁阳光大学

挺好的题已经发布了题解首先需要写两个dfs函数 dfs1和dfs2 且这两个函数在过程中会互相调用用链式前向星存图我们先遍历一下每一个edge[i].to 如果它从来没有被dfs1或者dfs2搜到过我们就用dfs1搜它然后对于它所在的图与它相邻的点我们用dfs2去搜而且只要是被dfs2搜到的点我们都ans++

2017-10-29 16:14:50 316

原创【动态规划】[luoguP1156]垃圾陷阱

题目用f[i][j]表示在投放第i个垃圾时垃圾高度为j的情况下最多能活到哪个时刻因为可能这头牛活不到投最后一个垃圾的时候所以最后要求ans dp过程中第一次高度相加能大于等于h的时候这个时间就是最优解可以直接输出时间退出代码如下#include<iostream>#include<cstdio>#include<cctype>#include<algorithm> using

2017-10-20 14:14:09 217

原创【动态规划】[luoguP1280]尼克的任务

倒着推此时有任务（不在工作状态）就必须选有很多个就选一个所以当这个时间如果有很多的任务同时开始我们要选取最优的那个取决这个任务结束后的情况然后差不多就有两种情况第一种是去工作的最大贡献时间第二种就是不去工作那么空闲时间就加1

2017-10-20 11:53:46 306

原创【动态规划】[luoguP1508]Likecloud-吃、吃、吃

题目刚学动态规划的时候都做过入门题 — 数字金字塔倒着推代码如下#include<iostream>#include<cstdio>#include<cctype> using namespace std; #define in = read(); typedef long long ll; typedef unsigned int ui; const ll

2017-10-20 10:02:59 299

原创【动态规划】[luoguP1736]创意吃鱼法

题目发表了题解。。我真的不知道我写的搜索还是DP 反正都差不多吧 - - 怎么搞呢首先我们用三个数组 map[][]存图 f[][]用来存如果矩阵的对角线是从左上到右下的话能取得的最大对角线长度 dp[][]则是同理的右上到左下的矩阵因为每一个有鱼的位置一开始本身就是一个矩阵所以初始化当map[i][j]=1的时候 dp[i][j]和f[i][j]都为1 然后在我们枚举一个k 往前

2017-10-20 09:58:05 329

原创【动态规划】[luoguP1681]最大正方形II

题目发了题解。。我们用map[][]存图然后对于f[i][j]我们用来表示到矩阵的第i行第j列可以构造最大为多少的正方形所以初始化很容易得出每一个格自身一开始都可以构成一个正方形因此在读入的时候把每一个f[i][j]设为1 然后我们要取正方形所以状态转移方程为 fij=min(f(i−1)j,min(fi(j−1),f(i−1)(j−1))+1f_{ij} = min(f_

2017-10-20 08:46:37 255

原创【动态规划】[luoguP1387]最大正方形

我觉得靠自己做动态规划！然而还是错了最后看了题解发现状态转移方程错了我的式子最后找到的是最大长方形。。挺好理解的感觉比II简单

2017-10-20 08:37:01 268

原创【数论】[AHOI2005]约数研究

找规律：以6为例：约数有1的数有6个 1 , 2 , 3 , 4 , 5 , 6 约数有2的数有3个 2，4，6 约数有3的数有2个 3，6 约数有4的数有0个约数有5的数有0个约数有6的数有1个 6 所以：约数有x的数有n除以x个即： fn=n/1+n/2+n/3.....+n/nf_n=n/1+n/2+n/3.....+n/n

2017-10-20 08:30:54 184

原创【数论】[luoguP1029]最大公约数和最小公倍数问题

一句话：最大公约数和最小公倍数的乘积就是原数的乘积所以： ①暴力直接枚举然后算最大公约数和最小公倍数比较也不慢其实 ②正解先把两数相乘然后枚举因数

2017-10-20 08:20:33 196

原创【数论】[HAOI2011]向量

除了枚举什么思路没有看了题解也不太懂只能贴代码了

2017-10-20 08:08:01 190

原创【数论】[luoguP2431]正妹吃月饼

很少做这种二进制的题感觉很陌生以后要多练练感觉位运算好绕把a二进制拆分然后从最低位开始找如果当前位是0的话就判断一下把它变成1之后是不是比b小小的话就变有点贪心思想

2017-10-16 09:42:31 172

原创【动态规划】[luoguP1868]饥饿的奶牛

一开始又没用读懂题 DP题 dp[i]表示牛走到i这个位置能吃到的最大草数最后ans找最大值关键找最右的端点然后从0一直找过去(为什么从0找我也不知道一开始从1找wa了一个大点从0找就ac了)

2017-10-16 09:34:02 443

原创【倍增】[luoguP1613]跑路

题目做完之后出现了一个大问题 - - 虽然这是个倍增但这个代码怎么看怎么像DP这道题是一个倍增加最短路的题好题 n很小所以用floyd就够了当然就算用什么堆优化迪杰斯特拉也没啥用必经倍增就n3n^3 每秒可以跑2^k米所以可以预处理出１秒钟可以到达的边再用一个Floyd求出1到n的最短路径就可以了关于预处理: f[i][u][v]表示u到v能否通过2^i到达边界条件就是在读入的时

2017-10-16 09:22:18 190

原创【数论】[HNOI2006]鬼谷子的钱袋

倍增以及二进制的思想比如我们要算的是10 如果要组成的一个数能由一部分加上另一部分组成就ok了 6~10可以由1~5加5组成所以要选5 接下来就把5除2然后再用小的一部分组成大的一部分一直除2到不能再除因为要从小到大输出但第一个确定的一定是最大的所以可以用栈存储

2017-10-16 07:47:35 295

原创【数论】[HNOI2008]越狱

一开始没思路后来看题解学会了先考虑所有情况每个人都有m种可能的宗教所以总方案数为mnm^n 然后是考虑不能越狱的因为这个情况好像比较好考虑因为只要相邻两个不一样就可以所以假如第一个人可以是m个宗教那第2个人到第n个人一定只能有m-1种所以这种情况的方案数就是m∗(m−1)(n−1)m*(m-1)^{(n-1)}然后两边做差就可以了需要用到快速幂边搞边取膜

2017-10-13 06:50:18 304

原创【动态规划】[luoguP1417]烹调方案

我们要先推一个贪心

2017-10-13 06:37:18 211

原创【数论】[luoguP1895]数字序列

这个题本来自己想了一个方法用一个数组记录序列的数字另一个记录到当前这个数字序列一共有多长结果没想到第一个数组还是需要很大的所以得换一种方法于是学了题解的做法来自题解主人 luoguID 大奕哥

2017-10-13 06:29:29 263

原创【图论】欧拉路

也就是一笔画问题在一个图中如果能一笔画就是欧拉路如果一笔画后的终点就是起点就是欧拉回路补充一个概念——奇点就是度为奇数的点如果一个图中有2个奇点就是欧拉路 0个奇点就是欧拉回路

2017-10-11 09:36:25 349 4

原创【图论】[luoguP2731]骑马修栅栏 Riding the Fences

半年前刚学图论的时候就做过今天竟然忘了翻书才想起来欧拉路。。也就是一笔画问题深搜就可以了

2017-10-11 09:27:26 241

原创洛谷日记8

今天成为了神犇关键是已经连续打卡200天（中间有断的不过续上了）离noip还有32天加油吧 COYG

2017-10-09 06:19:33 198

原创【动态规划】[NOIP2003]数字游戏

经典的环形DP 需要用到前缀和差分思想 f1数组去搞最大值 f2数组去搞最小值 f[i][j]表示前i个数字被分成了j份的最大或者最小价值枚举一个k表示那分出来的j份里面最后一份的开始位置就很容易想出状态转移方程了当然我还是看的题解

2017-10-08 21:02:21 521

原创 c++位运算

水一发这个

2017-10-03 11:14:53 195

原创【动态规划】[luoguP2858 USACO06FEB]奶牛零食Treats for the Cows

题目比较裸比较简单的区间dp 我们每次都是从两头拿掉其中的一个但是具体是哪一个我们不知道但我们知道的是一定是从两头拿我们设f[i][j]为剩下没有拿的最左端是第i个最右端是第j个能出状态转移方程式f[i][j]=max(f[i+1][j]+a[i]∗(n−j+i),f[i][j−1]+a[j]∗(n−j+i))f[i][j] = max(f[i + 1][j] + a[i]*

2017-09-26 14:17:52 280

空空如也

空空如也