6 Hillan_

尚未进行身份认证

An OIer From ZJ

等级
TA的排名 1w+

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

第二次做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>usingnamespacestd;#defineldlonglongchar

2017-03-10 21:55:27

Anarchy的解题报告

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

2017-03-10 15:49:42

2017.3.1

首先这是一篇检讨这场比赛我因为思考不充分便开始打T2bug如雪球一般越滚越大最后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的我在评测机上2sTL

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模拟赛总结反思

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

2017-02-18 18:44:44

BZOJ4695: 最假女选手

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

2017-02-17 11:35:51

Hackerrank How many substrings

好难啊QAQ今天又去想了一下然后向敦爷求证了一下发现思路还是对的代码太难实现了。。LCT维护last并在SegmentTree上更新。。。感觉自己被日死了最后看着板子打了一发。。先离线考虑每个串在最后出现的开始位置有贡献然后就是一个区间加区间减的操作在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>usingnamespacestd;intp;intFai(intx){intt=sqrt(x),res=1;for(inti=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>usingnamespacestd;charc;inlinevoidread(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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!