字符串

[Ctsc2014] 企鹅QQ

Description
PenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。 小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名称总是很相似的,例如Penguin1,Penguin2,Penguin3……于是小Q决定先对这种相似的情形进行统计。 小Q定义,若两个账户名称是相似的,当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的,但“Penguin1”和“2Penguin”不是相似的。而小Q想知道,在给定的 个账户名称中,有多少对是相似的。 为了简化你的工作,小Q给你的 个字符串长度均等于 ,且只包含大小写字母、数字、下划线以及‘@’共64种字符,而且不存在两个相同的账户名称。

Input

第一行包含三个正整数 , , 。其中 表示账户名称数量, 表示账户名称长度, 用来表示字符集规模大小,它的值只可能为2或64。 若 等于2,账户名称中只包含字符‘0’和‘1’共2种字符; 若 等于64,账户名称中可能包含大小写字母、数字、下划线以及‘@’共64种字符。 随后 行,每行一个长度为 的字符串,用来描述一个账户名称。数据保证 个字符串是两两不同的。 (更多…)

DefFrancis
动态规划

[NOI2009]诗人小G

题目描述

小G是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。 一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方,而一个排版的不协调度为所有行不协调度的总和。 小G最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小),并把排版的结果告诉他。 (更多…)

DefFrancis
数据结构

教主的魔法

题目描述

教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。 每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高) CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。 WD巨懒,于是他把这个回答的任务交给了你。 (更多…)

DefFrancis
数据结构

[CTSC2008]网络管理

题目描述

M公司是一个非常庞大的跨国公司,在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作,公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器,部门局域网内的所有机器都联向这个路由器,然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 高速光缆的数据传输速度非常快,以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化,在这些路由器上进行数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。作为M公司网络部门的一名实习员工,现在要求你编写一个简单的程序来监视公司的网络状况。该程序能够随时更新网络状况的变化信息(路由器数据交换延迟时间的变化),并且根据询问给出两个路由器通信路径上延迟第k大的路由器的延迟时间。 (更多…)

DefFrancis
动态规划

[BalticOI 2016 Day2]城市

题目描述

在 Byteland 有  个城市,并且其中有  个国王经常来访的主要城市。 其中有  条道路,每条道路连接两个城市。然而不幸的是,这些道路的环境极差使得国王无法全速驶过。 对于每条道路,翻修的成本是已知的。你的任务是选择性的翻修道路使得  个主要城市都可以经过翻修后的道路互相连通,且总成本尽量小。 (更多…)

DefFrancis
数据结构

高级打字机

题目描述

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。 请为这种高级打字机设计一个程序,支持如下3种操作: 1.T x:在文章末尾打下一个小写字母x。(type操作) 2.U x:撤销最后的x次修改操作。(Undo操作) (注意Query操作并不算修改操作) 3.Q x:询问当前文章中第x个字母并输出。(Query操作) 文章一开始可以视为空串。 (更多…)

DefFrancis