TirpitzOVO-CSDN博客

原创 [HDU P2089]不要62

原题链接数位DP入门真的是好久不写了入门题搞了一个小时依旧延续DP的优良传统想不到的状态推不出的转移但是好像这道题是数位DP的常规想法手好冷啊不想打字了…… 参考链接#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<cstdlib>u

2017-12-13 16:59:56 219

原创 [P1220]关路灯

原题链接这是一道DP题但是用爆搜也能过跑的还挺快的就是直接暴力搜索跑到边界去关灯#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<ctime>#include<cstdlib>#include<climits>#include<queu

2017-11-09 14:56:51 358

原创 [P3811][模板]乘法逆元

原题链接我只是想打个小费马的板子结果这个题用小费马过不了[气哭] 又跑去看了半天递推式总之就是 inv[i]=(p−pi)×inv[p%i]%pinv[i] = (p - \frac{p}{i}) × inv[p \% i] \% p #include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<

2017-11-08 15:04:06 456

原创 [P3939]数颜色

原题链接把每个颜色的每个位置记下来 lower_bound是神器#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<ctime>#include<cstdlib>#include<climits>#include<queue>#include<v

2017-11-07 16:57:55 1089

原创 2017/11/7

正反两张图三棵树求交集#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<ctime>#include<cstdlib>#include<climits>#include<queue>#include<vector>#define LL

2017-11-07 14:06:30 241

原创 [P1809]过河问题_NOI导刊2011提高（01）

原题链接参考链接贪心一共有两种不同方案分别对应某些情况因此两种取min#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<ctime>#include<cstdlib>#include<climits>#include<queue>#inc

2017-11-05 14:04:54 621

原创 2017/10

题目编号是我瞎搞的T1 因为数据范围很小我还以为是折半搜索没想到是个n3的DP不难看出跳楼的高度是单调的情况下才可能是最优这样就先把高度排序转移方程 dp[i][j] = min ( dp[i-1][k] + b[j].h - b[k].h ) + b[j].c ( k∈1~j-1 ) i表示跳了几次楼 j表示现在在哪座楼上 dp[i][j]表示跳i次楼到达j楼需要的最小

2017-10-30 16:18:29 281

原创但有用

wa这个题本质上十分暴力就是枚举再贪心但是想不到的话就 GG首先我们可以看出本质上只有＋0,1,2 三种情况因为加其他的数都相当于3x+0,1,2 与0,1,2相比操作数更多但结果相同3n搜索每行的情况搜完行以后对每一列进行贪心看看哪种情况能得到最多的稳数#include<iostream>#include<cstdio>#include<cstring>

2017-10-28 15:18:45 259

原创 [P3933][洛谷10月月赛R2·浴谷八连测R3 -Chtholly-]Chtholly Nota Seniorious

原题链接题目看起来好麻烦一开始都没读懂题意实际上是个二分+贪心二分一个最大的差值 check的时候按照贪心然后因为贪心还要把图旋转四次才能得到真正的结果#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<cstdlib>#inc

2017-10-28 08:39:11 581

原创 [P1280]尼克的任务

原题链接nico的任务 niconiconi这个题的DP方程对我来说还是有点难想的因为如果当前有多个任务的话需要根据任务的结束状态判断选择哪个但是正推的话还不知道结束后是什么状态所以 DP[i]代表从i~n的最大空闲时间#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#includ

2017-10-26 16:26:25 541

原创 [P1352]没有上司的舞会

原题链接树形DP入门 DP方程搞错了居然还过了90 (*/ω＼*)利用DFS递归求解每个点分为选和不选两种情况假设选为1不选为0 dp[x][0]+=max(dp[num[i]][1],dp[num[i]][0]); //这里一开始写成了dp[num[i]][1] 但它的儿子的两种状态实际上都是可选的 dp[x][1]+=dp[num[i]][

2017-10-26 10:49:11 656

原创天上掉馅饼

深切悼念天国的Bonus 看着额外加成四个大字欲哭无泪这个题做的大费周章还跑去问了数学老师什么是期望总之就是最大美味值×概率因为要求不吃的话以后也不能吃所以为了避免出现无效情况需要倒着枚举利用状态压缩实现是否符合前置条件的判断#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#

2017-10-25 16:33:07 276

原创国际跳棋

哇社会真的险恶这个题题面给了一大堆东西还夹杂着没用的设定加冕这种玩意只有在进行完一次操作之后才能进行然而题目要求只能进行一次操作所以完全就是逗你玩的题目大意就是求对单个棋子进行一次操作且吃子最多的方案数对王和普通棋子单独进行处理在无法吃子的时候就求能行动的棋子的行动方案数漏写了个地方居然还过了90#include<iostream>#include<cstd

2017-10-25 15:27:14 1646 1

原创 [P2680][NOIP2015]运输计划

原题链接二分+树上差分T了一个点就5分不想了二分一个最大长度超过这个长度的路线找它们的交Tarjan找LCA u，v+1 LCA-2#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<climits>#include<cstdlib>#include<ctime>#in

2017-10-24 07:55:20 248

原创括号序列

有关括号匹配好像大部分都是DP？讲真居然要把前缀和单独拿出来作为一维这个我是没想到但是知道了之后感觉异常合理#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<climits>#include<cstdlib>#include<ctime>#include<cstr

2017-10-23 15:03:17 413

原创秘密信息

就这种感觉？ 100分就是将重复的编号出现顺序在前后是一样的#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<climits>#include<cstdlib>#include<ctime>#include<cstring>#include<queue>#define LL

2017-10-23 14:15:30 244

原创大奖赛

30暴力搜 50 01背包 100 折半搜索以上三个做法都很裸顺便Lancelot+Morgan怕不是某呆毛王要提着咖喱棒来打架#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<climits>#include<cstdlib>#include<ctime>#include<cs

2017-10-23 14:07:23 204

原创 [P1311][NOIP2011]选择客栈

原题链接不知道标准正解是啥用了个有点奇葩的线段树记录[l,r]这段区间内第一个价格<=p的位置有一个写起来异常简洁的思路而且是O(n)复杂度在这里贴一下链接戳我(｡･ω･｡)#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<c

2017-10-19 17:33:41 793

原创 [P1080][NOIP2012]国王游戏

原题链接并不是真正的国王游戏顺便这个国王真小气是个贪心不是很好想就是左右手相乘升序排列但是只有我这么觉得然后还要加上高精#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<climits>#include<queue>#incl

2017-10-19 15:18:54 672

原创 [P2312][NOIP2014]解方程

原题链接水了个70 就是正常模拟+取模多取几个模数#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<climits>#include<queue>#include<vector>#include<ctime>#define LL lon

2017-10-19 08:01:19 195

原创 [P1970][NOIP2013]花匠

原题链接听说正解是DP#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<climits>#include<queue>#include<vector>#include<ctime>using namespace std;int n,i,cnt

2017-10-18 13:44:58 1429

原创 [P1969][NOIP2013]积木大赛

原题链接同机房的用了各种奇怪的算法听到我一脸懵逼这题就是先把公用的最小的建起来然后上升的肯定是要新建的答案加上与当前高度的差后面下降的不用管在之前建高的时候肯定放上了#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cli

2017-10-18 11:33:17 506

原创 [P1351][NOIP2014]联合权值

原题链接一开始并没有想到正解打了个70分的暴力然后正解是枚举中间点与它相邻的两个点一定符合条件把这些点的权值加起来平方再减去他们平方的和就是sum 再找两个最大权值的点就是maxn#include<iostream>#include<cstdio>#include<ctime>#include<algorithm>#include<climits>#inc

2017-10-17 17:20:55 182

原创 [P1967][NOIP2013]货车运输

原题链接因为数据比较水根本没用倍增总之这个题就这么水过去了求最大生成树再求个LCA 参考链接戳这里( • ̀ω•́ )✧顺便安利一个方法 tarjan求LCA 超好写的但是对这个题有点麻烦参考地址戳这里(◍´꒳`◍)#include<iostream>#include<cstdio>#include<ctime>#include<algorithm>#inclu

2017-10-17 15:25:43 190

原创 dan[非正解搜索+卡时可AC]

应该不是正解毕竟题目里给的m并没有用上但是搜索+卡时可以过卡时是好文明搜索葱枚举它在哪个栅栏因为栅栏一定能变成一个矩形所以只记录每个栅栏的边界中间加一点最优性剪枝最后跟我一起念卡时是好文明#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#

2017-10-08 11:15:14 232

原创逆欧拉函数[arc]

丧心病狂利用欧拉函数的公式实现逆推然后其中附带了一点素数判断[Miller-Rabin] 总之很麻烦φ(n)=n×(p1−1)×(p2−1)…(px−1)p1×p2×…pxφ(n)=\frac{n×(p_1-1)×(p_2-1)…(p_x-1)}{p_1×p_2×…p_x}#include<iostream>#include<cstring>#include<algorithm>

2017-10-08 10:08:25 553

原创欧拉函数

求1018范围内的数的欧拉函数我选择死亡emmmm 倒是有思路分解质因数利用欧拉函数的性质求值但是数太大了我不会qwq 于是这个时候就要用完全不会现在也没明白的 Miller-Rabin和Pollard-rho参考链接#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#in

2017-10-07 21:35:04 192

原创仙人掌[cactus]

目测图论结果是区间覆盖 (╯‵□′)╯︵┻━┻ 尊重一下你的名字好吗因为美妙的仙人掌的性质我们可以知道对于任意一个点i i和i+1一定直接相连这样就产生了一条链根据美妙的仙人掌的性质接下来再选两条边u1v1和u2v2的时候 [u1,v1]和[u2,v2]不能有重叠部分 tip:但是可以共用一个点这样就变成了选不重叠的区间使区间数量最大#include<iostream>

2017-10-07 18:07:01 265

原创 LYK快跑[run]

虽然时间是5s 但这并没有什么用这并不能证明你不是咸鱼puni降时间复杂度主要是在预处理出每个点的最小威胁值上把每一个怪物都入队然后进行BFS然后进行二分+BFS#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#inclu

2017-10-07 16:49:13 225

原创 select

一开始想了一个结果只有40看了题解就是枚举选i行，k-i列找最大值#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#include<string>#include<cstdl

2017-10-07 14:33:49 142

原创 program

样例坑爹系列已根据题面所给程序运行结果手动更正首先排序找到相同的对数 tip:允许重复然后倒过来统计某个数的个数和比这个数小的数的对数相乘#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<c

2017-10-07 10:05:27 118

原创 NP[阶乘取余]

这题还是挺亲切的暴力+特判轻松90然后剩下了10分根据题目的特殊性——大数据时模数是确定的进行分块打表#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#include<string

2017-10-07 09:15:00 583

原创 [T13365]他

原题链接折叠时做好对应#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#include<string>#include<cstdlib>#include<ctime>#define MOD

2017-10-06 19:46:55 179

原创 jian

【问题描述】有N个数，随机选择一段区间，如果这段区间的所有数的平均值在[m,r]中则你比较厉害求你比较厉害的概率【输入格式】第一行有三个数N,m,r，含义如上描述接下来一行有N个数代表每一个数的值【输出格式】输出一行一个分数如果答案为整数则直接输出该整数即可【样例输入 1】 4 2 3 3 1 2 4 【样例输出 1】 7/10 【样例输入 2】 4

2017-10-06 19:09:13 176

原创 [Tyvj P4876]近似排列计数[50]

原题链接用了个搜索两个剪枝明显在数字固定的地方就不要枚举了然后如果这个数只可能在这个位置用上那就只能用这个数了#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#include<stri

2017-10-05 17:10:34 170

原创 [Tyvj P4877]组合数

原题链接一对5、2产生一个0利用下式进行分解Cmn=n!m!(n−m)!C_n^m=\frac{n!}{m!(n-m)!}#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#include<string

2017-10-05 14:44:15 199

原创 [Tyvj P4875]排列

原题链接一开始想的是n2做法预处理+n2枚举然后看了题解利用单调栈固定左端点右端点跳到最大最小值发生改变的地方时间复杂度nlogn#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#

2017-10-05 11:12:31 159

原创 [Tyvj P4874]回形遍历

原题链接从 ( 0 , 0 ) 开始走每次都走一整行走过 ( x , y ) 开始记录步数走过了就手动一步步走回去#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#include<stri

2017-10-05 09:43:30 209

原创 [Tyvj P4864]天天去哪吃

原题链接简单粗暴模拟大法好还以为会超时但是毕竟只是个第一题#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#include<string>#include<cstdlib>#inclu

2017-09-30 09:25:01 175

原创柜[非正解]

参考网上的题解非正解正反搜一遍交汇的地方就能放镜子#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<queue>#include<vector>#include<climits>#include<string>#include<cstdlib>#include<cti

2017-09-29 16:39:07 121

空空如也

空空如也