4 半世blue

尚未进行身份认证

暂无相关描述

等级
博文 58
排名 11w+

cf 1102F Elongated Matrix

传送门:https://codeforces.com/contest/1102/problem/FYouaregivenamatrixa,consistingofnrowsandmcolumns.Eachcellcontainsanintegerinit.Youcanchangetheorderofrowsarbitrarily(inclu...

2019-01-11 22:12:40

570D Tree Requests (dsu_on_tree)

传送门:https://codeforces.com/contest/570/problem/D题目大意:给一棵树,每个节点有一个字母,问节点v的深度为h的儿子节点的所有字母能否组成一个回文串(深度是对于整棵树)很裸的一个树上合并,也可以使用二分来做//919ms#include<bits/stdc++.h>usingnamespacestd;constint...

2018-09-05 19:24:21

群论

将置换写成循环循环置换的分解循环置换的阶循环置换分解为对换置换的奇偶性http://www.doc88.com/p-905280660599.html

2018-08-29 21:03:02

dsu_on_tree

大佬博客:https://codeforces.com/blog/entry/44351使用范围:常用来求子树的信息,比如,如果一棵树上每个节点都有一种颜色,求一个子树中颜色c的出现次数复杂度分析:这个就是启发式合并,每一次合并都将小的集合合并到大的集合,每个元素的合并次数最多为lognlognlogn次,看起来像是n2n2n^2的合并,实际复杂度只有nlognnlognnlogn,如果使...

2018-08-29 20:57:50

hdu多校第五场 G题

题意是给定一个随机数生成器,得到l,r,val表示将区间[l,r]内比val小的元素修改为val解法有两种第一种是线段树解法,我们就用线段树维护一个区间最小值,当val比区间的minn还小那么就不更新,否则向下暴力更新。因为数据是随机生成的,所以暴力更新并不会被卡。开始的想法是将所有操作按val从大到小排序,那么我们每个点就只会被更新一次,但是由于操作次数太多,排序时间大于计算答案的...

2018-08-07 17:06:43

牛客多校第四场 J题 Hash Function(线段树建图优化+拓扑排序)

传送门:https://www.nowcoder.com/acm/contest/142/J题目大意就是给你一个散列表,还原出字典序最小的原序列解法:通过推样例发现,一个数x如果不在x%n的位置,那么从x%n到当前数字位置i-1的区间内都已经被占满,那么考虑从x%n到i-1所有的点到i建一条边,然后跑一次拓扑排序(这里渐变相当于是限制第i个数字一定比x%n到i-1的数字后出现...

2018-07-29 20:55:44

HYSBZ - 3884 上帝与集合的正确用法

#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e7+5;typedeflonglongLL;intp[maxn],phi[maxn];boolprime[maxn];LLeular(LLx){LLret=1;for(inti=2;i*i<=x;i++){...

2018-07-29 14:27:53

杭电多校第一场补题记录

很菜,只能靠补题了,打的时候直接被1004的tle卡爆1001.MaximumMultiple打了个一百以内数的因子表,队友看出了规律n|3的时候就是(n.3)^3n|2&&n|4的时候就是(n/2)*(n/4)^21003.TrianglePartition排个序就出来了1011.TimeZone把当前时间转化成UTC+0...

2018-07-24 10:55:58

Codeforces Round #492 (Div. 2)

http://codeforces.com/contest/996A.HittheLottery解法:贪心一下就好了#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);intn;cin>>n;i...

2018-07-08 21:47:58

Educational Codeforces Round 46 (Rated for Div. 2)

A.CodehorsesT-shirts题意:找出两份名单中不同衣服大小的个总件数解法:map模拟一下就行#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;map<string,int>mp,mp2;intmain(){intn;cin>...

2018-07-08 21:18:49

Codeforces Round #493 (Div. 2)

A.Balloons题意:两个人分气球,每个人至少有一个且两个人分到的气球个数不相等。解法:求出sum,找到一个数x,且2*x!=sum,则把这个气球分给一个人,其他的给另一个人#include<bits/stdc++.h>usingnamespacestd;#definemaxn100005inta[maxn];intmain(){...

2018-07-07 20:06:18

Codeforces Round #494 (Div. 3)

传送门:http://codeforces.com/contest/998A.Polycarp’sPockets直接找出数字出现次数最多的次数#include<bits/stdc++.h>usingnamespacestd;inta[106];intmain(){ios::sync_with_stdio(false);intn,...

2018-07-07 19:32:47

线性规划与网络流24题

传送门:https://www.oj.swust.edu.cn/problem/show/1739Description假设有n根柱子,现要按下述规则在这n根柱子中依次放入编号为1,2,3,…的球。(1)每次只能在某根柱子的最上面放球。(2)在同一根柱子中,任何2个相邻球的编号之和为完全平方数。试设计一个算法,计算出在n根柱子上最多能放多少个球。例如,在4根柱子上最多可...

2018-06-20 18:13:36

hiho 1393 : 网络流三·二分图多重匹配

传送门:http://hihocoder.com/problemset/problem/1393描述学校的秋季运动会即将开始,为了决定参赛人员,各个班又开始忙碌起来。小Hi和小Ho作为班上的班干部,统计分配比赛选手的重任也自然交到了他们手上。已知小Hi和小Ho所在的班级一共有N名学生(包含小Hi和小Ho),编号依次为1..N。运动会一共有M项不同的比赛,编号为1..M。第i...

2018-06-10 21:32:46

51nod 1089 最长回文子串 V2(Manacher算法)

传送门:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1089回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str,输出Str里最长回文子串的长度。Input输入Str(Str的长度<=100000)Output输出最长回文子串的长度L...

2018-05-27 17:22:16

hdu 2639 Bone Collector II【01背包第k优解】

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2639ProblemDescriptionThetitleofthisproblemisfamiliar,isn’tit?yeah,ifyouhadtookpartinthe“RookieCup”competition,youmusthaveseemt...

2018-05-13 15:29:13

hdu3033 I love sneakers!【分组背包】

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3033ProblemDescriptionAftermonthsofhardworking,Iserlohnfinallywinsawesomeamountofscholarship.Asagreatzealotofsneakers,hedecides...

2018-05-13 11:33:06

poj1170 Shopping Offers【状压+背包】

传送门:http://poj.org/problem?id=1170DescriptionInashopeachkindofproducthasaprice.Forexample,thepriceofafloweris2ICU(InformaticsCurrencyUnits)andthepriceofavaseis5ICU....

2018-05-10 19:09:02

poj2728 Desert King【最优比率生成树】

传送门:http://poj.org/problem?id=2728DescriptionDavidtheGreathasjustbecomethekingofadesertcountry.Towintherespectofhispeople,hedecidedtobuildchannelsalloverhiscountryto...

2018-04-12 19:54:56

bzoj2588 Spoj 10628. Count on a tree【主席树+lca】

传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=2588给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答uxorlastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。Input第一行两个整数N,M。第二行有N个整数,其中第i个...

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