- 博客(170)
- 收藏
- 关注
RSS订阅原创 最大子矩阵和（To the max） 杭电1081
To the MaxDescriptionGiven a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum ...
2019-10-09 10:53:01
285
原创 D. Take Your Seat
D. Take Your SeatDuha decided to have a trip to Singapore by plane.The airplane had
2019-08-19 11:32:04
548
转载 疯子坐飞机问题
题意：100人坐飞机，每个人按照编号入座，但第一个人在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？他们分别拿到了从1号到100号的座位，这些乘客会按号码顺序登机并应当对号入座如果他们发现对应号座位被别人坐了，就会在剩下空的座位随便挑一个坐．现在假设1号乘客疯了（其他人没疯），他会在100个座位中随便选一个座位坐下，问：第100人正确坐到自己坐位的概率是多少？（也可推...
2019-08-19 10:53:32
952
原创 As Easy as CAB(2016 ICPC Mid-Central USA Region)
题意：输入 字母(用变量名 AA 代替) n // 分别代表这个串中最大的字母(这个是按照原有字母表的顺序确定的) 、 n个串按照 新规定字母表的大小顺序 给出由小到大排序好的 n 个字符串，求 a - AA 之间的由小到大的新顺序思路：每相邻两行进行比较该列字母的大小遇到当前比较的两个字母不同时，用 ch[i][j] 标记一下，表示第ｉ行与第ｊ行不...
2019-08-15 10:57:33
256
原创 树链剖分代码(洛谷3384)
题目链接题意：树链剖分模板题 （树链剖分＋线段树）准备工作:第一步: 定义声明// 链式前向星存图 (**** 记得开２倍空间 ****)struct EDGE{ int to; int next;}edge[MAXX<<1];// 线段树结构体,存和、lazy标记 (**** 记得开４倍空间 ****)struct NODE{ ...
2019-08-13 09:14:40
333
转载 树链剖分 - 知识点
一、定义树链剖分就是将树分割成多条链，然后利用数据结构（线段树、树状数组等）来维护这些链。可以非常友(bao)好(li)的解决一些树上操作（友情提示：学树链剖分之前请先掌握线段树）二、思想树链剖分的思想比较神奇它的思想是：把一棵树拆成若干个不相交的链，然后用一些数据结构去维护这些链那么问题来了，如何把树拆成链？(1) 简单定义首先明确概念：重儿子：父亲...
2019-08-06 17:13:37
342
原创 线段树代码
以 hdu1166为例(区间求和、单点修改)一、定义const LL MAXX = 5e4+10;int sum[MAXX << 2];int a[MAXX];二、区间求和时,更新结点信息void PushUp(int id){ sum[id] = sum[id<<1] + sum[id<<1|1];}三、建树...
2019-08-06 10:52:31
366
转载 线段树从零开始
一、为什么使用线段树题目一：10000个正整数，编号1到10000，用A[1],A[2],A[10000]表示。修改：无统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.方法一：对于统计L,R ，需要求下标从L到R的所有数的和，从L到R的所有下标记做[L..R],问题就是对A[L..R]进行求和。这样求和，对于每个询问，需...
2019-08-05 15:02:01
191
原创 计蒜客G - Faulty Robot
As part of a CS course,Alice just finished programming her robot to explore a graph havingnnnodes,labeled1,2,...,n,1,2,...,n,andmmdirected edges. Initially the robot starts at node11.While nod...
2019-08-04 10:33:02
186
原创 Codeforces - 682C Alyona and the Tree
DescriptionAlyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex1, every vertex and every edge of which ...
2019-08-04 09:08:48
199
原创 图的存储 - 邻接矩阵.邻接表.链式前向星
对于ACM图论方面的题目总是免不了首先要建图存图，使用合适的存图方式不但是AC的必要条件，解题事半功倍。以下主要分析三种常见的存图方式的优缺点以及代码实现目录一、邻接矩阵1.定义12.存图思想13.表现形式14.代码15.优缺点1二、邻接表1.定义22.存图思想23.表现形式24.代码25.优缺点2三、链式前向星1.定义32.存图...
2019-07-30 11:56:20
576
原创 Codeforces 585B - Phillip and Trains
DescriptionThe mobile application store has a new game called "Subway Roller".The protagonist of the game Philip is located in one end of the tunnel and wants to get out of the other one. The tunn...
2019-07-29 17:27:42
282
原创 Codeforces 1167c - News Distribution
DescriptionIn some social network, there arennusers communicating with each other inmmgroups of friends. Let's analyze the process of distributing some news between users.Initially, some user...
2019-07-29 08:41:07
259
原创 Codeforces - 598D Igor In the Museum
DescriptionIgor is in the museum and he wants to see as many pictures as possible.Museum can be represented as a rectangular field ofn × mcells. Each cell is either empty or impassable. Empty ce...
2019-07-28 08:37:23
159
原创 Codeforces - 707B Bakery
M -BakeryDescriptionMasha wants to open her own bakery and bake muffins in one of thencities numbered from1ton. There arembidirectional roads, each of whose connects some pair of cities....
2019-07-27 17:57:37
209
原创 vector 用法详解
目录一、介绍1 定义2 特性二、用法1 一维 vector2 二维 vector一、介绍1 定义 vector(向量): C++中的一种数据结构,确切的说是一个类. 它相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的.2 特性...
2019-07-27 17:42:39
942
原创 Coprime Sequence (HDU 6025)
Coprime SequenceTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 3655Accepted Submission(s): 1687Problem DescriptionDo you know wh...
2019-05-30 10:06:57
167
原创 Codeforces - Increasing Subsequence(easy & hard version)
一、Increasing Subsequence (easy version)The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).You are gi...
2019-05-25 17:32:58
280
原创 Codeforces 1136B
B. Nastya Is Playing Computer GamesFinished her homework, Nastya decided to play computer games. Passing levels one by one, Nastya eventually faced a problem. Her mission is to leave a room, where a...
2019-05-24 12:02:45
267
原创 Increasing Subsequence (easy version) —— codeforces 1157
The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).You are given a sequence
2019-04-30 17:24:14
233
原创 威佐夫博弈
一、有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利二、分析：首先我们根据条件来分析博弈中的奇异局势第一个（0 ， 0），先手输，当游戏另一方面对（ 0 ， 0）时，他没有办法取了，那么肯定是先手在上一局取完了，那么输。 或者是当游戏另一方面对 （0，k）或 （k，0）时，先手一定输，后手可以...
2019-04-25 20:53:24
167
原创 尼姆博弈
一、有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。二、结论：把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜（此时异或值为不为0的数）三、CODE#include <algorithm>#include <iostream>#includ...
2019-04-25 20:43:25
151
原创 最大子段和
动态规划1049 最大子段和N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。收起输入第1行：整数序列的长度N（2 <= N <= 50000)第2 - N + ...
2019-04-16 16:57:57
159
原创 HDU 1238 Substrings
DescriptionYou are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given st...
2019-04-12 18:37:53
173
原创 并查集——带权路径
一、概念引入普通的并查集仅仅记录的是集合的关系，这个关系无非是同属一个集合或者是不在一个集合。而带权并查集，不仅记录集合的关系，还记录着集合内元素的关系或者说是元素连接线的权值。二、实现1、求 v 数组带权并查集有一个新的数组叫做意义是：从当前节点到根节点的有向距离（这里定义A到B的有向距离为dis时，B到A的有向距离为-dis）而对于两个点对的距离，如果他们不...
2019-04-11 16:23:13
1126
1
原创 并查集知识点
以为自己已经会用并查集了呢，碰到了一个带全路径并查集的问题，发现自己居然都没太理解具体思想是什么啊渣渣一、举个例子在讲并查集之前我们先举一个例子。（这个例子是出自别人之手，大都知道的例子）话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉...
2019-04-09 14:02:52
196
原创 Old Fafhioned Typefetting
UVALIVE 4875In Olden Days, before digital typesetting (before Babbage, even), typesetting was an art, practicedby highly skilled craftsmen. Certain character combinations, such as a-e or f-i were ty...
2019-04-03 21:03:38
218
原创 上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛
链接：https://ac.nowcoder.com/acm/contest/551#question一、CSL 爱烫头题目描述又到了一年一度的樱花节，CSL 的同学邀请 CSL 一起去赏樱花。于是爱美的 CSL 决定好好打扮一下自己。看了看自己日益减少的头发，CSL 觉得再不烫头就来不及了，于是拿出了所有的奖学金，想要做个头发。由于头发实在太少，一般的理发店无法处理，CSL 不得已要...
2019-03-31 19:40:09
339
原创 春季个人训练赛 9
**A - Penney Game（4873）**Penney’s game is a simple game typically played by two players. One version of the game calls for eachplayer to choose a unique three-coin sequence such as HEADS TAILS HEA...
2019-03-30 18:39:28
316
原创 (Ｃｆ1141C). Polycarp Restores Permutation
(Ｃｆ1141C). Polycarp Restores PermutationAn array of integers
2019-03-30 12:14:49
402
原创 Codeforces - 思维（第四周）
Ｃｆ（1141A)Game 23Polycarp plays "Game 23". Initially he has a number
2019-03-29 15:55:18
511
原创 Pen Counts(UVALIVE 6174)
Sample Input51 32 113 124 1005 9999Sample Output1 12 53 43925 4165834题意：用长度为 n 的绳子围三角形同一三角形的旋转是相同的，反射是不同的意思就是，对于等腰和等边三角形来说，不论怎么旋转只能算一种，其余的算两种思路：设定 a<=b<...
2019-03-26 15:37:10
174
原创 Faulhaber's Triangle (UVALIVE 6176)
Faulhaber’s Triangle ( UVALIVE 6176)InputThe first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data setsthat follow. Each data set should be processed identic...
2019-03-25 20:39:13
196
原创 春季个人训练赛 ５（广工新生赛）
１、A -hzy 和zsl 的生存挑战Descriptionzsl 和hzy 来到了臭臭城堡，打算挑战臭臭城堡的大魔王hyz，大魔王hyz设置了这样的一个挑战：1. zsl 和hzy两个人各自来到一间密室，期间两人无法以任何形式交流2. 大魔王hyz会随机在两个人的脑海里各发送一个数字，0或者是13. zsl 和 hzy 需要猜对这俩个数字才算通关，但是大魔王hyz觉得人生不...
2019-03-19 15:36:17
246
原创 春季个人训练赛－６
１、 Bit String ReorderingYou have to reorder a given bit string as specified. The only operation allowed is swapping adjacentbit pairs. Please write a program that calculates the minimum number of sw...
2019-03-18 11:58:52
263
原创 春季个人训练赛－３、４
１、 ParenthesesA bracket is a punctuation mark, which is used in matched pairs, usually used within articles orprograms. Brackets include round brackets, square brackets, curly brackets, angle bracke...
2019-03-17 20:10:59
332
原创 Codeforces —— 思维（第３周）
Codeforces 1138ASushi for TwoArkady invited Anna for a dinner to a sushi restaurant. The restaurant is a bit unusual: it offers
2019-03-14 16:35:51
330
原创 最短路例题
最短路请戳ONE：题目来源 最短路 Problem Description 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？ Input 输入包括多组数据。每组数据第一行是...
2019-03-07 20:50:18
422
原创 最小生成树详解
一、概念１、最小生成树是一副连通加权无向图中一棵权值最小的生成树如下图黑线表示的是一个最小生成树２、一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。二、相关性质１、个数多个最小生成树在一些情况...
2019-03-07 16:15:19
5155
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人