- 博客(28)
- 收藏
- 关注
RSS订阅
原创 永远的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
286
3
原创 NOIP联赛模板总结
是一个模板总结，待更新。基本数据结构字符串KMP模式匹配next[i]表示在A中以i结尾的非前缀子串与A的前缀能够匹配的最大长度。f[i]表示B中以i结尾的子串与A的前缀能够匹配的最长长度。//求next[]数组next[1] = 0;for(int i = 2, j = 0; i &amp;amp;amp;lt;= n; i++){ while(j&amp;amp;amp;gt;0 &amp;amp;amp;amp;&am
2018-10-29 21:37:19
170
原创 集训总结
1.暴力很好想，正解有时候能想到，但就是要打挂2.模板和数论部分尤其不熟悉，还有动规。接下来要做的：1.每天复习一个专题及以上，熟悉模板。2.把真题暴力全部打一遍。3.调整心态，该打拿的分要拿到...
2018-10-27 23:13:11
459
原创 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
585
原创 NOIP2018 模拟赛 10.22
T1 cards分析这道题很明显是一道最长不下降子序列的题，用sort排序+朴素dp可以拿60分，用树状数组优化就能拿100了。#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;algorithm&gt;#include&
2018-10-23 14:42:06
316
原创 NOIP2018模拟赛 10.20
T1 死宅与陷阱分析这道题比较简单，95分做法是用DFS预处理出，每个节点被走道的概率，在sort一波，贪心的思想把炸弹放到除起点外概率最高的的点。100分做法是把DFS改成拓扑排序。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#inc...
2018-10-20 20:05:58
229
原创 2018NOIP模拟赛 积木大赛
题目分析这道题暴力可以打85，直接枚举左端点和右端点，计算左端点和右端点之间需要填多少积木，如果小于等于m就选择右端点++， 否则就左端点++。正解，我们可以想到积木最后的形状一定有一部分是类似金字塔形状的，我们就二分高度，判断所用积木块是否超过m。#include<iostream>#include<cstdio>#include<cmath>...
2018-10-19 23:39:49
1685
原创 10.18NOIP2018模拟赛
T1 轻功Description题目背景： 尊者神高达进入了基三的世界，作为一个 mmorpg 做任务是必不可少的，然而跑地图却令人十分不爽。好在基三可以使用轻功，但是尊者神高达有些手残，他决定用梅花桩练习轻功。 题目描述： 一共有 n 个木桩，要求从起点（0）开始，经过所有梅花桩，恰好到达终点 n,尊者神高达一共会 k 种门派的轻功，不同门派的轻功经过的梅花桩数不同，花费时间也不同。但是尊者...
2018-10-18 23:29:14
191
原创 2018.10.17 NOIP模拟赛
T1 刺客信条分析这道题当时做的时候想到了二分的做法，但是没想出来怎么二分。所以华丽的爆0了。那么我们考虑二分距离，把每个人抽象成一个圆（为什么不是方形呢？方形的顶点到中心的距离和方形的边上一点到照片中心的距离各不相同），这个圆的半径r就是我们要二分的。当我们枚举到的半径2*r大于两个点之间的距离，那么着两个圆有相交的部分，...
2018-10-17 21:35:10
160
原创 2018NOIP 模拟题
T1分析一道水题。当a大于b的时候，我们选择串联一个电容器，于是就转化成了c1 +1 = a/b。当b大于a的时候，我们选择并联一个电容器，于是就有c1/c1+1 = a/b。代码#include&amp;lt;iostream&amp;gt;#include&amp;lt;cstdio&amp;gt;#include&amp;lt;algorithm&amp;gt;usi
2018-10-03 21:51:34
1524
原创 并查集专题题解
#1程序自动分析在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x1,x2,x3…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2,x2=x3,x3=x4,x4≠x1，这些约束条件显然是...
2018-09-20 21:12:52
380
原创 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
144
原创 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
227
原创 NOIP2011提高组Day 2
T1 这道题当时快速幂的模板写错了，很震惊居然还能拿到60分 然后就是广为人知的数学选修2-3的二项式定理，如果我没记错的话，是这样的： 那这道题最重要的一行代码就是：int ans=power(a,n)*power(b,m)%mod*C(k,m)%mod;#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;a...
2018-07-08 13:09:12
136
原创 NOIP2011 提高组Day 1题解
总结：第一天的三道题除了第三题代码长度有点超过我的接受范围之外，一二题难度还是比较适中滴，只可惜第二题我打的暴力忘了小小的优化一下，结果没得全分，有点难过了。T1 这道题的思路就是输入过后倒着寻找符合条件的地毯，因为越后放的地毯在越上面#include<iostream>#include<cstdio>#include<algorithm>...
2018-07-08 12:47:10
237
原创 NOIP2010 提高组
T1 OJ传送门 洛谷传送门 总结：一道比较简单的模拟题，这道题当时把if_push[Tra[tot_head]]= 0;写成了if_push[tot_head]= 0;差点没调出来….发现真相的我吐血三百升….#include&amp;lt;iostream&amp;gt;#include&amp;lt;cstdio&amp;gt;#include&amp;lt;algorithm&
2018-06-17 14:43:14
490
原创 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
250
原创 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
188
原创 NOIP2006提高组 能量项链
题目这道题是一道区间DP的题目具体推导过程有参看洛谷题解对于将两颗珠子合并为一颗珠子，能量=左边一颗珠子*右边一颗珠子*右边的下一颗珠子；三颗珠子合在一起，能量max = max（左边两颗珠子合在一起的能量+合并后与右边一颗珠子合并的能量， 右边两颗珠子合并后的能量+合并后与左边一颗珠子合并在一起的能量）。于是得到了代码中的状态转移方程#include<iostream>#inclu...
2018-05-27 14:30:47
226
原创 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
465
原创 关于数的划分
数的划分（一）题目中的有用信息：1.方案数可以重复 2.最小值为1 3.m不会大于n这道题用深搜的方法会TLE，我试过...呃...于是就用记搜？最重要的递归部分long long Solve(long long x,long long y){ if(y == 1 || ...
2018-02-12 20:31:46
441
原创 关于卡特兰数及典型例题
关于卡特兰数：f[0] = 1, f[1] = 1for（int i = 0; i < n; i++){ for(int j = 1; j <= i - 1; j++){ f[i] += f[j] * f[i - j - 1]; }}关于乘法原理和加法原理：1.便捷记忆：乘法原理：步步相关 加...
2018-02-12 20:02:20
1501
原创 斐波拉契数列
数据大了之后会爆时间..于是就选择用记搜附代码↓↓↓：#include<bits/stdc++.h>#define ll long longusing namespace std;int n, x;ll Num[100], Ans[100];ll Sum = 0;ll Temp[10000];ll Fib(int n){if(n == 0 || n == 1){return 1;}el...
2018-02-12 19:13:50
176
原创 2.12日递推专题第一题
1.公式推导：2 ^ n - 12.注意：①.开到 long long型 ②.不建议用pow附代码↓↓↓：#include<bits/stdc++.h>using namespace std;int main( ){int n;long long Sum = 1;scanf("%d", &n);for(int i = 1; i <= n; i++)...
2018-02-12 18:43:34
113
原创 特殊的约瑟夫问题
附代码↓↓↓注释都在程序里：#include <cstdio>#include <cmath>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <string>#include <sta
2018-02-11 22:40:54
1040
原创 2.11考试第二题
题目：一个基因序列可以抽象为一个包含有ci个数的正整数序列，要求将其按一定顺序排列，于是就有了如下要求：1.按长度为第一关键字，从小到大排序。2.若长度一样，则按字典序排列。3.如果存在两个元素相同，且i < j，则排列后i应在j前输出。一道vector的题，CSDN恶补了一下vector的相关知识...这道题没什么好说的...附代码：#include<iostream>#inc...
2018-02-11 22:34:15
136
原创 2.11日考试第一题
题目众所周知，2018-1-31是个神奇的日子。这天晚上，不仅有百年一遇的蓝月，还有千年一遇的奇观——wyf梦游。具体地说，wyf梦见自己在一张奇怪的图中。这张图有n个结点，m条带权有向边。此后死，wyf正在结点1,而教室竟然在遥远的结点n！wyf自然是很害怕迟到的，于是他想知道从1到n的最短路有多长。他还想知道：（怎么那么多想知道的）若能将任意一条边的边权变为0，从1到n的最短路有多长。Inpu...
2018-02-11 20:54:08
171
原创 01背包
设f[i][j]表示考虑完前i个物体，背包的容量为j（物体的总体积小于等于j）时的最大价值答案就是f[n][m]边界f[0][...] = 0转移：决策一：选f[i][j]->f[i+1][j+weight[i+1]] 不选f[i][j]->f[i+1][j];代码：#include#include#include#include#include
2018-01-29 11:28:13
119
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人