poj_3982_ProblemD_序列.cpp

Problem Links:

poj3982,

Problem:

序列

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3612		Accepted: 1571

Description

数列A满足An = An-1 + An-2 + An-3, n >= 3

编写程序，给定A0, A1 和 A2, 计算A99

Input

输入包含多行数据

每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767)
数据以EOF结束

Output

对于输入的每一行输出A99的值

Sample Input

1 1 1

Sample Output

69087442470169316923566147

Source

Solution:

Use string instead of the long long. The system won't allocate that much memory for it.

Source Code:

//Tue Nov 23 14:30:01 CST 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

string add(string A, string B)
{
    int sz = max(A.size(), B.size());
    int flag = 0;
    if(sz > (int)A.size()) A += string(sz-A.size(), '0');
    if(sz > (int)B.size()) B += string(sz-B.size(), '0');
    string ret = "";
    for(int i=0; i<sz; i++)
    {
        int temp = A[i]-'0' + B[i] - '0' + flag;
        flag = temp > 9 ? 1 : 0;
        temp %= 10;
        ret += ('0' + temp);
    }
    if(flag == 1)
        ret += ('0' + flag);
//  cout << A << ", " << B << ", " << ret << endl;
    return ret;
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
    string a0, a1, a2;
    while (cin >> a0 >> a1 >> a2)
    {
        vector<string> ret(100, "");
        reverse(a0.begin(), a0.end());
        reverse(a1.begin(), a1.end());
        reverse(a2.begin(), a2.end());
        ret[0] = a0;
        ret[1] = a1;
        ret[2] = a2;
        for (int i = 3; i < 100; i++)
        {
            ret[i] = add(ret[i - 1], add(ret[i - 2], ret[i - 3]));
        }
        reverse(ret[99].begin(), ret[99].end());
        cout << ret[99] << endl;
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

poj_3981_ProblemC_字符串替换.cpp

Problem Links:

poj3981,

Problem:

字符串替换

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3931		Accepted: 1933

Description

编写一个C程序实现将字符串中的所有"you"替换成"we"

Input

输入包含多行数据

每行数据是一个字符串，长度不超过1000
数据以EOF结束

Output

对于输入的每一行，输出替换后的字符串

Sample Input

you are what you do

Sample Output

we are what we do

Source

Solution:

Straight forward.

Source Code:

//Tue Nov 23 14:10:28 CST 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
    //  freopen("input.in", "r", stdin);
    //  freopen("output.out", "w", stdout);
    string str;
    while (getline(cin, str))
    {
        int sz = str.size();
        string ret = "";
        for (int i = 0; i < sz;)
        {
            if (str[i] != 'y')
            {
                ret += str[i];
                i++;
            }
            else
            {
                if (i + 2 < sz && str[i + 1] == 'o' && str[i + 2] == 'u')
                {
                    ret += "we";
                    i += 3;
                }
                else
                {
                    ret += str[i];
                    i++;
                }
            }
        }
        cout << ret << endl;
    }
    //  fclose(stdin);
    //  fclose(stdout);
    return 0;
}

poj_3980_ProblemB_取模运算.cpp

Problem Links:

poj3980,

Problem:

取模运算

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4360		Accepted: 2732

Description

编写一个C函数mod(int n, int m),实现取模运算%

Input

输入包含多行数据

每行数据是两个整数a, b (1 <= a, b <= 32767)
数据以EOF结束

Output

于输入的每一行输出a%b

Sample Input

5 3
100 2

Sample Output

2
0

Source

Solution:

Straight forward.

Take care of: 1st, use scanf instead of cin.

Source Code:

//Tue Nov 23 13:57:52 CST 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int mod(int m, int n)
{
    return m%n;
}

int main( int argc, const char* argv[] )
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
    int a, b;
    while(scanf("%d%d", &a, &b) != EOF)
    {
        printf("%d\n", mod(a, b));
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

poj_3979_ProblemA_分数加减法.cpp

Problem Links:

poj3979,

Problem:

分数加减法

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5903		Accepted: 1884

Description

编写一个C程序，实现两个分数的加减法

Input

输入包含多行数据
每行数据是一个字符串，格式是"a/boc/d"。

其中a, b, c, d是一个0-9的整数。o是运算符"+"或者"-"。

数据以EOF结束
输入数据保证合法

Output

对于输入数据的每一行输出两个分数的运算结果。
注意结果应符合书写习惯，没有多余的符号、分子、分母，并且化简至最简分数

Sample Input

1/8+3/8
1/4-1/2
1/3-1/3

Sample Output

1/2
-1/4
0

Source

Solution:

PS: Take care of each situation that could happen.

1st, if the numerator is 0;

2nd, if they have gcd greater than 1 after the operation.

Source Code:

//Mon Nov 22 23:32:14 CST 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
    int a, b, c, d;
    char ch1, ch2;
    while (cin >> a >> ch1 >> b >> ch2 >> c >> ch1 >> d)
    {
        //cout << a << b << c << d << endl;

        int temp = b / gcd(b, d) * d;
        int flag = 1;
        switch (ch2)
        {
        case '+':
            a = a * (temp / b) + c * (temp / d);
            break;
        case '-':
            a = a * (temp / b) - c * (temp / d);
            flag = a < 0 ? -1 : 1;
            a = a < 0 ? -a : a;
        }
        int temp2 = gcd(a, temp);
        //cout << temp2 << endl;
        a /= temp2;
        temp /= temp2;
        if(a == 0)  //One WA here w/o considering if a is 0;
        {
            cout << "0" << endl;
            continue;
        }
        if(temp == 1)
        {
            cout << a*flag << endl; //One WA here w/o *flag;
            continue;
        }
        cout << a * flag << "/" << temp << endl;
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

poj_3507_Judging_Olympia.cpp

Problem Links:

poj3507,

Problem:

Judging Olympia

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5058		Accepted: 2430

Description

For years, a group of Regional Contest Directors (RCDs) of the ACM International Collegiate Programming Contest (ICPC) have been unsatisfied with the way contest submissions get ranked. The group sees it is academically wrong to emphasize the importance of program correctness, disregarding the “quality” of the program itself. After all, programming as a profession promotes design, style, maintainability, etc. and not just correctness. The group’s suggestion is to have a panel of six judges. Each judge is assigned the task of grading the submissions based on a particular aspect: 1) Correctness; 2) Robustness; 3) Overall design; 4) Clarity; 5) Coding style; and finally 6) Maintainability. The final grade of a submission would be the average of the six grades it gets.
The old guards of the current ICPC judging style have always responded that it is not possible to impartially judge a program on anything but correctness. How can the ICPC be certain that judging is fair? In other words, how can the ICPC be sure that non of the judges is favoring certain teams and disadvantaging others? Any hint of accusation to the judging process and ICPC loses the prestigious status it worked on for years. (Alright! So they do have a point.) Still, this hasn’t stopped other domains from judging candidates based on subjective metrics. Take for example Gymnastics, or The Nobel Prizes, or even the ACM’s very own Doctoral Dissertation Award. These are all highly respected awards where the winner is selected by judges using subjective metrics. ICPC could use a new judging system based on what is used in gymnastics. Rather than having each judge grade a certain aspect of the program, each of the six judges would assign an overall grade (out of ten) based on all of the six metrics mentioned above. To enforce impartiality, the final grade of a submission would be calculated as the average of all the grades after deleting two grades: The highest and the lowest. Any judge that favors a certain team (and assigns them an undeserved high grade,) risks the possibility of that grade being dismissed. Similarly, any judge that attempts to disadvantage a team by assigning them a low grade faces a similar risk.
Write a program to print the final grade of a submission.

Input

Your program will be tested on one or more test cases. Each test case is described on a single input line listing the grades of the judges. The end of the test cases is identified with a dummy test case with all the grades being zero.

Output

For each test case, print the grade on a separate line (without unnecessary decimal points and/or zeros.)

Sample Input

8 8 8 4 4 4
8 8 6 4 4 3
0 0 0 0 0 0

Sample Output

6
5.5

Source

Arab and North Africa 2007

Solution:

Easy implementation;

Source Code:

//Sun Nov 14 20:37:24 CST 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main( int argc, const char* argv[] )
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
    int a[6];
    while(cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] && (a[0]||a[1]||a[2]||a[3]||a[4]||a[5]))
    {
        int mmax = a[0];
        int mmin = a[0];
        int sum = a[0];
        for(int i=1; i<6; i++)
        {
            mmax = max(mmax, a[i]);
            mmin = min(mmin, a[i]);
            sum += a[i];
        }
        cout << 1.0*(sum - mmax - mmin)/4. << endl;
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

第一章_1.6 状态空间搜索

1.6.1 状态空间:
1.6.2 盲目搜索算法:
1.6.3 启发式搜索算法:
1.6.4 博弈问题算法:
1.6.5 剪枝:
1.6.6 路径寻找问题:
1.6.7 约束满足问题:

第一章_1.5 动态规划:

1.5.1 动态规划的两种动机:
1.5.2 常见模型的分析:
1.5.3 若干经典问题和常见优化方法:

第一章_1.4 数据结构(2) ---- 拓宽和应用举例:

1.4.1 并查集:

Example: (例题)
E.g.01 : 代码等式.
E.g.02 : 团伙.
E.g.03 : Galaxy.
E.x.01 : Ubiquitous Religions.
E.x.02 : The Suspects.
E.x.03 : 食物链.
E.x.04 : Find them, Catch them.
E.x.05 : A Bug's Life.
E.x.06 : Wireless Networks.
E.x.07 : Cube Stacking.
E.x.08 : War.

1.4.2 堆及其变种:

1.4.3 字典的两种实现方式: 哈西表, 二叉搜索树:
1.4.4 两个特殊树结构: 线段树和 Trie:

Example:(例题)
E.x.02: IMMEDIATE DECODABILITY.

第一章_1.3 数据结构(1) -----入门:

1.3.1 栈和队列:

Example: (例题)
E.g.01 : Rails.
E.g.02 : Tempus et mobilius Time and motion.
Excise : (练习)
1.3.7 Bitmap.
1.3.8 Partition.
1.3.9 算法复杂度.

1.3.2 串:

Example: (例题)
E.g.01 : .
Excise : (练习)
1.3.12 Necklaces.
1.3.13 .

1.3.3 树和二叉数:

Example: (例题)
E.g.00 : Ilya Murometz.
E.g.01 : .
E.g.02 : .
Excise : (练习)
1.3.18
1.3.19 .
1.3.20 .
Extra :
1.3.18 Tree Recovery.(POJ)

1.3.4 图及其基本算法:

Example: (例题)
E.g.01 : .
E.g.02 : .
Excise : (练习)
1.3.25 .
1.3.26 .
1.3.27 .

1.3.5 排序与检索基本算法:

Example: (例题)
E.g.01 : Cable Master.
E.g.02 : Stacks of Flapjacks.
E.x.01 : Gaby Ivanushka.
E.g.03 : SOLDIERS.
E.g.04 : Exchange.
Excise : (练习)
1.3.30 .
1.3.31 .

第一章_1.2 基本算法:

1.2.1 枚举:

Example: (例题)
E.g. 01 : Balloons in a box.
E.g. 02 : Library.
Excise : (练习)
1.2.4 Conductor.
1.2.5 Flip Coin.
1.2.6 Discrete Function.
1.2.7 Subnumber
Extra:

1.2.2 贪心法:

Example: (例题)
E.g. 01 : Gone Fishing.
E.g. 02 : Enlightened Landscape.
E.g. 03 : Mirror.
Excise: (练习)
1.2.12
1.2.13
1.2.14
Extra:
001 : Crossing River.

1.2.3 递归与分治法:

Example: (例题)
E.g. 01
E.g. 02
E.g. 03
E.g. 04
Excise: (练习)
1.2.18

1.2.4 递归:

Example: (例题)
E.g. 01 : Evil Eyes
E.g. 02 : Lost Lists
E.g. 03 : Chain
Excise: (练习)
1.2.23
1.2.24
1.2.25 : Chain.
1.2.26
1.2.27
1.2.28
Extra:
001 : Time Zones.

 

poj_3753_根据关键字进行字符串拷贝.cpp

Problem Links:

poj3753,

Problem:

根据关键字进行字符串拷贝

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3494		Accepted: 707

Description

把源字符串拷贝到目的字符串，如果指定关键字，则以该关键字结束(不包括关键字本身)，如果拷贝失败，则得到空串。
具体要求：实现如下函数原型SafeStrcpy2KeyWord()，并在代码中调用该函数实现上述功能。该函数的实现要考虑各种可能的参数取值，以确保程序不出现崩溃。

int SafeStrcpy2KeyWord(char* pDestBuffer,	//拷贝的目的地地址

		       char* pSourceString,	//拷贝的源地址

		       int nDestBufferSize,	//拷贝的目的地缓冲区长度

		       char* szKeyWord);	//指定关键字符串

返回值：所拷贝的字符串长度。如果拷贝失败，则返回0。

Input

输入包含多组数据，以EOF结束
每组数据第一行为不含空格的源字符串，长度小于256；接下来的一行或多行都是关键字串（长度小于16），一直到END结束。“NULL”表示关键字串为空，此时输出的拷贝后的长度应为0，拷贝后的字符串为空串（也用”NULL”表示，见下文）。

Output

对于每组数据输出拷贝的长度和拷贝后的目的字符串，以空格分隔。如果该目的字符串为空，则用”NULL”表示。

Sample Input

/home/tony/work_server/1/rtest/relayer.out
/
/t
/1/r
.
NULL
END

Sample Output

0 NULL
5 /home
22 /home/tony/work_server
38 /home/tony/work_server/1/rtest/relayer
0 NULL

Source

Solution:

Do whatever the problem told you to do, but take care:
1st, if there is no match with the keyword, return the whole string.
2nd, take care of the for loop. It takes me 3 or 4 WAs.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Fri May 28 12:55:30 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int SafeStrcpy2KeyWord(string &des, string src, string keyword)
{
if (keyword == "NULL")
{
des.clear();
return 0;
}
int N = keyword.size();
int M = src.size();
for (int i = 0; i + N <= M; i++)
{
string str = src.substr(i, N);
if (str == keyword)
{
return i;
}
des += src[i];
}
return 0;
}

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
string str;
while (cin >> str)
{
string s;
getchar();
while (getline(cin, s) && s != "END")
{
string des;
int len = SafeStrcpy2KeyWord(des, str, s);
if (len == 0 && des.size() == 0)
cout << "0 NULL" << endl;
else if (len == 0)
cout << str.size() << " " << str << endl;
else
cout << len << " " << str.substr(0, len) << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj_3752_字母旋转游.cpp

Problem Links:

poj3752,

Problem:

字母旋转游戏

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4838		Accepted: 1757

Description

给定两个整数M，N，生成一个M*N的矩阵，矩阵中元素取值为A至Z的26个字母中的一个，A在左上角，其余各数按顺时针方向旋转前进，依次递增放置，当超过26时又从A开始填充。例如，当M=5，N=8时，矩阵中的内容如下：

   A   B   C   D   E   F   G   H

   V   W   X   Y   Z   A   B   I

   U   J   K   L   M   N   C   J

   T   I   H   G   F   E   D   K

   S   R   Q   P   O   N   M   L

Input

M为行数，N为列数，其中M，N都为大于0的整数。

Output

分行输出相应的结果

Sample Input

4 9

Sample Output

   A   B   C   D   E   F   G   H   I
   V   W   X   Y   Z   A   B   C   J
   U   J   I   H   G   F   E   D   K
   T   S   R   Q   P   O   N   M   L

Source

Solution:

Basically, it's just a straight forward  simulation.

In each state, select the next state.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Sat Apr 17 12:25:46 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int M, N;
while (cin >> M >> N)
{
vector<vector<char> > v(M, vector<char> (N, '#'));
int nextx = 0;
int nexty = 0;
int count = 0;
int position = 0;
int direction = 0; // right, down, left, up.
while (count < M * N)
{
count ++;
char letter = 'A' + position;
position = (position + 1) % 26;
v[nextx][nexty] = letter;
//Right;
if(direction == 0)
{
if(nexty + 1 == N || (nexty+1<N && v[nextx][nexty+1] != '#'))
{
direction = 1;
nextx++;
}
else
{
nexty++;
}
}
//Down;
else if(direction == 1)
{
if(nextx+1==M || (nextx+1<M && v[nextx+1][nexty] != '#'))
{
direction = 2;
nexty--;
}
else
{
nextx++;
}
}
//Left;
else if(direction == 2)
{
if(nexty-1<0 || (nexty-1>=0 && v[nextx][nexty-1] !='#'))
{
direction = 3;
nextx--;
}
else
{
nexty--;
}
}
//Up;
else
{
if(nextx-1 <0 || (nextx-1>=0 && v[nextx-1][nexty] != '#'))
{
direction = 0;
nexty++;
}
else
{
nextx--;
}
}
}
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
cout << " " << v[i][j];
}
cout << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj_3751_时间日期格式转换.cpp

Problem Links:

poj3751,

Problem:

时间日期格式转换

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4083		Accepted: 1918

Description

世 界各地有多种格式来表示日期和时间。对于日期的常用格式，在中国常采用格式的是“年年年年/月月/日日”或写为英语缩略表示的”yyyy/mm/dd”， 此次编程大赛的启动日期“2009/11/07”就是符合这种格式的一个日期，而北美所用的日期格式则为“月月/日日/年年年年”或”mm/dd /yyyy”，如将“2009/11/07”改成这种格式，对应的则是”11/07/2009”。对于时间的格式，则常有12小时制和24小时制的表示方 法，24小时制用0-24来表示一天中的24小时，而12小时制只采用1-12表示小时，再加上am/pm来表示上午或下午，比如”17:30:00”是 采用24小时制来表示时间，而对应的12小时制的表示方法是”05:30:00pm”。注意12:00:00pm表示中午12点，而12:00:00am 表示凌晨12点。

对于给定的采用”yyyy/mm/dd”加24小时制（用短横线”-”连接）来表示日期和时间的字符串，请编程实现将其转换成”mm/dd/yyyy”加12小时制格式的字符串。

Input

第一行为一个整数T（T<=10），代表总共需要转换的时间日期字符串的数目。
接下来的总共T行，每行都是一个需要转换的时间日期字符串。

Output

分行输出转换之后的结果

Sample Input

2
2009/11/07-12:12:12
1970/01/01-00:01:01

Sample Output

11/07/2009-12:12:12pm
01/01/1970-12:01:01am

Hint

注意中午和凌晨时间的特殊表示

Source

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Fri 29 Jan 2010 01:44:27 AM CST
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
string str;
int T;
cin >> T;
for(int i=0; i<T; i++)
{
string output;
cin >> str;
output += str.substr(5,5);
output += "/";
output += str.substr(0,4);
output += "-";
//output += str.substr(11);
int time = 10 * (str[11]-'0') + (str[12]-'0');
if(time == 0)
{
output += "12";
output += str.substr(13) + "am";
}
else if(time >0 && time <12)
{
output += str.substr(11) + "am";
}
else if(time == 12)
{
output += str.substr(11) + "pm";
}
else
{
time -= 12;
int d = time / 12;
int dd = time % 12;
output += ('0' + d);
output += ('0' + dd);
output += str.substr(13) + "pm";
}
cout << output << endl;
}
return 0;
}
[/sourcecode]

poj_3750_小孩报数问题.cpp

Problem Links:

poj3750,

Problem:

小孩报数问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4457		Accepted: 2145

Description

有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。

Input

第一行输入小孩的人数N（N<=64）
接下来每行输入一个小孩的名字(人名不超过15个字符)
最后一行输入W,S (W < N)，用逗号","间隔

Output

按人名输出小孩按顺序出列的顺序，每行输出一个人名

Sample Input

5
Xiaoming
Xiaohua
Xiaowang
Zhangsan
Lisi
2,3

Sample Output

Zhangsan
Xiaohua
Xiaoming
Xiaowang
Lisi

Source

Solution:

Simulation.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Sat 30 Jan 2010 05:48:22 PM CST
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
vector<string> v;
v.clear();
int N;
string str;
cin >> N;
for(int i=0; i<N; i++)
{
cin >> str;
v.push_back(str);
str.clear();
}
int start;
int loop;
char c;
cin >> start >> c >> loop;
// cout << start << ", " <<loop << endl;
start--;
while(!v.empty())
{
int next = (start+loop-1) % v.size();
cout << v[next] << endl;
start = next==v.size()-1 ? 0 : next;
v.erase(v.begin() + next);
}
return 0;
}
[/sourcecode]

poj_3748_位操作.cpp

Problem Links:

poj3748,

Problem:

位操作

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5792		Accepted: 2219

Description

假设你工作在一个32位的机器上，你需要将某一个外设寄存器的第X位设置成0(最低位为第0位，最高位为第31位)，将第Y位开始的连续三位设置成110（从高位到低位的顺序），而其他位保持不变。对给定的寄存器值R，及X，Y，编程计算更改后的寄存器值R。

Input

仅一行，包括R,X,Y，以逗号","分隔，R为16进制表示的32位整数，X,Y在0-31之间且Y>=3，(Y-X)的绝对值>=3，保证两次置位不会重合

Output

更改后的寄存器值R（16进制输出）

Sample Input

12345678,0,3

Sample Output

1234567c

Source

Solution:

Implement all the operations by using bit operation, that will be much easier than convert to any other format.

PS, take care of the cin and cout.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Sat Apr 17 14:43:26 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main( int argc, const char* argv[] )
{
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
int R, X, Y;
char c;
while(cin >> hex >> R >> dec >> c >> X >> c >> Y)
{
R &= ~(1<<(X));
R |= (1<<(Y));
R |= (1<<(Y-1));
R &= ~(1<<(Y-2));

cout << hex << R << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
[/sourcecode]

poj_3650_The_Seven_Percent_Solution.cpp

Problem Links:

poj3650,

Problem:

The Seven Percent Solution

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5293		Accepted: 3475

Description

Uniform Resource Identifiers (or URIs) are strings like http://icpc.baylor.edu/icpc/, mailto:foo@bar.org, ftp://127.0.0.1/pub/linux, or even just readme.txt that are used to identify a resource, usually on the Internet or a local computer. Certain characters are reserved within URIs, and if a reserved character is part of an identifier then it must be percent-encoded by replacing it with a percent sign followed by two hexadecimal digits representing the ASCII code of the character. A table of seven reserved characters and their encodings is shown below. Your job is to write a program that can percent-encode a string of characters.

Character	Encoding
" " (space)	%20
"!" (exclamation point)	%21
"$" (dollar sign)	%24
"%" (percent sign)	%25
"(" (left parenthesis)	%28
")" (right parenthesis)	%29
"*" (asterisk)	%2a

Input

The input consists of one or more strings, each 1–79 characters long and on a line by itself, followed by a line containing only "#" that signals the end of the input. The character "#" is used only as an end-of-input marker and will not appear anywhere else in the input. A string may contain spaces, but not at the beginning or end of the string, and there will never be two or more consecutive spaces.

Output

For each input string, replace every occurrence of a reserved character in the table above by its percent-encoding, exactly as shown, and output the resulting string on a line by itself. Note that the percent-encoding for an asterisk is %2a (with a lowercase "a") rather than %2A (with an uppercase "A").

Sample Input

Happy Joy Joy!
http://icpc.baylor.edu/icpc/
plain_vanilla
(**)
?
the 7% solution
#

Sample Output

Happy%20Joy%20Joy%21
http://icpc.baylor.edu/icpc/
plain_vanilla
%28%2a%2a%29
?
the%207%25%20solution

Source

Mid-Central USA 2007

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Tue Apr 20 11:49:19 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main( int argc, const char* argv[] )
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
string str;
while(getline(cin ,str) && str != "#")
{
for(int i=0; i<str.size(); i++)
{
if(str[i] == ' ') cout << "%20";
else if(str[i] == '!') cout << "%21";
else if(str[i] == '$') cout << "%24";
else if(str[i] == '%') cout << "%25";
else if(str[i] == '(') cout << "%28";
else if(str[i] == ')') cout << "%29";
else if(str[i] == '*') cout << "%2a";
else cout << str[i];
}
cout << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj_3637_Shopaholic.cpp

Problem Links:

poj3637,

Problem:

Shopaholic

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 3631		Accepted: 2119

Description

Lindsay is a shopaholic. Whenever there is a discount of the kind where you can buy three items and only pay for two, she goes completely mad and feels a need to buy all items in the store. You have given up on curing her for this disease, but try to limit its effect on her wallet.

You have realized that the stores coming with these offers are quite selective when it comes to which items you get for free; it is always the cheapest ones. As an example, when your friend comes to the counter with seven items, costing 400, 350, 300, 250, 200, 150, and 100 dollars, she will have to pay 1500 dollars. In this case she got a discount of 250 dollars. You realize that if she goes to the counter three times, she might get a bigger discount. E.g. if she goes with the items that costs 400, 300 and 250, she will get a discount of 250 the first round. The next round she brings the item that costs 150 giving no extra discount, but the third round she takes the last items that costs 350, 200 and 100 giving a discount of an additional 100 dollars, adding up to a total discount of 350.

Your job is to find the maximum discount Lindsay can get.

Input

The first line of input gives the number of test scenarios, 1 ≤ t ≤ 20. Each scenario consists of two lines of input. The first gives the number of items Lindsay is buying, 1 ≤ n ≤ 20000. The next line gives the prices of these items, 1 ≤ p_i ≤ 20000.

Output

For each scenario, output one line giving the maximum discount Lindsay can get by selectively choosing which items she brings to the counter at the same time.

Sample Input

1
6
400 100 200 350 300 250

Sample Output

400

Source

Nordic 2007

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Sat Jun 19 16:00:59 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++)
cin >> v[i];
sort(v.begin(), v.end());
int sum = 0;
for (int i = N - 3; i >= 0; i -= 3)
sum += v[i];
cout << sum << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj_3632_Optimal_Parking.cpp

Problem Links:

poj3632,

Problem:

Optimal Parking

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5732		Accepted: 3113

Description

When shopping on Long Street, Michael usually parks his car at some random location, and then walks to the stores he needs. Can you help Michael choose a place to park which minimises the distance he needs to walk on his shopping round? Long Street is a straight line, where all positions are integer. You pay for parking in a specific slot, which is an integer position on Long Street. Michael does not want to pay for more than one parking though. He is very strong, and does not mind carrying all the bags around.

Input

The first line of input gives the number of test cases, 1 ≤ t ≤ 100. There are two lines for each test case. The first gives the number of stores Michael wants to visit, 1 ≤ n ≤ 20, and the second gives their n integer positions on Long Street, 0 ≤ x_i ≤ 99.

Output

Output for each test case a line with the minimal distance Michael must walk given optimal parking.

Sample Input

2
4
24 13 89 37
6
7 30 41 14 39 42

Sample Output

152
70

Source

Nordic 2007

Solution:

Basic one.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Tue Apr 20 12:57:54 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N;
cin >> N;
while (N--)
{
int mmin = -1;
int mmax = -1;
int t;
cin >> t;
for(int i=0; i<t; i++)
{
int number;
cin >> number;
if(number < mmin || mmin == -1) mmin = number;
if(number > mmax || mmax == -1) mmax = number;
}
cout << 2 * (mmax - mmin) << endl;
}

// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj_3673_Cow_Multiplication.cpp

Problem Links:

poj3673,

Problem:

Cow Multiplication

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7792		Accepted: 5135

Description

Bessie is tired of multiplying pairs of numbers the usual way, so she invented her own style of multiplication. In her style, A*B is equal to the sum of all possible pairwise products between the digits of A and B. For example, the product 123*45 is equal to 1*4 + 1*5 + 2*4 + 2*5 + 3*4 + 3*5 = 54. Given two integers A and B (1 ≤ A, B ≤ 1,000,000,000), determine A*B in Bessie's style of multiplication.

Input

* Line 1: Two space-separated integers: A and B.

Output

* Line 1: A single line that is the A*B in Bessie's style of multiplication.

Sample Input

123 45

Sample Output

54

Source

USACO 2008 February Bronze

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Sun 31 Jan 2010 02:03:36 PM CST
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
string s1;
string s2;
cin >> s1 >> s2;
int sum1 = 0;
int sum2 = 0;
int sz1 = s1.size();
int sz2 = s2.size();
for(int i=0; i<sz1; i++)
{
sum1 += s1[i]-'0';
}
for(int i=0; i<sz2; i++)
{
sum2 += s2[i]-'0';
}
cout << sum1*sum2 << endl;
return 0;
}
[/sourcecode]

poj_3630_Phone_List.cpp

Problem Links:

poj3630,

Problem:

Phone List

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9408		Accepted: 2992

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers:

• Emergency 911


• Alice 97 625 999


• Bob 91 12 54 26

In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output "YES" if the list is consistent, or "NO" otherwise.

Sample Input

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output

NO
YES

Source

Nordic 2007

Solution:

Trie Tree.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Sun Jul 4 00:43:51 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define MMAX 100000
using namespace std;

int Count;

class TreeNode
{
public:
bool istring;
TreeNode *child[10];
};

vector<TreeNode> v(MMAX);

class TrieTree
{
private:
TreeNode root;
public:
void init();
bool insert(string word);
};

void TrieTree::init()
{
Count = 0;
root = v[Count++];
memset(root.child, NULL, sizeof(root.child));
root.istring = false;
}

bool TrieTree::insert(string word)
{
TreeNode *start = &root;
int len = word.size();
for (int i = 0; i < len; i++)
{
if (start->child[word[i] - '0'] == NULL)
{
start->child[word[i] - '0'] = &v[Count];
v[Count].istring = false;
memset(v[Count].child, NULL, sizeof(v[Count].child));
Count++;
}
else if (start->child[word[i] - '0']->istring == true || i == len - 1)
{
start->child[word[i] - '0']->istring = true;
return false;
}
start = start->child[word[i] - '0'];
}
start->istring = true;
return true;
}

int main(int argc, const char* argv[])
{
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
int ncase;
cin >> ncase;
while (ncase--)
{
int N;
cin >> N;
string str;
bool flag = true;
TrieTree x;
x.init();
for (int i = 0; i < N; i++)
{
cin >> str;
if (x.insert(str) == false)
{
flag = false;
}
}
if (flag == false)
{
cout << "NO" << endl;
}
else
{
cout << "YES" << endl;
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
[/sourcecode]

poj_3619_Speed_Reading.cpp

Problem Links:

poj3619,

Problem:

Speed Reading

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6238		Accepted: 2697

Description

All K (1 ≤ K ≤ 1,000) of the cows are participating in Farmer John's annual reading contest. The competition consists of reading a single book with N (1 ≤ N ≤ 100,000) pages as fast as possible while understanding it.

Cow i has a reading speed S_i (1 ≤ S_i ≤ 100) pages per minute, a maximum consecutive reading time T_i (1 ≤ T_i ≤ 100) minutes, and a minimum rest time R_i (1 ≤ R_i ≤ 100) minutes. The cow can read at a rate of S_i pages per minute, but only for T_i minutes at a time. After she stops reading to rest, she must rest for R_i minutes before commencing reading again.

Determine the number of minutes (rounded up to the nearest full minute) that it will take for each cow to read the book.

Input

* Line 1: Two space-separated integers: N and K
* Lines 2..K+1: Line i+1 contains three space-separated integers: S_i , T_i , and R_i

Output

* Lines 1..K: Line i should indicate how many minutes (rounded up to the nearest full minute) are required for cow i to read the whole book.

Sample Input

10 3
2 4 1
6 1 5
3 3 3

Sample Output

6
7
7

Source

USACO 2007 November Bronze

Solution:

1st, get the total reading time for each cow;

2nd, get the up limit of consecutive reading time; (PS: result - 1 = Times needed to rest).

3rd, total = total reading time + MinrestTime * (result from 2nd - 1);

 

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Fri Apr 23 01:56:26 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N, K;
while (cin >> N >> K)
{
vector<vector<int> > v(K, vector<int> (3));
for (int i = 0; i < K; i++)
{//The total Reading Time; Max Reading Time; Min Rest time;
cin >> v[i][0] >> v[i][1] >> v[i][2];
v[i][0] = (int) ((N + v[i][0] - 1) / v[i][0]);
// cout << v[i][0] << v[i][1] << v[i][2] << endl;
int times = (int) ((v[i][0] + v[i][1] - 1) / v[i][1]);
int total = v[i][0] + v[i][2]*(times-1);
cout << total << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]

poj_3589_Number-guessing_Game.cpp

Problem Links:

poj3589,

Problem:

Number-guessing Game

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4276		Accepted: 3148

Description

Larry likes playing the number-guessing game.

Two players are needed in a game. Suppose they are X and Y, and X presents a number for Y to guess. Firstly, X chooses a number with four different digits, keeping it in mind, and tells Y to start guessing. Every time Y has guessed, X should give out *A*B to show Y how close to the number his answer is. Here the symbol * stands for a number, and the number before A is the number of digits in Y's answer with both correct value and position. The number before B is the number of digits in Y's answer with correct value but incorrect position.

For example, if X chooses the number 5204, and Y guesses 4902, then X should give out 1A2B, in which 1A corresponds for digit 0 with both correct value and position and 2B corresponds for digit 2 and 4 with correct value but incorrect position. Then Y will go on guessing according to 1A2B that X presents him until he gets the totally correct number 5204 (when X shows him 4A0B).

Now you are given two numbers, and what you need to do is just testing how close they are.

Input

The first line of the input is an integer T which indicates the number of test cases. For each test case, input two numbers. Each number contains four different digits.

Output

For each test case, output *A*B stands for how close the two numbers are.

Sample Input

2
5204 4902
0123 3210

Sample Output

1A2B
0A4B

Source

South Central China 2008 hosted by NUDT

Solution:

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Sun 31 Jan 2010 02:14:54 PM CST
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
int N;
cin >> N;
for(int i=0; i<N; i++)
{
string str1;
string str2;
cin >> str1 >> str2;
int A = 0;
int B = 0;
for(int j=0; j<4; j++)
{
if(str1[j] == str2[j])
A ++;
else
{
for(int k=0; k<4; k++)
{
if(str2[j] == str1[k])
{
B++;
break;
}
}
}
}
cout << A << "A" << B << "B" << endl;
}
return 0;
}
[/sourcecode]

poj_3517_AndThenThereWasOne.cpp

Problem Links:

poj3517,

Problem:

And Then There Was One

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 3173		Accepted: 1587

Description

Let’s play a stone removing game.

Initially, n stones are arranged on a circle and numbered 1, …, n clockwise (Figure 1). You are also given two numbers k and m. From this state, remove stones one by one following the rules explained below, until only one remains. In step 1, remove stone m. In step 2, locate the k-th next stone clockwise from m and remove it. In subsequent steps, start from the slot of the stone removed in the last step, make k hops clockwise on the remaining stones and remove the one you reach. In other words, skip (k − 1) remaining stones clockwise and remove the next one. Repeat this until only one stone is left and answer its number. For example, the answer for the case n = 8, k = 5, m = 3 is 1, as shown in Figure 1.

Initial state	Step 1	Step 2	Step 3	Step 4
Step 5	Step 6	Step 7	Final state

Figure 1: An example game

Initial state: Eight stones are arranged on a circle.

Step 1: Stone 3 is removed since m = 3.

Step 2: You start from the slot that was occupied by stone 3. You skip four stones 4, 5, 6 and 7 (since k = 5), and remove the next one, which is 8.

Step 3: You skip stones 1, 2, 4 and 5, and thus remove 6. Note that you only count stones that are still on the circle and ignore those already removed. Stone 3 is ignored in this case.

Steps 4–7: You continue until only one stone is left. Notice that in later steps when only a few stones remain, the same stone may be skipped multiple times. For example, stones 1 and 4 are skipped twice in step 7.

Final State: Finally, only one stone, 1, is on the circle. This is the final state, so the answer is 1.

Input

The input consists of multiple datasets each of which is formatted as follows.

n k m

The last dataset is followed by a line containing three zeros. Numbers in a line are separated by a single space. A dataset satisfies the following conditions.

2 ≤ n ≤ 10000, 1 ≤ k ≤ 10000, 1 ≤ m ≤ n

The number of datasets is less than 100.

Output

For each dataset, output a line containing the stone number left in the final state. No extra characters such as spaces should appear in the output.

Sample Input

8 5 3
100 9999 98
10000 10000 10000
0 0 0

Sample Output

1
93
2019

Source

Japan 2007

Solution:

1 2 3 4 5 6 7 8
4 5 6 7 8 9 10 11
4 5 6 7 8 9 10
1 2 3 4 5 6 7
更简单一些，就是先求出n-1的解，再进行一次类似旋转的操作（即：（f（n-1）+m+1+n）%n），即可得到解；

/*约瑟夫问题的数学方法
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。

现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：
这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
////////2008-04-08;
#include<stdio.h>
int main()
{
int a[10001];
int m,n,k;
while(scanf("%d%d%d",&n,&k,&m)==3&&(n+m+k)>0)
{
int i;
a[1]=0;
for(i=2;i<n;i++)
{
a[i]=(a[i-1]+k)%i;
}
printf("%d\n",(a[n-1]+n+m+1)%n);
}
return 0;
}
[/sourcecode]

poj_3438_Look_and_Say.cpp

Problem Links:

poj3438, spoj03081,

Problem:

Look and Say

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 6516		Accepted: 3944

Description

The look and say sequence is defined as follows. Start with any string of digits as the first element in the sequence. Each subsequent element is defined from the previous one by "verbally" describing the previous element. For example, the string 122344111 can be described as "one 1, two 2's, one 3, two 4's, three 1's". Therefore, the element that comes after 122344111 in the sequence is 1122132431. Similarly, the string 101 comes after 1111111111. Notice that it is generally not possible to uniquely identify the previous element of a particular element. For example, a string of 112213243 1's also yields 1122132431 as the next element.

Input

The input consists of a number of cases. The first line gives the number of cases to follow. Each case consists of a line of up to 1000 digits.

Output

For each test case, print the string that follows the given string.

Sample Input

3
122344111
1111111111
12345

Sample Output

1122132431
101
1112131415

Source

Rocky Mountain 2007

Solution:

Straight forward.

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Sun 31 Jan 2010 02:00:16 AM CST
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
int N;
cin >> N;
for(int i=0; i<N; i++)
{
string str;
cin >> str;
int len = str.size();
char ch = str[0];
int count = 1;
for(int i=1; i<len; i++)
{
if(ch == str[i])
count++;
else
{
cout << count << (ch-'0');
ch = str[i];
count = 1;
}
}
cout << count << (ch - '0') << endl;
}
return 0;
}
[/sourcecode]