sdut专题

SDUT OJ 2798小鑫的城堡并查集

题目描述从前有一个国王，他叫小鑫。有一天，他想建一座城堡，于是，设计师给他设计了好多简易图纸，主要是房间的连通的图纸。小鑫希望任意两个房间有且仅有一条路径可以相通。小鑫现在把设计图给你，让你帮忙判断设计图是否符合他的想法。比如下面的例子，第一个是符合条件的，但是，第二个不符合，因为从5到4有两条路径（5-3-4和5-6-4）。输入多组输入，每组第一行包含一个整数m（m

sdut 1225 编辑距离(dp)

题目描述假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。例如：a="AB

hdu 1429胜利大逃亡(续) / sdut 2193 救基友记3(BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1429 做了热身赛http://blog.csdn.net/u013081425/article/details/21740001 之后发现这道题好水，之前怎么没刷到呢。。同样标记数组增加一维，标记到某一点时他拥有钥匙的状态，因为有10种钥匙，所以mark[][][1<<10+10]来标记每到一点的状态。

SDUT OJ 2892——字典树

A Time Limit: 60ms Memory limit: 65536K 有疑问？点这里^_^ 题目描述给出n(1<= n && n <= 2*10^6)个字符串,每个字符串只包含小写英文字母，且最多有五个。问这n个字符串中出现次数最多的有多少个。输入单组输入。第一行输入一个数字n，接下来n行，每行包含一个字符串。输出

校赛 SDUT OJ2860生日Party（BFS)

题目地址：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2860 唉。。校赛的时候把这题用搜索的时间复杂度2^15次方想成了15^15次方。。。。所以没写。。。后来用的最短路的floyd算法改成了最长路做的，但有一些细节不好处理，调了会没调出来。。赛后才想到用暴搜不会超时。。于是补完线代后怒敲暴搜代码

SDUT 3061 聪明的玛雅（状压DP）

题目地址：SDUT 3061 这题的比赛的时候的后台数据是错的。。。好坑啊。。。。就不吐槽出题人了。。比赛的时候我的思路是错的，漏考虑了一种情况。应该把所有状态下的最短距离都要求出来，而我当时的思路是按照前面能选两个则选两个的贪心思路来状压，但是有的时候可以最多走奇数个并且没全走完，这种情况下就不对了。正确思路是每次找两个没走过的状态，分成选一个和选两个两种情况来DP。然后最后找所有状态

SDUT OJ 3045 迷之图论 (树的直径)

题目地址：SDUT OJ 3045 这题比赛的时候想的差不多。。但是总是觉得不对。。写了一次就没再写，然后删了。。当时没想到的是第二次求出来的就是最长链。。当时想到的两次bfs找最大值（这一种方法其实结果也对。。TAT。。），还有找到点后在回溯减去重点等等。。但总觉得好像都不太对。。。赛后才知道这题原来是树的直径。。。。。牡丹江区域现场赛的时候遇到过，不过赛后也没看。。。找树的直径的方法其实

递推8-----7-8 sdut-C语言实验-王小二切饼0)

7-8 sdut-C语言实验-王小二切饼分数 20 全屏浏览切换布局作者马新娟单位山东理工大学王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切n(1<=n<=100)刀最多能分成多少块？” 输入格式: 输入切的刀数n。输出格式: 输出为切n刀最多切的饼的块数。输入样例: 在这里给出一组输入。例如： 100 输出样例:

sdut——魔幻数字47

题目描述数字47一向被数学界的人认为是很魔幻的一个数字，和47有关的任务被认为是魔幻任务。现在有一个简单的魔幻任务，给定a和b，打印所有在以a,b为端点的闭区间中最后两位为47的整数，你能一次AC吗？？输入第一行为一个整数n，表示有多少组测试数据。(n <= 100) 第2-n+1行，每行两个整数，分别代表a,b。(a,b <= 10000) 输出对于每组

sdut——选夫婿1

题目描述倾国倾城的大家闺秀潘小姐要选夫婿啦！武林中各门各派，武林外各大户人家，闻讯纷纷前来，强势围观。前来参与竞选的男生藏龙卧虎，高手云集，才子遍布，帅哥纷纭，更不乏富二代，官二代，可谓声势空前。每个人参与竞选的帅哥除了进行一段激情洋溢的求婚演讲以外，还要报上自己姓名、身高和体重，以及个人简历。最后再进行文武选拔，最后夺魁者方能得到潘小姐的芳心。潘小姐不爱名利

sdut——The area

题目描述 Ignatius bought a land last week, but he didn't know the area of the land because the land is enclosed by a parabola and a straight line. The picture below shows the area. Now given all the int

sdut——下沉的船

题目描述身份优先级: woman = child > man > captain. 多组数据（少于组），每一组有一个整数（，代表船上有个人，接下来行，每行有一个名字和他的身份。名字字符长度小于。数据保证不存在重名，注意可能存在多名船长输出输出n行，每一行输出一个名字，先上船的名字在前面。示例输入 6Jack captainAlice womanChar

链表5（考试用）7-5 sdut-C语言实验-链表的逆置

7-5 sdut-C语言实验-链表的逆置分数 20 全屏浏览作者马新娟单位山东理工大学输入多个整数，以-1作为结束标志，顺序建立一个带头结点的单链表，之后对该单链表的数据进行逆置，并输出逆置后的单链表数据。输入格式: 输入多个整数，以-1作为结束标志。输出格式: 输出逆置后的单链表数据。输入样例: 12 56 4 6 55 15 33 62 -1 输

链表4（法二）------7-4 sdut-C语言实验-单链表中重复元素的删除

7-4 sdut-C语言实验-单链表中重复元素的删除分数 20 全屏浏览切换布局作者马新娟单位山东理工大学按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。输入格式: 第一行输入元素个数 n (1 <= n <= 15)；第二行输入 n 个整数，保证在 int 范围内。输出格式: 第一行输

sdut pta 链表3(优化)-----7-3 sdut-C语言实验-链表的结点插入

7-3 sdut-C语言实验-链表的结点插入分数 20 全屏浏览切换布局作者马新娟单位山东理工大学给出一个只有头指针的链表和 n 次操作，每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。输入格式: 多组输入。每组数据首先输入一个整数n(n∈[1,100])，代表有n次操作。接下来的n行，每行有两个整数M

SDUT 链表9-------7-9 sdut-C语言实验-约瑟夫问题

7-9 sdut-C语言实验-约瑟夫问题分数 20 全屏浏览切换布局作者马新娟单位山东理工大学 n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。请输出最后一个人的编号。输入格式: 输入n和m值。输出格式: 输出胜利者的编号。输入

sdut lava lab7.5

7-5 sdut-JAVA-Valid Password 分数 9 全屏浏览切换布局作者马新娟单位山东理工大学 You have been requested to write a method that will be used when a user wishes to change his/her password. Your method should acc

sdut java lab7.2

7-2 sdut-JAVA-Words Containing AB 分数 9 全屏浏览切换布局作者马新娟单位山东理工大学 Write a program that requests a word as input containing the two letters a and b (in this order). Examples of valid words wo

sdut java实验7.1

7-1 sdut-JAVA-Pig Latin 分数 12 全屏浏览切换布局作者马新娟单位山东理工大学 Write a program that requests a word as input, translates the word into Pig Latin and outputs the word input and its equivalent in Pi

sdut 3553 sdut第八届校赛--A*B

题目链接：点击打开链接题目描述一天小白如往常一样约小黑粗去玩。他们两人划着木船在海上荡阿荡。小白突然跟小黑说“小黑，我来烤烤你" 黑"纳尼" 白"不不不，我来考考你。我这有一个整数n，你能求出1~n中奇数加和与偶数加和的乘积么？" 黑"恩……" 噗通。。。由于小黑迟迟没有得到答案，小白睡了过去，因受力不平衡。友谊的小船居然(终于)翻了…… 如果再给小黑一次机会，小黑会…

sdut 3555 sdut第八届校赛--小白の人品测试

题目链接：点击打开链接题目描述现在有n个人，编号从1到n ，每个人有一个人品值这是一个赤裸裸的金钱关系的世界如果小白想要小黑直接帮他一个忙，他需要支付的代价为 abs(小白的人品 - 小黑的人品)。小白也可以找小金，然后小金去拜托小黑帮他，这样他就要支付双份的代价，具体的，代价为 abs(小白的人品 - 小金的人品)+abs(小金的人品 - 小黑的人品)

sdut第八届校赛--小厚的三角形

题目链接：点击打开链接题目描述一天，小厚的好朋友给了他n个面积为1的正三角形。小厚比较喜欢规整的形状，所以他想要用这些正三角形拼成一个正多边形。要求恰好拼为一个正多边形，不可裁剪，多边形内部也不能有空隙。小厚想知道他能拼出的最大的一个正多边形面积为多少。正三角形可以有剩余。输入多组输入，输入到文件结束(EOF) 每组输入，输入一个正整数n（1 <= n <= 100

sdut第八届校赛－－简单题

题目链接：点击打开链接题目描述小明最近开始近视了，所以经常地看错东西，比如在他的眼中'0'和'O'是没有区别的，虽然看上去确实没有什么区别，但是第一个是数字中的0，第二个却是大写的'o',又比如'1','l'和'I'他现在看成是相同的，但是他们真的相同吗？第一个是数字1，第二个是小写的'L'，第三个是大写的'i',所以小明经常办糊涂事，今天老师给小明一份交作业的记录名单，让小明

sdut第八届校赛--小白的追求

题目链接：点击打开链接题目描述小白和小黑的小船翻了以后，小白就去追妹子去啦。但是问题随之而来，小白共有10个目标，编号0-9，但是小白只能追求一个，所以小白就去找小金请教如何解决，小金什么都没有说，用手指了一下小白，小白瞬间恍然大悟，“你是让我顺从本心吗？？”，小金说：“我让你哪来的滚哪去，正在写代码，没时间搭理你”。。。。。。，但是问题总要解决，小白决定听天由命，所以小白在小金的

sdut oj 3266 ///山理工第七届校赛--最大收益问题

题目链接：点击打开链接题目描述铁牌狗最近迷上了一款游戏，但铁牌狗实在是太笨了，他还是要请求你的帮助。有一个n行m列的矩阵A，矩阵A中每个数字均为正整数，现在铁牌狗要在其中选出一个r行c列的子矩阵B，这个子矩阵B中各个数字之和即为铁牌狗的得分，请你帮铁牌狗计算出他的最高得分是多少。输入首先输入一个组数T(1 <= T <= 10),表示接下来要输入T组数据。

sdut 3274 山理工第七届校赛--完美素数

题目链接：点击打开链接题目描述我们定义：如果一个数为素数，且这个数中含有7或3,那么我们称这个数为完美素数。素数的定义为：一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。我们的任务是判断一个数是不是完美素数，是输出YES，否则输出NO . 输入输入数据有多组测试用例，每组测试的第一行为一个整数n（1<=n<=100），下面n行每行有一个正整数x（2<=