2 Mr_Alice

尚未进行身份认证

暂无相关描述

等级
TA的排名 32w+

[分块or定期重构/三维BIT]2019牛客多校8-D Distance

n*m*h<=1e5的三维空间内有q<=1e5次操作,分两种:1.给点(x,y,z)打标记2.询问离位置A(x,y,z)最近的标记点到A的最近曼哈顿距离。两种做法:1.分块/定期重构如果所有的询问操作都在打标记后,那么从所有的标记点开始做一次多源bfs求最短路(每次可以走上下左右前后6个方向哦),则询问点的dis就是到离它最近的点的曼哈顿距离。分块的话,就把所...

2019-08-20 20:21:23

最近/最远曼哈顿距离

本文都是以二维举例的,实际上变成更多维也是差不多的情况啦,只是每个点的状态多了一些而已。最远曼哈顿距离:假设有两个点A(xi,yi),B(xj,yj)则两点之间的曼哈顿距离为|xi-xj|+|yi-yj|,根据两个点之间的位置关系,可以分为四种情况:(把相同点的坐标放在一起了)即(xi+yi)+(-xj-yj),(-xi+yi)+(xj-yj),(xi-yi)+(-xj+y...

2019-08-20 19:00:11

[时间分治+线段树]2019牛客多校8-E Explorer

https://ac.nowcoder.com/acm/contest/888/En个点m条双向边,每条边有通过的下界和上界size限制,主角要从1到n,可以在出发前改变一次size,问有多少种size可以从1到达n。边的上下界范围是1,1e9第一次碰到这样的题,很有意思。WA了一次是因为边界最大是n的两倍,我一开始线段树数组大小开成maxn<<2了,应该是(maxn*2)...

2019-08-16 16:15:54

[Splay模板题]BZOJ1588

很朴素的找前驱和后继,感觉set完全可以做的咳咳。用来练练splay吧……#include<bits/stdc++.h>#definelchild(x)(T[x].ch[0])#definerchild(x)(T[x].ch[1])#definefa(x)(T[x].fa)usingnamespacestd;typedeflonglongll...

2019-08-15 21:01:25

[Splay模板题]POJ3481 num巧用

threekindofoperation:op1:insertclientwhoseidisxandpriorityisptoqueueop2:gettheclientwith**highest**priorityanddrophimfromthequeueop2:gettheclientwith**lowest**...

2019-08-15 20:50:55

[点bcc] 点双连通分量缩点建图图示

2019-07-26 19:31:45

[容斥+二进制优化]51nod1284 2357的倍数

过了一个寒假啥都不会了,做点一级题找点自信。昨天强行算了所有的情况给A了,虽然也是容斥但是写法总感觉不太优秀。今天翻题解找到一个介绍二进制优化的,顿时惊为天人(这次是这么用的吗……总而言之大概理解了一下自己写了一波代码,已A。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;lln;ll...

2019-02-25 11:02:15

[链表模拟]51nod1289大鱼吃小鱼

一开始没有思路自己强行用链表模拟了一下。找到所有向右游的鱼,放进队列,每次处理它们向右走一步后的情况,分为4种:1.右边的鱼向左&更小链表中删掉右边的鱼,当前的鱼重新放回队列2.右边的鱼向左&更大链表中删掉当前的鱼3.右边的鱼向左&大小相同链表中交换两鱼的位置,当前的鱼重新放回队列4.右边的鱼向右走当前的的鱼重新放回队列经粗略分析可知...

2019-02-24 16:29:36

[匈牙利-二分图多重匹配]Gym-101873F 三排插问题

https://vjudge.net/contest/259384#status/Alice_and_Bob/F/0/N个电器M个插座,可以把其中一个变成3插。问最多可以使用多少电器。1.最大匹配2.对每个插座分别尝试再找两条增广路,记录最多可以找到的个数(可能是0,1,2)。对每个插座尝试后,将匹配信息恢复成step1结束后的样子。AC代码:#include&l...

2018-12-06 16:17:29

[对偶图最短路求最小割]BZOJ1001狼抓兔子

参考https://blog.csdn.net/MaxMercer/article/details/77976666平面图才有对偶图。平面图是能展开成一张->各边只在顶点处相交的图<-的图。平面图的对偶图是将这个图G的每一个面做新图G‘的点,在每一条边两边的面之间连边的图。随便找个图连一下会发现,对偶图中的每一个环对应原图中的一个割。盗了一张论文ppt里...

2018-10-30 19:44:04

[生成树计数] BZOJ1002 轮状病毒 生成树计数+JAVA

Step:1.求基尔霍夫矩阵(=度数矩阵-图的邻接矩阵)2.高斯消元求n-1阶主子式的行列式,答案就是生成树个数。n-1阶主子式就是n阶方阵去掉任意一个元素所在的行和列的所有元素,就变成了一个n-1阶的方阵。我把中心的那个点给去掉了。兢兢业业写完之后发现这个要用高精度,默默改用JAVA但是高斯消元的时候用BigDecimal要不就精度不够WA要不就T。后来找了一个用BigInteg...

2018-10-30 19:28:34

51 NOD 三级题总结

10133的幂的和等比数列求和公式啦~a1*(1-q^n)/(1-q)1021石子归并一开始自己想的dp怎么都过不了TT。最后发现是数组初始化越界了(……)做法1:dp[i][j]=区间[i,j]合并的最小花费。状态转移:dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);第一层for了i,j的差(区间长度,一层一层更新)。第二层fo...

2018-10-20 20:11:18

zjnu2017校赛M会长的正方形

出现正方形顶点都在格点上的情况:设x,y。比如x=0,y=1表示的就是边长为1的正方形,x=0,y=2表示边长为2的正方形,x=1,y=2表示边长为根号5的正方形,x=1,y=3表示的是边长为根号9的正方形。那么特定的x,y可以表示一种正方形。经过观察,x+y是刚好放下这个正方形所要的格子的边长。x*x+y*y是这个正方形的面积。再观察,假设格子大小为n,m(nL=1时,这种正方形

2018-01-05 18:52:36

zjnu2017校赛M小智的宝可梦

思路:暴力倒着推。开数组a[]存储0-n-1只小精灵吃到的食物数。从第一只小精灵开始。假设小智喂了它和最后一只小精灵数量为x的食物(x的范围是0-a[0]),然后a[0]和a[n-1]都减去x表示这是已经喂掉的食物。那么剩下的喂食情况都已经被决定了。第二只小精灵必须和第一只小精灵一起被喂食a[0]-x数量的食物,也就是第一只和最后一只一起吃完之后剩下还要吃的量。一直这样下去,如果出现

2018-01-05 18:38:30

zjnu2017校赛J认亲大会

/*思路:每个人做为一个顶点,在他们之间建双向边表示关系,最后以1为起点(now==0表示辈分)dfs所有关系,搜到now>0的就是辈分比1高的新的知识点:1.神奇的输入方式反思:1.链式前向星建图都不熟QAQ2.dfs的复杂度不会分析,这个地方不用考虑所有的情况,因为每个能走到的点结果唯一,要么一样,要么辈分小,要么辈分大*/

2018-01-04 20:14:45

zjnu校赛F 会长大人上课

比赛的时候卡E卡太久,心态崩了,太紧张的结果就是这题的思路也理不顺,赛后写着感觉还不错的==+还是代码经验太少了。。。WA了两次,第一次特判会长大人被数到的次数的时候if/else写串了,第二次是判断n#include#include#includeusingnamespacestd;typedeflonglongll;intt;longlongn,

2018-01-03 19:46:36

zjnu2017校赛 E 会长大人的异世界生活(模拟题)

http://acm.zjnu.edu.cn/xiaosai/contests/1000/problems/1004.html/*1.输入2.特殊处理空串的情况,有分隔符号在开头,中间,结尾(分倒数第二个是不是分隔符号两种情况,注意注释)3.处理其他情况新的知识点:1.关于tring.clear();.empty();+=44;√+=tmp

2018-01-03 18:15:23

[dfs] poj1321

2017/12/21一直觉得DFS和BFS应该是最简单的东西,打开发现并没有思路,心态崩了……【思路】每一行只能找到最多一个能放旗子的地方,但是如果能放则有多个可能。dfs层数,开始从第一层开始,找到一个可以放棋子的点就放下,顺便标记这一列的cvis(colvis)为1,表示这列已经有棋子了。然后去dfs它的下一层,结束后再恢复原来的状态。因为这题可以放的棋子数目K不等于N,所以...

2017-12-21 21:27:56

[Trie树]HDU - 1671 Phone List (字典树)

Givenalistofphonenumbers,determineifitisconsistentinthesensethatnonumberistheprefixofanother.Let’ssaythephonecataloguelistedthesenumbers:1.Emergency9112.Alice97625...

2017-11-06 19:02:19

[主席树]hdu2665 区间第k大

InputThefirstlineisthenumberofthetestcases.Foreachtestcase,thefirstlinecontaintwointegernandm(n,m<=100000),indicatesthenumberofintegersinthesequenceandthenumbe...

2017-08-23 16:11:09

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。