NUMBER BASE CONVERSION
Write a program to convert numbers in one base to numbers in a second base. There are 62 different digits:{ 0-9,A-Z,a-z }HINT: If you make a sequence of base conversions using the output of 阅读全文 »
poj1218
15
9月
2015
THE DRUNK JAILER
A certain prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner in it, and each cell is locked.One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the hall locking every other cell (cells 2, 4, 6, ?). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ?). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He repeats this for n rounds, takes a final drink, and passes out. Some number of prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.
Given the number of cells, determine how many prisoners escape jail.
Input
The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.
Output
For each line, you must print out the number of prisoners that escape when the prison has n cells.
Sample Input
2
5
100
Sample Output
2
10
Source
题目类型：模拟
算法分析：先将数组中的每一个元素初始化为某一个标志，然后按照题目所给的关于开、闭门及转换门状态的规律模拟进行n次，最后统计与初始标志相反的元素的个数，即为所求
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <cstdio> #include <iostream> #include <fstream> #include <cstring> using namespace std; int isopen[106]; int main() { int n, cases; //ifstream cin ("aaa.txt"); cin >> cases; while (cases--) { cin >> n; memset (isopen, -1, sizeof (isopen)); int i; for (i = 1; i <= n; i++) { int j; for (j = 1; i * j <= n; j++) isopen[i*j] = - isopen[i*j]; } int num = 0; for (i = 1; i <= n; i++) { if (isopen[i] == 1) num++; } printf ("%d\n", num); } return 0; } |
poj1195
15
9月
2015
Mobile phones
Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S * S matrix with the rows and columns 阅读全文 »
poj1182
15
9月
2015
食物链
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。 阅读全文 »
poj1163
15
9月
2015
The Triangle
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either 阅读全文 »
poj1157
15
9月
2015
LITTLE SHOP OF FLOWERS
You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.
Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.
| V A S E S | ||||||
| 1 | 2 | 3 | 4 | 5 | ||
| Bunches | 1 (azaleas) | 7 | 23 | -5 | -24 | 16 |
| 2 (begonias) | 5 | 21 | -4 | 10 | 23 | |
| 3 (carnations) | -21 | 5 | -4 | -20 | 20 | |
According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.
To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.
Input
- The first line contains two numbers: F, V.
- The following F lines: Each of these lines contains V integers, so that Aij is given as the jth number on the (i+1)st line of the input file.
- 1 <= F <= 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.
- F <= V <= 100 where V is the number of vases.
- -50 <= Aij <= 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.
Output
The first line will contain the sum of aesthetic values for your arrangement.
Sample Input
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
Sample Output
53
Source
题目类型：线性dp
算法分析：类似于经典线性dp的三角形最大和问题，只不过这里的下一行的数必须上一行的数的列数大，可以直接在原数组上进行递推，最后查找最后一行中最大的数即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1000000000 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; int ans[maxn][maxn]; int main() { // ifstream cin ("aaa.txt"); int row, col; while (cin >> row >> col) { for (int i = 0;i < row; i++) for (int j = 0; j < col; j++) cin >> ans[i][j]; for (int i = 1; i < row; i++) { for (int j = i; j < col; j++) { int temp = ans[i][j]; ans[i][j] += ans[i-1][0]; for (int k = 1; k < j; k++) ans[i][j] = max (ans[i][j], ans[i-1][k] + temp); } } int maxval = -INF; for (int i = 2; i < col; i++) maxval = max (maxval, ans[row-1][i]); cout << maxval << endl; } return 0; } |
poj1151
15
9月
2015
Atlantis
There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different 阅读全文 »
poj1149
maksyuki 发表于 oj 分类，标签: 图论(网络流)-最大流
15
9月
2015
PIGS
Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs. All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold. More precisely, the procedure is as following: the customer arrives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses. An unlimited number of pigs can be placed in every pig-house. Write a program that will find the maximum number of pigs that he can sell on that day.
Input
The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.
Output
The first and only line of the output should contain the number of sold pigs.
Sample Input
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6
Sample Output
7
Source
Croatia OI 2002 Final Exam - First day
题目类型：最大流
算法分析：将每个顾客看做是一个节点，然后对于第一个去猪圈的顾客，将源点和其相连，边权是这个猪圈的初始猪数，对于一个猪圈，之后来的顾客，其与前一个在这个猪圈的顾客相连，权值是INF，最后每个顾客希望得到的最大猪数就是其与汇点相连的边权，建完图之后，直接调用EK算法即可，注意此时源点和汇点分别取值0、n+1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; struct Node { int c, f;//分别表示弧之间的容量和流量 }; Node edge[maxn][maxn]; int n, m, pre[maxn], a[maxn]; long long Edmonds_Karp (int s, int t) { queue <int> q; memset (a, 0, sizeof(a)); memset (pre, 0, sizeof(pre)); long long maxflow = 0; while (1) { memset (a, 0, sizeof(a)); a[s] = INF; q.push(s); while (!q.empty()) { int tt = q.front(); q.pop(); for (int i = 0; i <= n + 1; i++) if(!a[i] && edge[tt][i].c > edge[tt][i].f) { pre[i] = tt; q.push (i); a[i] = a[tt] < edge[tt][i].c - edge[tt][i].f ? a[tt]:edge[tt][i].c - edge[tt][i].f; } } if(a[t] == 0) break; for(int i = t; i != s; i = pre[i]) { edge[pre[i]][i].f += a[t]; edge[i][pre[i]].f -= a[t]; } maxflow += a[t]; } return maxflow; } int pig[maxn], last[maxn]; int main() { // ifstream cin ("aaa.txt"); while (cin >> m >> n) { memset (edge, 0, sizeof (edge)); memset (last, 0, sizeof (last)); for (int i =1; i <= m; i++) cin >> pig[i]; for (int i = 1; i <= n; i++) { int tt; cin >> tt; for (int j = 1; j <= tt; j++) { int k; cin >> k; if (!last[k]) edge[0][i].c += pig[k]; else edge[last[k]][i].c = INF; last[k] = i; } cin >> edge[i][n+1].c; } cout << Edmonds_Karp (0, n + 1) << endl; } return 0; } |
poj1144
maksyuki 发表于 oj 分类，标签: 图论-求解割点\割边(Tarjan)
15
9月
2015
Network
A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.
Input
The input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N < 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated
by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0;
Output
The output contains for each block except the last in the input file one line containing the number of critical places.
Sample Input
5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0
Sample Output
1
2
Hint
You need to determine the end of one line.In order to make it's easy to determine,there are no extra blank before the end of each line.
Source
题目类型：割点数量
算法分析：直接使用Tarjan算法求出每个点的连通分量的个数，然后按照所得的结果判断每个节点是否是割点，注意要额外判断根节点的情况！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits>() #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define i64 long long const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; //分别表示邻接矩阵、访问数组、dfs深度优先数、当前节点可以到达的最低优先数和每个节点的连通分量数(删去该节点) int edge[maxn][maxn], vis[maxn], dfsn[maxn], low[maxn], subnets[maxn]; int n, id;//分别表示节点总数和全局标志(标记dfs深度优先数) void Init (int rt) { for (int i = 0; i < maxn; i++)//初始化邻接矩阵 for (int j = 0; j < maxn; j++) { if (i == j) edge[i][j] = 0; else edge[i][j] = INF; } dfsn[rt] = low[rt] = id = 1;//将根节点的dfsn和low值都置为1 memset (vis, 0, sizeof (vis)); vis[rt] = 1;//初始化访问数组vis memset (subnets, 0, sizeof (subnets));//初始化连通分量数组subnets } void dfs (int u) { for (int v = 1; v <= n; v++)//依次判断所有的邻接点 { if (edge[u][v] < INF && u != v && !vis[v])//如果邻接且v为u的孩子节点 { vis[v] = 1; dfsn[v] = low[v] = ++id;//访问该孩子节点并打上标志 dfs (v);//递归地访问v的孩子节点 low[u] = min (low[u], low[v]);//使用u的孩子节点v的low值来更新u的low值 if (low[v] >= dfsn[u])//如果孩子节点的low值(深度)大于等于当前节点u的dfsn值(深度)，连通分量个数自加1 subnets[u]++; } else if (edge[u][v] < INF && u != v && vis[v])//如果邻接且v为u的祖先节点 low[u] = min (low[u], dfsn[v]);//直接使用回边中祖先节点的dfsn值更新u的low值即可 } } int main() { // CPPFF; while (cin >> n) { if (n == 0) break; Init(1); string s; getline (cin, s); while(getline(cin, s)) { stringstream ss (s); int a; ss >> a; if (a == 0) break; int b; while (ss >> b) { edge[a][b] = edge[b][a] = 1; } } dfs (1); int res = 0; for (int i = 1; i <= n; i++) { if (i == 1 && subnets[i] > 1) res++; else if (i != 1 && subnets[i]) res++; } cout << res << endl; } return 0; } |
poj1135
15
9月
2015
Domino Effect
Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build 阅读全文 »
poj1125
15
9月
2015
Stockbroker Grapevine
Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge 阅读全文 »
poj1122
15
9月
2015
FDNY to the Rescue!
The Fire Department of New York (FDNY) has always been proud of their response time to fires in New York City, but they want to make their response time even better. To help them 阅读全文 »
poj1068
15
9月
2015
Parencodings
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways: 阅读全文 »
poj1067
maksyuki 发表于 oj 分类，标签: 博弈-Wythoff
15
9月
2015
取石子游戏
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 阅读全文 »
poj1064
maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举
15
9月
2015
Cable master
Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it.To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible.
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled.
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.
Input
The first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point.
Output
Write to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point.
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes).
Sample Input
4 11
8.02
7.43
4.57
5.39
Sample Output
2.00
Source
题目类型：二分
算法分析：在[0, INF]之间二分枚举长度。对于每一次枚举的长度，判断使用该长度是否能够将k个电缆割好。如果能，则向上枚举长度，否则向下枚举长度，注意本题的坑点是精度！！！！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 16000 + 66; double ans[maxn]; int n, k; bool Solve (double val) { int i, sum = 0; for (i = 0; i < n; i++) { sum += (int) (ans[i] / val); } if (sum >= k) return true; return false; } int main() { // freopen ("aaa.txt", "r", stdin); while (scanf ("%d%d", &n, &k) != EOF) { int i; for (i = 0; i < n; i++) scanf ("%lf", &ans[i]); double L = 0, R = INF * 1.0, mid; int cnt = 1; while (cnt <= 100) { mid = (L + R) / 2.0; if (Solve (mid)) L = mid; else R = mid; cnt++; } printf ("%.2f\n", floor (L * 100) / 100); } return 0; } |