15 | 9月 | 2015 | 超客的水墨烟雨

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

Sample Output

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

USACO 2005 February Gold

题目类型：二分

算法分析：首先将距离按照从小到大的顺序排列，二分枚举距离，然后按照该距离将牛分配到这些牛棚中，看能不能将牛全部安排好，如果能则将距离提高，继续枚举；否则将距离减小，继续枚举

#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;
}

#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

maksyuki 发表于 oj 分类，标签: 数论-离散对数

15 9月 2015

Discrete Logging

Given a prime P, 2 <= P < 2³¹, 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

B^L == N (mod P)

Input 阅读全文 »

poj2406

maksyuki 发表于 oj 分类，标签: 字符串-KMP

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

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

Source

Waterloo local 2002.07.01

题目类型：KMP中Next数组应用

算法分析：直接计算出输入字符串的Next数组，然后判断len % (len – Next[len])是否为0，如果为0，则len / (len – Next[len])即为最后的答案，否则结果为1

#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;
}

#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

maksyuki 发表于 oj 分类，标签: 图论-最短路

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

Hint

INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.

Source

USACO 2004 November

题目类型：Dijkstra算法

算法分析：直接使用Dijkstra求解即可，注意输入数据可能出现重边的情况，此时贪心的将最小边权保留!!!

#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;
}

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

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

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

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坐标处的点的个数

#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;
}

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

maksyuki 发表于 oj 分类，标签: DP-树形DP

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

Source

Ural State University Internal Contest October'2000 Students Session

题目类型：树形DP

算法分析：使用dp[i][0]和dp[i][1]分别表示以第i个节点为子树且i来、不来时的最大喜欢直，然后使用树的后序遍历从叶子节点开始将每个节点的最大喜欢值求出来，注意本题中没有告诉root位置，所以需要自己在输入中找

#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;
}

#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

maksyuki 发表于 oj 分类，标签: 图论-最短路

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

Ulm Local 1998

题目类型：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的路径上载重限制为无穷

#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;
}

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

Ulm Local 1998

题目类型：队列

算法分析：使用map<int, int> team来表示成员的团队标志，使用一个队列表示团队队列，使用一个队列数组表示子团队的队列。先输入所有成员的团队标志，然后分类模拟，如果是”STOP”；则退出模拟；如果是”ENQUEUE”，则将新成员输入并判断其所在的团队是否在团队队列中，如果不在就将所在团队插入到团队队列中，然后将新成员插入到子团队的队列中；如果是”DEQUEUE”，则先输出团队队列队头成员并删除，接着判断被删除成员先前所在的子团队队列是否为空，如果为空，则从团队队列中删除该子队列

#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;
}

#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

maksyuki 发表于 oj 分类，标签: 博弈-Nim

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

Yes

Source

POJ Monthly,readchild

题目类型：Nim博弈

算法分析：这是一道Nim博弈的经典题目。算法是用二进制表示每堆火柴棍的根数。将二进制表示的输入数据各个位分别相加，再求除以2的余数，如果余数为0，则先手的必输，反之，则必胜

#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;
}

#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

maksyuki 发表于 oj 分类，标签: 数据结构-笛卡尔树

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的。在向笛卡尔树中插入节点时要注意修改待插入节点的左孩子的父节点！！！

#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;
}

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

maksyuki 发表于 oj 分类，标签: 数论-不定方程

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

Japan 2004

题目类型：二元一次不定方程

算法分析：题目中要求ax+by尽可能小，即方程右边只有d(ax+by=d)，才可能满足条件。此时可以使用扩展欧几里得算法分别求出不定方程的最小非负特解x0和y0。然后分别求出此时的y和x。最后比较两个x、y的和的大小。取较小的那个x和y输出

#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;
}

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:

2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
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

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进制的数转换为十进制输出的数组中

#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;
}

#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 w₁h₁+w₂h₂+...+w_nh_n < 10⁹.

Output

Simply output Max(S) in a single line for each case.

Sample Input

1 2

3 4

1 2

3 4

1 2

3 4

-1

Sample Output

Source

Shanghai 2004 Preliminary

题目类型：单调队列

算法分析：一道经典的使用单调队列思想解的题。坐标从小到大的分析，如果存在一个高度不超过先前的高度，则应该将先前高度的矩形块的面积出栈并计算，更新最大值。否则就一直入栈。最后将还在栈中的矩形块的面积计算出来并更新最大值

#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;
}

#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;

}

poj2080

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

15 9月 2015

alendar

A calendar is a system for measuring time, from hours and minutes, to months and days, and finally to years and centuries. The terms of hour, day, month, year and century are all units of time measurements of a calender system. According to the Gregorian calendar, which is the civil calendar in use today, years evenly divisible by 4 are leap years, with the exception of centurial years that are not evenly divisible by 400. Therefore, the years 1700, 1800, 1900 and 2100 are not leap years, but 1600, 2000, and 2400 are leap years. Given the number of days that have elapsed since January 1, 2000 A.D, your mission is to find the date and the day of the week.

Input

The input consists of lines each containing a positive integer, which is the number of days that have elapsed since January 1, 2000 A.D. The last line contains an integer −1, which should not be processed.
You may assume that the resulting date won’t be after the year 9999.

Output

For each test case, output one line containing the date and the day of the week in the format of "YYYY-MM-DD DayOfWeek", where "DayOfWeek" must be one of "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday" and "Saturday".

Sample Input

1730

1740

1750

1751

-1

Sample Output

2004-09-26 Sunday
2004-10-06 Wednesday
2004-10-16 Saturday
2004-10-17 Sunday

Source

Shanghai 2004 Preliminary

题目类型：模拟

算法分析：直接进行日期模拟即可

#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;

int dayofyears (int year)
{
    if (year % 4 == 0 && year % 100 != 0) return 366;
    if (year % 400 == 0) return 366;
    else return 365;
}

int dayofmonths (int month, int year)
{
    if (month == 2)
    {
        if (dayofyears (year) == 366) return 29;
        else return 28;
    }
    else if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8
    || month == 10 || month == 12)
        return 31;

    else return 30;
}
int main()
{
    int N, year, month, day, temp;
    char week[][20] = {"Saturday", "Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday", "Friday"};

    //fstream cin ("aaa.txt");
    cin >> N;

    while (N != -1)
    {
        year = 2000, month = 1, day = 1;
        temp = N;
        while (N >= dayofyears (year))
        {
            N -= dayofyears (year);
            year++;
        }
        while (N >= dayofmonths (month, year))
        {
            N -= dayofmonths (month, year);
            month ++;
        }
        N++;
        if (month >= 10)
        {
            if (N < 10)
                printf ("%d-%d-0%d %s\n", year, month, N, week[temp%7]);
            else printf ("%d-%d-%d %s\n", year, month, N, week[temp%7]);

        }
        else
        {
            if (N < 10)
                printf ("%d-0%d-0%d %s\n", year, month, N, week[temp%7]);
            else printf ("%d-0%d-%d %s\n", year, month, N, week[temp%7]);
        }
        cin >> N;
    }
return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

using namespace std;

int dayofyears (int year)

{

if (year % 4 == 0 && year % 100 != 0) return 366;

if (year % 400 == 0) return 366;

else return 365;

}

int dayofmonths (int month, int year)

{

if (month == 2)

{

if (dayofyears (year) == 366) return 29;

else return 28;

}

else if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8

|| month == 10 || month == 12)

return 31;

else return 30;

}

int main()

{

int N, year, month, day, temp;

char week[][20] = {"Saturday", "Sunday", "Monday", "Tuesday",

"Wednesday", "Thursday", "Friday"};

//fstream cin ("aaa.txt");

cin >> N;

while (N != -1)

{

year = 2000, month = 1, day = 1;

temp = N;

while (N >= dayofyears (year))

{

N -= dayofyears (year);

year++;

}

while (N >= dayofmonths (month, year))

{

N -= dayofmonths (month, year);

month ++;

}

N++;

if (month >= 10)

{

if (N < 10)

printf ("%d-%d-0%d %s\n", year, month, N, week[temp%7]);

else printf ("%d-%d-%d %s\n", year, month, N, week[temp%7]);

}

else

{

if (N < 10)

printf ("%d-0%d-0%d %s\n", year, month, N, week[temp%7]);

else printf ("%d-0%d-%d %s\n", year, month, N, week[temp%7]);

}

cin >> N;

}

return 0;

}

poj2031

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

15 9月 2015

Building a Space Station

You are a member of the space station engineering team, and are assigned a task in the construction process of the station. You are expected to write a computer program to complete the task. The space station is made up with a number of units, called cells. All cells are sphere-shaped, but their sizes are not necessarily uniform. Each cell is fixed at its predetermined position shortly after the station is successfully put into its orbit. It is quite strange that two cells may be touching each other, or even may be overlapping. In an extreme case, a cell may be totally enclosing another one. I do not know how such arrangements are possible. All the cells must be connected, since crew members should be able to walk from any cell to any other cell. They can walk from a cell A to another cell B, if, (1) A and B are touching each other or overlapping, (2) A and B are connected by a `corridor', or (3) there is a cell C such that walking from A to C, and also from B to C are both possible. Note that the condition (3) should be interpreted transitively. You are expected to design a configuration, namely, which pairs of cells are to be connected with corridors. There is some freedom in the corridor configuration. For example, if there are three cells A, B and C, not touching nor overlapping each other, at least three plans are possible in order to connect all three cells. The first is to build corridors A-B and A-C, the second B-C and B-A, the third C-A and C-B. The cost of building a corridor is proportional to its length. Therefore, you should choose a plan with the shortest total length of the corridors. You can ignore the width of a corridor. A corridor is built between points on two cells' surfaces. It can be made arbitrarily long, but of course the shortest one is chosen. Even if two corridors A-B and C-D intersect in space, they are not considered to form a connection path between (for example) A and C. In other words, you may consider that two corridors never intersect.

Input

The input consists of multiple data sets. Each data set is given in the following format.

n
x1 y1 z1 r1
x2 y2 z2 r2
...
xn yn zn rn

The first line of a data set contains an integer n, which is the number of cells. n is positive, and does not exceed 100.

The following n lines are descriptions of cells. Four values in a line are x-, y- and z-coordinates of the center, and radius (called r in the rest of the problem) of the sphere, in this order. Each value is given by a decimal fraction, with 3 digits after the decimal point. Values are separated by a space character.

Each of x, y, z and r is positive and is less than 100.0.

The end of the input is indicated by a line containing a zero.

Output

For each data set, the shortest total length of the corridors should be printed, each in a separate line. The printed values should have 3 digits after the decimal point. They may not have an error greater than 0.001.

Note that if no corridors are necessary, that is, if all the cells are connected without corridors, the shortest total length of the corridors is 0.000.

Sample Input

3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0

Sample Output

20.000
0.000
73.834

Source

Japan 2003 Domestic

题目类型：MST

算法分析：按照题目中的数据建立边数组edge，然后直接调用kruskal算法计算最小权值和即可。建立边数组edge时，对于两个太空舱的圆心距小于等于两个太空舱的半径之和的情况，这两个太空舱之间的距离定义为0.000，反之，则距离定义为圆心距减去两个半径之和(表面距离)。注意浮点数误差

#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 = 266 + 66;
const int EPS = 1e-6;

struct Node
{
    double x, y, z, r;
};

Node ans[maxn];
int parent[maxn];

struct Point
{
    int u, v;
    double w;
};

Point edge[maxn*maxn];

int len, n;
double sum;

int UnFind (int val)
{
    if (parent[val] == -1)
        return val;

return parent[val] = UnFind (parent[val]);
}

bool Cmp (Point a, Point b)
{
    return a.w < b.w;
}


void kruskal ()
{
    int i;
    for (i = 0; i < maxn; i++)
        parent[i] = -1;

    sum = 0.000;
    int remain = n;
    for (i = 0; i < len && remain > 1; i++)
    {
        if (UnFind (edge[i].u) != UnFind (edge[i].v))
        {
            parent[UnFind(edge[i].u)] = UnFind (edge[i].v);
            sum += edge[i].w;
            remain--;
        }
    }
}


int main()
{
//    ifstream cin ("aaa.txt");

    while (cin >> n)
    {
        if (n == 0)
            break;

        int i;
        for (i = 0; i < n; i++)
            cin >> ans[i].x >> ans[i].y >> ans[i].z >> ans[i].r;

        len = 0;

        int j;
        for (i = 0; i < n - 1; i++)
            for (j = i + 1; j < n; j++)
            {
                edge[len].u = i;
                edge[len].v = j;

                double dis = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2)
                                   + pow (ans[i].z - ans[j].z, 2));

                if (dis > ans[i].r + ans[j].r + EPS)
                    edge[len].w = dis - (ans[i].r + ans[j].r);

                else
                    edge[len].w = 0.000;

                len++;
            }

        sort (edge, edge + len, Cmp);
        kruskal ();

        cout << fixed << setprecision (3) << sum << endl;
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#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 = 266 + 66;

const int EPS = 1e-6;

struct Node

{

double x, y, z, r;

};

Node ans[maxn];

int parent[maxn];

struct Point

{

int u, v;

double w;

};

Point edge[maxn*maxn];

int len, n;

double sum;

int UnFind (int val)

{

if (parent[val] == -1)

return val;

return parent[val] = UnFind (parent[val]);

}

bool Cmp (Point a, Point b)

{

return a.w < b.w;

}

void kruskal ()

{

int i;

for (i = 0; i < maxn; i++)

parent[i] = -1;

sum = 0.000;

int remain = n;

for (i = 0; i < len && remain > 1; i++)

{

if (UnFind (edge[i].u) != UnFind (edge[i].v))

{

parent[UnFind(edge[i].u)] = UnFind (edge[i].v);

sum += edge[i].w;

remain--;

}

int main()

{

// ifstream cin ("aaa.txt");

while (cin >> n)

{

if (n == 0)

break;

int i;

for (i = 0; i < n; i++)

cin >> ans[i].x >> ans[i].y >> ans[i].z >> ans[i].r;

len = 0;

int j;

for (i = 0; i < n - 1; i++)

for (j = i + 1; j < n; j++)

{

edge[len].u = i;

edge[len].v = j;

double dis = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2)

+ pow (ans[i].z - ans[j].z, 2));

if (dis > ans[i].r + ans[j].r + EPS)

edge[len].w = dis - (ans[i].r + ans[j].r);

else

edge[len].w = 0.000;

len++;

}

sort (edge, edge + len, Cmp);

kruskal ();

cout << fixed << setprecision (3) << sum << endl;

}

返回首页上一页 1 2 3 4 5 下一页最后一页

超客的水墨烟雨

poj2456

poj2417

poj2406

poj2387

poj2352

poj2342

poj2263

poj2259

poj2234

poj2201

poj2142

poj2115

poj2105

poj2082

poj2080

poj2031

分类目录

标签云

书签

近期评论

2015年9月
一	二	三	四	五	六	日
« 8月				10月 »
	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