`
bcyy
  • 浏览: 1881082 次
文章分类
社区版块
存档分类
最新评论

Timus 1723. Sandro's Book 题解

 
阅读更多

It's been quite a number of years since Lich Sandro retired. Sometimes in the evenings, when he feels especially lonely, he takes a book that was presented to him by his student magicians on the occasion of his retirement.
This evening the great magician is also reading the book. One of the chapters describes Sandro's famous discovery: he invented a universal spell many years ago. Any substring (a few consecutive symbols of the string) of the universal spell is also a spell, and its power is equal to the number of times this spell is encountered in the universal spell (for example, the string “ue” encounters in the string “queue” twice, and the string “aba” encounters in the string “abababa” three times).
Sandro has a lot of free time now and he wants to find the most powerful spell. Help Sandro do it.

Input

The only input line contains the universal spell invented by Sandro. The spell is a non-empty string consisting of lowercase English letters with length at most50.

Output

Output any of the most powerful spells, according to Sandro's definition.

Sample

input output
tebidohtebidoh
tebidoh


本题就看故事, 故事看起来一长串, 理解起来也挺费力,所以一开始我使用KMP算法查找了所有子串:

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

class SandroBook
{
	vector<int> tbl;
	int encounter;
	string spell;
public:
	SandroBook():tbl(), encounter(0)
	{

	}

	int kmpSearch(string txt, string pat, int sta=0)
	{
		tbl.resize(pat.size());
		genTbl(pat);
		int c = 0;
		for (int i = 0, j = 0; i < txt.size(); i++)
		{
			if (pat[j] == txt[i]) j++;
			else if (j > 0)
			{
				j = tbl[j-1];
				i--;
			}
			if (pat.size() == j)
			{
				c++;
				j = tbl[j-1];
			}
		}
		return c;
	}

	void genTbl(const string &pat)
	{
		for (int i = 1, j = 0; i < pat.size(); i++)
		{
			if (pat[i] == pat[j]) tbl[i] = ++j;
			else if (j > 0)
			{
				j = tbl[j-1];
				i--;
			}
		}
	}
	void SandroRun()
	{
		string txt;
		cin>>txt;
		encounter = 0;
		for (int i = 0; i < txt.size(); i++)
		{
			for (int d = i+1; d < txt.size(); d++)
			{
				string pat = txt.substr(i, d-i+1);
				int c = kmpSearch(txt, pat, i+1) + 1;
				if (c > encounter)
				{
					encounter = c;
					spell = pat;
				}
			}
		}
		cout<<spell;
	}
};

上面程序可以AC。很sophisticated 的KMP算法。

但是后来一想,这个不对啊,子串包括了一个字母的子串,那么本题就太简单了,看起来甚至像是一个玩笑了。

经验证的确如此,因为下面程序也能通过。教训还是题意的问题,如果可以问,一定要先问清楚题意。大概本题出题者就是在开玩笑。

#include <iostream>
#include <stdio.h>

using namespace std;

int mainSandro()
{
	char str[50];
	int maxi,max,i=0;
	int ch[26]={0};

	scanf("%s",&str);
	while(str[i++]) ch[str[i]-'a']++;

	maxi=0;
	max=ch[maxi];

	for(i=1;i<26;i++)
	{
		if(ch[i]>max)
		{
			maxi=i;
			max=ch[maxi];
		}
	}
	printf("%c\n",maxi+'a');
	return 0;
}




分享到:
评论

相关推荐

    Sandro Tosi - Matplotlib for Python Developers (2009)

    《Matplotlib for Python Developers》是一本由Sandro Tosi撰写的书籍,该书于2009年由Packt Publishing出版。本书主要面向Python开发者,旨在教授如何利用Matplotlib库创建高质量的图表。 **作者简介:** Sandro ...

    Mastering Node.js(PDF版免积分下载)

    5. 从提供的部分内容中可以看到,Sandro Pasquali是***的创始人,该公司于1997年成立并销售了世界上第一个基于JavaScript的应用开发框架,并获得部署和广告技术的专利,预示了基于互联网的软件的未来。 6. Sandro ...

    Node.js英文书籍2013出版共9本(一次下载)

    Mastering Node.js By Sandro Pasquali (Packt 2013).pdf Node.js for PHP Developers (OReilly 2013).pdf Node.js the Right Way (Pragmatic 2013).pdf Pro.Node.js.for.Developers (Apress 2013).pdf Professional...

    移相器课程:通过移相器https://sandro.github.iophaser-lessons进行编程课程

    移相器课程:通过移相器https://sandro.github.iophaser-lessons进行编程课程

    Introduction to Deep Learning.pdf

    10. 作者信息:文档还提供作者信息,指出作者Sandro Skansi来自萨格勒布大学,位于克罗地亚的萨格勒布。作为所在领域的专家,作者能够提供深度学习领域的深入见解和实践经验。 总结来说,这份文件介绍了一本关于...

    Sandro:您的个人GPS助手-项目开发

    【Sandro:您的个人GPS助手-项目开发】是一款利用GPS技术进行定位监控的应用程序,旨在帮助用户追踪并管理目标对象的位置信息。这个项目的核心功能是通过GPS定位技术获取实时地理位置,以便用户能够有效地监视和了解...

    sandro-design:桑德罗·佩雷拉(Sandro Pereira)的个人网站!

    桑德罗·佩雷拉(Sandro Pereira)的在线作品集 您好,我叫Sandro Pereira,这是我的在线投资组合。 我写这篇文章主要是为了我的利益,因为我倾向于忘记事情。 文档很重要! 我在用什么 ,因为变量和嵌套样式使事情...

    mastering-node:“掌握 Node.js”一书中的练习 - Sandro Pasquali

    《掌握 Node.js》是Sandro Pasquali撰写的一本深入探讨Node.js技术的书籍,旨在帮助读者成为Node.js开发的专家。在这个压缩包文件“mastering-node-master”中,我们很可能会找到书中的一些实践代码和练习,以加深对...

    sandro:公司计算机存储库

    【标题】"sandro:公司计算机存储库"指的是一个名为"Sandro"的项目,它可能是某个公司的内部计算机代码仓库。这个存储库包含了该公司的软件开发资源,可能涉及到多个项目或系统的源代码、配置文件以及相关的文档。 ...

    TripServiceKata:.NET 版本的 Sandro Mancuso 重构卡塔

    测试和重构遗留代码Sandro Mancuso 重构 kata 的 .NET 版本(见链接)。代码 git clone https://github.com/orient-man/TripServiceKata.gitcd TripServiceKatagit checkout demo-start使用 git 导航重构步骤有用的 ...

    Trip_Service_Kata_Java:桑德罗·曼库索(Sandro Mancuso)重构旧版代码kata

    由Sandro Mancuso制作的重构遗留代码kata。 我涵盖了他的仓库中的指南,该指南包括对TripService类进行单元测试,并对其进行重构,以打破依赖关系,并以表达域的精心设计的代码结尾。 这是Sandro Mancuso的存储库...

    意大利语有个性自我的介绍.doc

    Mi chiamo Sandro Bruni. Bruni è il mio cognome, mentre Sandro è il mio nome.” 3. **来自何方**:简单介绍你的家乡或居住地,例如:“Sono di Roma”(我来自罗马)。 4. **基本信息**:分享你的职业和...

    Risk:风险风险团队(Alen、Shane、Alex、Sandro)

    风险团队,如"Alen、Shane、Alex、Sandro"这样的组合,通常负责识别、评估、优先级排序以及应对可能对项目产生负面影响的风险因素。这个团队的角色是确保项目的稳定性和成功性,通过预防或最小化潜在问题来保护公司...

    一款占用内存小,速度超快的免安装浏览器,推荐使用!

    ....-- sandro26 GB超级稳定的性能及较快的速度和较小的资源占用正是现在其他IE内核浏览器所欠缺的,也是我们最需要的,因此GB是最好的IE内核浏览器。 ....-- wjse 同样很喜欢GB!!喜欢她的纤细、喜欢她的自由制定 ...

    Matplotlib for Python Developers.pdf

    此外,文档列出了多位对本书有贡献的人物,包括作者Sandro Tosi、编辑团队负责人Akshara Aware、审阅者Michael Droettboom和Reinier Heeres、获取编辑Usha Iyer、开发编辑Rakesh Shejwal、技术编辑Namita Sahni、...

Global site tag (gtag.js) - Google Analytics