• 2016 CCPC Changchun Onsite

    2016 CCPC Changchun Onsite

    hdu5912.Fraction计算连分数的答案,直接模拟即可[crayon-5994bb837dcd6608125431/]hdu5914.Triangle问长度1到n的线段,至少要去掉多少,使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列,手算完打表[crayon-5994bb837dcea067506270/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd,求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现,第k大的全排列的权值为n-2+k构造方式...

  • 【cf538X】Codeforces Round #300

    【cf538X】Codeforces Round #300

    A.CuttingBanner枚举切掉中间部分匹配[crayon-5994bb837f435538544144/]B.QuasiBinary用最少的只包含01的数凑出n每次贪心在非0位上取1[crayon-5994bb837f441999075557/]C.Tourist'sNotes根据每俩个的时间及高度差可计算答案[crayon-5994bb837f446323260247/]D.WeirdChess暴力暴力暴力[crayon-5994bb837f44b770388457/]E.DemiurgesPlayAgain考虑进入某个根,最终会取得子树第几小的叶子[crayon-5994bb837f451120513...

    02015年4月27日1,817模拟,贪心,主席树,调和级数
  • 【bzoj3932】[CQOI2015]任务查询系统

    【bzoj3932】[CQOI2015]任务查询系统

    好好的一道主席树题我写成了树状数组套主席树TT原因是为了练习模板(一开始根本没想。。。)TTbzoj16s通过,倒数第二是9s。。。多个log萌萌哒[crayon-5994bb837fb57254981848/]  ...

    72015年4月8日3,772主席树,树状数组
  • 【bzoj3772】精神污染

    【bzoj3772】精神污染

    Description兵库县位于日本列岛的中央位置,北临日本海,南面濑户内海直通太平洋,中央部位是森林和山地,与拥有关西机场的大阪府比邻而居,是关西地区面积最大的县,是集经济和文化于一体的一大地区,是日本西部门户,海陆空交通设施发达。濑户内海沿岸气候温暖,多晴天,有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市,还有以疗养地而闻名的六甲山地等。兵库县官方也大力发展旅游,为了方便...

    02015年1月27日2,702dfs序,主席树
  • 【bzoj3514】Codechef MARCH14 GERALD07加强版

    【bzoj3514】Codechef MARCH14 GERALD07加强版

    DescriptionN个点M条边的无向图,询问保留图中编号在[l,r]的边的时候图中的联通块个数。Input第一行四个整数N、M、K、type,代表点数、边数、询问数以及询问是否加密。接下来M行,代表图中的每条边。接下来K行,每行两个整数L、R代表一组询问。对于type=0的测试点,读入的L和R即为询问的L、R;对于type=1的测试点,每组询问的L、R应为Lxorlastans和Rxorlastans。Output K行每行一个整数代表该组询问的联通块...

    32014年9月11日3,478主席树,link cut tree
  • 【bzoj3551】[ONTAK2010]Peaks加强版

    【bzoj3551】[ONTAK2010]Peaks加强版

    Description【题目描述】同3545Input第一行三个数N,M,Q。第二行N个数,第i个数为h_i接下来M行,每行3个数abc,表示从a到b有一条困难值为c的双向路径。接下来Q行,每行三个数vxk,表示一组询问。v=vxorlastans,x=xxorlastans,k=kxorlastans。如果lastans=-1则不变。Output同3545HINT【数据范围】同3545题解本题强制在线。。。据出题人的做法。。。就是做最小生成树,但合并两结点x,y的时新建结点ext,把ext连向fa...

    22014年8月30日3,073kruskal,主席树
  • 【bzoj2588】Spoj 10628. Count on a tree

    【bzoj2588】Spoj 10628. Count on a tree

    Description给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答uxorlastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。Input第一行两个整数N,M。第二行有N个整数,其中第i个整数表示点i的权值。后面N-1行每行两个整数(x,y),表示点x到点y有一条边。最后M行每行两个整数(u,v,k),表示一组询问。OutputM行,表示每个询问的答案。SampleInput8...

    62014年6月17日3,564主席树
  • 【poj2104】K-th Number

    【poj2104】K-th Number

    DescriptionYouareworkingforMacrohardcompanyindatastructuresdepartment.Afterfailingyourprevioustaskaboutkeyinsertionyouwereaskedtowriteanewdatastructurethatwouldbeabletoreturnquicklyk-thorderstatisticsinthearraysegment.Thatis,givenanarraya[1...n]ofdifferentintegernumbers,yourprogrammustansweraseriesofquestionsQ(i,j,k)intheform:"Whatwouldbethek-thnumberina[i...j]segment,ifthissegmentwassorted...

    02014年5月14日4,126treap,树套树,主席树,线段树
  • 【bzoj1901】Zju2112 Dynamic Rankings

    【bzoj1901】Zju2112 Dynamic Rankings

    Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。第一行有两个正整数n(1≤n≤...

    02014年4月28日4,323主席树,树状数组
  • 【bzoj3524/2223】[Poi2014]Couriers

    【bzoj3524/2223】[Poi2014]Couriers

    Description给一个长度为n的序列a。1≤a[i]≤n。m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。Input第一行两个数n,m。第二行n个数,a[i]。接下来m行,每行两个数l,r,表示询问[l,r]这个区间。Outputm行,每行对应一个答案。SampleInput7511323431314371766SampleOutput10304HINT【数据范围】n,m≤500000SourceByDzy题解coolinging:可持久化...

    32014年4月19日3,701主席树