- 博客(78)
- 收藏
- 关注
RSS订阅原创 HDU 3572(网络流)
Problem DescriptionOur geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factory has introduced M new machines in order to process the coming N tasks. For the i-th task, the factory has to
2020-11-07 14:48:32
140
原创 github使用
github最近想把代码放到github上，那么以后如果去打比赛的时候需要模板就可以直接去那里下载打印了，然后就开始整了。使用方法也很简单。首先你需要登录github官网:GitHub官网然后你需要创建账户，如果之前创建过，直接登录即可。登录之后，你需要创建一个仓库：点击‘+’然后点击 New repository就进入仓库创建页面了。创建仓库时，必填的只有仓库的名字，然后有一个选项：public:任何人都可以看到这个仓库，你可以选择一些人可以提交代码到这个仓库。private:只有
2020-10-28 09:35:26
242
原创 luogu P3369(Splay)
今天的杭电多校打了之后，有一个题，我们有思路，但是却实现不了，之后看了题解发现需要用到动态树，然后，我太菜了，啥都不会（呜呜呜，猛男落泪）。然后去了解了一下发现，动态树需要前置技能splay，所以今天肝了一下，从晚上9点开始写代码，一直到一点才A掉题。闲话说完，现在说一下splay的一些做法。因为这里条件有限，所以不会太详细，大家可以看一下这个blog这篇博客只写一些博主的理解。模板题：P3369接下来介绍一下splay的操作：旋转节点：splay的旋转，就是保持二叉树的特性将节点上旋，因为
2020-08-14 01:59:59
178
1
原创 SPOJ - SUBLEX Lexicographical Substring Search（后缀自动机）
Little Daniel loves to play with strings! He always finds different ways to have fun with strings! Knowing that, his friend Kinan decided to test his skills so he gave him a string S and asked him Q questions of the form:If all distinct substrings of stri
2020-07-28 11:12:58
117
原创 SPOJ-NSUBSTR Substring（后缀自动机）
You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string ‘ababa’ F(3) will be 2 because there is a string ‘aba’ that
2020-07-27 22:30:45
112
原创 2020-HDU 多校训练赛1011 （Lyndon 分解）
Minimum IndexTime Limit: 3000/1500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 264 Accepted Submission(s): 56Problem DescriptionLet s=s1 s2⋯sn be a string of length n. For any integer k between 1 to n, the kth
2020-07-22 14:57:49
294
原创 牛客多校第三场 E-Two Matchings
题目大意有一个长度为n的数组a，然后让我们求两个序列p,q，满足p和q是由序列1-n两两交换得到的，并且对于每一个i满足pi!=qi。然后使得值最小，求这个值。解题思路题目可以翻译成：对于数组a，两两组队，使得式子的值最小。也就是我们要找一个序列，使得这个式子最小，和一个序列使得这个式子次小。对于最小的值，我们可以对数组a排序之后每两个组成一队，可以知道这个值是最小的，证明方法，就是在数轴上表示出来，可以证明其他画法都会在包含该方法的线段之外还会包含其他额外的线段。对于次小值，我们可以将n分成4
2020-07-18 23:23:37
124
原创 牛客多校第三场 F-Fraction Construction Problem
题目大意给出一个a b，求c,d,e,f,使得d,f<b，1<c,e<4×10^12.解题思路：对于a,b，如果gcd(a,b)!=1,那么我们可以很好的发现，(a/gcd(a,b)) /(b/gcd(a,b))=a/b。并且满足b/gcd(a,b)<=b。所以我们不妨令d=f=b/gcd(a,b)。然后分母相同，就只需要满足c-e=a/gcd(a,b)就可以了，随便令e等于一个值，c=e+a/gcd(a,b)。就可以了。对于a,b，如果gcd(a,b)=1,那么对于c/d-
2020-07-18 21:26:15
176
原创 牛客多校2020年第二场F-Fake Maxpooling
题目大意：有一个矩阵A，其中Aij=LCM(i,j)。问在该矩阵中所有的k子矩阵的最大值的和。解题思路：先暴力求出目标矩阵，然后利用单调栈维护最大值下标。最后将答案加上即可。代码：#pragma GCC optimize(2)#include <bits/stdc++.h>#include <unordered_map>using namespace std;std::mt19937 rnd(233);#define pp pair<int,int>#d
2020-07-13 20:43:23
221
原创 luogu P1646 happiness
题目描述高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。输入格式第一行两个正整数n，m。接下来是六个矩阵第一个矩阵为n行m列此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。第二个矩阵为n行m列此矩阵的第i行
2020-07-11 15:42:01
649
原创 luogu P4126最小割
题目链接：https://www.luogu.com.cn/problem/P4126题目大意：给出一个图，和源点和汇点，问图中的边中有哪些是最小割的可行边，哪些是最小割的必须边。思路：可行边可行边的意思是，某一种最小割方案会经过的边，（但我理解的是，最小割的必须边，也就是最小割一定会经过这些边，其他的最小割的方案是在这些边上面添加了一些其他边组成的方案）。一条边是最小割的可行边的充要条件是：我们可以思考一下最小割的定义，割去权值和最小的边，使得源点和汇点不连通，那么如果边u-v是最小割的可行边
2020-07-09 15:51:28
150
原创 luogu-p2292(AC自动机)
题目描述标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。我们称一段文章T在某个字典D下是可以被理解的，是指如果文章T可以被分成若干部分，且每一个部分都是字典D中的单词。例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’}...
2020-02-29 18:26:12
151
原创 POJ 2778(AC自动机+矩阵快速幂)
DescriptionIt’s well known that DNA Sequence is a sequence only contains A, C, T and G, and it’s very useful to analyze a segment of DNA Sequence，For example, if a animal’s DNA sequence contains segm...
2020-02-29 11:30:31
143
原创 UVA - 11019(AC自动机)
Given an N × M matrix, your task is to find the number of occurences of an X × Y pattern.InputThe first line contains a single integer t (t ≤ 15), the number of test cases.For each case, the first ...
2020-02-27 10:24:05
152
原创 HDU 3065(AC自动机)
Problem Description小t非常感谢大家帮忙解决了他的上一个问题。然而病毒侵袭持续中。在小t的不懈努力下，他发现了网路中的“万恶之源”。这是一个庞大的病毒网站，他有着好多好多的病毒，但是这个网站包含的病毒很奇怪，这些病毒的特征码很短，而且只包含“英文大写字符”。当然小t好想好想为民除害，但是小t从来不打没有准备的战争。知己知彼，百战不殆，小t首先要做的是知道这个病毒网站特征：包含多...
2020-02-25 21:35:01
109
原创 HDU 2222(AC自动机)
Problem DescriptionIn the modern time, Search engine came into the life of everybody like Google, Baidu, etc.Wiskey also wants to bring this feature to his image retrieval system.Every image have a...
2020-02-25 16:26:17
214
原创 HDU 4300(扩展KMP)
Problem DescriptionClairewd is a member of FBI. After several years concealing in BUPT, she intercepted some important messages and she was preparing for sending it to ykwd. They had agreed that each...
2020-02-24 23:17:31
184
原创 HDU 4333(扩展KMP)
Problem DescriptionOne day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several last digits to the front of the integer. Of course, he c...
2020-02-24 22:29:34
103
原创 HDU 3068(manacher)
给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c…y,z组成的字符串S两组case之间由空行隔开(该空行不用处理)字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组ca...
2020-02-06 21:24:10
104
原创 ACWing 246(线段树+(树状数组)+gcd)
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。对于每个询问，输出一个整数表示答案。输入格式第一行两个整数N,M。第二行N个整数A[i]。接下来M行表示M条指令，每条指令的格式如题目描述所示。...
2020-02-06 20:50:17
181
原创 HDU 3746(KMP)
CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to...
2020-02-06 18:10:55
85
原创 Substring Frequency(KMP)
A string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given two non-empty strings A and B, both contain lower case English alphabets. You have to find the ...
2020-02-06 17:35:04
124
原创 ACWing 240(并查集 扩展域)
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是"1 X Y"，表示X和Y是同类。第二种说法是"2 X Y"，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话...
2020-02-06 11:33:55
172
1
原创 HDU 1711(KMP)
Given two sequences of numbers : a[1], a[2], … , a[N], and b[1], b[2], … , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2...
2020-02-06 10:37:59
96
原创 HDU 1269(tarjin)
Problem Description为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j...
2020-02-04 21:05:14
116
原创 HDU 2767(tarjin)
Problem DescriptionConsider the following exercise, found in a generic linear algebra textbook.Let A be an n × n matrix. Prove that the following statements are equivalent:A is invertible.Ax = b ...
2020-02-04 20:48:17
169
原创 Nearest Common Ancestors (LCA)
数据结构中的树，在计算机科学中是非常重要的，例如我们来看看下面这棵树：在图中我们对每个节点都有编号了。 8号节点是这棵树的根。我们定义，一个子节点向它的根节点的路径上，任意一个节点都称为它的祖先。例如， 4号节点是16号节点的祖先。而10号节点同样也是16号的祖先。事实上，16号的祖先有8，4，10，16共四个。另外8， 4， 6，7都是7号节点的祖先，所以7号和16号的公共祖先是4和8号，而...
2020-02-01 00:01:50
286
原创 luogu-p1129(匹配问题)
题目描述小QQ是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个N \times NN×N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角...
2020-01-31 23:13:11
150
原创 HDU 2063(匹配问题)
Problem DescriptionRPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意...
2020-01-31 21:51:34
119
原创 POJ 2060(最小路径覆盖)
DescriptionRunning a taxi station is not all that simple. Apart from the obvious demand for a centralised coordination of the cabs in order to pick up the customers calling to get a cab as soon as po...
2020-01-30 22:52:19
158
原创 HDU 4185(匈牙利算法)
Problem DescriptionThanks to a certain “green” resources company, there is a new profitable industry of oil skimming. There are large slicks of crude oil floating in the Gulf of Mexico just waiting t...
2020-01-30 22:02:55
166
原创 CodeForces 343D(树链剖分+线段树)
Mad scientist Mike has constructed a rooted tree, which consists of n vertices. Each vertex is a reservoir which can be either empty or filled with water.The vertices of the tree are numbered from 1 ...
2020-01-27 20:57:23
1398
2
原创 SCU - 4438（字符串hash）
Censorfrog is now a editor to censor so-called sensitive words (敏感词).She has a long text p. Her job is relatively simple – just to find the first occurence of sensitive word w and remove it.frog re...
2020-01-21 21:54:33
18224
原创 LightOJ - 1077(GCD)
Given two points A and B on the X-Y plane, output the number of the lattice points on the segment AB. Note that A and B are also lattice point. Those who are confused with the definition of lattice po...
2020-01-21 16:23:56
1328
3
原创 CodeForces - 514D (线段树+二分)
An army of n droids is lined up in one row. Each droid is described by m integers a1, a2, …, am, where ai is the number of details of the i-th type in this droid’s mechanism. R2-D2 wants to destroy th...
2020-01-21 16:17:52
185
3
原创 HDU-6534 (莫队算法+树状数组)
Problem DescriptionChika gives you an integer sequence a1,a2,…,an and m tasks. For each task, you need to answer the number of “friendly pairs” in a given interval.friendly pair: for two integers ai...
2020-01-16 20:55:54
182
原创 UVA - 11297(线段树套线段树)
放个链接在这里：UVA - 11297This year, there have been many problems with population calculations, since in some cities, thereare many emigrants, or the population growth is very high. Every year the ACM (fo...
2020-01-16 16:43:25
249
原创 BZOJ-2002(分块)
Description某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，...
2020-01-16 11:06:16
138
原创 CodeForces - 356A(fhq-treap)
上个题目链接：CodeForces - 356AHooray! Berl II, the king of Berland is making a knight tournament. The king has already sent the message to all knights in the kingdom and they in turn agreed to participate ...
2020-01-15 17:04:28
288
原创 Spoj 10628 (树上主席树+LCA)
You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.We will ask you to perform the following operation:u v k : ask for the kth minimum weight ...
2020-01-15 14:14:49
237
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人