搜索
题目大意:给你一棵树,每次选取其中的两个叶子结点,往答案中加上它们的距离,并删去其中一个结点。你可以自由进行上述操作,使得最后答案最大。问答案最大是多少,并输出其中一种方案。思路:贪心。首先找出树的直
2022-04-21
题目大意:给你一个长度为n的数列a,按顺序进行以下m次操作,每次将区间[l,r]中的所有x变成y,问最后数列是怎样的。思路:线段树。每个线段树结点上维护当前区间每个数分别会变成多少。时间复杂度O(ml
2022-04-21
题目大意:有n个国家要派代表开会,每个国家有两个代表可供选择。有m对代表有仇,不能同时开会。若每个国家只能派一个代表开会,问是否存在一种方案,使得每个国家都能正常参会?如果有,输出字典序最小的一种。思
2022-04-21
题目大意:有n个人,m种物品,第i种物品有a[i]个。现在给这些人发物品,要求每个人至少发到一件物品。问有多少种不同的发法。思路:首先不考虑“每个人至少发到一件物品”的限制,那么答案应该是$\prod
2022-04-21
题目大意:给你一个长度为n的数列,给你m个数k。对于每个k,你可以进行若干次操作,每次把一个超过k的数的多余部分移到旁边一个数。问对于每个k,进行若干次操作以后,最长的满足每个数都不小于k的区间长度。
2022-04-21
题目大意:给你一个长度为n的序列a,你可以将其分为若干段,最终的答案为每一段不同数个数的平方和。思路:不难想到一个O(n^2)的DP:f[i]min{f[j]+cnt(j,i)^2}考虑一些优化。首先
2022-04-21
题目大意:有n(n<50000)场赛车游戏,每场游戏有不同的赛车,总共有ABC三种不同的场地。赛车对使用场地有要求,a型赛车不能在A上开,b型赛车不能在B上开,c型赛车不能在C上开,x型赛车可以
2022-04-21
题目大意:给你一个长度为n的数列f,f中共有m种不同的数,每种数都有一个权值w[i]。你可以选定一个f中的区间,定义区间的权值为这一区间只出现一次的数的权值和。问权值最大的区间的权值是多少?思路:对于
2022-04-21
题号:洛谷33791%:pragmaGCCoptimize(Ofast)2include<cstdio>3include<vector>4include<cctype&g
2022-04-21
题目大意:给你一棵n个结点的带边权的树,问长度恰好为k的路径至少经过多少条边?思路:重心剖分。对于每次剖分出来的子树,存一下从根出发的长度为i的路径至少经过几条边f[i]。注意要保证经过根结点,所以一
2022-04-21
题目大意:给定一颗n个节点树,边权为1,树上有m个点被标记,问从树上一个点出发,经过所有被标记的点的最短路程,以及可行的最小的端点编号。(起终点自选)M<N<123456思路:随便定一个标
2022-04-21
题目大意:有n个人围成一圈,m张牌,每张牌有一个数a[i]。总共进行n1轮游戏。每一轮庄家从牌堆中抽出一张牌,从自己开始顺时针数a[i]个人,把这个人淘汰掉,然后将牌放回去。下一轮的庄家为淘汰掉的人的
2022-04-21
区间检测(range)TimeLimit:1SMemoryLimit:128MDescription给定一个长度为n的序列,进行m次检测,每次检测某个区间中,是否有重复的数。Input第一行,两个整数
2022-04-21
题目大意:有n次操作,每次覆盖数轴上的区间[l,r]。现在要你挑出m次操作,使得数轴上有一个整点恰好被覆盖m次,且最大覆盖区间与最小覆盖区间大小之差最小。思路:首先把询问按长度排序,然后用尺取法O(n
2022-04-21
OJ题号:POJ2342、洛谷1352思路:树形动规(递归实现),每次返回一个pair,分别记录包括本人的最大值和不包括本人的最大值,每次如果遇到convivialityrating为负的就忽略。1i
2022-04-21
题目大意:定义magic(x)为将x按十进制顺序写下来,依次对相邻两个数写下差的绝对值,并去除前导0得到的新数。若对得到的magic(x)重复进行多次magic,最后会变成一个一位数。若最后变成的数是
2022-04-21
OJ题号:洛谷1083思路:ZKW线段树1include<cstdio>2include<cctype>3include<algorithm>4inlineintg
2022-04-21
题目大意:有一棵n节点的树,根为1号节点。每个节点有两个权值ki,ti,初始值均为0。给出三种操作:1Add(x,d)操作:将x到根的路径上所有点的ki←ki+d2Mul(x,d)操作:将x到根的路径
2022-04-21
题目大意:给出一个$n(n\leq10^5)$个结点的带边权的树,$q(q\leq10^5)$个询问,每次询问用$y$条路径覆盖整棵树且覆盖$x$至少一次,最多能覆盖的道路长度是多少?强制在线。思路:
2022-04-21
OJ题号:洛谷1005思路:动态规划。不难发现每行能够取得的最大值仅与当前行的数据有关,因此本题可以对每行的数据分别DP,最后求和。设$f_{i,j}$表示左边取$i$个、右边取$j$个的最大值,则D
2022-04-20