- 博客(283)
- 收藏
- 关注
RSS订阅原创 【洛谷4735】 最大异或和（可持久化01Trie）
传送门【题目分析】emmmm，似乎是个最大异或和的模板？先将第二个操作里的式子转一下，求a[p]^a[p+1]^....a[n]^x等价于前缀异或和sum[p-1]^sum[n]^x，后面两个的异或值是一个定值，所以我们只用在[l,r]中找到使sum[p]^(sum[n]^x)最大的即可。【代码~】#include<bits/stdc++.h>using nam...
2019-11-15 08:02:51
266
原创 【校内OJ2645】 hyc的xor/mex （01Trie）
传送门【题目分析】因为所有的操作都是对于全局的，所以可以单独把所有操作的值x存下来，每次询问的时候带到Trie上跑就好了。（wsm会有什么权值线段树这种东西？【代码~】#include<bits/stdc++.h>using namespace std;const int MAXN=1e7+10;int n,q;int tag;int siz[MAXN...
2019-11-15 07:51:05
261
原创 【TJOI2018】 异或（可持久化01Trie+树链剖分）
传送门【题目分析】可持久化Trie与主席树其实没啥太大的实现上的差别，因为一次只会插入一个串，也就只会在前一个版本的Trie上改变一条链，那么其他儿子就可以与主席树类似的操作直接继承。那么如何判断两个版本之间是否有一个串呢？我们对每个节点记一个size，只要后一个版本该节点的size>前一个版本该节点的size，那么就一定至少有一个串经过了当前节点。有了这个东西我们就可以直接...
2019-11-14 08:21:31
294
原创 CSP前的常见错误分析
就是一个菜鸡的总结1.代码类1.有时候不开long long，所以以防万一只要有开long long的可能就直接全局long long，就是有时候需要注意内存。2.字符串的读入总是令人智熄，所以可能的话统一用scanf，像类似线段树输入操作的时候就直接开一个字符数组，这样就不会被空格啊行末回车啊什么的按在地上摩擦。（PS：有字符数组的读入好像不能用fread了？）3.调试语句一定要...
2019-11-12 20:24:31
5759
2
原创 校内OJ 4765 bestJob（分类讨论）
传送门【题目分析】细节打挂一堆。。。。。。。。。其实还挺好想的。。。。先将每个人的答案字符串转为二进制数，0表示N，1表示Y。分情况讨论如下：1.k1=0,k2=0全是第三类人的话，只用满足答案对应的二进制串没有出现过，这个用map就能维护，注意枚举要到最大值，但因为不同的串和反串最多100个，所以不用枚举多少就能找到答案。2.k1!=0,k2!=0两种人都有，...
2019-10-23 20:45:08
310
2
原创 图论专题总结及近年NOIP有关真题
目录写在前面1.图的建立和遍历2.最短路3.拓扑排序4.生成树5.连通块6.二分图，网络流等写在前面这篇文章主要总结部分NOIP的图论知识点以及一些NOIP真题。1.图的建立和遍历图的存储方式主要就是邻接矩阵和前向星这两种，这里不多赘述。遍历说白了就是纯粹的暴力。。。。但也是一种很重要的拿部分分的方式。。。主要就是深度优先搜索和广度优先搜索两种搜...
2019-10-20 18:14:47
421
2
原创 【洛谷1312】【NOIP2011DAY1T3】 Mayan游戏（模拟）
传送门【题目分析】T3考模拟有点意思，不过考场可能还真想不到自己错在哪了hhh我的做法比较暴力，因为n不大，就直接枚举所有情况，有一些比较显然的性质：1.当前位置有方块才交换（因为忘了这个WA了3个）2.相同方块不用交换（剪枝？）3.除非左边为空，否则不进行向左交换的操作。然后就是一些小细节了嘻嘻嘻，看看代码就行，写的还算清真。【代码~】#include<...
2019-10-16 09:41:23
147
原创 CF1053E Euler tour（构造）
传送门【题目分析】什么神仙题都拿来当T2。。。。。首先还是列出比较明显的性质：1.两个相同非零数之间的长度为奇数2.一头一尾非零但不相等无解3.一段区间如果已知数字互不相同，如果0的个数小于区间长度的一半，无解（即下去了上不来）4.子树区间要么完全包含要么不相交，相交不包含无解有以上几个性质就可以排除一些情况，然后是填数。对于当前处理的区间[L,R]，对于区间中...
2019-10-06 10:52:03
227
原创 2019.10.3 模拟测试
T1 permut可能逆序对这种东西天生血克我吧QAQ结果还有打表找出规律来的？？？结果最后还是个挺好想的DP？？？？靠，，，#include<bits/stdc++.h>using namespace std;const int MAXN=1e3+10;const int p=1e4;int T;int n,k;int dp[MAXN][MAXN]...
2019-10-05 15:57:52
116
原创 【洛谷2296】【NOIP2014DAY2T2】寻找道路（最短路）
传送门【题目分析】这是DAY2T2？？？？？？嘻嘻嘻嘻嘻嘻嘻嘻直接从终点跑到起点的最短路就行了。。。。。。然而我sb了先把合法点跑出来再做的最短路反正能过就行hhhh#include<bits/stdc++.h>using namespace std;const int MAXN=1e4+10;const int MAXM=2e5+10;const i...
2019-10-04 10:58:41
117
原创 POJ2054 Color a Tree（贪心）
POJ传送门【题目分析】这是什么神仙贪心。。。。。。首先可以得到一个比较明显的性质，对于当前树中的最大点，在它的父亲被染色后一定会染它。那么对于染色序列中的三个点x,y,z，如果已知x,y是连续染色，那么就有两种情况：1）染色序列为x,y,z，代价为x+2y+3z2）染色序列为z,x,y，代价为z+2x+3y然后就是一个神仙操作，两边加上(z-y)再同时除以2，得到两个...
2019-09-28 10:10:42
242
原创 洛谷3953【NOIP2017DAY1T3】 逛公园（最短路+DP）
氵谷传送门【题目描述】很仙的一道最短路，想出状态定义后还是比较好做的。首先跑出1到所有点的最短路，记作dis[i]。定义状态方程dp[x][i]表示到点x比最短路大i的路径条数，根据这个数据规模明显直接O(nk)枚举就行。DP转移方程：，这里因为一个点可以被多次搜到，所以记忆化可以做到剪枝效果。而后面这个式子看着长其实移项后就是，其中表示如果走这条边比最短路长多少，然后用当前枚...
2019-09-27 20:09:59
177
原创 【模板】维护序列2（线段树）
内网传送门【题目分析】取模取挂可真是令人质壁分离。。。。两两乘积和可以直接用两个区间的区间和相乘再加上两个区间各自的乘积和得到，而相邻乘积和直接两段相加再加上左区间右端点与右区间左端点乘积就好了。注意+MOD%MOD【代码~】#include<bits/stdc++.h>using namespace std;typedef long long LL;c...
2019-09-20 18:58:32
170
原创 【NOIP2018DAY1T3】【洛谷5021】 赛道修建（二分+贪心）
洛谷传送门【题目分析】感叹自己当年为何连二分都能打挂。。。首先最短路径最长，很容易想到二分，关键就是check的写法。正解是有点神仙的贪心，用dp[u]表示u的子树内未被选择的最大路径的长度，对于子节点v，如果满足dp[v]+w[u,v]>=mid cnt就加1，否则压入multiset中作为待选择路径。将未选择的路径排序，然后就是lowerbound找mid-len即可...
2019-09-14 09:57:17
192
原创 2019.9.13模拟测试
搜索比赛垫底了QAQ果然我还是太菜了蓝瘦香菇T1 解密牛语codevs传送门这道题神坑的一点就是原串不知道为啥可以读出48的串长。。。。。缓缓扣出一个？（咕成90调半天）其实就是搜索+疯狂剪枝，就成为O（玄学）根据如下几个性质进行剪枝：对于1.串长一定为47+3*k2.第一个s前的前缀与最后一个s后的后缀一定与原串相同。3.两个相邻s之间串的顺序一...
2019-09-13 17:08:54
185
原创 CF484D Kindergarten（贪心）
氵谷传送门【题目分析】很有意思的一道贪心，然而因为太菜了猜到结论自己把自己否了显然我们可以对每一个峰顶和谷底进行划分，然后每个峰顶一定会作正贡献，每个谷底一定会做负贡献，所以就比较左右两个数的贡献，由此得到dp方程：当a[i-2],a[i-1],a[i]单调时为上面的式子，否则为下面的式子。#include<bits/stdc++.h>using names...
2019-09-12 20:05:50
221
原创 2019.9.7 模拟测试
T1 矩形这是一道防AK题（确信）反正我被防了（是个辣鸡）vanvan没想到还能斜着放，我说第一题怎么能这么简单很巧妙的方法就是将一个矩形的对角线放在另一个矩形中再判断高度差即可#include<bits/stdc++.h>using namespace std;const double eps=1e-8;int n;double a1,a2,b1,b2;...
2019-09-07 16:58:51
137
原创 2019.8.21模拟测试
T1 sequenceummmmm，结论推错很棒哟。。。。迭代几次可以得到一个等比数列，那么b就是一个一次常量，若|a|<1只会无限接近于某个值而无法达到无穷大。然后就是a=-1,a=0,a+b=1的时候非法我太蔡了#include<bits/stdc++.h>using namespace std;typedef long long LL;const...
2019-08-21 19:23:07
110
原创 2019.8.15模拟测试
T1 前缀数组大水题能说啥。。。。。第三个大样例用freopen和直接打开不一样？emmmmm。。。。。#include<bits/stdc++.h>using namespace std;typedef long long LL;const int MOD=1e9+7;LL ans;int Read(){ int i=0,f=1; char c=ge...
2019-08-15 18:28:38
115
原创 2019.8.12模拟测试
8.10的暂且咕掉叭。。。。T1 物理终于开始向物理竞赛方向扩展了吗！#@%……￥%很氵的模拟，开个栈走一遍就行了。#include<bits/stdc++.h>using namespace std;#define mp make_pairint n,len;double dz[310];int pos[310],vis[310],cnt;double...
2019-08-12 20:20:53
116
原创 【SHOI2015】 脑洞治疗仪（线段树）
氵谷传送门网上看到ODT吊打线段树的dalao。。。STO但我不会ODT所以只能写线段树QAQ三个操作分别对应：区间赋值为0，区间求1个数赋值为0再在指定区间从左往右填0，查询区间最长0。第一个和第三个操作比较常规，难点在第二个。一开始想的是直接统计1个数赋值，但可能被这种hack：将第五个挖出放在前四个中，最后就应该是1 1 0 1 0，但错误做法会变成 1 1 1 1 ...
2019-08-09 10:36:42
169
原创 2019.8.8 模拟测试
T1：昆特牌wsm这题面这么迷呢。。。。模拟细节好多过艹。。。。幸好第五种只有俩点有一个还水（雾注意判重和非法情况（哈戳戳的写了个map去映射操作序列跑的贼慢【丑陋的代码】#include<bits/stdc++.h>using namespace std;int n,w,ans=-0x3f3f3f3f,tot;int use[10],que[10];...
2019-08-08 20:25:11
259
原创 校内OJ3755 数据结构题（线段树）
【题目描述】给出一个长为n的序列编号 输入格式 含义 1 1 l r 求区间[l,r]的和 2 2 l r 求区间[l,r]的最大值 3 3 l r 求区间[l,r]的最小值 4 4 l r x 将区间[l,r]内的所有数加上 x 5 5 i x 将第i个数按位异或 x 6 6 l ...
2019-07-19 10:20:54
130
原创 TYVJ2002 扑克牌（期望）
传送门【题目分析】定义数组dp[a][b][c][d][x][y]表示当前已经翻了a张黑桃，b张红桃，c张梅花，d张方块，小王状态为x，大王状态为y的期望值，x,y为0-4的数，分别表示黑桃红桃梅花方块和未翻。那么现在剩下的牌就是res=(54-a-b-c-d-(x!=4)-(y!=4))那么我们可以得到dp[a][b][c][d][x][y]的递推式：如果x=4或y=4，...
2019-03-06 17:30:48
340
原创 洛谷4316 TYVJ1933 绿豆蛙的归宿（期望+拓扑）
洛谷传送门【题目分析】受收集邮票这道题的影响，定义ans[x]表示从节点x到终点的期望路径长度。分析一下很容易能得出ans[x]的递推式：，其中out[x]表示离开x的边的数量。所以直接建一个从终点到起点的反图，一边建一边统计答案即可，答案就是ans[1]【代码~】#include<bits/stdc++.h>using namespace std;c...
2019-03-06 11:49:43
147
原创 洛谷2495 【SDOI2011】消耗战（虚树）
传送门【题目分析】很好的虚树入门题。很明显不可能询问一次就对整棵树进行一次遍历，这样会直接T掉，发现其实很多点是不用保留的，这也是虚树的好处：简化整个图然后进行操作。所以我们将所有关键点及其LCA储存进最后的图中，构建虚树。然后就是常规DP，每个点记一个到根的边最小值，遍历到叶子节点时直接返回最小值，否则记录所有儿子最小值之和，与直接割当前点进行比较取较小值即可。（为啥我非...
2019-03-02 16:55:59
216
原创 洛谷2016 战略游戏（树形DP）
传送门【题目分析】之前觉得这种入门DP很难来着qwq由于n很小，加上可以记忆化，所以直接暴力搜索，枚举父亲是否放了，如果没放那么当前点只能选择放，否则两种都可以，这样dfs下去统计答案即可。【代码~】#include<bits/stdc++.h>using namespace std;const int MAXN=2e3+10;const int MAXM=...
2019-03-01 21:25:23
364
原创 洛谷4550 收集邮票（期望DP）
传送门【题目分析】 为啥这道题都是道权限题。。。。 虽然代码很短，但是要想清楚还是很难。 令f[i]表示当前已经拥有了i种邮票，要拥有n种邮票的期望操作次数。 那么对于下一次的操作无外乎两种：又一次取到已经得到的邮票和取到新的邮票。 取到已得到的邮票概率为in\frac{i}{n}ni，取到新的邮票的概率为n−in\frac{n-i}{n}nn−i，所以可以得到...
2019-03-01 21:03:34
270
原创 洛谷2599 【ZJOI2009】取石子游戏（博弈论+DP）
传送门【题目分析】这谁想得到要DP啊。。。。。ZJOI果然神题倍出。参考了YYB的博客，传送门。（确实讲的很好！一看就懂！）定义两个数组：和，L[i][j]表示在区间[i,j]左边放一堆数量为L[i][j]的石子，此时先手必败，R[i][j]表示在区间[i,j]右侧放一堆数量为R[i][j]的石子，此时先手必败。如果存在两个或以上的L[i][j]，那么显然左边的可以通过取任意个...
2019-03-01 20:12:25
448
原创 BZOJ1228 【SDOI2009】E&D（博弈+SG函数）
传送门【题目分析】很好的博弈论分析题。首先这个题明显可以分为独立的n/2个子游戏，所以只用判sg值的异或和是否为0即可。所以考虑每一个子游戏。首先先给结论：只要有一堆石子为偶数，那么当前局势必胜；如果两堆均为奇数，那么当前必败。下面给出证明：1.如果两堆为奇数，由于最后的目标状态（1，1）也为两个奇数，而奇数只能分为一个奇数与一个偶数之和，所以自己只能分为一堆奇数一堆偶...
2019-02-23 21:05:30
191
原创 HDU5754 Life Winner Bo（混合博弈）
传送门【题目分析】一次将几种博弈混在一起，好题！转换一下思路，将过程视作从两堆石子中取石子，一堆有(n-1)个，一堆有(m-1)个，走一步相当于在取石子。首先看王的走法：可以向右向下向右下走，转换一下就是从一堆中取出1个石子或从两堆中同时取出1个石子。分析一下，一次操作相当于改变一堆石子的奇偶性或同时改变两堆石子的奇偶性，最终目标是将两堆石子都变为0，那么就是说两堆石子都是偶数...
2019-02-23 15:32:24
245
原创 博弈及SG函数的一点学习笔记
一点前置补充先定义几个概念：1.一般博弈emmm，一个人玩多没意思。。。多个人玩情况可能太复杂，所以一般博弈讨论的就是双人间博弈，并且双人进行公平游戏，即规则相同且信息对等，两人轮流操作（即非随机选择），无法操作者判负。2.状态类似于DP中的状态，即当前的游戏局面。3.必胜（败）局面如果存在一种一定获胜的方法，那么当前局面就是必胜局面。反之，如果不能存在一种一定获胜...
2019-02-23 11:58:11
197
原创 HDU1848 Fibonacci again and again（SG函数）
传送门【题目分析】SG入门题吧。首先根据SG定理，三堆石子是互相独立的，所以整个游戏的sg值就是三堆石子的sg值异或和。考虑如何计算sg值：直接上暴力，先将前20个fibonacci求出来（因为石子数不会超过1e3），显然，gs(0)=0，然后按照gs的定义方式直接枚举1-1000所有状态的gs值，每一个状态直接枚举所有不大于他的斐波那契数减去即后继，再算一下mex就行了。...
2019-02-23 11:30:31
195
原创 HDU1517 A Multiplication Game（博弈论）
传送门【题目分析】经典博弈问题。首先n的位置为必胜态，所以均为必败态，为必胜态。。。。。以此类推，所以只用一直除一个18（不过要向上取整），最后判断，如果在1~9之间则先手胜出，否则后手胜。【代码~】#include<bits/stdc++.h>using namespace std;long long n;int main(){ while(scan...
2019-02-23 10:27:03
202
原创 POJ1067 取石子游戏（Betty定理）
传送门【题目分析】根据题意打个表，可以知道前几个必败点：(0,0),(1,2),(3,5),(4,7)......观察一下可以发现，第一项为前面没出现的最小自然数，即mex，第二项为前一项+i（将(1,2)视为第一项），所以可以猜想，所有必败点的形式就是，下面给出证明：1.首先可以知道，对于一个必败点(a,b)，那么对于所有(k,b)(a,k)(k,a)(b,k)都是必胜状态（因为...
2019-02-23 09:37:01
498
原创 Betty定理及证明
Betty定理：如果两个无理数a,b满足：那么对于两个集合A,B：有下面两个结论：下面给出证明：1.对于所有整数，最多只会在A（B）中出现一次。由，且a,b为正可以得到a,b均大于1，所以[na]的跨度大于1，所以向下取整不会有重复。2.对于前一个结论，用反证法证明，令整数k使得：那么就有：化一下得到：同理：两式相加：显然...
2019-02-23 09:21:40
4420
原创 NOIP模拟 斐波那契（set+fib）
【题目描述】斐波那契数列又称兔子数列，可以通过以下方式产生：一开始只有一只兔子，一个月之后这只兔子每个月会繁殖出另一只兔子。之后每只兔子出生后都按照以上规则繁殖。我们把每个月的兔子的数量作为数列中的数就可以得到斐波那契数列。现在草原上有 n 只兔子排成一排，每只兔子有一个繁殖能力 ai。小 F 想把这些兔子分组，要求一个组内的兔子必须是连续的一段。而且因为兔子们不太喜欢兔子数列，所以组内任意两...
2019-02-23 08:29:57
415
原创 NOIP模拟 栅栏（二维树状数组+矩阵异或）
【题目描述】小 Z 决定要去 AK PION 2018, 不过在这之前，他要先把家里的牛给养大。小 Z 家里的牛棚是一个 n ∗ m 的网格，牛均匀地分布在这些网格中。一开始小 Z 的牛都很小，习性也都相近，所以牛棚中没有栅栏。不过随着时间的推移，不同品种的牛的不同习性逐渐暴露出来，这时候小 Z 会建造栅栏来把不同习性的牛给分隔开。不过，时间久了之后，牛之间也需要交流感情，所以小 Z ...
2019-02-23 08:29:51
374
原创 NOIP模拟 序列（主席树）
【题目描述】最近小 X 对序列的研究产生了一定的兴趣。小 X 把一个区间的中位数看成将这个区间内的数排序之后位于中间的数，如果区间的长度为偶数的话则是较小的数。一开始，小 X 想研究一个序列的所有区间中，中位数最大的区间是哪一个。后来他想了想觉得太简单了，于是决定把这个问题加大一点难度：小 X 现在想知道有多少区间的中位数位于他给定的 [l1, r1] 之间。后来他想了想便自己...
2019-02-23 08:29:39
296
原创 洛谷1829 【国家集训队】Crash的数字表格（莫比乌斯反演）
传送门【题目分析】又一次败给了取模。。。。。qwq还是先翻译一下题目：lcm不好求，转一下变成gcd：枚举gcd(i,j)=p：后面这一堆直接除一个p，因为i,j各含一个p，所以直接抵消：这一块就是两个等差数列相乘，令：，所以有:容斥+反演一下：化一下得到：换个元，令T=pt：所以这就是我们要求的式子，显然前半截可以直...
2019-02-19 17:13:07
140
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人