- 博客(320)
- 收藏
- 关注
RSS订阅
原创 Noip 2018 游记
Day0Day 0Day0突然意识到明天就是NoipNoipNoip了。。。莫名恐慌，感觉前一周的状态其实不是很好，药丸~~。中午的火车，下午到达临汾，车上写了一道ztz11ztz11ztz11推荐给我的题，结果好像不太会。。下午就跑到lfyzlfyzlfyz，领了饭卡+胸牌，在签名墙上签了个名，就去愉快的试机了，键盘好软，差评。敲了个高精A+BA+BA+B，拍了一会就被叫去吃饭了。饭还是可以的...
2018-11-26 16:25:30
286
原创 那些年犯下的逗比错误
博主可能太蒟蒻了，老是烦一些逗比问题，特此记录。 （学习游神）1、数组开不够，通常是图论的边。两次考试的爆零加上两个小时无意义的调试。。还是记不住。。BZOJ 3143 游走 多亏radish巨。2、赋值long long极大值的时候没有1ll 。直接1<<60 。。BZOJ 2165 大楼。被郝神一眼看出鄙视了半天。。3、位运算没加括号，永远知道位运算
2018-07-02 20:28:07
340
2
原创 LUOGU P3047 [USACO12FEB]附近的牛Nearby Cows
传送门解题思路树形dp，看到数据范围应该能想到是O(nk)级别的算法，进而就可以设出dp状态，dp[x][j]表示以x为根的子树，距离它为i的点的总和，第一遍dp首先自底向上，dp出每个节点的子树中到他距离为j的，转移方程dp[x][j]=dp[u][j-1] ，第二遍dp自顶向下，dp出每个节点父亲那头的距离为j的，转移方程dp[u][j]+=dp[x][j-1]-dp[u][j-2]代码...
2018-09-18 17:19:40
194
原创 LUOGU P2986 [USACO10MAR]伟大的奶牛聚集Great Cow Gat…
传送门解题思路首先第一遍dfs预处理出每个点的子树的siz，然后可以处理出放在根节点的答案，然后递推可得其他答案，递推方程 sum[u]=sum[x]-(val[i]*siz[u])+(siz[1]-siz[u])*val[i]代码#include<iostream>#include<cstdio>#include<cstring>#include...
2018-09-18 17:06:38
153
原创 LUOGU 9月 月赛
T1 签到题传送门解题思路将原式化简一下，让n个1变成 (10^n-1)/9 ，然后再移项，变成了高次同余形式，用bsgs求解。交了好几次都是80，后来才被告知要快速乘。代码#include<iostream>#include<cstdio>#include<cstring>#include<map>#incl...
2018-09-17 15:49:46
217
原创 poj 3263
传送门解题思路如果x与y互相看见，那么他们一定比之间的高，所以给他们之间的高度-1，最后得到的答案是所有牛的高度+h，之间-1会T，用差分数组或线段树维护即可。代码#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include&l...
2018-09-16 20:33:04
310
原创 LUOGU P2280 [HNOI2003]激光炸弹
传送门解题思路二维前缀和。代码#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;cstring&gt;using namespace std;const int MAXN = 5005;inline int rd(){ int x=0,f=1;char ch=getchar(); ...
2018-09-16 20:12:41
124
原创 poj 1958
传送门四塔汉诺塔问题，转移方程非常玄学，f[i]=min(f[j]*2+d[i-j]) （1 <=j < i），d表示三塔下的汉诺塔问题，这个方程的意思是将j个在四塔模式下有A挪到B，然后把其余i-j个在三塔模式下移到D，最后再将j个在四塔模式下挪到D。代码#include<iostream>#include<cstdio>#includ...
2018-09-16 19:53:45
281
原创 tyvj 1266 费解的开关
传送门解题思路枚举第一行的状态，判断后面可不可行。代码#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 15;const int inf = 0x3f3f3f3f;int n,a[MAXN][M...
2018-09-16 19:43:12
316
原创 poj 2288
传送门解题思路状压dp，记录路径条数，dp[S][i][j]表示状态为S，前一个点是i，再前一个点是j的最大值，然后在开个一样的数组记录方案数，时间复杂度O(2^n*n^2)，注意要用long long，还有数据有一个点的情况。代码#include<iostream>#include<cstdio>#include<cstring>...
2018-09-16 14:50:17
162
原创 LUOGU P4626 一道水题 II
传送门解题思路通过手(y)推(y)可知，其实就是要求每个质数的幂次方小于等于n，将这个质数的幂次方累积到答案一定是最优的，然后发现10000的平方>1e8，所以在筛质数的时候就将10000以上的先乘到答案里。。register卡常过得。代码#include<iostream>#include<cstdio>#include<cst...
2018-09-14 16:03:22
105
原创 BZOJ 2456: mode
传送门解题思路喆巨考我的题，我这么菜当然瞬间被考住，想了半天没想出来，后来喆巨讲了才突然大彻大悟。。 思路就是因为众数次数一定大于其他数出现次数的和，就可以拿其他数抵消众数，cnt为当前答案下前面这个答案比其他数多的情况。代码int n,cnt,ans,k;int main(){ __builtin_scanf("%d",&n); while(n...
2018-09-13 22:22:09
93
原创 替罪羊树（模板）
传送门 替罪羊树，优秀的数据结构，关键思想是 假如这棵树长残了就拍扁重构成一棵二叉树，常数很小。alpha是一个平衡因子，用来判断这棵树是否长残，一般取0.5~0.9，比较玄学。代码#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;algorithm&am
2018-09-13 21:36:52
265
原创 LUOGU P4168 [Violet]蒲公英
传送门解题思路分块码农题，设分成T块，cnt[i][j][k]表示第i块到第j块，k出现的次数，需要离散化。all[i][j] 表示第i块到第j块的众数。然后这两个数组先预处理出来。然后询问的时候先将答案设成区间大块的众数，然后剩余部分暴力往cnt里加来更新答案。T取n^(1/3)时最优，时间复杂度O(n^(5/3))代码#include<iostream>...
2018-09-13 16:06:57
257
原创 洛谷题目统计爬虫
#include <stdio.h>#include <windows.h>#include <conio.h>#ifdef URLDownloadToFile#undef URLDownloadToFile#endiftypedef int(__stdcall *UDF)(LPVOID,LPCSTR,LPCSTR,DWORD,LPVOID);UD...
2018-09-12 20:31:48
1237
原创 LUOGU P3819 松江1843路
传送门解题思路比较有意思的一道思路题，首先假如有两个点，每个点的人数都是1，那么将车站建在两个点之间的任意一个位置最后的答案均为这两点的长度，那么考虑在加一个人数为1的点在这两个之间，那么最优的一定是在这个点建在新加的点上，这样的长度还是原来两点的长度，然后做饭就被这样yy出来了。每次将最左端和最右端的点的距离假如答案，因为最优一定是在他们两个中间，而这样这两个点的贡献就是距离，所以用...
2018-09-12 16:30:11
142
原创 LUOGU P2015 二叉苹果树
传送门解题思路树形背包，dp[x][i] 表示以x为根的子树留i个树枝的最大值。代码#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;const int MAXN = 105;inlin...
2018-09-11 21:28:48
142
原创 LUOGU P1273 有线电视网
传送门解题思路明显的树形背包，dp[x][j] 表示以x为根的子树选j个用户的最大值，最后答案取一个最大的j使得dp[1][j] > 0 就行了。代码#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespa...
2018-09-11 20:58:16
138
原创 LUOGU P2052 [NOI2011]道路修建
传送门解题思路这题怕是noi的耻辱，理解题意有点困难，是建好树以后算，并不是决策。理解题意后就十分简单了，一遍dfs。代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#in...
2018-09-11 20:34:23
200
原创 51nod 1301 集合异或和
题面解题思路动态规划，刚开始想的是dp[i][j][k]表示考虑了前i个数，A集合异或和为j，B集合异或和为k，时间复杂度O(n^3) ，得了50分。。正解应该是dp[i][j][k]表示前i个数，A^B=j，A与B第一位不同的数，B的这一位为k的方案数，因为要保证A < B，那么一定是A与B第x位之前的数相等，第x位B=1,A=0，首先枚举这一位数，然后用跑异或背包，因为前x位...
2018-09-07 17:07:45
187
原创 LUOGU P2590 [ZJOI2008]树的统计
传送门解题思路树链剖分，把dfs序用线段树维护，记录一个最大值，记录一个和，两个函数。代码#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;const int MAXN=30005;...
2018-09-02 23:36:29
80
原创 LUOGU P3178 [HAOI2015]树上操作
传送门解题思路树链剖分裸题，线段树维护。代码#include<iostream>#include<cstdio>#include<cstring>#define int long longusing namespace std;const int MAXN = 100005;inline int rd(){ i...
2018-09-02 22:56:50
116
原创 LUOGU P4016 负载平衡问题
题目描述GG 公司有 nn 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。输入输出格式输入格式： 文件的第 11 行中有 11 个正整数 nn ，表示有 nn 个仓库。第 22 行中有 nn 个正整数，表示 nn 个仓库的库存量。输出格式： 输出最少搬运量。输入输出样例...
2018-08-26 15:45:55
145
原创 LUOGU P2296 寻找道路 （noip 2014）
传送门解题思路首先建一张反图，从终点dfs出哪个点直接或间接相连，然后直接跑最短路，跑的时候判断一下所连的点是否与终点相连。代码#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#inclu...
2018-08-25 22:10:37
5994
原创 LUOGU P1351 联合权值（noip 2014）
传送门解题思路直接暴力枚举每个点，然后再枚举这个点的相连点，然后用一个前缀和，复杂度不会证明，，代码#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 200005;const int mod = 1...
2018-08-25 22:05:54
95
原创 LUOGU P4113 [HEOI2012]采花
传送门解题思路莫队题卡莫队。。。莫队只能拿到100分，满分200。正解主席树？？发个莫队100分代码。代码#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<alg...
2018-08-25 17:50:27
132
原创 LUOGU P4251 [SCOI2015]小凸玩矩阵
传送门解题思路二分图匹配，首先二分一个答案，然后对于权值小于这个答案的，行向列连边，然后跑最大匹配，如果最大匹配数>n-k，说明权值比它小的也一定可以满足答案，就缩小边界，时间复杂度O(nmlog(nm)）代码#include<iostream>#include<cstdio>#include<cstring>#inclu...
2018-08-25 17:47:42
162
原创 LUOGU P2756 飞行员配对方案问题
题目背景第二次世界大战时期..题目描述英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找...
2018-08-24 21:44:16
170
原创 LUOGU P2286 [HNOI2004]宠物收养场
题目描述凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养场总是会有两种情况发生：被遗弃的宠...
2018-08-22 22:40:51
76
原创 LUOGU P2485 [SDOI2011]计算器
传送门解题思路板子题，第一问快速幂，第二问求逆元，第三问bsgs代码#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<map>using namespace std;typedef long lon...
2018-08-22 17:52:44
156
原创 BZOJ 2744: [HEOI2012]朋友圈
传送门解题思路直接跑最大团洛谷上能得70分，惊了。说说正解，首先A国的必须xor后mod2余1，就相当于两个人必须是1奇1偶，所以A国的人只能选0,1,2个，我们可以暴力枚举选谁。继续考虑B国，现在的问题实际上就简化为了在B国中选出一个最大团，这个团也必须和A国所选出的人是朋友，又因为最大团=总点数-补图的最大匹配，补图就是将原来连着的边断了，原来没连的边连上，而进一步可以发现其实B国...
2018-08-22 16:54:18
177
原创 LUOGU P4316 绿豆蛙的归宿
题意翻译「Poetize3」 题目背景随着新版百度空间的上线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。 题目描述给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。...
2018-08-21 21:00:36
154
原创 LUOGU P2939 [USACO09FEB]改造路Revamping Trails
题意翻译约翰一共有N)个牧场.由M条布满尘埃的小径连接.小径可 以双向通行.每天早上约翰从牧场1出发到牧场N去给奶牛检查身体.通过每条小径都需要消耗一定的时间.约翰打算升级其中K条小径，使之成为高 速公路.在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为0.请帮助约翰决定对哪些小径进行升级，使他每天从1号牧场到第N号牧场所花的时间最短 题目描述Farmer John ...
2018-08-21 18:48:02
242
原创 LUOGU P3830 [SHOI2012]随机树
传送门解题思路一道比较好的期望dp题，对于第一问来说，设f[i]表示有i个叶子节点的平均叶子深度，当展开一次，它的影响是对于某棵树的某个叶子来说让他的总叶节点数+这个叶子的深度再+2，因为不知道是哪个叶子展开，直接算太麻烦，所以这个叶子的深度其实就相当于平均值，这点比较巧妙，也就是说直接+一个平均值+2即可，所以转移方程为f[i]=(f[i-1](i-1)+f[i-1]+2)/i ，f...
2018-08-21 17:30:09
152
原创 LUOGU P3024 [USACO11OPEN]奶牛跳棋Cow Checkers
题目描述One day, Bessie decides to challenge Farmer John to a game of ‘Cow Checkers’. The game is played on an M*N (1 <= M <= 1,000,000; 1 <= N <= 1,000,000) checkerboard that initially cont...
2018-08-21 16:01:46
276
原创 LUOGU P1937 [USACO10MAR]仓配置Barn Allocation
传送门解题思路扫了一眼觉得是贪心+线段树，结果贪心的时候刚开始按区间长度排的序。。这还有82分，后来叉了自己，换成按右端点排序过了。代码#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>...
2018-08-20 21:29:14
101
原创 LUOGU P3708 koishi的数学题
传送门解题思路发现当x+1时，有的x%i会+1，有的会变成0，而变成0的说明是x的约数，就可以nlogn预处理出每个约数的贡献，然后每次用n-约数。代码#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespa...
2018-08-20 20:37:06
95
原创 LUOGU P3539 [POI2012]ROZ-Fibonacci Representation
传送门解题思路打了个表发现每次x只会被比x大的第一个fab或比x小的第一个fab表示，就直接写了个爆搜骗分，结果过了。。代码#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;typedef ...
2018-08-20 20:04:46
126
原创 LUOGU P1779 魔鬼杀手_NOI导刊2010提高（03）
传送门解题思路背包，首先先用aoe都打残然后单伤补刀，用f[i]表示AOE打了i的伤害的最小花费，g[i]表示单伤打了i的伤害的最小花费。代码#include<iostream>#include<cstdio>#include<cstring>#include<cstdio>#include<cstring&...
2018-08-20 19:13:43
241
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人