3 walk_dog

尚未进行身份认证

我要认证

爽文写手

等级
TA的排名 24w+

NOIP联赛模板总结

是一个模板总结,待更新。基本数据结构字符串KMP模式匹配next[i]表示在A中以i结尾的非前缀子串与A的前缀能够匹配的最大长度。f[i]表示B中以i结尾的子串与A的前缀能够匹配的最长长度。//求next[]数组next[1] = 0;for(int i = 2, j = 0; i <= n; i++){ while(j>0 &&am

2018-10-29 21:37:19

集训总结

1.暴力很好想,正解有时候能想到,但就是要打挂2.模板和数论部分尤其不熟悉,还有动规。接下来要做的:1.每天复习一个专题及以上,熟悉模板。2.把真题暴力全部打一遍。3.调整心态,该打拿的分要拿到...

2018-10-27 23:13:11

NOIP2018模拟赛

T1 字符串(string)【题目描述】定义两个字符串A,B相似当且仅当满足以下两个条件中的至少一个: (1)A和B相同; (2)将A分为长度相同的两个子串A0,A1,将B分为长度相同的两个子串B0,B1,满足A0相似于B0,A1相似于B1或A0相似于B1,A1相似于B0。 给定两个字符串S,T,问它们是否相似。 有多组数据。【输入数据】第一行一个整数t表示数据组数。 每组数据第一行一个字...

2018-10-23 19:45:03

NOIP2018 模拟赛 10.22

T1 cards分析这道题很明显是一道最长不下降子序列的题,用sort排序+朴素dp可以拿60分,用树状数组优化就能拿100了。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include&amp

2018-10-23 14:42:06

NOIP2018模拟赛 10.20

T1 死宅与陷阱分析这道题比较简单,95分做法是用DFS预处理出,每个节点被走道的概率,在sort一波,贪心的思想把炸弹放到除起点外概率最高的的点。100分做法是把DFS改成拓扑排序。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#inc...

2018-10-20 20:05:58

2018NOIP模拟赛 积木大赛

题目分析这道题暴力可以打85,直接枚举左端点和右端点,计算左端点和右端点之间需要填多少积木,如果小于等于m就选择右端点++, 否则就左端点++。正解,我们可以想到积木最后的形状一定有一部分是类似金字塔形状的,我们就二分高度,判断所用积木块是否超过m。#include<iostream>#include<cstdio>#include<cmath>...

2018-10-19 23:39:49

10.18NOIP2018模拟赛

T1 轻功Description题目背景: 尊者神高达进入了基三的世界,作为一个 mmorpg 做任务是必不可少的,然而跑地图却令人十分不爽。好在基三可以使用轻功,但是尊者神高达有些手残,他决定用梅花桩练习轻功。 题目描述: 一共有 n 个木桩,要求从起点(0)开始,经过所有梅花桩,恰好到达终点 n,尊者神高达一共会 k 种门派的轻功,不同门派的轻功经过的梅花桩数不同,花费时间也不同。但是尊者...

2018-10-18 23:29:14

2018.10.17 NOIP模拟赛

T1 刺客信条分析这道题当时做的时候想到了二分的做法,但是没想出来怎么二分。所以华丽的爆0了。那么我们考虑二分距离,把每个人抽象成一个圆(为什么不是方形呢?方形的顶点到中心的距离和方形的边上一点到照片中心的距离各不相同),这个圆的半径r就是我们要二分的。当我们枚举到的半径2*r大于两个点之间的距离,那么着两个圆有相交的部分,...

2018-10-17 21:35:10

2018NOIP 模拟题

T1分析一道水题。当a大于b的时候,我们选择串联一个电容器,于是就转化成了c1 +1 = a/b。当b大于a的时候,我们选择并联一个电容器,于是就有c1/c1+1 = a/b。代码#include<iostream>#include<cstdio>#include<algorithm>usi

2018-10-03 21:51:34

并查集专题题解

#1程序自动分析在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本:假设x1,x2,x3…代表程序中出现的变量,给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x4≠x1,这些约束条件显然是...

2018-09-20 21:12:52

NOIP2013提高组Day 1

T2这道题其实就是就是求逆序对数目,然后我们可以想到第一个数组里第k大的数对应第二个数组里第k大的数 求逆序对个数第一个想到的就是归并排序了#include<iostream>#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const i...

2018-07-24 18:50:42

NOIP2012Day2 T1/T2题解

T1 同余方程 一道拓展欧几里得的模板题,比较简单#include<iostream>#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;ll A, B;ll x, y;ll Tmp;void Exgcd(ll a, ll b)...

2018-07-14 16:45:31

NOIP2011提高组Day 2

T1 这道题当时快速幂的模板写错了,很震惊居然还能拿到60分 然后就是广为人知的数学选修2-3的二项式定理,如果我没记错的话,是这样的: 那这道题最重要的一行代码就是:int ans=power(a,n)*power(b,m)%mod*C(k,m)%mod;#include<iostream>#include<cstdio>#include<a...

2018-07-08 13:09:12

NOIP2011 提高组Day 1题解

总结:第一天的三道题除了第三题代码长度有点超过我的接受范围之外,一二题难度还是比较适中滴,只可惜第二题我打的暴力忘了小小的优化一下,结果没得全分,有点难过了。T1 这道题的思路就是输入过后倒着寻找符合条件的地毯,因为越后放的地毯在越上面#include<iostream>#include<cstdio>#include<algorithm>...

2018-07-08 12:47:10

永远的A+B Problem:写在最前

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int a, b;int main(){ scanf("%d%d", &a, &b); printf("%d", a+b); return 0;}

2018-06-17 14:47:19

NOIP2010 提高组

T1 OJ传送门 洛谷传送门 总结:一道比较简单的模拟题,这道题当时把if_push[Tra[tot_head]]= 0;写成了if_push[tot_head]= 0;差点没调出来….发现真相的我吐血三百升….#include<iostream>#include<cstdio>#include<algorithm&

2018-06-17 14:43:14

NOIP2014 提高组 day2

T1 无线网络发射器选址一道很水的题,唯一需要注意的点就是判断边界,不然就会像我一样只有10分#include<iostream>#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const int MAXN = 200;ll d, n, k;i...

2018-06-09 11:40:30

NOIP2014提高组day1

T1 生活大爆炸版石头剪刀布这道题是一道很水的模拟题,写的时候注意把表中未给出的输赢关系自己补上就是了。#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int MAXN = 205;int N, Na, Nb;int out[3][MAXN...

2018-06-09 11:21:01

NOIP2006提高组 能量项链

题目这道题是一道区间DP的题目具体推导过程有参看洛谷题解对于将两颗珠子合并为一颗珠子,能量=左边一颗珠子*右边一颗珠子*右边的下一颗珠子;三颗珠子合在一起,能量max  = max(左边两颗珠子合在一起的能量+合并后与右边一颗珠子合并的能量, 右边两颗珠子合并后的能量+合并后与左边一颗珠子合并在一起的能量)。于是得到了代码中的状态转移方程#include<iostream>#inclu...

2018-05-27 14:30:47

NOIP2006提高组 金明的预算方案

###题目这道题一个标准的0-1背包问题需要注意的是读入的时候对于主件和附件的存储关系注释都打在代码里了```c++#include <iostream>#include<cstdio>#include<algorithm>using namespace std;const int MAXN = 32005;int n, m, v, p, q;in...

2018-05-27 14:13:13

查看更多

勋章 我的勋章
    暂无奖章