校选icpc
1. 百步穿杨
Problem Description
时维九月,序属三秋,辽军大举进攻MCA山,战场上两军正交锋.辽军统帅是名噪一时的耶律-James,而MCA方则是派出了传统武将中草药123.双方经过协商,约定在十一月八日正午十分进行射箭对攻战.中草药123早早就开始准备,但是他是武将而不是铁匠,造弓箭的活就交给聪明能干的你了,现在告诉你每种弓箭规格,即箭身的长度,以及每种规格弓箭所需要的数目,要求你把需要的弓箭都输出.
弓箭的基本样子为 “>±–+>”,其中"±–+"为箭身,数据保证箭身长度 > 2
Input
首先输入一个t,表示有t组数据，跟着t行： 每行一个N (N < 50 ),接下去有N行,第i行两个整数Ai , Bi,分别代表需要箭身长度为Ai的弓箭Bi枝. (Ai < 30 , Bi < 10 ) 输入数据保证每一个Ai都是不同的.
Output
按照箭身的长度从小到大的顺序依次输出所有需要的弓箭,"每一种"弓箭后输出一个空行.
Sample Input
1
4
3 4
4 5
5 6
6 7
Sample Output
>+-+>
>+-+>
>+-+>
>+-+>
>+--+>
>+--+>
>+--+>
>+--+>
>+--+>
>+---+>
>+---+>
>+---+>
>+---+>
>+---+>
>+---+>
>+----+>
>+----+>
>+----+>
>+----+>
>+----+>
>+----+>
>+----+>
tips：
一定要认真读题目！！测试数据是从小到大输出，所以就忘了要排序了，本题需要用结构体排序 , 需要自己写一个关于判断结构体排序的算法，return a1.len < a2.len
Result： @@两颗星
#include <iostream>
#include <string>
#include <algorithm>
#include <time.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int N = 1005;
long long n;
int t, ni, Ai[100], Bi[100];
typedef struct ARRAY
{
int len;
int num;
} array; // 结构体
ARRAY arr[51];
bool pd(ARRAY a1, ARRAY a2)
{
return a1.len < a2.len; // 自我创建的排序算法
}
int main()
{
cin >> t;
for (int i = 0; i < t; i++)
{
cin >> ni;
for (int j = 0; j < ni; j++)
{
cin >> Ai[j] >> Bi[j];
arr[j].len = Ai[j];
arr[j].num = Bi[j];
}
sort(arr, arr + ni, pd);
for (int j = 0; j < ni; j++)
{
for (int k = 0; k < arr[j].num; k++)
{
cout << ">+";
for (int l = 0; l < arr[j].len - 2; l++)
{
cout << "-";
}
cout << "+>" << endl;
}
cout << endl;
}
}
}
2. Michael Scofield’s letter HDU 2007-11 Programming Contest
Problem Description
I believe many people are the fans of prison break. How clever Michael is!! In order that the message won’t be found by FBI easily, he usually send code letters to Sara by a paper crane. Hence, the paper crane is Michael in the heart of Sara. Now can you write a program to help Sara encode the letter from Michael easily?
The letter from Michael every time is a string of lowercase letters. You should encode letters as the rules below:
b is ’ ', q is ‘,’, t is ‘!’, m is l, i is e, c is a, a is c, e is i, l is m. It is interesting. Are you found that it is just change michael to leahcim?
Input
The input will consist of several cases, one per line. Each case is a letter from Michael, the letteres won’t exceed 10000.
Output
For each case, output the encode letter one line.
Sample Input
pmicsibforgevibliqbscrct
ebmovibyout
Sample Output
please forgive me, sara!
i love you!
-
tips：
由于输入进来的数据不确定有多少组，则需要用 while(getline(cin,str)) 的方式
Result： @@两颗星
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <time.h>
#include <stdio.h>
using namespace std;
// char str[10001];
string str;
int main()
{
while (getline(cin, str))
{
for (int i = 0; i < str.length(); i++)
{
if (str[i] == 'b')
{
str[i] = ' ';
}
else if (str[i] == 'q')
{
str[i] = ',';
}
else if (str[i] == 't')
{
str[i] = '!';
}
else if (str[i] == 'm')
{
str[i] = 'l';
}
else if (str[i] == 'i')
{
str[i] = 'e';
}
else if (str[i] == 'c')
{
str[i] = 'a';
}
else if (str[i] == 'a')
{
str[i] = 'c';
}
else if (str[i] == 'e')
{
str[i] = 'i';
}
else if (str[i] == 'l')
{
str[i] = 'm';
}
}
cout << str << endl;
}
}
3. 回文数猜想 杭电ACM集训队训练赛（VII）
Problem Description
一个正整数，如果从左向右读（称之为正序数）和从右向左读（称之为倒序数）是一样的，这样的数就叫回文数。任取一个正整数，如果不是回文数，将该数与他的倒序数相加，若其和不是回文数，则重复上述步骤，一直到获得回文数为止。例如：68变成154（68+86），再变成605（154+451），最后变成1111（605+506），而1111是回文数。于是有数学家提出一个猜想：不论开始是什么正整数，在经过有限次正序数和倒序数相加的步骤后，都会得到一个回文数。至今为止还不知道这个猜想是对还是错。现在请你编程序验证之。
Input
每行一个正整数。 特别说明：输入的数据保证中间结果小于2^31。
Output
对应每个输入，输出两行，一行是变换的次数，一行是变换的过程。
Sample Input
27228
37649
Sample Output
3
27228--->109500--->115401--->219912
2
37649--->132322--->355553
-
tips :
数据表示范围 ： int [-231,231-1]
long long的[-263,263-1]
由于不是回文的话，需要加上该数的逆数d，所以在回文判断的时候，写成全局变量，但是一定要注意，每次使用完之后，再次调用的时候需要置0 ，因为在构造拆分的时候用的是 d = d x 10 + s / 10 ;
- 判断回文可以用 string类型，也可以用while(n>0) 分离个位构造新数
code:
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <time.h>
#include <stdio.h>
using namespace std;
const int N = 1005;
typedef long long ll;
ll a, b, c, d, t,aa[N];
bool check_hui(ll n)
{
t = n;
d = 0; // 记得清0 ， 使用全局变量的时候一定要记得清0
while (t > 0)
{
d = d * 10 + t % 10;
t = t / 10;
}
if (d == n)
{
return true;
}
return false;
}
int main()
{
while (scanf("%d", &a) != EOF)
{
int cnt=0;
while (!check_hui(a)) // 不是回文数 一直执行
{
aa[cnt] = a;
a = a + d;
cnt++;
}
cout<< cnt<<endl;
for(int i = 0; i < cnt; i++){
cout<<aa[i]<<"--->";
}
cout << a << endl;
}
}
4. red and black
Problem Description
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20. There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows. ‘.’ - a black tile ‘#’ - a red tile ‘@’ - a man on a black tile(appears exactly once in a data set)
Output
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
Sample Output
45
59
6
13
-
tips：
-
我不会，赋祥写
code：
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <time.h>
#include <stdio.h>
#include <queue>
using namespace std;
int n, m;
char mp[21][21];
int num, x, y;
int main()
{
queue<int> X;
queue<int> Y;
while (1)
{
cin >> n >> m;
if (n == 0 && m == 0)
break;
num = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cin >> mp[j + 1][i + 1];
if (mp[j + 1][i + 1] == '@')
{
x = j + 1;
y = i + 1;
X.push(x);
Y.push(y);
mp[j + 1][i + 1] = '#';
}
}
}
while (!X.empty())
{
num++;
x = X.front();
y = Y.front();
X.pop();
Y.pop();
if (x > 1)
{
if (mp[x - 1][y] != '#')
{
X.push(x - 1);
Y.push(y);
// cout << mp[x - 1][y] << endl;
mp[x - 1][y] = '#';
}
}
if (x < n)
{
if (mp[x + 1][y] != '#')
{
X.push(x + 1);
Y.push(y);
mp[x + 1][y] = '#';
}
}
if (y > 1)
{
if (mp[x][y - 1] != '#')
{
X.push(x);
Y.push(y - 1);
mp[x][y - 1] = '#';
}
}
if (y < m)
{
if (mp[x][y + 1] != '#')
{
X.push(x);
Y.push(y + 1);
mp[x][y + 1] = '#';
}
}
}
cout << num << endl;
}
}
5. Work 2015 Multi-University Training Contest 3
It’s an interesting experience to move from ICPC to work, end my college life and start a brand new journey in company.
As is known to all, every stuff in a company has a title, everyone except the boss has a direct leader, and all the relationship forms a tree. If A’s title is higher than B(A is the direct or indirect leader of B), we call it A manages B.
Now, give you the relation of a company, can you calculate how many people manage k people.
Input
There are multiple test cases. Each test case begins with two integers n and k, n indicates the number of stuff of the company. Each of the following n-1 lines has two integers A and B, means A is the direct leader of B. 1 <= n <= 100 , 0 <= k < n 1 <= A, B <= n
Output
For each test case, output the answer as described above.
Sample Input
7 2
1 2
1 3
2 4
2 5
3 6
3 7
Sample Output
2
-
Tips:
-
题目大体意思是： 求解树的每个节点的子树个数（不一定是二叉树）
-
注意题目输入的是多组数据，但未知有多少组，需要注意用while (scanf(“%d%d”, &n, &k) != EOF)
-
code:
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <time.h>
#include <stdio.h>
using namespace std;
typedef struct FATHER
{
int son[101];
int sonnum;
} father;
int n, m;
int A, B;
father man[101];
int fa = 0;
int num = 0;
int search(int now)
{
int count = 0;
for (int i = 0; i < man[now].sonnum; i++)
{
count += search(man[now].son[i]);
}
if (count == m)
num++;
return count + 1;
}
int main()
{
while (scanf("%d%d", &n, &m) !=EOF)
{
num = 0;
for (int i = 0; i < n - 1; i++)
{
cin >> A >> B;
man[A].son[man[A].sonnum] = B;
man[A].sonnum++;
if (fa == 0 || fa == B)
{
fa = A;
}
}
search(fa);
cout << num << endl;
}
return 0;
}
6. desert 巴卡斯杯" 中国大学生程序设计竞赛 - 女生专场
Problem Description
A tourist gets lost in the desert with n liters of water. He drinks positive integer units of water each day.
Write a program to calculate how many different ways the tourist can drink up the water.
Input
The first line contains the number of test cases T(T<10). Next T lines contain the number n(1 < n < 1000000) for each test case.
Output
Output consists of T lines. Each line contains the binary number which represents number of different ways to finish up the water specified in the test case.
Sample Input
1
3
Sample Output
100
[hint]
3 liters of water can be comsumed in four different ways show in the following.
1. 1 1 1
2. 1 2
3. 2 1
4. 3
If we write 4 in binary, it's 100.
[/hint]
-
tips:
这一题有规律 : 类似 整数拆分+ 排列组合
6
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <time.h>
#include <stdio.h>
#include <stack>
using namespace std;
int n, m;
int main()
{
cin >> n;
while (n--)
{
cin >> m;
cout << "1";
for (int i = 0; i < m - 1; i++)
cout << "0";
cout << endl;
}
return 0;
}
7. Let the Balloon Rise ZJCPC2004
Problem Description
Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges’ favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.
This year, they decide to leave this lovely job to you.
Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) – the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters. A test case with N = 0 terminates the input and this test case is not to be processed.
Output
For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.
Sample Input
5
green
red
blue
red
red
3
pink
orange
pink
0
Sample Output
red
pink
-
tips:
map映射 通过pair的方式插入，以及计数
类似： 记录输入中字符串出现的次数
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <time.h>
#include <stdio.h>
#include <map>
using namespace std;
int n;
string str;
int main()
{
map<string, int> mp;
map<string, int>::iterator it;
while (1)
{
cin >> n;
mp.clear();
if (n == 0)
break;
for (int i = 0; i < n; i++)
{
cin >> str;
//getchar();
// cout << str << " ";
it = mp.find(str);
if (it != mp.end())
{
it->second++;
}
else
{
mp.insert(make_pair(str, 1));
}
}
it = mp.begin();
while (it != mp.end())
{
if (it->second > mp.find(str)->second)
{
str = it->first;
}
it++;
}
cout << str << endl;
}
}