题目 作为NOIP2018的题目,我觉得不需要把题目贴出来了. 大意就是,在一个n∗mn*mn∗m的010101矩阵中,从左上角到右下角的路径中,对于任意的两条,上面的那条小于下面的那条.问满足这样的矩阵的个数. 好吧,有点简陋-- 比赛思路 一眼看下去,诶,nnn这么小,一下子就想到了状压DP. 然后有一点很显然:(i,j)≤(i+1,j−1)(i,j)\leq (i+1,j-1)(i,j)≤(i+1,j−1). 依照这个性质,我打出了一个状压DP. 然后发现,第二个样例崩了. 然后手算了半天

OJ题号:洛谷1005 思路: 动态规划. 不难发现每行能够取得的最大值仅与当前行的数据有关,因此本题可以对每行的数据分别DP,最后求和. 设$f_{i,j}$表示左边取$i$个.右边取$j$个的最大值,则DP方程为$f_{i,j}=max(f_{i-1,j}+a_{i-1}*2^{i+j},f_{i,j-1}+a_{m-j}*2^{i+j})$. 然而数据规模较大,使用 int 只有40分,用 unsigned long long 只有60分.所以需要高精度,不过实现起来并不复杂. 另外有一些

目录 @题目描述@ @题解@ @代码@ @题目描述@ 小 D 特别喜欢玩游戏.这一天,他在玩一款填数游戏. 这个填数游戏的棋盘是一个 n×m 的矩形表格.玩家需要在表格的每个格子中填入一个数字(数字 0 或者数字 1 ),填数时需要满足一些限制. 下面我们来具体描述这些限制. 为了方便描述,我们先给出一些定义: 我们用每个格子的行列坐标来表示一个格子,即(行坐标,列坐标).(注意: 行列坐标均从 0 开始编号) 一条路径是合法的当且仅当: (1)这条路径从矩形表格的左上角的格子(0,0)出发,到

NOIP2018提高组金牌训练营——动态规划专题 https://www.51nod.com/Live/LiveDescription.html#!#liveId=19 多重背包 二进制优化转化成01背包就好了 1503 猪和回文 http://www.51nod.com/Challenge/Problem.html#!#problemId=1503 一只猪走进了一个森林.很凑巧的是,这个森林的形状是长方形的,有n行,m列组成.我们把这个长方形的行从上到下标记为1到n,列从左到右标记为1到m.处

[NOIp2018提高组]货币系统 题目大意: 有\(n(n\le100)\)种不同的货币,每种货币的面额为\([1,25000]\)之间的一个整数.若两种货币系统能够组合出来的数是相同的的,那我们就称这两种货币系统是等价的.给定一个货币系统,求不同面额货币数最少的等价的货币系统. 思路: 将面额从小到大排序,如果一种面额能够被其它面额表示出来,那么这种面额就是多余的.因此只需要跑一个背包即可. 源代码: #include<cstdio> #include<cctype> #inc

前言 关于\(NOIP2018\),详见此博客:NOIP2018学军中学游记(11.09~11.11). \(Day2\)的题目和\(Day1\)比起来,真的是难了很多啊. \(T1\):旅行(点此看题面) 对于树的情况,显然可以把相邻的点全部存下来,排序一遍后依次遍历即可. 对于基环外向树的情况,一种简单的方法是每次断一条边,把它当成树的情况,这样是\(O(n^2)\)的. 但我考场上没想到这种做法,结果对于环上的情况单独讨论,结果把这题弄成了一个极为复杂的模拟题,总共打了两个小时才打完.不过

NOIP2018提高组省一冲奖班模测训练(六) https://www.51nod.com/Contest/ContestDescription.html#!#contestId=80 20分钟AC掉第一题. 然后第二题感觉和最长公共子序列有关,怒干2h,写出了一个错误的算法 只拿了百分之20的数据的分 第三题觉得是数学题,然后推不出来(然而正解是dp……似曾相识的场景) A 工程制图基础 https://www.51nod.com/Contest/Problem.html#!#contestP

NOIP2018提高组省一冲奖班模测训练(四) 这次比赛只AC了第一题,而且花了40多分钟,貌似是A掉第一题里面最晚的 而且还有一个半小时我就放弃了…… 下次即使想不出也要坚持到最后 第二题没思路 第三题想用分块搞一搞,然后发现空间开不下(其实可以用分块搞) 主要是认识了今天AK的曲恒毅大佬,收获很大 砍树 小D有一棵树,这棵树有n个节点,n-1条边,保证连通.树上每个点要么被染成黑色,要么是白色.他定义一棵树的奇怪值为:这棵树中,白色节点与黑色节点数量的差的绝对值.比如这个例子中,树上有5个白

NOIP2018提高组省一冲奖班模测训练(三) 自己按照noip的方式考,只在最后一两分钟交了一次 第一题过了,对拍拍到尾. 第二题不会.考试时往组合计数的方向想,推公式,推了一个多小时,大脑爆炸,还是一直推不出来(然而正解是dp??) 第三题打了暴力 如果是正式比赛的话,就在省一分数线徘徊. 第二题如果能拿一点部分分的话,那省一就比较稳了 正式比赛的话应该部分分会有,这套题的第二题部分分貌似拿不了 讲解讲的非常细,非常清晰.比雅礼集训听的舒服太多太多了. Anan的派对 Anan想举办一个派对

NOIP2018提高组金牌训练营——搜索专题 1416 两点 福克斯在玩一款手机解迷游戏,这个游戏叫做”两点”.基础级别的时候是在一个n×m单元上玩的.像这样: 每一个单元有包含一个有色点.我们将用不同的大写字母来表示不同的颜色. 这个游戏的关键是要找出一个包含同一颜色的环.看上图中4个蓝点,形成了一个环.一般的,我们将一个序列 d1,d2,...,dk 看成一个环,当且仅当它符合下列条件时: 1.    这k个点不一样,即当 i≠j时, di 和 dj不同. 2.    k至少是4. 3.  

NOIP2018提高组金牌训练营——字符串专题 1154 回文串划分 有一个字符串S,求S最少可以被划分为多少个回文串. 例如:abbaabaa,有多种划分方式.   a|bb|aabaa - 3 个回文串 a|bb|a|aba|a - 5 个回文串 a|b|b|a|a|b|a|a - 8 个回文串   其中第1种划分方式的划分数量最少. Input 输入字符串S(S的长度<= 5000). Output 输出最少的划分数量. Input示例 abbaabaa Output示例 3 复习了一波划

比赛链接 NOIP2018提高组省一冲奖班模测训练(二) 今天发挥正常,昨天不在状态…… 花了很久A了第一题 第二题打了30分暴力 第三题投机取巧输出test1答案(连暴力都不知道怎么打,太弱了) 2585分和4个人并列rank3 还行吧 LXL的雕像 地主lxl拥有一块 n×m 的土地,有一天他突发奇想,想要在自己的土地上建造若干雕像来纪念自己的伟业. 已知每个雕像底座的尺寸均为  l×l  .为了美观,lxl想把雕像排列成一个矩形网格,每个雕像与其相邻的雕像(或者与土地边缘)的距离  x 

题目链接 https://www.luogu.org/problem/P5019 解题思路 一道典型的贪心题. 假设从左往右填坑,如果第i个深与第i+1个,那么第i+1个就不需要额外填: 如果第i+1个大于第i个,就需要填i+1-i的深度,所以就相当于把>0的差分数组加起来就AC了. AC代码 #include<iostream> #include<cstdio> using namespace std; ]; long long ans; int main(){ int n

2017年全国大学生信息安全竞赛 Reverse 填数游戏 起因是吾爱破解大手发的解题思路,觉得题挺有意思的,就找来学习学习 这是i春秋的下载链接 http://static2.ichunqiu.com/icq/resources/fileupload/CTF/echunqiu/qgdxs/numgame_8808BCE6D17A3EF92461A50079264767.zip 以防万一呢,我在网盘也放了一份名字叫numgame_8808BCE6D17A3EF92461A50079264767.

[NOIp2018提高组]旅行: 题目大意: 一个\(n(n\le5000)\)个点,\(m(m\le n)\)条边的连通图.可以从任意一个点出发,前往任意一个相邻的未访问的结点,或沿着第一次来这个点的边返回.需要遍历每一个点.没经过一个新的结点,就将这个结点写下来.最终可以得到一个序列.求字典序最小的序列. 思路: 对于树的情况,显然从\(1\)出发,每次从字典序最小的相邻结点DFS即可. 对于有环的情况,由于环只有一个,我们可以将环找出来,枚举删掉环上的每一条边,然后按树的情况求解即可. 时

[NOIp2018提高组]赛道修建 题目大意: 给你一棵\(n(n\le5\times10^4)\)个结点的树,从中找出\(m\)个没有公共边的路径,使得第\(m\)长的路径最长.问第\(m\)长的路径最长可以是多少. 思路: 二分答案+树形DP.\(f[x]\)表示以\(x\)为根的子树中最多能找出几个长度\(\ge k\)的路径.\(g[x]\)表示去掉已经满足的路径,从\(x\)子树内往上连的最长的路径有多长. 转移时将所有子结点的贡献\(g[y]+w\)排序.若贡献已经\(\ge k\)

[NOIp2013提高组]积木大赛/[NOIp2018提高组]铺设道路 题目大意: 对于长度为\(n(n\le10^5)\)的非负数列\(A\),每次可以选取一个区间\(-1\).问将数列清零至少需要几次操作. 思路: 差分后,将大于\(0\)的差分累加入答案即可. 源代码: #include<cstdio> #include<cctype> #include<algorithm> inline int getint() { register char ch; whil

Day1 T1 积木大赛 NOIp2013D2T1.....看到的时候我还以为我记错了,以为原题是一次可以随便加,这题只能加一,出考场后查了下发现一模一样. #include <iostream> #include <cstdio> using namespace std; const int N=100010; int n,d[N],ans; int main() { int i; scanf("%d",&n); for (i=1;i<=n;++

D1T1:铺设道路 回忆NOIP2013D2T1 积木大赛,发现这两题唯一的区别就是一个是造山一个是填坑,而把填坑的操作反序就是造山,所以可以直接使用那道题的方法. 具体方法是,从左到右每次考虑新的一列,若这一列的坑比左边一列浅,那么可以在填左边一列的时候顺便填好这个坑(只要把所有右端点为i-1的操作右端点全部改为i即可),不需要任何操作.若这一列的坑比左边深,那么就必须先将这一列的坑填到与左边平齐,再让左边的操作顺带把这个坑填平. 于是有:若a[i]<=a[i-1],ans不变,否则ans+=

NOIP2018提高组省一冲奖班模测训练(五) http://www.51nod.com/Contest/ContestDescription.html#!#contestId=79 今天有点浪…… 第一题想了一个多小时想到了正解,然后敲到一半就去看lol总决赛了(恭喜IG!!!!!!) 然后就没有然后了…… A 循环 小D站在一个长度为n的环,环上的位置从0到n-1编号.位置0与位置n-1相邻.对于一个位置i, 小D只能跳到距离位置i不超过R[i]的位置上. 可以顺时针也可以逆时针跳.比如当n

传送门 Description 耳熟能详,就不多说了 Solution 对于一个不会推式子的蒟蒻,如何在考场优雅地通过此题 手玩样例,发现对于 \(n=1\) , \(ans=2^m\) .对于 \(n=2\) , \(ans=4\times 3^{m-1}\) .或者干脆打出 \(n,m\le 3\) 的表 肉眼观察法,发现似乎有 \(f(n,m+1)=3f(n,m)\),但这并不是正确的,但如果你仅仅是这么认为了,你仍然能够获得很多分数 想结论,都是特别特别显然的那种: \(f(n,m)=f