• 等级
  • 114774 访问
  • 238 原创
  • 1 转发
  • 15375 排名
  • 17 评论
  • 1 获赞

#长期填坑# 一个奇怪的静态树上联通块处理技巧

第二次做CC的那道边上gcd的题目想出来一个奇怪的技巧 可以把理论复杂度从O(nw‾‾√logn+q2w‾‾√logn)O(n\sqrt{w} logn+q^2\sqrt{w}logn)变成O((n+q)w‾‾√lognw)O((n+q)\sqrt{w}lognw) 在线询问 支持可持久化 空间的话。。貌似有点大大。。和时间复杂度同阶 然而这个是理论复杂度。。。并查集的loglog和线段树的

2017-03-16 08:52:54

BZOJ4762: 最小集合

感谢度教。。。转化条件1 : 使得Or集为全集使得Or集为全集 其他不变一个合法集合S必不存在一个大小为|S|−1的子集T满足条件1一个合法集合 S 必不存在 一个大小为 |S|-1的子集T满足条件1 即一个集合合法必不存在一对长度和小于|S|的前缀与后缀使得Or集为全集即一个集合合法 必不存在一对长度和小于|S|的前缀与后缀使得Or集为全集然后考虑暴力 g[i][j][k]表示已经做了前

2017-03-13 12:10:16

BZOJ4768: 2555加强版之wxh loves substring

很显然的后缀平衡树 一开始以为要可持久化 发现根本不用。。 treap的常数要死人啊?寄刀片寄刀片 #include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<map> #include<cmath> using namespace std; #define ld long longchar

2017-03-10 21:55:27

Anarchy的解题报告

题目大意: 假设高斯定理在mm维空间成立 已知mm维空间所有整点电荷 aja_j 给出mm维空间下x,yx,y两点距离公式 以及x点在y点引发的电势公式 降序输出求前100个点的电势T≤51≤m≤18n≤3∗105T≤5 1≤m≤18 n≤3*10^5 时限7s7s考试的时候看这道题的时候 感觉这道题根本不可做啊??? 部分分很友好啊?除了一个5分的点 其他我都不会。。看

2017-03-10 15:49:42

2017.3.1

首先这是一篇检讨 这场比赛我因为思考不充分便开始打T2 bug如雪球一般越滚越大 最后GG这场比赛我没有仔细阅读题面 而是看一眼题目 自信心爆膨 便开始刚T2 导致其他题目暴力没打 五个小时的时间里 我的T2遇到了很多问题 而我并没有从根本上去质疑我的算法 而是不断地打着补丁 并作死。。。这场我觉得是对我最有启发的一场比赛 1、仔细阅读所有题目之后再开始 2、思考时需要保证

2017-03-01 17:15:17

2017.2.25被虐记录

好惨啊 怎么三道数学题啊 先放个坑

2017-02-26 09:30:46

2017.7.22模拟赛被虐记录

感觉自己要完 成功被虐了两倍分。。 其实故事是这样的 看了第二题 发现是个SB树分 然后就没有然后了 突然Manchery说自己的代码会被卡常 然后我拿了大样例 没开优化跑了0.8s 时限2s 感觉很稳啊 看了第一题 完全没思路 看了看大样例 我日 SB题。。。 但是要特判几个hack点。。。 第三题 弃疗 暴力都不会。。。 然后。。。本机跑0.8s的我在评测机上2s TL

2017-02-22 18:25:57

补2016.2.21

貌似昨天的又忘了写了? 做了一上午的题 下午我在干嘛?好像是在推一个生成函数的题目。。然后发现二项式定理和暴力乘法答案不一样 弃疗。。。。感觉自己已经是一条咸鱼了晚上TC 成功贡献一记Hack 有小哥叉了我的随机化的代码是闹哪样?

2017-02-22 18:08:43

补2016.2.20

来 我来补一下昨天 昨天讲了一些组合数学的内容 感觉好像没什么营养的样子? 好像这些都是说给高一的人听的吧?多项式什么的感觉好像没有劼老师讲的愉悦啊? 最后的混吃等死。。。

2017-02-21 11:03:16

2017.2.18模拟赛总结反思

第一次模拟赛被绍一大爷虐惨了。。。。看T1 woc这不是SB虚树么?打上ST表之后发现自己丝薄了。。 听着别人键盘噼里啪啦 蜜汁心慌一小时后我才发现T1可以O(n32)O(n^{\frac{3}{2}})的做 然后感觉复杂度太高 看着旁边Manchery已经码起来了 感觉很害怕 问了一下复杂度 居然和我一样 于是我也不虚了然后调出大样例手造数据发现自己代码跑的还蛮快的 之后开始刚第三

2017-02-18 18:44:44

BZOJ4695: 最假女选手

我好像被卡空间了啊? 惨啊.. 代码好丑啊QAQ 考虑更新 类似VEB Tree的记录当前最大值 不过这样子还是不容易更新最小值的 于是记录一个次大值 和最大值个数便于更新 对于最大值用类似方法维护#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; char

2017-02-17 11:35:51

Hackerrank How many substrings

好难啊QAQ 今天又去想了一下 然后向敦爷求证了一下 发现思路还是对的代码太难实现了。。 LCT维护last并在Segment Tree上更新。。。 感觉自己被日死了 最后看着板子打了一发。。 先离线 考虑每个串在最后出现的开始位置有贡献 然后就是一个区间加 区间减的操作 在Access的时候更新线段树 时间复杂度O(nlognlogn)O(nlognlogn)你看800+sub

2017-02-16 20:40:51

HDU5766 Filling

Burnside+插头DP 旋转有四个群 不动 旋转 π2\frac{π}{2} ππ 3π2\frac{3π}{2} 显然要染色在某置换下不动则每一块结构相同 考虑分别计算 显然 旋转π2\frac{ π}{2} 与旋转 3π2\frac{ 3π}{2} 答案相同我们只需要考虑旋转π2\frac{ π}{2}的情况 此时将n*n的格子分成[n+12][\frac{n+1}{

2017-02-15 15:40:53

Stirling数学习笔记

劼爷上的课现在才去整理…第一类Stirling数 s(n,m)表示n个元素组成m个圆排列s(n,m)表示n个元素组成m个圆排列 由以上定义我们可以得出递推公式:由以上定义我们可以得出递推公式: s(n,m)=∑n−1i=0s(n−i,m−1)∗Ci−1n−1∗(i−1)! s(n,m)=\sum_{i=0}^{n-1}s(n-i,m-1)*C_{n-1}^{i-1}*(i-1)! 以及

2016-12-18 15:39:16

Hackerrank XOR Subsequences

求连续子串的Xor和出现次数最多的Xor和 Xoryi=xAi=(Xorx−1i=1Ai)Xor(Xoryi=1Ai)Xor_{i=x}^{y}Ai=(Xor_{i=1}^{x-1}Ai) Xor (Xor_{i=1}^{y}Ai) 最后发现其实就是个卷积形式 上FWT即可 中间处理过程可能会爆int 所以加上取模会免掉不必要的麻烦#include<cstdio> #include<iost

2016-12-15 18:19:41

FFT优化进制转换 十进制转二进制

其实进制转换都能这么做.. ∑ni=0xi∗Basei\sum_{i=0}^{n}x_i*Base^i ∑n2−1i=0xi∗Basei+Basen2∗∑n2i=0xi+n2∗Basei\sum_{i=0}^{\frac{n}{2}-1}x_i*Base^i+Base^{\frac{n}{2}}*\sum_{i=0}^{\frac{n}{2}}x_{i+\frac{n}{2}}*Base^i

2016-12-14 19:49:52

Hackerrank Hard Homework

题目链接: https://www.hackerrank.com/contests/w26/challenges/hard-homework 题目大意: 给定nn 求正整数x,y,zx,y,z满足x+y+z=nx+y+z=n 最大化sin(x)+sin(y)+sin(z)sin(x)+sin(y)+sin(z)一开始往死里搞没拆出来.. 搞了一个O(nlogn)O(nlogn)的做法结果死

2016-12-12 19:25:16

ZOJ2674 Strange Limit

欧拉函数….#include<cstdio> #include<cmath> #include<iostream> using namespace std;int p;int Fai(int x) { int t=sqrt(x),res=1; for(int i=2;i<=t&&i<=x;i++) if(x%i==0) { x/=i;

2016-12-11 20:35:45

Ural1540 Battle for the Ring

区间DP+SG函数看到代码淦过去的时候我的内心是崩溃的… 明明O(n^4)啊。。#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std;char c; inline void read(int&a)

2016-12-11 19:22:25

Hackerrank Random Number Generator

题目链接: https://www.hackerrank.com/challenges/random-number-generator-1 题目大意: Pi>=0P_i>=0 且1=Σni=1Pi1=Σ_{i=1}^{n}P_i 最大化 Σni=1Pi∗(1−Pi)∗iΣ_{i=1}^{n}P_i*(1-P_i)*i一开始的感觉很对 但是发现拉格朗日出现负数就不会处理 后来问了uo

2016-12-09 17:10:55

Hillan_

An OIer From ZJ
关注
  • 其他/OIer
  • 中国
奖章
  • 持之以恒