HDU

Theme Section(HDU-4763) 题面 It’s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a ’theme section’. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of ‘EAEBE’, where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters ‘a’ - ‘z’. ...

Wow! Such Doge!(HDU-4847) 题面 Chen, Adrian (November 7, 2013). “Doge Is An Ac- tually Good Internet Meme. Wow.”. Gawker. Retrieved November 22, 2013. Doge is an Internet meme that became popular in 2013. The meme typically con- sists of a picture of a Shiba Inu dog ac- companied by multicolored text in Comic Sans MS font in the foreground. The text, representing a kind of internal monologue, is deliberately written in broken English, and usually contains the word “wow” and the phrases “such x”, “much x”, “many x”, “very x” and “so x”. Kabosu, the Shiba Inu featured in the original meme, was first pictured in a 2010 blog post by Atsuko Sato, a Japanese kindergarten teacher. Afterwards, varia- tions of the pictures using overlaid Comic Sans text were posted from a Tumblr blog, Shiba Confessions. However, the use of the intentionally misspelled “doge” dates back to June 2005, when it was mentioned in an episode of Homestar Runners puppet series. In August 2013, images of the meme were spammed on Reddit’s r/MURICA subreddit by 4chan’s random imageboard, /b/. A search of the term doge on Google Trends shows an explosion of popularity occurring in October 2013, and more so in the following month. By November 2013, the meme had become widespread on the Internet. Google later created a Doge Easter egg: when doge meme was entered into the YouTube search bar, all of the site’s text would be displayed in colorful Comic Sans, similar to the kind used by the meme. The meme was ranked #12 on MTV’s list of “50 Things Pop Culture Had Us Giving Thanks For” in 2013. Io9 compared the internal dialog of the Shiba Inu dogs to lolcat-speak. The image most commonly associated with the meme is of a female Shiba Inu named Kabosu, taken from a Japanese blog documenting the dog’s daily activities. The spelling of doge has several variants, leading to debate on its actual pronunciation. On December 13, Doge was named the “top meme” of 2013 by Know Your Meme. In December 2013, the Dogecoin was introduced as a new cryptocurrency, making it the first cryptocurrency to be based on an Internet meme; the viral phenomenon, along with usage of the Comic Sans MS typeface, gave it “the Internet density of a large star” according to Medium writer Quinn Norton. In late December 2013, members of the U.S. Congress produced material in the meme’s style. Huffington Post commented that Doge was “killed” because of the Congress members’ usage of the meme. By early 2014, Doge’s popularity was sustained by internet communities on social media, accompanied by the rapid growth and acceptance of Dogecoin. In April 2014, Doge experienced a second major media resurgence due to revelations of the Dogecoin community’s intent to sponsor Josh Wise in NASCAR and place a picture of the Shiba Inu on his vehicle. ...

最长回文(HDU-3068) 题面 给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等 ...

Girls’ research(HDU-3294) 题面 One day, sailormoon girls are so delighted that they intend to research about palindromic strings. Operation contains two steps: First step: girls will write a long string (only contains lower case) on the paper. For example, “abcde”, but ‘a’ inside is not the real ‘a’, that means if we define the ‘b’ is the real ‘a’, then we can infer that ‘c’ is the real ‘b’, ’d’ is the real ‘c’ ……, ‘a’ is the real ‘z’. According to this, string “abcde” changes to “bcdef”. Second step: girls will find out the longest palindromic string in the given string, the length of palindromic string must be equal or more than 2. ...

吉哥系列故事-完美队形II(HDU-4513) 题面 吉哥又想出了一个新的完美队形游戏！ 假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] … h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形： ...

Best Reward(HDU-3613) 题面 After an uphill battle, General Li won a great victory. Now the head of state decide to reward him with honor and treasures for his great exploit. One of these treasures is a necklace made up of 26 different kinds of gemstones, and the length of the necklace is n. (That is to say: n gemstones are stringed together to constitute this necklace, and each of these gemstones belongs to only one of the 26 kinds.) ...

How many(HDU-2609) 题面 Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me How many kinds of necklaces total have.(if two necklaces can equal by rotating ,we say the two necklaces are some). For example 0110 express a necklace, you can rotate it. 0110 -> 1100 -> 1001 -> 0011-> 0110. 输入 The input contains multiple test cases. Each test case include: first one integers n. (2<=n<=10000) Next n lines follow. Each line has a equal length character string. (string only include ‘0’,‘1’). ...

String Problem(HDU-3374) 题面 Give you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings: String Rank SKYLONG 1 KYLONGS 2 YLONGSK 3 LONGSKY 4 ONGSKYL 5 NGSKYLO 6 GSKYLON 7 and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once. Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also. ...

Corporate Identity(HDU-2328) 题面 Beside other services, ACM helps companies to clearly state their “corporate identity”, which includes company logo but also other signs, like trademarks. One of such companies is Internet Building Masters (IBM), which has recently asked ACM for a help with their new identity. IBM do not want to change their existing logos and trademarks completely, because their customers are used to the old ones. Therefore, ACM will only change existing trademarks instead of creating new ones. ...

Substrings(HDU-1238) 题面 You 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 strings. 输入 The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string. ...

Clairewd’s message(HDU-4300) 题面 Clairewd 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 letter of these messages would be transfered to another one according to a conversion table. Unfortunately, GFW(someone’s name, not what you just think about) has detected their action. He also got their conversion table by some unknown methods before. Clairewd was so clever and vigilant that when she realized that somebody was monitoring their action, she just stopped transmitting messages. But GFW knows that Clairewd would always firstly send the ciphertext and then plaintext(Note that they won’t overlap each other). But he doesn’t know how to separate the text because he has no idea about the whole message. However, he thinks that recovering the shortest possible text is not a hard task for you. Now GFW will give you the intercepted text and the conversion table. You should help him work out this problem. ...

Count the string(HDU-3336) 题面 It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example: s: “abab” The prefixes are: “a”, “ab”, “aba”, “abab” For each prefix, we can count the times it matches in s. So we can see that prefix “a” matches twice, “ab” matches twice too, “aba” matches once, and “abab” matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For “abab”, it is 2 + 2 + 1 + 1 = 6. The answer may be very large, so output the answer mod 10007. ...

Simpsons’ Hidden Talents(HDU-2594) 题面 Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had. Marge: Yeah, what is it? Homer: Take me for example. I want to find out if I have a talent in politics, OK? Marge: OK. Homer: So I take some politician’s name, say Clinton, and try to find the length of the longest prefix in Clinton’s name that is a suffix in my name. That’s how close I am to being a politician like Clinton Marge: Why on earth choose the longest prefix that is a suffix??? Homer: Well, our talents are deeply hidden within ourselves, Marge. Marge: So how close are you? Homer: 0! Marge: I’m not surprised. Homer: But you know, you must have some real math talent hidden deep in you. Marge: How come? Homer: Riemann and Marjorie gives 3!!! Marge: Who the heck is Riemann? Homer: Never mind. Write a program that, when given strings s1 and s2, finds the longest prefix of s1 that is a suffix of s2. ...

Period (HDU-1358) 题面 For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK , that is A concatenated K times, for some string A. Of course, we also want to know the period K. ...

Cyclic Nacklace (HDU-3746) 题面 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 tide over the last days. Being inspired by the entrepreneurial spirit of “HDU CakeMan”, he wants to sell some little things to make money. Of course, this is not an easy task. ...

剪花布条 (HDU-2087) 题面 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？ ...

Number Sequence (HDU-1711) 题面 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], …… , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one. ...

Paint Chain(HDU-3980) 题面 Aekdycoin and abcdxyzk are playing a game. They get a circle chain with some beads. Initially none of the beads is painted. They take turns to paint the chain. In Each turn one player must paint a unpainted beads. Whoever is unable to paint in his turn lose the game. Aekdycoin will take the first move. Now, they thought this game is too simple, and they want to change some rules. In each turn one player must select a certain number of consecutive unpainted beads to paint. The other rules is The same as the original. Who will win under the rules ?You may assume that both of them are so clever. ...

Be the Winner(HDU-2509) 题面 Let’s consider m apples divided into n groups. Each group contains no more than 100 apples, arranged in a line. You can take any number of consecutive apples at one time. For example “@@@” can be turned into “@@” or “@” or “@ @"(two piles). two people get apples one after another and the one who takes the last is the loser. Fra wants to know in which situations he can win by playing strategies (that is, no matter what action the rival takes, fra will win). ...

Stone Game II (HDU-4388) 题面 Stone Game II comes. It needs two players to play this game. There are some piles of stones on the desk at the beginning. Two players move the stones in turn. At each step of the game the player should do the following operations. First, choose a pile of stones. (We assume that the number of stones in this pile is n) Second, take some stones from this pile. Assume the number of stones left in this pile is k. The player must ensure that 0 < k < n and (k XOR n) < n, otherwise he loses. At last, add a new pile of size (k XOR n). Now the player can add a pile of size ((2*k) XOR n) instead of (k XOR n) (However, there is only one opportunity for each player in each game). The first player who can’t do these operations loses. Suppose two players will do their best in the game, you are asked to write a program to determine who will win the game. ...

悼念512汶川大地震遇难同胞——选拔志愿者(HDU-2188) 题面 对于四川同胞遭受的灾难，全国人民纷纷伸出援助之手，几乎每个省市都派出了大量的救援人员，这其中包括抢险救灾的武警部队，治疗和防疫的医护人员，以及进行心理疏导的心理学专家。根据要求，我校也有一个奔赴灾区救灾的名额，由于广大师生报名踊跃，学校不得不进行选拔来决定最后的人选。经过多轮的考核，形势逐渐明朗，最后的名额将在“林队”和“徐队”之间产生。但是很巧合，2个人的简历几乎一模一样，这让主持选拔的8600很是为难。无奈，他决定通过捐款来决定两人谁能入选。 选拔规则如下： 1、最初的捐款箱是空的； 2、两人轮流捐款，每次捐款额必须为正整数，并且每人每次捐款最多不超过m元(1<=m<=10)。 3、最先使得总捐款额达到或者超过n元（0<n<10000）的一方为胜者，则其可以亲赴灾区服务。 我们知道，两人都很想入选志愿者名单，并且都是非常聪明的人，假设林队先捐，请你判断谁能入选最后的名单？ ...

邂逅明下(HDU-2897) 题面 当日遇到月，于是有了明。当我遇到了你，便成了侣。 那天，日月相会，我见到了你。而且，大地失去了光辉，你我是否成侣？这注定是个凄美的故事。（以上是废话） 小t和所有世俗的人们一样，期待那百年难遇的日食。驻足街头看天，看日月渐渐走近，小t的脖子那个酸呀（他坚持这个姿势已经有半个多小时啦）。他低下仰起的头，环顾四周。忽然发现身边竟站着位漂亮的mm。天渐渐暗下，这mm在这街头竟然如此耀眼，她是天使吗？站着小t身边的天使。 小t对mm惊呼：“缘分呐~~”。mm却毫不含糊：“是啊，500年一遇哦！”（此后省略5000字….） 小t赶紧向mm要联系方式，可mm说：“我和你玩个游戏吧，赢了，我就把我的手机号告诉你。”小t，心想天下哪有题目能难倒我呢，便满口答应下来。mm开始说游戏规则：“我有一堆硬币，一共7枚，从这个硬币堆里取硬币，一次最少取2枚，最多4枚，如果剩下少于2枚就要一次取完。我和你轮流取，直到堆里的硬币取完，最后一次取硬币的算输。我玩过这个游戏好多次了，就让让你，让你先取吧~” 小t掐指一算，不对呀，这是不可能的任务么。小t露出得意的笑：“还是mm优先啦，呵呵~”mm霎时愣住了，想是对小t的反应出乎意料吧。 她却也不生气：“好小子，挺聪明呢，要不这样吧，你把我的邮箱给我，我给你发个文本，每行有三个数字n，p，q，表示一堆硬币一共有n枚，从这个硬币堆里取硬币，一次最少取p枚，最多q枚，如果剩下少于p枚就要一次取完。两人轮流取，直到堆里的硬币取完，最后一次取硬币的算输。对于每一行的三个数字，给出先取的人是否有必胜策略，如果有回答WIN，否则回答LOST。你把对应的答案发给我，如果你能在今天晚上8点以前发给我正确答案，或许我们明天下午可以再见。” 小t二话没说，将自己的邮箱给了mm。当他兴冲冲得赶回家，上网看邮箱，哇！mm的邮件已经到了。他发现文本长达100000行，每行的三个数字都很大，但是都是不超过65536的整数。小t看表已经下午6点了，要想手工算出所有结果，看来是不可能了。你能帮帮他，让他再见到那个mm吗？ ...

取石子游戏(HDU-2516) 题面 1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win". ...

A simple stone game(HDU-2486) 题面 After he has learned how to play Nim game, Mike begins to try another stone game which seems much easier. The game goes like this: Two players start the game with a pile of n stones. They take stones from the pile in turn and every time they take at least one stone. The one who goes first can take at most n-1 stones for his first move. From then on a player can take at most k times as many stones as his opponent has taken last time. For example, if one player take m stones in his turn, then the other player can take at most k * m stones next time. The player who takes the last stone wins the game. Suppose that those two players always take the best moves and never make mistakes, your job is to find out who will definitely win the game. ...

取(2堆)石子游戏(HDU-2177) 题面 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子? ...

Switch lights(HDU-3404) 题面 lxhgww is playing a game with his computer Deep Blue. The game is played on a matrix containing lights. At first, some lights are on, while others are off. lxhgww and Deep Blue take turns to switch the lights. For each step, the player should choose a rectangle in the matrix: (x1 , y1) , (x1 , y2) , (x2 , y1) , (x2 , y2) , (x1<=x2,y1<=y2, the light at (x2, y2) should be on) and change the lights’ status on the four vertex of the rectangle, namely on to off, and off to on. The player turns all the lights off wins the game. Notice the rectangle is possibly degenerated to line or even a single cell so that the player may also switch two or one besides four lights in a move. Deep Blue’s strategy is perfect, if it has a chance to win, never will it lose. Does lxhgww have a chance to win if he takes the first step? ...

Fibonacci again and again(HDU-1848) 题面 任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生，它是这样定义的： F(1)=1; F(2)=2; F(n)=F(n-1)+F(n-2)(n>=3); 所以，1,2,3,5,8,13……就是菲波那契数列。 在HDOJ上有不少相关的题目，比如1005 Fibonacci again就是曾经的浙江省赛题。 今天，又一个关于Fibonacci的题目出现了，它是一个小游戏，定义如下： 1、 这是一个二人游戏; 2、 一共有3堆石子，数量分别是m, n, p个； 3、 两人轮流走; 4、 每走一步可以选择任意一堆石子，然后取走f个； 5、 f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8…等数量）； 6、 最先取光所有石子的人为胜者； ...

Brave Game(HDU-1846) 题面 十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。 今天，大家选择上机考试，就是一种勇敢（brave）的选择；这个短学期，我们讲的是博弈（game）专题；所以，大家现在玩的也是“勇敢者的游戏”，这也是我命名这个题目的原因。 当然，除了“勇敢”，我还希望看到“诚信”，无论考试成绩如何，希望看到的都是一个真实的结果，我也相信大家一定能做到的~ ...

Good Luck in CET-4 Everybody!(HDU-1847) 题面 大学英语四级考试就要来临了，你是不是在紧张的复习？也许紧张得连短学期的ACM都没工夫练习了，反正我知道的Kiki和Cici都是如此。当然，作为在考场浸润了十几载的当代大学生，Kiki和Cici更懂得考前的放松，所谓“张弛有道”就是这个意思。这不，Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。 “升级”？“双扣”？“红五”？还是“斗地主”？ 当然都不是！那多俗啊~ 作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的： 1、 总共n张牌; 2、 双方轮流抓牌； 3、 每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…） 4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者； 假设Kiki和Cici都是足够聪明（其实不用假设，哪有不聪明的学生~），并且每次都是Kiki先抓牌，请问谁能赢呢？ 当然，打牌无论谁赢都问题不大，重要的是马上到来的CET-4能有好的状态。 ...

Rabbit and Grass(HDU-1849) 题面 大学时光是浪漫的，女生是浪漫的，圣诞更是浪漫的，但是Rabbit和Grass这两个大学女生在今年的圣诞节却表现得一点都不浪漫：不去逛商场，不去逛公园，不去和AC男约会，两个人竟然猫在寝食下棋…… 说是下棋，其实只是一个简单的小游戏而已，游戏的规则是这样的： 1、棋盘包含1*n个方格，方格从左到右分别编号为0，1，2，…，n-1； 2、m个棋子放在棋盘的方格上，方格可以为空，也可以放多于一个的棋子； 3、双方轮流走棋； 4、每一步可以选择任意一个棋子向左移动到任意的位置（可以多个棋子位于同一个方格），当然，任何棋子不能超出棋盘边界； 5、如果所有的棋子都位于最左边（即编号为0的位置），则游戏结束，并且规定最后走棋的一方为胜者。 ...