Maximum sum
Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
Your task is to calculate d(A).
Input
The input consists of T(<=30) test cases. The number of 阅读全文 »
poj2478
15
9月
2015
Farey Sequence
The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are
F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
You task is to calculate the number of terms in the Farey sequence Fn.
Input
There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 106). There are no blank lines between cases. A line with a single 0 terminates the input.
Output
For each test case, you should output one line, which contains N(n) ---- the number of terms in the Farey sequence Fn.
Sample Input
2
3
4
5
0
Sample Output
1
3
5
9
Source
POJ Contest,Author:Mathematica@ZSU
题目类型：法雷级数
算法分析：法雷级数F(n)等于小于等于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 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 |
#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 = 1000000 + 66; long long euler[maxn]; void GetEuler () { for (long long i = 0; i < maxn; i++) euler[i] = i; for (long long i = 2; i < maxn; i += 2) euler[i] >>= 1; for (long long i = 3; i < maxn; i += 2) { if (euler[i] == i) { for (long long j = i; j < maxn; j += i) euler[j] = euler[j] - euler[j] / i; } } } int main() { // ifstream cin ("aaa.txt"); GetEuler (); for (long long i = 1; i < maxn; i++) euler[i] += euler[i-1]; long long val; while (cin >> val) { if (val == 0) break; cout << euler[val] - 1<< endl; } return 0; } |
poj2456
maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举
15
9月
2015
Aggressive cows
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000). His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Input
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Line i+1 contains an integer stall location, xi
Output
* Line 1: One integer: the largest minimum distance
Sample Input
5 3
1
2
8
4
9
Sample Output
3
Hint
OUTPUT DETAILS:
FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.
Huge input data,scanf is recommended.
Source
题目类型：二分
算法分析：首先将距离按照从小到大的顺序排列，二分枚举距离，然后按照该距离将牛分配到这些牛棚中，看能不能将牛全部安排好，如果能则将距离提高，继续枚举；否则将距离减小，继续枚举
|
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 |
#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 = 166000 + 66; int ans[maxn]; int n, c; bool Solve (int val) { int i, sum = 1, p = ans[0]; for (i = 1; i < n; i++) { if (ans[i] - p >= val) { sum++; p = ans[i]; } } if (sum >= c) return false; return true; } int main() { // freopen ("aaa.txt", "r", stdin); while (scanf ("%d%d", &n, &c) != EOF) { int i; for (i = 0; i < n; i++) scanf ("%d", &ans[i]); sort (ans, ans + n); int L = 1, R = ans[n-1], mid; while (L <= R) { mid = (L + R) >> 1; if (Solve (mid)) R = mid - 1; else L = mid + 1; } printf ("%d\n", R); } return 0; } |
poj2417
15
9月
2015
Discrete Logging
Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that
BL == N (mod P)
Input 阅读全文 »
poj2406
15
9月
2015
Power Strings
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "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).
Input
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.
Output
For each s you should print the largest n such that s = a^n for some string a.
Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
Source
题目类型：KMP中Next数组应用
算法分析：直接计算出输入字符串的Next数组，然后判断len % (len – Next[len])是否为0，如果为0，则len / (len – Next[len])即为最后的答案，否则结果为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 |
#include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int INF = 0x7FFFFFFF; const int maxn = 1000000 + 66; int Next[maxn], len; string s; void Build () { Next[0] = -1, Next[1] = 0; int k = 0, i; for (i = 2; i <= len; i++) { while (k >= 0 && s[i-1] != s[k]) k = Next[k]; Next[i] = ++k; } } int main() { // ifstream cin ("aaa.txt"); while (cin >> s) { if (s == ".") break; len = s.length (); Build (); if (len % (len - Next[len]) == 0) cout << len / (len - Next[len]) << endl; else cout << "1" << endl; } return 0; } |
poj2387
15
9月
2015
Til the Cows Come Home
Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible. Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.
Input
Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.
* Line 1: Two integers: T and N
* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.
Output
* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.
Sample Input
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output
90
Hint
INPUT DETAILS:
There are five landmarks.
OUTPUT DETAILS:
Bessie can get home by following trails 4, 3, 2, and 1.
Source
题目类型：Dijkstra算法
算法分析：直接使用Dijkstra求解即可，注意输入数据可能出现重边的情况，此时贪心的将最小边权保留!!!
|
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 |
#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; bool vis[maxn];//表示节点的最短路是否已经得到 //分别表示邻接矩阵、节点最短路的长度和顶点的个数 int edge[maxn][maxn], dis[maxn], n; void Init () { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i == j) edge[i][j] = 0; else edge[i][j] = INF; } } void Dijkstra (int s) { memset (vis, false, sizeof (vis));; vis[s] = true; for (int i = 1; i <= n; i++)//初始化源点相邻接的节点的最短距离 dis[i] = edge[s][i]; dis[s] = 0;//源点到自己的最短路是0，十分重要!!! for (int i = 2; i <= n; i++) { int minval = INF, minpos = s; for (int j = 1; j <= n; j++)//遍历将还未确定最短路的节点中具有最小距离的的节点找到 if (j != s && !vis[j] && minval > dis[j]) { minval = dis[j]; minpos = j; } vis[minpos] = true;//访问该节点 for (int j = 1; j <= n; j++)//更新由于minpos节点确定最短路之后导致的最小距离变化 if (j != s && !vis[j] && edge[minpos][j] < INF && edge[minpos][j] + dis[minpos] < dis[j]) dis[j] = edge[minpos][j] + dis[minpos]; } } int main() { // ifstream cin ("aaa.txt"); int t; while (cin >> t >> n) { Init (); for (int i = 1; i <= t; i++) { int u, v, w; cin >> u >> v >> w; if (edge[u][v] > w) edge[u][v] = edge[v][u] = w; } Dijkstra (n); cout << dis[1] << endl; } return 0; } |
poj2352
15
9月
2015
Stars
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars. For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3. You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
0
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
Source
Ural Collegiate Programming Contest 1999
题目类型：线段树
算法分析：由于题目中已经给出的坐标是已经按照y坐标递增排序好的，所以以某点(x,y)和原点为对角线构造的矩形中的点的个数可以直接求在[0,x]范围内点的横坐标的个数，然后判断完level之后，直接更新x坐标处的点的个数
|
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 |
#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 int MOD = 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 32000 + 66; int cnt[maxn<<2], sum[maxn<<2]; void PushUp (int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void UpDate (int rt, int l, int r, int val, int num) { if (l == r) { sum[rt] += num; return ; } int m = (l + r) >> 1; if (val <= m) UpDate (lson, val, num); else UpDate (rson, val, num); PushUp (rt); } int Query (int rt, int l, int r, int L, int R) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; int ans = 0; if (L <= m) ans += Query (lson, L, R); if (R > m) ans += Query (rson, L, R); return ans; } int main() { // freopen ("aaa.txt", "r", stdin); int n; while (scanf ("%d", &n) != EOF) { memset (cnt, 0, sizeof (cnt)); memset (sum, 0, sizeof (sum)); int i, val_x, val_y; for (i = 0; i < n; i++) { scanf ("%d%d", &val_x, &val_y); cnt[Query(1, 0, maxn, 0, val_x)]++; UpDate (1, 0, maxn, val_x, 1); } for (i = 0; i < n; i++) printf ("%d\n", cnt[i]); } return 0; } |
poj2342
15
9月
2015
Anniversary party
There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings.
Input
Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go N – 1 lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
Output
Output should contain the maximal sum of guests' ratings.
Sample Input
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
Sample Output
5
Source
Ural State University Internal Contest October'2000 Students Session
题目类型：树形DP
算法分析：使用dp[i][0]和dp[i][1]分别表示以第i个节点为子树且i来、不来时的最大喜欢直，然后使用树的后序遍历从叶子节点开始将每个节点的最大喜欢值求出来，注意本题中没有告诉root位置，所以需要自己在输入中找
|
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 |
#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 = 6000 + 66; int dp[maxn][2], parent[maxn], vis[maxn]; int n; void dfs (int root) { vis[root] = 1; for (int i = 1; i <= n; i++) if (!vis[i] && parent[i] == root) { dfs (i); dp[root][1] += dp[i][0]; dp[root][0] += max (dp[i][0], dp[i][1]); } } int main() { // ifstream cin ("aaa.txt"); while (cin >> n) { memset (dp, 0, sizeof (dp)); for (int i = 1; i <= n; i++) cin >> dp[i][1]; memset (parent, 0, sizeof (parent)); memset (vis, 0, sizeof (vis)); int a, b, root = 0; while (cin >> a >> b) { if (a == 0 && b == 0) break; parent[a] = b; root = b; } dfs (root); cout << max (dp[root][0], dp[root][1]) << endl; } return 0; } |
poj2263
15
9月
2015
Heavy Cargo
Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive. Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.
Input
The input will contain one or more test cases. The first line of each test case will contain two integers: the number of cities n (2<=n<=200) and the number of road segments r (1<=r<=19900) making up the street network.
Then r lines will follow, each one describing one road segment by naming the two cities connected by the segment and giving the weight limit for trucks that use this segment. Names are not longer than 30 characters and do not contain white-space characters. Weight limits are integers in the range 0 - 10000. Roads can always be travelled in both directions.
The last line of the test case contains two city names: start and destination.
Input will be terminated by two values of 0 for n and r.
Output
For each test case, print three lines:
- a line saying "Scenario #x" where x is the number of the test case
- a line saying "y tons" where y is the maximum possible load
- a blank line
Sample Input
4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0
Sample Output
Scenario #1
80 tons
Scenario #2
170 tons
Source
题目类型：Floyd思想
算法分析：以读入的字符串构建图，然后使用Floyd算法思想来迭代求解，迭代公式为：edge[i][j] = max (edge[i][j], min (edge[i][k], edge[k][j]))。注意一定要初始化edge[i][j]数组，其中i == j时，edge[i][j] == INF，表示自己到自己的路径上载重无限制。当i != j时，edge[i][j] == 0，表示i到j的路径上载重限制为无穷
|
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 |
#include <iostream> #include <fstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int maxn = 666 + 66; const int INF = 66666666; int edge[maxn][maxn]; int n, r; vector <string> vec; int GetVal (string val) { int i; for (i = 0; i < vec.size (); i++) if (val == vec[i]) return i; vec.push_back (val); return i; } void floyd () { int i, j, k; for (k = 0; k < n; k++) { for (i = 0; i < n; i++) { for (j = 0; j < n; j++) edge[i][j] = max (edge[i][j], min (edge[i][k], edge[k][j])); } } } int main() { // ifstream cin ("aaa.txt"); int flag = 1; while (cin >> n >> r) { if (n == 0 && r == 0) break; vec.clear (); int i, j; for (i = 0; i < maxn; i++) for (j = 0; j < maxn; j++) { if (i == j) edge[i][j] = INF; else edge[i][j] = 0; } string val_a, val_b; int val_w; for (i = 0; i < r; i++) { cin >> val_a >> val_b >> val_w; int u = GetVal (val_a); int v = GetVal (val_b); edge[u][v] = val_w; edge[v][u] = val_w; } floyd (); cout << "Scenario #" << flag++ << endl; cin >> val_a >> val_b; int u = GetVal (val_a); int v = GetVal (val_b); cout << edge[u][v] << " tons" << endl << endl; } return 0; } |
poj2259
maksyuki 发表于 oj 分类，标签: 数据结构-队列\双端\单调\优先
15
9月
2015
Team Queue
Queues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa is a team queue, for example. In a team queue each element belongs to a team. If an element enters the queue, it first searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue. Your task is to write a program that simulates such a team queue.
Input
The input will contain one or more test cases. Each test case begins with the number of teams t (1<=t<=1000). Then t team descriptions follow, each one consisting of the number of elements belonging to the team and the elements themselves. Elements are integers in the range 0 - 999999. A team may consist of up to 1000 elements.
Finally, a list of commands follows. There are three different kinds of commands:
- ENQUEUE x - enter element x into the team queue
- DEQUEUE - process the first element and remove it from the queue
- STOP - end of test case
The input will be terminated by a value of 0 for t.
Warning: A test case may contain up to 200000 (two hundred thousand) commands, so the implementation of the team queue should be efficient: both enqueing and dequeuing of an element should only take constant time.
Output
For each test case, first print a line saying "Scenario #k", where k is the number of the test case. Then, for each DEQUEUE command, print the element which is dequeued on a single line. Print a blank line after each test case, even after the last one.
Sample Input
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0
Sample Output
Scenario #1
101
102
103
201
202
203
Scenario #2
259001
259002
259003
259004
259005
260001
Source
题目类型：队列
算法分析：使用map<int, int> team来表示成员的团队标志，使用一个队列表示团队队列，使用一个队列数组表示子团队的队列。先输入所有成员的团队标志，然后分类模拟，如果是”STOP”；则退出模拟；如果是”ENQUEUE”，则将新成员输入并判断其所在的团队是否在团队队列中，如果不在就将所在团队插入到团队队列中，然后将新成员插入到子团队的队列中；如果是”DEQUEUE”，则先输出团队队列队头成员并删除，接着判断被删除成员先前所在的子团队队列是否为空，如果为空，则从团队队列中删除该子队列
|
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 <iostream> #include <fstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int maxn = 1000 + 66; int team[999999+6]; int main() { int flag = 1; // ifstream cin ("aaa.txt"); // freopen ("aaa.txt", "r", stdin); int n; while (cin >> n) { if (n == 0) break; int i; for (i = 0; i < n; i++) { int num; cin >> num; int j, temp; for (j = 0; j < num; j++) { cin >> temp; team[temp] = i; } } cout << "Scenario #" << flag++ << endl; string input; queue <int> tq, q[maxn]; while (cin >> input) { if (input == "STOP") break; if (input == "ENQUEUE") { int temp; cin >> temp; int val = team[temp]; if (q[val].empty ()) tq.push (val); q[val].push (temp); } else if (input == "DEQUEUE") { if (!tq.empty ()) { int temp = tq.front (); cout << q[temp].front () << endl; q[temp].pop (); if (q[temp].empty ()) tq.pop (); } } } cout << endl; } return 0; } |
poj2234
15
9月
2015
Matches Game
Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not.
Input
The input consists of several lines, and in each line there is a test case. At the beginning of a line, there is an integer M (1 <= M <=20), which is the number of piles. Then comes M positive integers, which are not larger than 10000000. These M integers represent the number of matches in each pile.
Output
For each test case, output "Yes" in a single line, if the player who play first will win, otherwise output "No".
Sample Input
2 45 45
3 3 6 9
Sample Output
No
Yes
Source
POJ Monthly,readchild
题目类型：Nim博弈
算法分析：这是一道Nim博弈的经典题目。算法是用二进制表示每堆火柴棍的根数。将二进制表示的输入数据各个位分别相加，再求除以2的余数，如果余数为0，则先手的必输，反之，则必胜
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <cstdio> #include <iostream> using namespace std; int main() { int n; while (cin >> n) { int t = 0, k; while (n--) { cin >> k; t ^= k; } printf ("%s\n", t ? "Yes" : "No"); } return 0; } |
poj2201
15
9月
2015
Cartesian Tree
Let us consider a special type of a binary search tree, called a cartesian tree. Recall that a binary search tree is a rooted ordered binary tree, such that for its every node x the following condition is satisfied: each node in its left subtree has the key less then the key of x, and each node in its right subtree has the key greater then the key of x. That is, if we denote left subtree of the node x by L(x), its right subtree by R(x) and its key by kx then for each node x we have
- if y ∈ L(x) then ky < kx
- if z ∈ R(x) then kz > kx
The binary search tree is called cartesian if its every node x in addition to the main key kx also has an auxiliary key that we will denote by ax, and for these keys the heap condition is satisfied, that is
- if y is the parent of x then ay < ax
Thus a cartesian tree is a binary rooted ordered tree, such that each of its nodes has a pair of two keys (k, a) and three conditions described are satisfied. Given a set of pairs, construct a cartesian tree out of them, or detect that it is not possible.
Input
The first line of the input file contains an integer number N -- the number of pairs you should build cartesian tree out of (1 <= N <= 50 000). The following N lines contain two numbers each -- given pairs (ki, ai). For each pair |ki|, |ai| <= 30 000. All main keys and all auxiliary keys are different, i.e. ki != kj and ai != aj for each i != j.
Output
On the first line of the output file print YES if it is possible to build a cartesian tree out of given pairs or NO if it is not. If the answer is positive, on the following N lines output the tree. Let nodes be numbered from 1 to N corresponding to pairs they contain as they are given in the input file. For each node output three numbers -- its parent, its left child and its right child. If the node has no parent or no corresponding child, output 0 instead.
The input ensure these is only one possible tree.
Sample Input
7
5 4
2 2
3 9
0 5
1 3
6 6
4 11
Sample Output
YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0
Source
Northeastern Europe 2002, Northern Subregion
题目类型：笛卡尔树的构建
算法分析：直接使用O(n)的右链算法构建出一个笛卡尔树，最后进行一次遍历将所有节点的儿子父亲关系找到，然后直接输出。如果所给节点中存在相同的key值的话，直接输出NO，这是因为BST中是不可能出现相同key的。在向笛卡尔树中插入节点时要注意修改待插入节点的左孩子的父节点！！！
|
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 126 127 128 129 130 131 132 |
#pragma comment(linker, "/STACK:102400000,102400000") #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 LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 5e4 + 66; struct node { int l, r, par, key; int v, rnd; }; bool operator < (const node &aa, const node &bb) {return aa.v < bb.v;} node dt[maxn], res[maxn]; bool vis[maxn]; void Init () { for (int i = 0; i < maxn; i++) { dt[i].l = dt[i].r = dt[i].par = 0; dt[i].rnd = -INF; } } void Insert (int rt) { int i = rt - 1; while (dt[i].rnd > dt[rt].rnd) i = dt[i].par; dt[rt].l = dt[i].r; dt[dt[i].r].par = rt; dt[rt].par = i; dt[i].r = rt; } int main() { // CFF; int n; while (scanf ("%d", &n) != EOF) { memset (vis, false, sizeof (vis)); bool is_valid = true; Init (); for (int i = 1; i <= n; i++) { scanf ("%d%d", &dt[i].v, &dt[i].rnd); dt[i].key = i; if (vis[dt[i].v]) is_valid = false; else vis[dt[i].v] = true; } if (!is_valid) puts ("NO"); else { puts ("YES"); sort (dt + 1, dt + 1 + n); for (int i = 1; i <= n; i++) Insert (i); for (int i = 1; i <= n; i++) { if (!dt[i].l) res[dt[i].key].l = 0; else res[dt[i].key].l = dt[dt[i].l].key; if (!dt[i].r) res[dt[i].key].r = 0; else res[dt[i].key].r = dt[dt[i].r].key; if (!dt[i].par) res[dt[i].key].par = 0; else res[dt[i].key].par = dt[dt[i].par].key; } for (int i = 1; i <= n; i++) printf ("%d %d %d\n", res[i].par, res[i].l, res[i].r); } } return 0; } |
poj2142
15
9月
2015
The Balance
Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Although she could put four 300mg weights on the medicine side and two 700mg weights on the other (Figure 2), she would not choose this solution because it is less convenient to use more weights. You are asked to help her by calculating how many weights are required.
Input
The input is a sequence of datasets. A dataset is a line containing three positive integers a, b, and d separated by a space. The following relations hold: a != b, a <= 10000, b <= 10000, and d <= 50000. You may assume that it is possible to measure d mg using a combination of a mg and b mg weights. In other words, you need not consider "no solution" cases.
The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.
Output
The output should be composed of lines, each corresponding to an input dataset (a, b, d). An output line should contain two nonnegative integers x and y separated by a space. They should satisfy the following three conditions.
- You can measure dmg using x many amg weights and y many bmg weights.
- The total number of weights (x + y) is the smallest among those pairs of nonnegative integers satisfying the previous condition.
- The total mass of weights (ax + by) is the smallest among those pairs of nonnegative integers satisfying the previous two conditions.
No extra characters (e.g. extra spaces) should appear in the output.
Sample Input
700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0
Sample Output
1 3
1 1
1 0
0 3
1 1
49 74
3333 1
Source
题目类型：二元一次不定方程
算法分析：题目中要求ax+by尽可能小，即方程右边只有d(ax+by=d)，才可能满足条件。此时可以使用扩展欧几里得算法分别求出不定方程的最小非负特解x0和y0。然后分别求出此时的y和x。最后比较两个x、y的和的大小。取较小的那个x和y输出
|
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 |
#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 lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 50000 + 66; long long ex_gcd (long long a, long long b, long long &x, long long &y) { if (b == 0) {x = 1; y = 0; return a;} long long tt = ex_gcd(b, a % b, y, x); y = y - a / b * x; return tt; } int main() { // ifstream cin("aaa.txt"); // freopen ("aaa.txt", "r", stdin); long long a, b, d; while (cin >> a >> b >> d) { if (a == 0 && b == 0 && d == 0) break; long long tt, xx, yy; tt = ex_gcd(a, b, xx, yy); // cout << xx << " " << yy << endl; long long maxval_posx = -1, maxval_posy = -1; xx = xx * d / tt; yy = yy * d / tt; // cout << xx << " " << yy << endl; long long tx = xx % (b / tt); if (xx < 0) tx += b / tt; long long ty = (d - a * tx) / b; if (ty < 0) ty = -ty; long long maxval = tx + ty; maxval_posx = tx, maxval_posy = ty; ty = yy % (a / tt); if (ty < 0) ty += a / tt; // cout << ty << endl; tx = (d - b * ty) / a; if(tx < 0) tx = -tx; if (maxval > tx + ty) { maxval_posx = tx; maxval_posy = ty; } cout << maxval_posx << " " << maxval_posy << endl; } return 0; } |
poj2115
maksyuki 发表于 oj 分类，标签: 数论-线性同余方程(组)
15
9月
2015
C Looooops
A Compiler Mystery: We are given a C-language style for loop of type
for (variable = A; variable != B; variable += C)
statement; 阅读全文 »
poj2105
maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理
15
9月
2015
IP Address
Suppose you are reading byte streams from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of '1s' and '0s' (bits) to a dotted decimal format. A dotted decimal format for an IP address is form by grouping 8 bits at a time and converting the binary representation to decimal representation. Any 8 bits is a valid part of an IP address. To convert binary numbers to decimal numbers remember that both are positional numerical systems, where the first 8 positions of the binary systems are:
27 26 25 24 23 22 21 20
128 64 32 16 8 4 2 1
Input
The input will have a number N (1<=N<=9) in its first line representing the number of streams to convert. N lines will follow.
Output
The output must have N lines with a doted decimal IP address. A dotted decimal IP address is formed by grouping 8 bit at the time and converting the binary representation to decimal representation.
Sample Input
4
00000000000000000000000000000000
00000011100000001111111111111111
11001011100001001110010110000000
01010000000100000000000000000001
Sample Output
0.0.0.0
3.128.255.255
203.132.229.128
80.16.0.1
Source
México and Central America 2004
题目类型：简单字符处理
算法分析：按照题目的要求将每8位的二进制数字转换为十进制，注意使用c语言中自带的库函数strtol，将base进制的数转换为十进制输出的数组中
|
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 |
#include <cstdio> #include <iostream> #include <fstream> #include <cstdlib> using namespace std; int main() { int cases; //ifstream cin ("aaa.txt"); cin >> cases; while (cases--) { int i; for (i = 0; i < 4; i++) { char s[16]; int temp; scanf ("%8s", s); temp = strtol (s, 0, 2); if (i < 3) printf ("%d.", temp); else printf ("%d\n", temp); } } return 0; } |
poj2082
maksyuki 发表于 oj 分类，标签: 数据结构-队列\双端\单调\优先
15
9月
2015
Terrible Sets
Let N be the set of all natural numbers {0 , 1 , 2 , . . . }, and R be the set of all real numbers. wi, hi for i = 1 . . . n are some elements in N, and w0 = 0. Define set B = {< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑0<=j<=i-1wj <= x <= ∑0<=j<=iwj} Again, define set S = {A| A = WH for some W , H ∈ R+ and there exists x0, y0 in N such that the set T = { < x , y > | x, y ∈ R and x0 <= x <= x0 +W and y0 <= y <= y0 + H} is contained in set B}. Your mission now. What is Max(S)? Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy. But for this one, believe me, it's difficult.
Input
The input consists of several test cases. For each case, n is given in a single line, and then followed by n lines, each containing wi and hi separated by a single space. The last line of the input is an single integer -1, indicating the end of input. You may assume that 1 <= n <= 50000 and w1h1+w2h2+...+wnhn < 109.
Output
Simply output Max(S) in a single line for each case.
Sample Input
3
1 2
3 4
1 2
3
3 4
1 2
3 4
-1
Sample Output
12
14
Source
题目类型：单调队列
算法分析：一道经典的使用单调队列思想解的题。坐标从小到大的分析，如果存在一个高度不超过先前的高度，则应该将先前高度的矩形块的面积出栈并计算，更新最大值。否则就一直入栈。最后将还在栈中的矩形块的面积计算出来并更新最大值
|
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 |
#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 double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 10000007; const int maxn = 100000 + 66; struct Node { long long h, w; Node (long long hh, long long ww) : h (hh), w (ww) {} Node () {h = 0, w = 0;} }; int main() { // freopen ("aaa.txt", "r", stdin); int n; while (scanf ("%d", &n) != EOF) { if (n == -1) break; deque <Node> deq; long long maxval = -INF, cnt; int i, W, H; for (i = 0; i < n; i++) { scanf ("%d%d", &W, &H); cnt = 0; while (!deq.empty() && deq.back().h >= H) { Node temp = deq.back (); deq.pop_back(); if (maxval < temp.h * (temp.w + cnt)) maxval = temp.h * (temp.w + cnt); cnt += temp.w; } deq.push_back (Node (H, W + cnt)); } cnt = 0; while (!deq.empty ()) { Node temp = deq.back (); deq.pop_back (); if (maxval < temp.h * (temp.w + cnt)) maxval = temp.h * (temp.w + cnt); cnt += temp.w; } printf ("%lld\n", maxval); } return 0; } |