4 Just_JK

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 2w+

2019 ICPC Asia Nanchang Regional (dsu on tree+treap平衡树)

题意:给你一棵树,每个点有一个val让你找树上有多少有序对(x,y)满足以下条件:1.x!=y2.x不是y的祖先;y不是x的祖先3.x与y的最短路径长度<=k4.x与y的最小公共祖先的值vz,满足2vz=vx+vy解析:就是启发式合并,同时建n棵权值treap树,来维护该权值下,有多少深度的点插入进来。在遍历轻孩子找答案时,每一次,已经确定根和一个点...

2019-12-13 13:50:53

2019CCPC 哈尔滨 E - Exchanging Gifts (离散化+fastIO+bfs)

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <queue> #include <iostream> ...

2019-11-20 12:12:41

2019 ICPC Asia Nanjing Regional J Spy (KM,最大权匹配)

题意:A队有n个队,每个队赏金是p[i],能力值是a[i]B队有2n个人现在要组成n个小队,每一个队从b[](长度为n)中取一个人,c[](长度为n)中取一个人,组成小队,组成的队伍的能力值是两个能力值之和。现在B队中的每个小队,随机遇到A队中的一个小队进行比拼,如果B小队的能力值大于A小队,就获胜并获得赏金,两个小队比拼之后就都out,不能再进行比拼。问你期望得到的赏金n是多少?解...

2019-12-01 21:02:34

q = x*w + b 后向传递梯度求导(求dx,dw,db)

x:N∗Dx: N*Dx:N∗Dw:D∗Mw: D*Mw:D∗Mb:Mb: Mb:M后向传递得到:αfαq=dout\frac{\alpha f}{\alpha q} = doutαqαf​=doutdout:N∗Mdout:N*Mdout:N∗M求解dxdxdxαqi,kαxi,j=wj,kαfαqi,j∗αqi,kαxi,j=douti,k∗wj,k∵q and&nbsp...

2019-10-30 15:32:17

Codeforces Round #426 (Div. 1) B. The Bakery(区间内不同数个数+dp)

题目链接:http://codeforces.com/problemset/problem/833/B题意:给你一个长度为n的数组a,让你把它分成连续的k段(数组里数的顺序不能改变)使得权值之和最大。每一段的权值就是该段内不同数的个数解析:拼多多笔试的时候做到,所以赛后找了道一样的题目补一下。一开始看到这题,以为是用斜率dp来做,后来写出公式之后发现不能很好地用斜率表示。这里的dp...

2019-10-24 15:18:33

ICPC China Nanchang National Invitational A. PERFECT NUMBER PROBLEM(筛法打表)

题目链接题意:让你输出前5个完美数完美数:一个数,除了他本身外,它的因子和=他本身,那么这个数是完美数解析:比赛的时候,第5个数一直打不出来,.,然后就网上搜了一下...看了大佬的打表方法,记录一下#include <cstdio>#include <cstdlib>#include <cmath>#include &l...

2019-04-21 15:55:50

HDU 6521 Party(思维+STL/吉司机线段树)

题目链接题意:有n个人,m场派对,n个人一开始互相不认识。每一场派对,你需要输出有多少对人,是第一次互相见面解析:这道题大佬的思路维护a[i],表示[1..i]之内i最远认识到谁,即[a[i]...i)的人,i都已经认识了。那么对于询问[l,r],我们需要更新i∈[l,r] a[i]=min(a[i],l)同时计算贡献是ans+=a[i]-l算这个有两种做...

2019-04-21 15:49:17

2017-2018 ACM-ICPC German Contest (GCPC 2017) E Perpetuum Mobile (level 3)(spfa判环+log转换小数乘法)

题目链接题意:题面70%的都是废话,还有很多影响读题的条件...其实就是给你一个有向图,问你这个有向图里面存不存在环,使得组成环的边的权值的总乘积>1有输出"inadmissiable",否则输出"admissiable"解析:这道题其实就是一道spfa判负权环的题目,找最长路。但是这里的小数很难处理,因为有4位小数,并且还有5000条边,乘积的话数据的数值和精度...

2019-04-21 15:08:31

Codeforces Round #551 (Div. 2) C. Serval and Parenthesis Sequence(括号匹配)(level 1)

题目链接题意:给你一个包含'(',')','?'的字符串。然后定义严格前缀,s[1...x] 1<=x<|s|让你用 '(' 或 ')' 替换 '?',使得s串的严格前缀都不是正确的圆括号,但是s是正确的圆括号圆括号的定义就是串中所有'('都能正确匹配一个')' '()()' '(())'解析:括号匹配的题目是真的做不来...想了一天...然后想出思路...

2019-04-15 21:11:09

ZOJ 4097 Rescue the Princess(tarjan判桥+LCA)(level 3)

题目链接题意:给你一个无向图,n个点,m条边,图中可能存在重边,自环然后有q个询问(n<=1e5,m<=2e5,q<=1e5)每一次询问u,v,w,问你能不能找到两条路径v->u,w->u使得两条路径中没有公共的边有->Yes,无->No解析:其实这道题tarjan判桥的特征挺明显的——无向图,重边,自环然后你画一下样例...

2019-04-15 13:45:03

2018-2019 ACM-ICPC Southeastern European Regional (SEERC 2018) G - Matrix Queries (level 3)(线段树)

题目链接题意:给你一个(2^n)*(2^n)的矩阵,矩阵元素只有0,1两种颜色。定义一个元素的价值是1.如果一个矩阵都是一种颜色,那么他的价值为12.如果一个矩阵不纯色,那么他的价值是把他分成4个(2^(k-1))*(2^(k-1))(假设原来的大小是(2^k)*(2^k))的矩阵的价值之和+1然后有q个操作,一开始矩阵都是0颜色,每一次操作,你需要把t=0,把第x...

2019-04-12 19:22:10

P2495 [SDOI2011]消耗战 (level 3)(虚树)

题目链接题意:给你一棵n个点的树,树上的边有权值>0然后给你m个询问,每一次询问给你k个点(不包含1(根节点))让你在树上删除几条边,使得从1出发,无法到达这k个点,并使得删掉的边的权值尽可能小,输出权值Σki<=500000解析:这道题我是先看了虚树,然后再做这道题。用虚树做的题目有一个很明显的特征就是询问的点的总和(也就是上面的Σki<=500...

2019-04-09 16:47:28

2018-2019 ACM-ICPC Southeastern European Regional (SEERC 2018) C Tree(level 2)(树的直径)(4种解法)

题目链接题意:给你一棵n个点的树(n<=100),每一个点有白/黑色,让你选m个黑色的点,使得你选的这m个点的集合里最远的两个点的距离最小解析:这道题我训练的时候是用st的LCA求两点距离+二分+最大团验证来做的,代码有167行比赛的时候...估计得写将近1个小时,然后还被自己LCA模板上的一个数组大小卡了半个小时...这道题赛后看了大佬们的代码,大多都是和树的直...

2019-04-08 13:38:31

树的直径

求法:1.先任意选一个点,找到离这个点距离最远的点q2.然后以q为根,找距离q最远的点p,那么pq就是这棵树的直径了证明:假定st是直径,我们需要证明的其实就是一个性质树上任意一个点x,距离x最远的点=直径的一个端点?那么我们假定的条件就是距离x最远的点y!=直径的一个端点,同时还要保证st是直径的性质,看这样的条件下,能否成立情况1: x在直径上sx=...

2019-04-08 11:38:19

牛客练习赛43 B Tachibana Kanade Loves Probability(输出分数的第k1~k2位小数)(快速幂)(level 1)

题目链接题意:如上题,给你一个分数m/n,让你输出该分数的第k1~k2位小数解析:除法得到分数的过程是m=m%n第一位小数: m=m*10 m/n-> m=m%n第二位小数: m=m*10 m/n-> ...

2019-04-06 16:00:18

Comet OJ - Contest #0 A 解方程(积性函数)(level 2)

题目链接题意:你只需要给出解的数量和所有解的 xyz 之和对 (109+7) 取模的值即可若方程有无穷多组自然数解,则在这一行输出 “infty”(不含引号),否则在这一行输出两个整数,其中第一个整数表示方程的解数,第二个整数表示所有解的 xyz之和对 (109+7)取模的值,这两个整数之间用恰好一个空格隔开,行末不要有多余的空格。解析:是有理数的时候,只需要输出infty...

2019-04-06 14:02:16

Comet OJ - Contest #0 D 项链与计数(level 4)(树上并环)(Kruskal+按秩合并并查集)

题目链接题意:定义简单环:一个点数和边数相等的回路,并且这条回路上没有出现重复的点或边。定义项链:定义 “项链” 是由一些简单环组成的子图,不妨设项链包括 k个简单环 C1C1​, C2​, ……, Ck​ (x`),那么项链需要满足:当且仅当 ∣i−j∣≤1 时,简单环 Ci和 Cj 共用顶点; 简单环 Ci 和 Ci+1 恰好共用一个顶点; 任意两个不同的简单环 ...

2019-04-06 10:50:52

Comet OJ - Contest #0 B 旅途(level 3)(概率dp)

题目链接题意:有一个n个点的环,编号为1...n第一天你在节点1,每一天你会在这个点游玩然后下一天,你有3种选择1.p%的概率顺时针走一步,到下一个城市游玩2.q%的概率逆时针走一步,到上一个城市游玩3.(100-p-q)%的概率待在原地再玩一天设f[i]=在第m天后,你游玩了i个城市的概率请你计算对1e9+7取模的结果解析:这道题看到的时候,就感觉用概...

2019-04-02 19:40:30

ICPC Nanning L. Twice Equation (打表找规律)(level 1)

题目链接题意:2*m(m+1) = n*(n+1)然后给你一个L,让你输出一个最小的n>=L,(所有数都是整数)解析:这道题虽然只有level 1,比赛的时候也很多人做出来,但是这种题我是完全做不出来....m:0tot:0n:0.0m:2tot:12n:3.0m:14tot:420n:20.0m:84tot:14...

2019-03-30 17:10:31

ICPC Nanning J. Rearrangement (level 1)(思维)

题目链接题意:有一个2*n的矩阵,里面有数字,让你重新安排数字,使得相邻两个数字之和不能被3整除可以的话输出YES,否则输出NO解析:这道题很简单,就是把0都交替排列 0 0 ...0 0 0 ...这样然后1从左边开始排到右边,2从右边开始排到左边我们总可以调整中间0的位置来使得1,2不相邻...

2019-03-29 09:43:50

查看更多

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