4 Toooooocold

尚未进行身份认证

暂无相关描述

等级
博文 114
排名 5w+

【DP】Gym100524E Ebola Virus

Souce:2014-2015SummerPetrozavodskCamp,AndrewStankevichContest46(ASC46)Problem:n个村庄,如果第i个村庄没有被治疗,每天会死掉a[i]个人。现在起始在第一个村庄,每次选择花费一天的时间往前走/往后走/治疗当前村庄,使得总共死去的人数最少。但行动有个限制,如果你的前进方向上有一个曾经被路过但没有被治...

2018-12-07 18:43:30

【树形DP】Gym101667A Broadcast Stations

Souce:2017-2018ACM-ICPC,AsiaDaejeonRegionalContestProblem:一棵5e3的树,可以选择一些点放上基站,如果u上的基站价值为d,那么距离u小于等于d的点都会被覆盖,问使得整棵树被覆盖的最小价值。Idea:g[u][j]g[u][j]g[u][j]表示u点这颗子树里距离u点大于j的点都被覆盖的最小价值。显然g[u][j]=∑g[...

2018-12-04 21:25:15

【斯坦纳树】18牛客多校1G Steiner Tree

Source:牛客网暑期ACM多校训练营(第一场)Problem:求斯坦纳树的个数Idea:斯坦纳树的dp分成两个部分,其中第一部分dp[S][u]→dp[S][v]dp[S][u]\todp[S][v]dp[S][u]→dp[S][v]通过最短路更新,不会算重复,定义这一部分得到的斯坦纳树为fff,最后一步为根的延伸。第二部分dp[S0][u]+dp[S0⊕S][v]→dp[S][v]d...

2018-12-04 18:01:44

【LCT】HDU5398 GCD Tree

Souce:Souce:Souce:2015Multi-UniversityTrainingContest9Problem:Problem:Problem:1e5个查询,每次给一个n,表示一张n个节点的完全图,点的标号从1到n,任意两点之间的边权为标号的gcd,求最大生成树。Idea:Idea:Idea:如果只有单次查询,直接按gcd大小从后往前做就好了。那么现在只能从前往后动...

2018-12-01 17:55:43

【并查集】Gym101840E Evaluations

Souce:Souce:Souce:EgyptianCollegiateProgrammingContest2017(ACMECPC2017)Problem:Problem:Problem:给一颗1e5的树。树上路径定义为两点之间所有连边的边权的乘积。1<=边权<=1e5。问有多少条路径刚好是两个不同质数的乘积。Idea:Idea:Idea:由于1很特殊,对所...

2018-11-28 01:04:35

【sam+二分】Gym101840B Breaking the Curse

Souce:Souce:Souce:EgyptianCollegiateProgrammingContest2017(ACMECPC2017)Problem:Problem:Problem:给定两个字符串s1和s2,q次查询,每次查询s1中的一段区间[L,R]中有多少个子串在s2中出现过。Idea:Idea:Idea:对s2建sam,用s1跑最长公共子串,得到每个位置i往左...

2018-11-28 00:50:29

【广义sam】Gym101194F Mr. Panda and Fantastic Beasts

Sourcce:Sourcce:Sourcce:2016-2017ACM-ICPCCHINA-FinalProblem:Problem:Problem:给n个串,找一个最短且字典序最小的子串只在第一个串中出现过。Idea:Idea:Idea:如果不需要字典序最小,可以二分答案+hash或者对后n-1个串建广义sam,跑失配,但是这样比较最小字典序就很麻烦(虽然暴力比能过)。考虑对n个串...

2018-11-23 02:22:27

【莫比乌斯反演】CodeForces 1043F Make It One

Souce:Souce:Souce:CodeforcesRound#519byBotanInvestmentsProblem:Problem:Problem:给n个数(n<=3e5),每个数<=3e5,选择最少的数,使得他们的gcd为1。输出这个最小子集的大小。Idea:Idea:Idea:可以二分,或者直接枚举,因为2 * 3 * 5 * 7 * 11 * 13 * ...

2018-10-29 15:50:11

【DP】Gym101933A Altruistic Amphibians

Source:Source:Source:2018-2019ACM-ICPCNordicCollegiateProgrammingContest(NCPC2018)Problem:Problem:Problem:坑里有一堆青蛙,青蛙有身高、跳跃高度、体重。青蛙可以叠罗汉,但是不可以撑起超过自己体重的重量。问有多少青蛙可以跳出去。体重总和<=1e8Idea:Idea:Idea...

2018-10-27 03:08:29

【LCA】Gym101669I Divide and Conquer

Source:Source:Source:2017-2018ACM-ICPCSoutheasternEuropeanRegionalProgrammingContest(SEERC2017)Problem:Problem:Problem:n=1e5,m=2n−1n=1e5,m=2n-1n=1e5,m=2n−1的图,其中n−1n-1n−1条边构成A树,另n−1n-1n−1条边...

2018-10-07 16:19:47

【原根+FFT】牛客国庆Day1 I Steins;Gate

Souce:Souce:Souce:牛客国庆集训派对Day1Problem:Problem:Problem:N=1e5,a1,a2,...,aNN=1e5,a1,a2,...,aNN=1e5,a1,a2,...,aN,对于每一个akakak,求有多少个有序二元组(i,j)(i,j)(i,j)满足a[i]∗a[j]=a[k](modP)a[i]*a[j]=a[k](modP)a[i...

2018-10-06 15:56:26

【差分+DP】Gym101620K Kitchen Knobs

Souce:Souce:Souce:2017-2018ACM-ICPC,CentralEuropeRegionalContest(CERC17)Problem:Problem:Problem:n=500n=500n=500个长度为7的整数。需要把每个整数都变成最大循环表示,每次操作可以使连续的一段整数循环移动k位(往左/往右),求最少操作。Idea:Idea:Idea:除去每...

2018-10-04 23:03:13

【线段树】Gym101620I Intrinsic Interval

Source:Source:Source:2017-2018ACM-ICPC,CentralEuropeRegionalContest(CERC17)Problem:Problem:Problem:n=1e5n=1e5n=1e5的全排列。定义一个区间是好区间当区间内的值域是连续的,即mx−mn=R−Lmx-mn=R-Lmx−mn=R−L。mmm个查询[li,ri][l_i,r_i...

2018-10-04 21:05:33

【带权中位数】CodeForces 1053C Putting Boxes Together

Source:Source:Source:CodeforcesRound#512(Div.1,basedonTechnocup2019EliminationRound1)Probelm:Probelm:Probelm:n=2e5个物品从左到右排列,第i个物品的位置pos[i],重量w[i]。每次询问如果将pos[l]…pos[r]这段物品移到某个连续区间[x,x+(r-l...

2018-10-02 15:27:07

【四维偏序】18牛客多校9G Longest Common Subsequence

source:source:source:牛客网暑期ACM多校训练营(第九场)problem:problem:problem:n=1e4n=1e4n=1e4,求四个序列的最长公共子序列。前三个序列每个数不会出现超过两次。Idea:Idea:Idea:每个数在不同序列中的下标构成的元素(pa,pb,pc,pd)(pa,pb,pc,pd)(pa,pb,pc,pd)的四维偏序问题,总共只有8n8n8...

2018-09-18 20:06:46

【杜教筛/min25筛】计蒜客 Easy Math

Source:Source:Source:ACM-ICPC2018徐州赛区网络预赛Idea:Idea:Idea:f(n,m)=∑i=1mμ(i∗n)=μ(n)∗∑i=1mμ(i)[gcd(i,n)=1]f(n,m)=∑i=1mμ(i∗n)=μ(n)∗∑i=1mμ(i)[gcd(i,n)=1]f(n,m)=\sum_{i=1}^{m}\mu(i*n)=\mu(n)*\sum_{i=1}^...

2018-09-11 02:20:32

【线性基】计蒜客 The Great Nim Game

Souce:Souce:Souce:ACM-ICPC2018南京赛区网络预赛Problem:Problem:Problem:n=1e10000000堆石头;f(i)=(af(i−1)4+bf(i−1)3+cf(i−1)2+df(i−1)1+e−1)%k+1,(k≤212),表示每堆石头的大小。求多少个石头子集可以使得nim游戏的先手必胜。n=1e10000000堆石头;f(i)=(af(...

2018-09-01 22:34:48

【基环树】HDU5329 Question for the Leader

Souce:Souce:Souce:2015Multi-UniversityTrainingContest4Problem:Problem:Problem:一棵n=1e5n=1e5n=1e5的基环树,对于k=1...nk=1...nk=1...n,问是否能将基环树切割成k份大小相同的连通块。Idea:Idea:Idea:如果只是一棵树切成k份,当且仅当kkk个点sz[u]≡0mod...

2018-08-07 21:55:21

【分治+线段树】HDU6328 Rectangle Radar Scanner

Souce:Souce:Souce:2018Multi-UniversityTrainingContest3Problem:Problem:Problem:二维平面上给出n=1e5个有权值w=1e9的点,且x坐标刚好从1到n各不相同,1<=y<=n。现在m=1e6的询问,每个询问给出一个矩形,问矩形内所有点的权值积、最大值、最小值。Idea:Idea:Idea:查询离线...

2018-08-03 17:10:40

【cdq分治+DP】HDU5324 Boring Class

Source:Source:Source:2015Multi-UniversityTrainingContest3Problem:Problem:Problem:给两个长度为n=5e4的序列,A和B,要求在A序列中找一个非递增的子序列,同时这个子序列的下标在B串中非递增。要求这个子序列最长,输出字典序最小的方案。Idea:Idea:Idea:经典的三维偏序,CDQ分治。由于要求字典...

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