lwqq3-CSDN博客

原创 codeforces766E. Mahmoud and a xor trip（DP）

题意：给定一棵树每个节点有权值任意选两个点i和j满足i<=j其贡献为i到j路径所有点的xor和求所用点对的和题解：感觉带xor的题从位运算考虑会好很多于是对于每个点枚举每一位对于每一位dp[i][0]表示从i点开始这一位xor和为0的路径数那么dp[i][1]同理设j为这个点的儿子那么转移就把他所有儿子的贡献加起来如果i这一位为0 dp[i][0] += dp[j][0], ...

2018-04-16 23:54:31 253

原创 BZOJ1821: [JSOI2010]Group 部落划分 Group（并查集）

题意：把平面上的n个点分为k个集合使得距离最近的两个集合距离最大集合之间的距离定义为其中最近两个点的距离题解：先预处理出每两个点之间的距离然后排个序对于当前的最近距离如果当前的集合数大于k个集合说明可以把这两个点合并在一起使得跳过这个最近距离直到不能合并位置 #include <stdio.h>#include <algorithm>#include <...

2018-04-11 12:02:35 147

原创 BZOJ2563: 阿狸和桃子的游戏（巧妙的贪心）

决定以后写博客还是把题意写上题意：给一个含点权和边权的图两个人轮流操作每次选一个点选完后最后每个人的得分为所有选择点的点权 + 如果选了这条边两个端点的边权最后输出这两个人的分数差题解：贪心就行。。。把每条边的边权平分给包含他的两个点，这样如果这条边被一个人选了刚好就加上了这条边的边权，如果被两个人选择到了，答案刚好一减，排个序贪心，给思路跪了。然后注意下如果边权为奇数分不尽的情...

2018-04-10 16:08:22 238

就是SG了......每堆石子的操作可以平均分为x堆且这堆不小于f才能分暴力把每种操作分的堆的sg值xor起来就可以求出这个新的了然后这个题居然有个神优化很容易得到把x分为i堆的sg值为（x % i == 1) ? sg[x / i + 1] : 0 ^ (i - x % i) % 2 == 1 ? sg[x / i] : 0然后对于x / i这样不同的值最多有根号x个然后按x / i分块的...

2018-04-02 00:33:12 186

原创 BZOJ4300: 绝世好题（DP）

好裸的DP。。。按位存一下当前位能取的最大值我好菜(⊙﹏⊙)#include <stdio.h>#include <algorithm>#include <iostream>using namespace std;int zd[40];int q[100005];int main(){ int n; int ans = 0; s...

2018-03-22 11:54:21 143

原创 codeforces940F. Machine Learning（带修莫队）

带修莫队有点裸因为感觉再暴力求mex的时候感觉不会太大最多就是个常数级带修莫队还写的不够熟 TLE了好久注意下分块的大小以及带关键字的排序很奇怪这个题明明都是1e5的数据范围开1e5的数组大小会re 所以都开的2e5 (⊙﹏⊙)#include <stdio.h>#include <algorithm>#include <iostream>#in...

2018-03-22 10:50:01 306 1

原创 LOJ#6285. 数列分块入门 9（分块）

题意查询区间最小众数死啃了clj的区间众数解题报告... 真实太强辣还有一个logn的优化没学会待填坑大概就是分块然后枚举最多2根号n + 1个元素询问这些元素在这个区间出现了多少次先预处理同一个元素在数组中出现的位置存入容器中然后二分查询即可#include <stdio.h>#include <algorithm>#include <iostr...

2018-03-15 11:19:37 927

原创 codeforces946D. Timetable（DP)

预处理一下每一天逃课i天能获得的最大收益我的预处理好蠢啊但是不想改了具体看丑丑的代码TATdp_i j表示第i天一共逃j节课所获得的收益类似背包的转移方程 dp[i][k + j] = max(dp[i][j + k], dp[i - 1][j] + cost[i][k]); // j为之前i - 1天逃课总数第i天逃k节课最后再减去一下就行了写了一晚上写崩了啊我好菜#include...

2018-03-08 00:48:06 341

原创 BZOJ1588: [HNOI2002]营业额统计（splay）

splay模板题注意一下没有前驱和后驱的情况#include <stdio.h>#include <algorithm>#include <iostream>using namespace std;int rt, cnt, sz;int ch[40005][2];int cn[40005];int fa[40005];int val[40005...

2018-03-06 14:26:33 157

原创 BZOJ3224: Tyvj 1728 普通平衡树（splay）

splay模板题学习了zyf2000的博客万分感谢！#include <stdio.h>#include <algorithm>#include <iostream>using namespace std;int rt, cnt;int so[100005][2];int fa[100005];int sz[100005];int cn[10...

2018-03-06 11:47:08 207

原创 BZOJ1208: [HNOI2004]宠物收养所（splay)

splay模板题调了好久啊TAT#include <stdio.h>#include <algorithm>#include <iostream>#include <cmath>using namespace std;int ch[80005][2];int fa[80005];int val[80005];int cn[80005...

2018-03-06 11:41:14 263

原创 BZOJ4521: [Cqoi2016]手机号码（数位DP）

就裸数位DP了...比较奇怪的是之前只写了pos和sta两位状态一直不对于是把dfs的变量都加成状态就莫名过了不明白呀#include <stdio.h>#include <algorithm>#include <iostream>#include <string.h>using namespace std;typedef long l...

2018-02-23 02:05:44 150

lwqq3的博客