- 博客(282)
- 收藏
- 关注
RSS订阅原创 Regular Forestation（树的重心 + 树哈希）
题目描述A forestation is an act of planting a bunch of trees to grow a forest, usually to replace a forest that had been cut down. Strangely enough, graph theorists have another idea on how to make a forest, i.e. by cutting down a tree!A tree is a graph of N
2020-09-01 18:55:36
306
原创 小路绫只会做料理 (ayaya)（树状数组 二分）
题目描述小路绫 (Komichi Aya) 想要给阳子 (Inokuma Youko) 做便当。小路绫现在有n种食材，编号从1到n，她会按编号顺序放入这n种食材。对于每种食材阳子有一个美味度ai。小路绫知道，对于所有1≤i≤n，设前i种食材的美味度总和。当加入第i种食材时，如果si>m，阳子就会吃撑。所以小路绫每放入一种食材时，都会想知道：最少要从之前已经选过的食材中去掉多少食材，才不会让阳子吃撑。当然，小路绫不会真正地把食材去掉，她只是想知道结果而已。才不是关心你呢！输入第一行为两
2020-08-13 23:53:38
386
原创 跳方格 (lattice) （差分+二分）
题目描述有一个长长的走廊，巨神 ctt 把它分成m方格，从左到右编号为1,2,…,m。有一天，巨神 ctt 得到了n个蹦床，他把这些蹦床放在方格里，他在编号为1的方格里放了一个蹦床，在编号为2,3,…,m-1的方格中放置了n-1个蹦床（一个方格只能放一个蹦床）。巨神 ctt 估算了自己的跳远水平和蹦床的弹性，知道了他从第i个蹦床跳跃最多可以跳过li个方格（若这个蹦床放置的方格编号为k，则他最多能跳到编号为k+li的方格里，l1表示从编号为1的方格里的蹦床跳跃最可以跳过l1个方格），他开始计算从编号为1
2020-08-13 23:25:20
571
原创 Expectation（生成树计数）
题目描述You are given an undirected graph consisting of n vertices with m weighted edges. We define the weight of a spanning tree as the bitwise AND of all edges’ weight in spanning tree.Now select a spanning tree randomly, you should calculate the expected
2020-08-06 22:32:17
222
原创 小Y的图（kruskal重构树）
题目描述小Y有一个n个点的无向图，图中的每个点从1到n标号。图中还有m条边，每条边有一个长度。小Y有Q个询问，每次询问两个点所有路径中，最长的边最小值是多少，若这两个点之间没有任何路径，输出 -1。输入第一行三个整数n、m和Q。接下来m行每行三个整数x、y、z（1≤x,y≤n,1≤z≤1000000），表示有一条连接x和y长度为z的边。接下来Q行每行两个整数x、y(x≤y)，表示一组询问。输出Q行每行一个整数，表示一组询问的答案。样例输入5 5 41 2 31 3 23 2 11
2020-07-24 17:17:39
301
原创 高中题（线性代数）
题目描述一个数列{an}，满足an+2=x⋅an+1+y⋅an，求答案对998244353取模。输入第一行一个整数T，即数据组数。下面T行，每行5个整数，即n，a1，a2，x，y，含义如上。输出共T行，每行1个整数，即每组数据的答案。样例输入33 0 2 0 03 1 2 0 13 1 0 0 1样例输出8102提示对于100%的数据，1≤T≤104，1≤n≤1018，0≤a1，a2，x，y≤998244352。思路这题要求的对象是递推式的三次方和，因此可以通过矩阵快
2020-06-30 23:05:45
1165
原创 集合 (set)（数论）
题目描述你需要维护一个数的集合，一开始这个集合中包含1~n中的所有正整数，你需要支持以下三种操作：·0 x删除集合中所有 x 的倍数；·1 x对于所有正整数i，将 ix 加入集合；·2 k询问元素 k 是否在当前集合中。输入第一行两个正整数n,m，分别表示初始集合和操作次数。接下来m行，每行两个整数表示一个操作，格式同问题描述。输出对于每个询问，输出一行 yes 或 no 表示答案。样例输入10 62 50 52 100 21 32 6样例输出yesnoyes提示
2020-06-24 15:07:29
343
原创 Yet Another Bracket Sequence（线段树）
题目描述One day, Little Gyro was playing with a series of Bracket Sequences, A Bracket Sequence is a string that only contains two kinds of characters ‘(’ and ‘)’. Let us define a regular Bracket Sequence in the following way:Empty sequence is a regular sequ
2020-06-06 19:21:58
250
原创 卡牌对战游戏（线段树）
题目描述Alice和Bob都非常喜欢卡牌对战游戏，在一次对战游戏中，Alice召唤了 n个随从，其中第 i个随从的生命值ai，攻击力是b i，现在是Bob的轮次，他需要尽可能降低场攻，Bob有一张名叫“亵渎”的法术牌，在自己的回合开始时，Bob可以指定任意一名 Alice的随从，对它发动“亵渎”，该随从会直接死亡。此后，当有随从死亡时，Bob可以继续指定随从发动“亵渎”，但是必须保证指定的随从在上一次死亡随从的右边。当Bob在第i轮指定发动“亵渎”的随从，其生命值与上一轮死亡的随从的生命值差值的绝对值不超
2020-06-06 19:17:48
385
原创 和平精英（并查集 + 二分）
**题目描述 **在未来，和平成为世界主流。但出于战略意义上的考虑，以及训练成果考核的需要，各国约定：每隔一段时间，便进行一场世界范围内的联合军事演习。2120年的军事演习开始了，演习场地是一个矩形，左上角坐标为(0,0)，右下角坐标为 (x,y)。敌人起始位置在(0,0)，我方大本营在 (x,y)。我方有 n个雷达分布在矩形之中， n个雷达的侦测范围都是半径为 r的圆。敌人只能在矩形内活动，并且不能走进雷达的侦测范围。现在，你需要找到一个最小的r，使得敌军不能避开雷达来到我方大本营。输入描述
2020-06-06 19:11:43
481
原创 Alice的难题（欧拉筛 + 状压dp）
**题目描述 **众所周知，Alice是一个电视迷。但是期末考试逼近， Alice依然沉迷于看电视剧，于是 Bob给Alice出了一个题。如果 Alice不能解答这个题，就只能去复习准备考试了。问题如下：给定n个整数（3≤n≤100000）排成一行，每个数字表示 Alice看过的第 i 部电视剧的时长，现在规定每部电视剧的鸡汤值为电视时长的最小质因子。现在要求Alice任意选出三段连续且不相交的区间，且区间长度分别是 a,b,c（a,b,c都是正整数，且 a,b,c的和不超过 n。且0 <T<
2020-06-06 19:03:26
434
原创 倒水(water)（单调栈）
题目描述有一天，你拿来了一个长方形的容器，然后开始往里面倒水。这个长方形的容器由n个单元组成，每一个单元都有一个高度。现在你想知道，要想让水没过第i个位置，他至少需要倒进去多少单位的水。输入第一行一个整数n。接下来一行n个整数，第i个整数hi表示第i个位置的高度。输出为了减少输出量，假设要想让水没过第i个位置，需要倒进去ai单位的水，那么你需要输出，其中表示二进制异或。样例输入【样例1】53 5 1 2 0【样例2】53 2 3 2 3样例输出【样例1】13【样例2】
2020-05-31 21:37:45
249
原创 路径和（cdq分治）
题目描述对于一张有向图，定义d(u,v,w)为从u号点出发，不经过v号点，最终到达w号点的最短路径长度。如果不存在这样的路径，d(u,v,w)的值为−1。你也可以认为d(u,v,w)是删去v点和其相关的边后，图中u到w的最短路。现在给定这张有向图每两个点之间的有向边的长度（如果不存在连边则为−1），对于所有满足1≤x,y,z≤n,x≠y,y≠z的有序数对(x,y,z)，求它们d(x,y,z)的和。你可以借助样例一解释来理解上面这句话的意思。输入第一行输入一个正整数n，表示该地区的点数。接下来输
2020-05-31 21:34:20
527
原创 小星星（树上差分+堆）
题目描述小星星住在猪崽子城。猪崽子城可以看成是有N个路口，N−1条道路的无向图。为了迎接即将到来的体育中考，小星星的老师易语言给小星星制定了一系列的锻炼计划。具体地说，在接下来M天内，易语言要小星星在第i天，从路口Ai跑步到Bi。然而小星星并不是很喜欢锻炼身体，他已经快疯了！好在小星星和猪崽子市的市长那奶牛混得很熟，那奶牛可以把猪崽子城的一些道路进行改造。具体地说，对于一条长度为L的道路，那奶牛可以把它的长度改造成⌊K×Li⌋，其中K是给定的0到1之间的常数，⌊x⌋表示x向下取整后的值。一条道路可
2020-05-31 21:29:12
326
原创 战争 I（最短路+离线算法）
题目描述某年，白国和委国之间的战争爆发了！然而，在委国指挥官委兆的眼里，白国人不堪一击。现在他手上有一张白国的地图，发现白国有 n 个据点，m 条无向道路，他们有各自的长度。于是他决定按一定顺序破坏白国的一些据点，使得所有连接这些据点与其他据点的道路无法通行。同时，为了更有效率的攻城略地，也为了满足委兆的成就感，他有时还想知道当前某两个据点间的最短路径长。请编程满足他的要求。输入第一行两个正整数 n,m。接下来 m 行，每行有三个数 a,b,v表示一条连接 a,b的无向边。接下来一行一个正整数
2020-05-31 21:24:51
289
原创 2020 年 “游族杯” 全国高校程序设计网络挑战赛 Coronavirus Battle（cdq分治+离散化）
题意对每个三维点(x,y,z)，只有在这个单位时间存在一个点位于(x’,y’,z’) { x’<x && y’<y && z’<z}时，这个点才能在这个单位时间存活，求每个点的存活时间思路对z轴进行离散化，然后对整体进行cdq分治，求每个点之后有几个点代码实现#pragma GCC optimize(3,"Ofast","inline")#include<bits/stdc++.h>using namespace std;type
2020-05-24 18:11:22
245
原创 Nastya and Scoreboard（dp+贪心）
Denis, after buying flowers and sweets (you will learn about this story in the next task), went to a date with Nastya to ask her to become a couple. Now, they are sitting in the cafe and finally… Deni...
2020-04-26 17:16:14
343
原创 Weights Distributing（bfs 前缀和)
You are given an undirected unweighted graph consisting of n vertices and m edges (which represents the map of Bertown) and the array of prices p of length m. It is guaranteed that there is a path bet...
2020-04-22 22:21:53
285
原创 走格子（bfs+dji)
题目描述CYJ想找到他的小伙伴FPJ，.CYJ和FPJ现在位于一个房间里,这个房间的布置可以看成一个N行M列的矩阵,矩阵内的每一个元素会是下列情况中的一种:1.障碍区域—这里有一堵墙(用‘#’表示).2.这是CYJ最开始在的区域(用‘C’表示).3.这是FPJ在的区域(用‘F’表示).4.空区域(用‘.’表示).CYJ携带了一个所谓传送枪的东西,这是一把可以创造传送门的枪械,在每一次行...
2020-04-19 21:56:47
416
原创 队爷的讲学计划（tarjan +拓扑排序）
题目描述队爷为了造福社会，准备到各地去讲学。他的计划中有n个城市，从u到v可能有一条单向道路，通过这条道路所需费用为q。当队爷在u城市讲学完之后，u城市会派出一名使者与他同行，只要使者和他在一起，他到达某个城市就只需要花1的入城费且只需交一次，在路上的费用就可免去。。但是使者要回到u城市，所以使者只会陪他去能找到回u城市的路的城市。。队爷从1号城市开始讲学，若他在u号城市讲学完毕，使者会带他尽可...
2020-04-12 22:49:53
248
原创 次长上升子序列（LIS 树状数组）
题目描述最长上升子序列是一道经典的题目,liu_runda很想在模拟赛中考考这个题目,但是他又不想被选手骂出原题,于是就把原题魔改一下再出出来.对于一个数列a[1],a[2]…a[n], 我们定义子序列是一系列下标的集合: {x1,x2…xm}其中, 1<=x1<x2<x3…<xm<=n本题的上升子序列应满足a[x1]<=a[x2]<=a[x3]…...
2020-04-05 21:42:19
196
原创 人品问题（树形DP）
题目描述网上出现了一种高科技产品——人品测试器。只要你把你的真实姓名输入进去，系统将自动输出你的人品指数。把儿不相信自己的人品为0。经过了许多研究后，把儿得出了一个更为科学的人品计算方法。这种方法的理论依据是一个非常重要的结论：人品具有遗传性。因此，一个人的人品完全由他的祖先决定。把儿提出的人品计算方法相当简单，只需要将测试对象的k个祖先的人品指数（可能为负数）加起来即可。选择哪K个祖先可以由测...
2020-03-17 00:11:47
412
原创 Sugoroku（单调队列优化DP）
题目描述Takahashi is playing a board game called Sugoroku.On the board, there are N+1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.The g...
2020-03-16 23:41:35
245
原创 Moving Points（树状数组）
There are n points on a coordinate axis OX. The i-th point is located at the integer point xi and has a speed vi. It is guaranteed that no two points occupy the same coordinate. All n points move with...
2020-02-25 14:22:06
447
原创 学期计划（模拟）
题目描述你已经将你的学期计划报告存入了个人电脑。在你的计划中有若干个数学表达式。这些表达式中没有多余括号（删去一对匹配的括号而使表达式值不变，这样的一对括号就叫多余括号）。当你外出时，你的弟弟在报告的一些表达式中加入了一些匹配的多余括号。假设新的表达式语法正确而且它的值与原式的值相等。为了将报告复原，你须要写一个程序来去除多余括号。为了简化问题，我们假设有以下规则：输入文件含有多个表达式，...
2020-02-10 20:39:14
361
原创 方格取数（dp）
题目描述设有N*N的方格图(N<=8)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。输入输入的第一行为一个整数N（表示N*N的方格图），接下来的每行...
2020-02-10 20:36:54
514
原创 上学（暴力）
题目描述FJ的农场有n个小镇, 奶牛bessi在小镇0,它的学校在小镇n-1. bessi要坐车到学校去上学. N个小镇之间有公交车, bessi就是坐公交车去上学.小镇之间有m部公交车,我们用(a, b, leave, time, cost) 来描述一部公交车的信息: 表示有一部公交车在时刻leave从小镇a出发, 经过time分钟到达城市b, 车票价格是cost.由于bessi今天睡过头...
2020-02-09 17:56:57
300
原创 Coins Respawn（SPFA 最长路）
题目描述There is a directed graph with N vertices numbered 1 to N and M edges. The i-th edge is directed from Vertex Ai to Vertex Bi, and there are Ci coins placed along that edge. Additionally, there is...
2020-02-09 17:54:43
387
原创 Max GCD（暴力）
题目描述We have a sequence of N integers: A1,A2,⋯,AN.You can perform the following operation between 0 and K times (inclusive):·Choose two integers i and j such that i≠j, each between 1 and N (inclusiv...
2020-02-08 19:05:25
546
1
原创 杀怪物（暴力）
题目描述为了庆祝自己的生日，小张推出一款游戏。游戏在一个20*20的方格上进行，上面有一些怪物，用#表示，其他是空格，用 . 表示。怪物有两点体力。体力为0时死亡。你可以进行以下操作：（1）使一个横行上的怪物体力减一（2）使一个竖行上的怪物体力减一对每个横行或竖行只能操作一次，限定n次，问最多能杀死多少个怪物。输入第一行为整数n（1≦n≦40），表示操作的次数。接下来是一个20*2...
2020-02-08 19:00:21
740
原创 奇怪的数列（暴力）
题目描述有这么一个奇怪的数列，当an是偶数的时候an+1=an/2 ；当an是奇数的时候an+1=3an+1。现在给出a1，当数列的第n项an=1时，我们称n为这个数列的回归数字。比如说a1=22时，数列为：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1．．．．．．这时候a16=1，16就是这个数列的回归数字。经猜测每一个的a1 都存在对应的回归数字。...
2020-02-08 18:57:57
989
2
原创 理财年代（暴力）
题目描述最近通货膨胀很厉害，CPI跑得比银行利息要快，既要抗通胀又要避风险，其中一种很好的方式，就是购买银行发行的理财产品。虽然理财产品的利息比银行定期要高，而且没有风险，但是，购买理财产品需要一定的资金门槛，而且还要保证把钱存入一定时间不能取出来，因此也是有一定的限制的。郭小姐很喜欢研究银行的理财产品，她计划在2011年拿10万元进行理财产品的投资，为了简单方便，她在2011年每次投资理财产...
2020-02-08 18:56:07
222
原创 Bucket Brigade（bfs)
题目描述A fire has broken out on the farm, and the cows are rushing to try and put it out!The farm is described by a 10×10 grid of characters like this:…………B………R…………L……The character ‘B’ repre...
2020-02-07 23:46:11
727
原创 Guess the Animal（思维）
题目描述When bored of playing their usual shell game, Bessie the cow and her friend Elsie like to play another common game called “guess the animal”.Initially, Bessie thinks of some animal (most of the ...
2020-02-07 23:44:52
996
原创 Digits Parade（dp）
题目描述Given is a string S. Each character in S is either a digit (0, …, 9) or ?.Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided ...
2020-02-07 22:47:40
192
原创 剪草（dp）
题目描述有N棵小草，编号0至N-1。奶牛Bessie不喜欢小草，所以Bessie要用剪刀剪草，目标是使得这N棵小草的高度总和不超过H。在第0时刻，第i棵小草的高度是h[i]，接下来的每个整数时刻，会依次发生如下三个步骤：（1）每棵小草都长高了，第i棵小草长高的高度是grow[i]。（2）Bessie选择其中一棵小草并把它剪平，这棵小草高度变为0。注意：这棵小草并没有死掉，它下一秒还会生长的。...
2020-02-07 22:44:25
240
原创 单元格（模拟）
题目描述在一个R行C列的表格里，我们要选出3个不同的单元格。但要满足如下的两个条件：（1）选中的任意两个单元格都不在同一行。（2）选中的任意两个单元格都不在同一列。假设我们选中的单元格分别是：A，B，C，那么我们定义这种选择的“费用”= f[A][B] + f[B][C] + f[C][A]。 其中f[A][B]是指单元格A到单元格B的距离，即两个单元格所在行编号的差的绝对值 + 两个单元...
2020-02-07 18:49:01
263
原创 蚂蚁（模拟）
在二维平面坐标轴里面，有N只蚂蚁，第i只蚂蚁所在的点的坐标是(xi, yi)，坐标都是整数。所有蚂蚁的移动速度都相等，都是每秒移动1个单位。每只蚂蚁都有一个固定的移动方向，是如下4种方向之一，都是平行于坐标轴的： N表示向北（即朝上）， 则y坐标正方向。 E表示向东（即朝右）， 则x坐标正方向。 S表示向南（即向下）， 则y坐标负方向。 W表示向西（即向左）， 则x坐标负方向。当...
2020-02-07 18:42:20
1353
原创 Virus Tree 2（树）
题目描述You are given a tree with N vertices and N−1 edges. The vertices are numbered 1 to N, and thei-th edge connects Vertex ai and bi.You have coloring materials of K colors. For each vertex in the ...
2020-02-06 17:57:11
475
原创 得分（dp）
题目描述现在 zql手上有 N 道题，他总共有 T 的时间来完成他们中的一些或全部。每道题有一个完成所需时间 t[i]和一个难度系数 c[i]。如果 zql 在剩余 x 个单位时间的时候开始做题i，并且能够完成，那么总分加上 x*c[i]。现在 zql 要从这 N 道题中选出一些在T个单位时间内完成，并且按照某种顺序依次完成它们（zql 每个单位时间只能做一道题，并且一旦他决定做某题就会一直做直...
2020-02-06 17:52:34
468
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人