1 丶di

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 15w+

P1972 [SDOI2009]HH的项链 树状数组+离线

P1972 [SDOI2009]HH的项链 树状数组+离线文章目录题目描述输入格式输出格式题解题目描述HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答…… 因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。输入格式一行一个正整数 n,表示项链长度。第二行 n

2020-09-11 12:05:09

牛客 白兔的字符串 哈希预处理匹配字符串

题目链接:牛客15253 白兔的字符串题目描述白兔有一个字符串T。白云有若干个字符串S1,S2…Sn。白兔想知道,对于白云的每一个字符串,它有多少个子串是和T循环同构的。提示:对于一个字符串a,每次把a的第一个字符移动到最后一个,如果操作若干次后能够得到字符串b,则a和b循环同构。所有字符都是小写英文字母输入描述:第一行一个字符串T (∣T∣<=106)(|T|<=10^6)(∣T∣<=106) 第二行一个正整数n (n<=1000)(n<=1000)(n&lt

2020-08-31 22:30:24

AtCoder Regular Contest 064 English E - Cosmic Rays 预处理+dij最短路

题目链接:Cosmic RaysProblem StatementOn thexy-plane, Snuke is going to travel from the point (xs,ys) to the point (xt,yt). He can move in arbitrary directions with speed 1. Here, we will consider him as a point without size.There are N circular barriers de

2020-08-17 18:35:31

HDU-2586 How far away? LCA模板题 倍增 邻接表/head

题目链接:HDU-2586求树上两点距离最短,即ans=两点深度和-LCA最近公共祖先深度*2文章目录模板1 邻接表存图模板2 head链式前向星存图模板1 邻接表存图#pragma GCC optimize(2)#include <bits/stdc++.h>#define ll long long#define endl '\n'#define inf 0x3f3f3f3fusing namespace std;const int mod=1e9+7;const in

2020-08-16 13:07:34

Educational Codeforces Round 93 (Rated for Div. 2)A-B-C-D

比赛链接:Educational Codeforces Round 93 (Rated for Div. 2)A.Bad Triangle 思维题意:n个数从小到大,是否可以挑出三个数不能构成三角形,输出这个三个数的下标,否则输出-1#pragma GCC optimize(2)#include<bits/stdc++.h> using namespace std;#define endl "\n"int main(){ ios_base::sync_with_stdio(

2020-08-15 14:30:29

Codeforces Round #661 (Div. 3)D-E1

D. Binary String To Subsequences题意:一个长度为n的字符串,可以从左到右拆分到多个集合中,保证该集合的前一个字符与后来的字符不同,问最少需要多少个集合。题解:用两个数组t0和t1分别存储0和1模拟,每个0隶属于它出现时t1数组最后一个1的位置,每个1隶属于它出现时t0数组最后一个0的位置,若遇到10或01可以刚好可以凑成一队就都pop消去,若凑不成,ans++表示多开一个集合。#pragma GCC optimize(2)#include<bits/stdc++

2020-08-07 21:20:31

牛客等级之题N1 追债之旅 - N2 Rinne Loves Study(8.6场)

牛客等级之题N1-A.追债之旅(8.6场)题目描述小明现在要追讨一笔债务,已知有n座城市,每个城市都有编号,城市与城市之间存在道路相连(每条道路都是双向的),经过任意一条道路需要支付费用。小明一开始位于编号为1的城市,欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天,而欠债人每天都会挥霍一定的钱,等到第k天后(即第k+1天)他就会离开城n并再也找不到了。小明必须要在他离开前抓到他(最开始为第0天),同时希望自己的行程花费和欠债人挥霍的钱的总和最小,你能帮他计算一下最小总和吗?输入

2020-08-06 23:43:22

2020牛客暑期多校训练营(第八场)I.Interesting Computer Game并查集

题目链接:Interesting Computer Game题意n个回合,每个回合输出两个数,分别是ai、bi,且每个回合求进行三个操作中的一个操作,分别是①不进行操作,②如果之前的回合中未选出过ai,则可以选出ai,③如果之前的回合中未选出过bi,则可以选出bi。求n个回合后,获得不同数字个数的最大值。题解并查集维护连通块的点数和边数。对于每个连通块,如果有x个点、y条边,则有y≥x-1若y=x-1,则说明该连通块是最小连通块,恰好连通,对答案贡献为x-1若y≥x,则该连通块所有的点都可以选

2020-08-04 02:19:37

Codeforces Round #658 (Div. 2) D. Unmerge预处理+01背包dp

补题,题目链接:Codeforces Round #658 (Div. 2) D. Unmerge题目描述Let a and b be two arrays of lengths n and m, respectively, with no elements in common. We can define a new array merge(a,b) of length n+m recursively as follows:If one of the arrays is empty, the res

2020-08-02 15:48:49

HDU - 1978 How many ways 记忆化搜索dp+bfs

题目链接:HDU - 1978 How many ways题目描述这是一个简单的生存游戏,你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下:1.机器人一开始在棋盘的起始点并有起始点所标有的能量。2.机器人只能向右或者向下走,并且每走一步消耗一单位能量。3.机器人不能在原地停留。4.当机器人选择了一条可行路径后,当他走到这条路径的终点时,他将只有终点所标记的能量。如上图,机器人一开始在(1,1)点,并拥有4单位能量,蓝色方块表示他所能到达的点,如果他在

2020-07-31 20:07:09

牛客 [HAOI2016]食物链 拓扑排序+记忆化搜索(入门)

题目链接:[HAOI2016]食物链题目描述如图所示为某生态系统的食物网示意图,据图回答第1小题现在给你n个物种和m条能量流动关系,求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3…am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链输入描述:第一行两个整数n和m,接下来m行每行两个整数ai,bi描述m条能量流动关系。(数据保证输入数据符号生物学特点,且不会有重复的能量流动

2020-07-31 20:00:56

牛客编程巅峰赛S1第7场 - 黄金&钻石A-B-C

比赛链接:牛客编程巅峰赛S1第7场 - 黄金&钻石A.牛牛打怪兽 DFS题意身为屯里第一剑士的牛牛来到训练场里闯关,由于过于勤奋,牛牛的宝剑的耐久度降到了 2 ,这意味着牛牛最多只能打倒两只怪兽,否则将会被淘汰。训练场的地图可以看作一棵以1为根节点的树,训练场的终点为这棵树的叶子结点,树上的每个结点最多有一只怪兽,结点与结点间的边上没有怪兽。每一个有怪兽的结点上牛牛都需要打倒怪兽才算安全,并且牛牛一旦选定好打怪路线之后便不能走回头路。请问牛牛有多少种到达终点且不被淘汰的路径。输入第一

2020-07-31 14:48:26

百度之星2020初赛一1003 Distance dp预处理打表

题目链接:1003 DistanceProblem Description初始有 a,b 两个正整数,每次可以从中选一个大于 1 的数减 1,最后两个都会减到 1,我们想知道在过程中两个数互质的次数最多是多少。Input第一行一个正整数 test(1≤test≤1000000)test(1 \le test \le 1000000)test(1≤test≤1000000) 表示数据组数。接下来 test 行,每行两个正整数 a,b(1≤a,b≤1000)a, b(1 \le a, b \le 10

2020-07-29 16:35:18

CodeForces - 52C-Circular RMQ 线段树区间操作

题目链接:CodeForces - 52C Circular RMQ题目描述You are given circular array a 0, a 1, …, a n - 1. There aretwo types of operations with it:inc(lf, rg, v) — this operation increases each element on the segment[lf, rg] (inclusively) by v; rmq(lf, rg) — this op

2020-07-29 16:03:42

牛客14894 最长回文 manacher马拉车

题目链接:牛客 最长回文 题目描述有两个长度均为n的字符串A和B。可以从A中选一个可以为空的子串A[l1…r1],B中选一个可以为空的子串B[l2…r2],满足r1=l2,然后把它们拼起来(A[l1…r1]+B[l2…r2])。求用这样的方法能得到的最长回文串的长度。注意:求的不是本质不同的回文串个数哦!!!输入描述第一行一个数n第二行表示字符串A第三行表示字符串B输出描述输出一行一个数表示答案题解分别对两个字符串进行manacher预处理,找到他们自身回文的p[]数组我们需要

2020-07-23 11:20:53

广州大学第十四届ACM大学生程序设计竞赛题解(待续)

比赛连接:传说门在此前言目录A.攀登B.BadelineC.Celestial ResortD.清理杂物E.注意风F.Mirror TempleG.倒放K.草莓失踪A.攀登题意:输出leftup、up、rightup、left、right、leftdown、down、rightdown与QuickDrop、Squat、Grasp、Jump的搭配所需要的按键。题解:没有算法直接暴力模拟,需要注意恶心人的会卡缓冲区的换行,所以每次输入后缓冲区没清空导致有些数据输出不了,因此可以手动添加cin.ignor

2020-07-20 02:08:38

牛客 遗迹逃亡 基础bfs

题目连接:牛客 遗迹逃亡基础迷宫类bfs广搜题题目描述为了寻找稀有的宝可梦,小梁进了一个古代遗迹中。在一次意外的触发之下,她复活了超古代宝可梦化石翼龙并激怒了对方,现在化石翼龙准备攻击小梁,她要逃离这个遗迹了。但化石翼龙的实力过于强大,让这个本就历经风霜的遗迹开始了毁灭性的崩塌,有大量的落石下落,现在我们要帮助小梁逃离这个遗迹。遗迹是一个\text{N * M}N * M 的矩阵,\text{g}g表示该遗迹的出口;\text{s}s表示小梁所处位置;现在遗迹中有大量落石正在下落。因为小梁不能翻越

2020-07-17 22:20:41

线段树区间修改区间求和区间最大最小值模板

C++线段树区间修改区间最大最小值模板#pragma GCC optimize(2)#include<bits/stdc++.h> using namespace std;#define ll long long#define endl "\n"const int MAX=1e5+5;struct node{ ll sum,lz;//总和、lazy标记 ll mx,mn;//最大值max,最小值min}d[MAX<<2];ll n,m;ll a[MAX];

2020-07-17 13:54:30

牛客13593 大家一起来数二叉树吧 简单dp

题目连接:大家一起来数二叉树吧题目描述某一天,Zzq正在上数据结构课。老师在讲台上面讲着二叉树,zzq在下面发着呆。突然zzq想到一个问题:对于一个n个节点,m个叶子的二叉树,有多少种形态呐?你能告诉他吗?对于第一组样例的解释输入描述每一组输入一行,两个正整数n,m(n<=50)意义如题目输出描述每一行输出一个数,表示相应询问的答案取模1000000007题意n个节点,m个叶子,问有多少种形态的二叉树题解二叉树的每一次延伸一个节点相当于加上一棵子树,考虑到是二叉树,所

2020-07-17 11:41:28

北京师范大学第十六届程序设计竞赛决赛-重现赛 ACDEFGI

校队师兄拉了这套题给我们热身练习,故此写一下题解记录(2020-7-14)A.塞特斯玛斯塔真正的签到题,题目虽然很长但是真正有用的只有最后一句话,判断是否有“MILLION Master”,有则输出“MILLION Master”,无则输出“NA Noob”。#pragma GCC optimize(2)#include<bits/stdc++.h> using namespace std;#define endl "\n"string str;int main(){ i

2020-07-15 10:33:51

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取