- 博客(12)
- 收藏
- 关注
RSS订阅原创 noip提高组2018反思——（滚粗记）
noip提高组2018反思单选题第七题这一题我在做的时候非常的傻，只想的可以找出两条线段和为线段总长，然后就没有任何怀疑地将1/2选了上去其实我们选多一些点将所有情况都枚举出来就会发现其实答案是1/3第八题这一题后面两个我是知道的肯定是的然后我记得二叉树也是Catalan数。然后。。然后。。我就推了一下！！！n个节点的二叉树。非常的正确再加上B选项听都没有听说过果断选...
2018-10-15 20:36:42
673
1
原创 国庆七连测——4
今天终于有时间写博客了蒟蒻前几天忙于订正题目。。。今天题目比较简单所以才有时间来写博客。（昨天最后一题还没有搞懂。。km当初没学只学了匈牙利）第一题给你n根相同的木棍平均分给m个人问木棍一共要分次。这道题很简单，直接用gcd判断当分到第几个人时要不要切割。n表示木棍根数ns表示切到第几根木棍m表示总人数ms表示已经分的人数所以如果ns/n==ms/m那么就是给这个人分的时候...
2018-10-04 15:06:58
148
原创 0708hgoi
由于前两题都很简单，就简单写下思路。 1.一个人往下走与一个人往上走碰到之后改变方向，就相当于两人继续往前走。于是我们就可以将箱子平均分配给每个人。多余的箱子分给完成任务最早的人。这样就可以轻松求得答案了。 2.o（nlogn）的算法就是将圆拉成一条直线，并将它倍长。从1到n点往后n个点中进行二分，由此可以得出答案。 o（n）的算法就是从起点开始，有两个标记，一个左标记，一个右标记。在总值小...
2018-07-08 19:04:10
175
原创 0618hgoi
第一题 用最暴力的方法 (ax+by)^k中x^ny^m的次数 首先用排列组合求出有几种乘的方法可以算出x^ny^m 再算出每一个组合x^ny^m的次数 由于过大要用高精度第二题 用二分的方法二分w 由于w越大y越大所以可以利用w的单调性二分 判断时就可以利用符合条件的v和num(符合条件的个数)的前缀和来快速求值 所以寻找复杂度nlogn的,判断复杂度是o(n)的第三题...
2018-06-18 22:49:05
148
原创 【图论——2-sat】——wedding婚宴
这道题我们可以很轻易地发现是用2-sat来解答的，2-sat也很容易想出来。于是本蒟蒻就很快地写了出来。然而接下来的wa什么的就一直伴随了我一整个上午，整个人都不好了。 这道题最恶心的是妻子的位置要固定。#include<cstdio>#include<cstring>#include<vector>#include<algorithm&
2018-05-10 14:20:48
211
原创 【图论——点双连通分量+二分染色判断奇圈】——Knights of the Round Table 圆桌骑士
这里我们用的思想是求出点连通分量然后通过二分染色的方法判断奇圈 因为我们要让骑士坐成一圈，所以我们可以用连通分量（此处暂时还不能确定是边连通分量还是点连通分量）来表示 我们再思考，一骑士个骑士可以参加多个会议，所以我们要用的是可以有点相同的点连通分量。 想好这些，在考虑题目中所说的只能有奇数个骑士参加会议，所以我们就保证这个连通分量为奇圈 而奇圈又如何判断呢 我们可以用二分染色法 从连...
2018-04-26 14:30:03
461
原创 【图论——割点与桥】——洛谷P3388【模板】割点（割顶）
此处用u表示这个节点，用v表示u的子节点，fa表示u的父亲节点pre[u]表示dfs中u这个点被第几个扫到用low[u]表示u能到的v中pre[v]的最小值割点：如果low[v]<=pre[u]就证明u这个点的子节点没有办法到达u的父亲节点也就证明去掉这个点就会产生一个连通分量（多一个不相连的图）利用这个性质就可以求割点桥：方法与割点相同判断时不同low[v]<pr...
2018-04-24 11:27:02
789
5
原创 【巧妙思想——栈】——City skyline 地平线上的城市
这到题是一个单调栈的题，就是让轮廓的高度依次进栈，如果刚刚进入的高度小于栈顶的高度，就让栈顶出栈，再比较他和栈顶的高度，如果相等则ans++；最后用n-ans得出答案，因为楼全是矩形，所以奶牛看到的n个高度是矩形重叠形成的，所以用看到的总高度数减去重叠的数，就得出有几栋楼了。原理：如果有相同高度的出现就证明可以用同一块方块覆盖于是ans++#include<cstdio>...
2018-04-23 14:45:53
3422
原创 【动态规划——单调队列维护】——烽火传递
用q[i]表示到i前面符合条件的最小代价为多少（要取到i)单调队列维护区间中q[i]的最小值l,r表示单调队列的队首与队尾从1到n循环，若q[qj[r]]>q[i]（队尾比当前大）弹出队尾将当前放入若qj[l]<i-m（长度大于要求）l++最后更新一下q[i]=q[l]+a[i]（符合要求区间中最小值加当前值为当前最小值）答案在n—n-m+1中#inc...
2018-04-23 10:09:23
429
原创 【动态规划——基础】01背包与无限背包
无限背包讲解：一个物品可以放很多次所以先前更新的状态要求影响后面更新的状态01背包要求是从最大值向后扫以保证每个物品只用一次所以每个物品可以用多次，从前往后扫即可例子（f[i]表示与上程序中一样）：假设物品质量4容量1001：从10往前扫，扫到f[0]=1,然后更新f[0+4]=1无限：从0往后扫，首先扫到f[0]=1,更新f[0+4]=1再往后扫，再次扫到...
2018-04-22 15:43:40
1299
原创 【动态规划——盗版无限背包（有个数限制）】coin——金币
题目讲解：用一个数组f[i]表示i的价格是否能达到f[0]=1，表示价格为0可以到达，赋初值后用s[i][j]表示到达i的价格用的第j个钱几个用无限背包的方法加一句判断s[i][j]<j所能用的最大个数（无限背包不会的话看程序后的讲解）#include<cstdio>#include<cstring>int n,m;int a[...
2018-04-22 15:24:45
486
1
原创 【动态规划——状态压缩】dream——蒙德里安的梦
用二进制状态压缩，用f[i][s]表示做到第i行状态为s。s的二进制表示第几位（第几个位置）是否被放过——状态s=10（1010）第一个位置被放过，第二个位置没被放过，第三个位置被放过，第四个位置没被放过。然后分层枚举本层状态与上层状态，若两种状态相符合，f[i][s]+=f[i-1][ss]（ss为上层状态，s为本层状态）。判断状态符合方法：1、s中j位为0，ss中j位为1（在i...
2018-04-19 20:42:09
252
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人