题解

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. ...

Blue Jeans (POJ-3080) 题面 The Genographic Project is a research partnership between IBM and The National Geographic Society that is analyzing DNA from hundreds of thousands of contributors to map how the Earth was populated. As an IBM researcher, you have been tasked with writing a program that will find commonalities amongst given snippets of DNA that can be correlated with individual survey information to identify new genetic markers. A DNA base sequence is noted by listing the nitrogen bases in the order in which they are found in the molecule. There are four bases: adenine (A), thymine (T), guanine (G), and cytosine (C). A 6-base DNA sequence could be represented as TAGACC. ...

Power Strings (POJ-2406) 题面 Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n). 输入 Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case. ...

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). ...

Partitioning Game(LightOJ-1199) 题面 Alice and Bob are playing a strange game. The rules of the game are: Initially there are n piles. A pile is formed by some cells. Alice starts the game and they alternate turns. In each tern a player can pick any pile and divide it into two unequal piles. If a player cannot do so, he/she loses the game. Now you are given the number of cells in each of the piles, you have to find the winner of the game if both of them play optimally. ...

Crazy Calendar(LightOJ-1393) 题面 2011 was a crazy year. Many people all over the world proposed on 11-11-11, married on 11-11-11, some even went through surgery only to have 11-11-11 as their child’s birth date. How crazy people can be! Don’t they see there is a “20” hidden? Then what to do? A very elegant solution came from ARR, a very famous and funny character - why do we need to follow Christian (or some calls it Gregorian) calendar? Why don’t we start our own calendar on the day of marriage? And those who like to celebrate their marriage ceremony too frequent, why don’t they declare only 1 day per year. In that fashion they can celebrate their anniversary every day. And may be one minute a year or a second or … Uh.. getting complex. Let’s back to the title. From now, we start to have a new calendar system, “Kisu Pari Na”. And we hope to update this calendar on every national contest. ...

Misere Nim(LightOJ-1253) 题面 Alice and Bob are playing game of Misère Nim. Misère Nim is a game playing on k piles of stones, each pile containing one or more stones. The players alternate turns and in each turn a player can select one of the piles and can remove as many stones from that pile unless the pile is empty. In each turn a player must remove at least one stone from any pile. Alice starts first. The player who removes the last stone loses the game. ...

Matrix Game(LightOJ-1247) 题面 Given an m x n matrix, where m denotes the number of rows and n denotes the number of columns and in each cell a pile of stones is given. For example, let there be a 2 x 3 matrix, and the piles are 2 3 8 5 2 7 That means that in cell(1, 1) there is a pile with 2 stones, in cell(1, 2) there is a pile with 3 stones and so on. ...

Left Right(LightOJ-1192) 题面 Two players, Alice and Bob are playing a strange game in a 1 x n board. The cells are numbered from 0 to n-1, where the left most cell is marked as cell 0. Each cell can contain at most one piece. There are two kinds of pieces, gray and white. Alice moves all the gray pieces, and bob moves all the white ones. The pieces alternate, that is, leftmost piece is gray, next is white, next to that is gray, then it’s white again, and so on. There will always be equal number of black and gray pieces. Alice can only move pieces to the right. Bob can only move pieces to the left. ...

Incredible Chess(LightOJ-1186) 题面 You are given an n x n chess board. Only pawn is used in the ‘Incredible Chess’ and they can move forward or backward. In each column there are two pawns, one white and one black. White pawns are placed in the lower part of the board and the black pawns are placed in the upper part of the board. The game is played by two players. Initially a board configuration is given. One player uses white pieces while the other uses black. In each move, a player can move a pawn of his piece, which can go forward or backward any positive integer steps, but it cannot jump over any piece. White gives the first move. ...

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次怎样取子? ...

Beans Game(ZOJ-3057) 题面 There are three piles of beans. TT and DD pick any number of beans from any pile or the same number from any two piles by turns. Who get the last bean will win. TT and DD are very clever. 输入 Each test case contains of a single line containing 3 integers a b c, indicating the numbers of beans of these piles. It is assumed that 0 <= a,b,c <= 300 and a + b + c > 0. ...

A simple stone game(POJ-3922) 题面 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. ...

Light Switching Game(POJ-3533) 题面 The Light Switching Game is played on a 1000 × 1000 × 1000 cube of cells with a light in each cell, as Figure.1 shows. Initially, most of the lights are off while exactly N lights are on. Two players take moves alternately. A move consists of switching the lights at the corners of a cuboid, i.e. (x1,y1,z1), (x1,y1,z2), (x1,y2,z1), (x1,y2,z2), (x2,y1,z1), (x2,y1,z2), (x2,y2,z1), (x2,y2,z2) where 1 ≤ x1 ≤ x2 ≤ 1000, 1 ≤y1 ≤ y2 ≤ 1000, 1 ≤z1 ≤ z2 ≤ 1000 and the light at the corner (x2,y2,z2) must be on (and turned off after the move). Notice the cuboid is possibly degenerated to a rectangle, a line or even a single cell so that the player may also switching four, two or one besides eight lights in a move. The player loses the game when he can not take a move. ...