- 博客(70)
- 收藏
- 关注
RSS订阅原创 算法优化专题F POJ - 2431
【题目大意】奶牛的车的油箱破了,每开一个单位距离会花费一单位体积油,奶牛距离城镇L个单位长度。在奶牛到城镇的路途中有n个加油站,第i个加油站距离城镇xi,能加yi的油。如果奶牛能到达城镇,则输出奶牛最少需要的加多少个加油站里的油。如果奶牛不能达到城镇输出-1.【解题思路】贪心让奶牛用光油能到达位置x,那么此时要补充油只能从位置x（包括x）前面的加油站加油,很显然要选最多油的加油站。用大根堆...
2020-03-03 12:47:32
220
原创 算法优化专题E POJ - 2528
【题目大意】有一块长度为x的板(1<=x<=10000000)均分成x份,每份长一个单位长度。现在有n张海报(1<=n<=10000),每张海报有个区间[li,ri],表示这张海报会占用[li,ri]的位置,若区间[li,ri]有其他海报,那么这些海报会被新贴的覆盖,按照输入的顺序贴这n张海报。问最后能看见多少张海报。(同一张海报由于被覆盖分成多段只算一张)【解题思路】...
2020-03-03 11:55:49
235
原创 算法优化专题D HDU - 1754
【题目】很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。Input本题目包含多组测试，请处理到文件结束。在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5...
2020-03-03 10:16:19
206
原创 算法优化专题 C POJ-2777
【题目大意】长度为L的板被分成L段,每段长一个单位长度 (1 <= L <= 100000),有O个操作 (1 <= O <= 100000)操作分两种C A B C 表示将区间[A,B]染成颜色C (1 <= C <= 30)P A B 输出[A,B]有多少种不同的颜色开始时[1,L]的颜色为1【解题思路】观察颜色的种数最多为30种。因此可...
2020-03-03 10:05:29
197
原创 算法优化专题B POJ - 3468
【题目大意】有n个数,a1,a2,a3,…,an,有Q个操作。(1 ≤ N,Q ≤ 100000)操作分两种C a b c 表示将区间[a,b]上的每个数都加上c （-10000 ≤ c ≤ 10000）。Q a b 表示输出区间[a,b]的和。【解题思路】可以用线段树解决。也可以用树状数组解决这种改一段查一段的区间和问题。原数组为a[i]令d[i]=a[i]-a[i-1]su...
2020-03-03 09:39:22
274
原创 算法优化专题A POJ-2352
【题目大意】平面上有n(1<=N<=15000)颗星星,每颗星星都有个坐标(xi,yi) (0<=X,Y<=32000).第i颗星星的能级等于坐标满足(x<=xi且y<=yi)的星星的数量。问0~n-1能级的星星各有多少个。【解题思路】先将n个坐标按x坐标从小到大排好（若x坐标相等,y坐标小的排前面）。这样处理对于第i颗星星的能级,题目就转化成, 求前i...
2020-03-03 09:23:04
165
原创 20.2.25排位赛H
【题目大意】有n(1<=n<=1000)个数a[1],a[2],a[3],…,a[n]。（1<=a[i]<=n,且任意两个数不相等）现在给出n-1个数b[1],b[2],b[3],…,b[n-1],b[i]=b[i]+b[i+1]。求a[1],a[2],a[3],…,a[n]若有有多组解,输出字典序最小的解。【解题思路】因为1<=n<=1000,所以...
2020-02-27 19:14:43
119
原创 20.2.25排位赛F
【题目大意】有n(2<=n<=1000)个点,m条单向边(1<=m<=2000),每个点有一个价值wi(0<=wi<=1000,w1=0),开始时Bessie在开始时在点1,Bessie每经过一个点,她会获得wi的价值(她多次可以多次经过这个点,并且可以获得多次的wi价值)。每经过一个点后(拿到了这个点的价值)要确保,她手上的总价值大于等于cTT(T为她走过的...
2020-02-27 18:52:45
109
原创 20.2.25排位赛E
【题目大意】Bessie有n(1<=n<=100)个单词,每个单词长度1~15,现在要按照输入的顺序输出单词,使得每行的单词字母数小于等于k（两个单词用空格隔开,空格不算入字母数,行末不能有多余的空格）。【解题思路】模拟【代码】#include <cstdio>#include <iostream>#include <string>u...
2020-02-27 17:50:36
117
原创 20.2.25排位赛D
【题目大意】一条赛道k(1<=k<=10^9)米长,Bessie在刚开始在位置0,速度为0m/s,每过一秒,它可以提速1m/s,保持当前速度,或者减速1m/s。有N个询问,求Bessie到达位置k时速度不超过x m/s所要的最短时间。【解题思路】先让Bessie加速到最高速度m再减速到x(如果最高速度未达到x,那就是一直加速到最高速度),假设此时的走过的路程为s,现在来考虑保持匀...
2020-02-27 17:35:51
109
原创 20.2.25排位赛A
【题目大意】有n(1<=n<=10^5)只编号为1,2,3…,n的奶牛分别位于p1,p2,p3,…,pn(1<=pi<=n)的位置上,有m(1<=m<=10 ^5)条虫洞,第i条虫洞连接着ai与bi,它的宽度为wi。(1<=ai,bi<=n,ai≠bi,1<=wi<=10 ^ 9).在任意时刻,位于虫洞两端的奶牛可以交换位置。奶牛想通过...
2020-02-27 12:22:35
146
原创 20.2.22排位赛H
【题目大意】有n（1<=n<=7500）头奶牛,要分成k(2<=k<n)组（不能有空组）,对于不在同一组的奶牛x,y要相见,要走(x<y)(2019201913x+2019201949y) mod 2019201997的距离。奶牛分成k组后,令M为任意两头来自不同组的奶牛为了见面行走的距离的最小值,FJ想让这个M值越大越好。求M最大能为多少。【解题思路】令g(...
2020-02-24 13:16:06
112
原创 20.2.22排位赛G
【题目大意】在一个10*10的地图上,现在有一处谷仓发生火灾,奶牛们要在谷仓与湖之间建立一条救援通道,求救援通道的最小长度‘.’表示空地,‘R’表示石头,不能通过,‘B’表示火灾,‘L’表示湖。【解题思路】用BFS以谷仓为起点开始搜索,记录到达湖的最小长度。【代码】#include <cstdio>#include <iostream>#include <...
2020-02-24 12:19:30
83
原创 20.2.22排位赛F
【题目大意】有n个点(1<=n<=100),有n-1条有向边,问是否存在一个点x使得其他n-1个点均存在路径到达x。若存在x,输出x(有多个输出最小的x),否则输出-1。【解题思路】用floyd算法处理所有点i到点j的最短路径。再对每个点判断其他n-1个点是否存在路径到达该点。【代码】#include <cstdio>using namespace std;...
2020-02-24 12:07:52
127
原创 20.2.22排位赛B
【题目意义】有n(1<=n<=400)堆蛇,第i堆蛇有ai条蛇。Bessie有一个可以变换任意大小的网,但它只能变换t次(1<=t<n)。Bessie对每堆蛇只捕捉一次,所以要求网的大小g要大于等于对应堆的蛇的数量ai。每次捕捉会浪费g-ai的空间,问将所以蛇捕捉所需要浪费的最小空间。开始时Bessie的网可以是任意大小。【解题思路】对于用一次变换捕捉第j+1堆到第i...
2020-02-24 11:52:07
106
原创 20.2.22排位赛A
【题目大意】平面坐标上有n(2<=n<=10^5)头牛,有m条无向边(1<=n<=10 ^5)。任意两个存在路径的牛属于同一集合。现在FJ要用一个平行于x轴,y轴的矩形圈住至少一个牛的集合,问矩形的周长最小时多少？【解题思路】用并查集将n头牛分成若干个集合。在每个集合中取最大的x,最小的y,最大的x,最大的y,即可求出将这个集合中的牛圈住的最小周长, 比较所有集合的最...
2020-02-24 11:30:51
97
原创 20.2.19排位赛I
【题目大意】有个长度为n(1<=n<=100)的字符串st,求最小长度L,使得任意长度为L的st的子串有且仅有一个。【解题思路】由于n比较小,可以枚举L,并判断长度为L的子串是否符合题意。【代码】#include <cstdio>#include <iostream>#include <string>using namespace s...
2020-02-21 12:04:40
116
原创 20.2.19排位赛G
【题目大意】有8只牛分别为Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, and Sue,有n(1<=n<=7)条信息,每条信息以"x must be milked beside y",表示x与y要相邻,输出8只牛字典序最小的顺序。【解题思路】先将8只牛按字典序最小排序,再根据信息连边,由于数据比较小,用邻接矩阵...
2020-02-21 11:57:19
134
原创 20.2.19排位赛E
【题目大意】有一棵n(1<=n<=10^5)个节点的树,每个节点有个标志要么为H,要么为G,有M（1<=M<=10 ^5）个询问,每组询问（x,y,c）,若x到y的路径上有c,那么输出1,否则输出0【解题思路】不妨以1为根节点,h[i]表示根节点1到x的路径上H的数量,g[i]表示根节点1到x的路径上H的数量。t为x与y的最近公共祖先,fa为t的父亲则x到y的路径...
2020-02-21 11:51:21
120
原创 20.2.19排位赛C
【题目大意】有一个长度为n(1<=n<=10^5),均由小写字母组成的字符串st,且最大的字母不超过M(1<=M<=26,将字母用数字表示,a为1).有M*M的矩阵a,a[i][j]表示将i修改j要花费a[i][j]的费用。求将字符串st修改成字符串s,字符串s满足s[i]=s[j],s[i-1]≠s[i]且s[j]≠s[j+1],j-i+1>=k。【解题思路】...
2020-02-21 11:25:05
100
原创 20.2.19排位赛D
【题目大意】在数轴（0,L）的整点上有n只牛(1<=n<=10^5),每只牛有重量,位置(1<=L<= 10 ^9,每只牛的位置均不相同),以及速度(1或-1,1表示向右走,-1表示向左走),当牛走到0或L时停止移动。若两只及两只以上牛在(0,L)上相遇,它们会交换速度(即反弹,原本速度为1的牛速度变成-1,速度为-1的牛速度变成1),问当到达0位置的牛的重量加上到达L位...
2020-02-21 10:16:43
166
原创 20.2.19排位赛B
【题目大意】将自然数中3的倍数,5的倍数,15的倍数剔除,剩下的自然数从小到大排序组成一个数列,求这个数列的第n项(1<=n<=10^9)。【解题思路】3,5,15的最小公倍数为30。如果x被剔除,那么x+30k也会被剔除。30为一个循环节,求出30以内剩下的数有t个那么答案为30n/t+第n%t个数。【代码】#include <cstdio>using ...
2020-02-20 20:16:58
95
原创 20.2.19排位赛A
【题目大意】有n个数(1<=n<=20),每个数ai的范围1<=ai<=n。给出k组排列,问有多少对数(x,y)在k组排列里均满足x排在y前面。【样例输入】3 44 1 2 34 1 3 24 2 1 3【样例输出】4【解题思路】由于n很小,可以枚举x与y,然后再k组排列里判断是否满足题意。【代码】#include <cstdio>us...
2020-02-20 20:04:31
192
原创 寒假集训数论H / POJ - 2689
题目The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of prim...
2020-01-27 12:11:35
139
原创 寒假训练数论I / HDU - 3037
题目Although winter is far away, squirrels have to work day and night to save beans. They need plenty of food to get through those long cold days. After some time the squirrel family thinks that they h...
2020-01-23 20:09:20
170
原创 寒假训练1.17训练赛J
题目大意有n个孩子(编号号1~n ,3<=n<=2*10^5),手拉手围成一个圈。（按顺时针方向）给出编号为i的孩子的后面两个孩子的编号ai1,ai2(但你不清楚i后面一个孩子的编号是ai1还是ai2),求这个圈的孩子编号的顺序(以任意孩子开头输出一种即可)解题思路将给出的ai1与ai2相连可以得到这个环,从任意节点(不妨从节点1开始)开始遍历这个环,只不过得到顺序有可能与题目要...
2020-01-21 19:59:42
103
原创 寒假训练1.17训练赛I
题目大意给出n,k,问n能否分解为k个2的幂之和(1=2^0)。解题思路将n分解成t个2的幂之和参照二进制转十进制的过程,如13,二进制下为1101,所以15=1+2^1 +22+24如果k<t,输出NO每次将最大的幂m,分解成两个m/2,知道最大的幂为1为止,如果还不够k个输出NO代码#include <cstdio>#include <iostream&...
2020-01-21 19:03:52
90
原创 寒假训练1.17训练赛G
题目大意给出一个长度为n(2<=n<=1e5)的数组。删除一个数,使得数组中最大值减最小值的差最小。解题思路最大值减最小值的差只与最大值和最小值有关。代码#include <cstdio>#include <iostream>#include <algorithm>using namespace std;int a[202020]...
2020-01-21 18:34:47
82
原创 寒假训练1.17训练赛E
题目Polycarp loves ciphers. He has invented his own cipher called repeating.Repeating cipher is used for strings. To encrypt the string s=s1s2…sm (1≤m≤10), Polycarp uses the following algorithm:he wr...
2020-01-21 18:12:19
165
原创 寒假训练1.17训练赛D
题目有一个长度为n(1<=n<=2*10^5)且仅包含着"R",“B”,"G"三种字母的字符串s。你可以将任意一个字母修改成另外两个字母。要求相邻两个字母不能相同,求最小的修改次数。解题思路如果有字符串中一段连续的B,例如BBBBB,那么可以看一下连续的B后面接着是哪一种字母(末尾没有,初始化加上一个),这样的话可以把第偶数位的B改成另一位字母。例如BBBBR可以改为BG...
2020-01-21 18:05:05
93
原创 寒假训练1.17训练赛C
题目大意有一个长度为n(1<=n<=2*10^5)且仅包含着"R",“B”,"G"三种字母的字符串s。你可以将任意一个字母修改成另外两个字母。对于任意i,j,如果s[i]=s[j],那么要求| i-j | mod 3=0。求最小的修改次数。解题思路前三个字母确定了,那么后面的字母也就确定了。因此只要确定开头三个字母的顺序(共六种),每种顺序算一遍去最小值即可。代码#i...
2020-01-21 17:51:31
138
原创 寒假训练1.17训练赛B
B题目大意给出一个有a,b的全部因数组成的数列D(数列长度不超过128,Di不超过1000,有重复),输出a,b(任意顺序)解题思路假设a>b用一个桶记录每种数的个数。数列中最大的数肯定是a。将a的因子在数列中删去,剩下的最大的数是b代码#include <cstdio>#include <iostream>#include <algorith...
2020-01-21 17:28:57
86
原创 寒假训练1.17训练赛A
题目大意有两个区间[L1,R1],[L2,R2](1<=L1<R1<=1e9, 1<=L2<R2<=1e9)求a,b满足一下条件L1<=a<=R1,L2<=b<=R2,a≠b有q个询问(1<=1<=500)解题思路如果L1≠L2,那么可以输出a=L1,b=L2如果L1=L2,那么可以输出a=L1,b=R2代码#...
2020-01-21 12:56:40
108
原创 寒假训练数论K
题目Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.Two integers are said to be co-prime or relatively prime if they have no c...
2020-01-21 12:36:46
247
原创 寒假训练数论J
题目解题思路不会证明,找规律。。。发现答案是(2^(n-1))mod(1e9+7)由于n很大,1e9+7是个质数由费马小定理 2^(1e9+6)≡1(mod (1e9+7))所以答案是(2^((n-1) mod (1e9+6)))mod(1e9+7)代码#include <cstdio>#include <iostream>using namespace...
2020-01-21 12:12:16
199
1
原创 寒假训练数论G
题目小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，今天，小明想考考你对素数的认识。 问题是这样的：一个十进制数，如果是素数，而且它的各位数字和也是素数，则称之为“美素数”，如29，本身是素数，而且2+9 = 11也是素数，所以它是美素数。 给定一个区间，你能计算出这个区间内有多少个美素数吗？Input第一行输入一个正整数T，表示总共有T组数据(T <= 1000...
2020-01-20 18:06:51
324
原创 寒假训练数论F
题目两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的...
2020-01-20 17:50:41
169
原创 寒假训练数论E
题目In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), highest common factor (hcf), or greatest common measure (gcm), of two or more integers (when at le...
2020-01-19 20:56:32
231
原创 寒假集训数论D
题目Vitaly is a very weird man. He’s got two favorite digits a and b. Vitaly calls a positive integer good, if the decimal representation of this integer only contains digits a and b. Vitaly calls a go...
2020-01-19 20:52:39
163
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人