lightoj1035

maksyuki 发表于 oj 分类，标签: 数论-素因子分解

27 8月 2015

1035 - Intelligent Factorial Factorization

Input

Given an integer N, you have to prime factorize N! (factorial N).

Input starts with an integer T (≤ 125), denoting the number of test cases.

Each case contains an integer N (2 ≤ N ≤ 100).

Output

For each case, print the case number and the factorization of the factorial in the following format as given in samples.

Case x: N = p₁ (power of p₁) * p₂ (power of p₂) * ...

Here x is the case number, p₁, p₂ ... are primes in ascending order.

Sample Input	Output for Sample Input
3236	Case 1: 2 = 2 (1)Case 2: 3 = 2 (1) * 3 (1)Case 3: 6 = 2 (4) * 3 (2) * 5 (1)

Notes

The output for the 3^rd case is (if we replace space with '.') is

Case.3:.6.=.2.(4).*.3.(2).*.5.(1)

题目类型：素因子分解

算法分析：N!中有素数p的个数为[N/p] + [N/p^2] + [N/p^3] + …由于N不太大，可以先将100以内的素数都打出来，然后从小到大判断每一个素数及其倍数是否满足 N / p ^ k != 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 = 100 + 66;

bool prime[maxn];

void GetPrime ()
{
    memset (prime, true, sizeof (prime));

    int i;
    for (i = 2; i < maxn; i++)
    {
        int j;
        for (j = 2; j * i < maxn; j++)
            prime[i*j] = false;
    }
}


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

    GetPrime ();

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        cout << "Case " << flag++ << ": " << n << " = ";

        int i, sum;
        bool is_first = true;

        for (i = 2; i < maxn; i++)
        {
            if (prime[i])
            {
                if (n / i == 0)
                    break;

                sum = n / i;
                int temp = i;
                while (n / (temp * i))
                {
                    sum += n / (temp * i);
                    temp *= i;
                }

                if (is_first)
                {
                    is_first = false;
                    cout << i << " " << "(" << sum << ")";
                }

                else
                    cout << " * " << i << " " << "(" << sum << ")";
            }
        }

        cout << endl;
    }
    
return 0;
}

100

101

102

103

104

105

106

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

bool prime[maxn];

void GetPrime ()

{

memset (prime, true, sizeof (prime));

int i;

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

{

int j;

for (j = 2; j * i < maxn; j++)

prime[i*j] = false;

}

int main()

{

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

GetPrime ();

int t, flag = 1;

cin >> t;

while (t--)

{

int n;

cin >> n;

cout << "Case " << flag++ << ": " << n << " = ";

int i, sum;

bool is_first = true;

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

{

if (prime[i])

{

if (n / i == 0)

break;

sum = n / i;

int temp = i;

while (n / (temp * i))

{

sum += n / (temp * i);

temp *= i;

}

if (is_first)

{

is_first = false;

cout << i << " " << "(" << sum << ")";

}

else

cout << " * " << i << " " << "(" << sum << ")";

}

cout << endl;

}

return 0;

}

lightoj1029

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

27 8月 2015

1029 - Civil and Evil Engineer

Since the Civil Engineer is clever enough and tries to make some profit, he made a plan. His plan is to find the best possible connection scheme and the worst possible connection scheme. Then he will report the average of the costs.A Civil Engineer is given a task to connect n houses with the main electric power station directly or indirectly. The Govt has given him permission to connect exactly n wires to connect all of them. Each of the wires connects either two houses, or a house and the power station. The costs for connecting each of the wires are given.

Now you are given the task to check whether the Civil Engineer is evil or not. That's why you want to calculate the average before he reports to the Govt.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a blank line and an integer n (1 ≤ n ≤ 100) denoting the number of houses. You can assume that the houses are numbered from 1 to n and the power station is numbered0. Each of the next lines will contain three integers in the form u v w (0 ≤ u, v ≤ n, 0 < w ≤ 10000, u ≠ v) meaning that you can connect u and v with a wire and the cost will be w. A line containing three zeroes denotes the end of the case. You may safely assume that the data is given such that it will always be possible to connect all of them. You may also assume that there will not be more than 12000 lines for a case.

Output

For each case, print the case number and the average as described. If the average is not an integer then print it in p/q form. Where p is the numerator of the result and q is the denominator of the result; p and q are relatively-prime. Otherwise print the integer average.

Sample Input

Output for Sample Input

310 1 10

0 1 20

0 0 0

0 1 99

0 2 10

1 2 30

2 3 30

0 0 0

0 1 10

0 2 5

0 0 0

Case 1: 15Case 2: 229/2Case 3: 15

题目类型：MST

算法分析：将边表edge按照边权从小到大和从大到小排两次并使用kruskal分别计算权值和，最后求两者之和并按照题目要求输出即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 16000;

struct Node
{
    int u, v, w;
};

Node edge[maxn];
int len, suma, sumb, parent[666];
int n;

void Init ()
{
    int i;
    for (i = 0; i < 666; i++)
        parent[i] = i;
}

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

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

void kruskal ()
{
    Init ();

    int i, 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);
            remain--;
            suma += edge[i].w;
        }
    }
}

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

return gcd (b, a % b);
}

bool Cmpa (Node a, Node b)
{
    return a.w < b.w;
}

bool Cmpb (Node a, Node b)
{
    return a.w > b.w;
}


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

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        cin >> n;
        n++;

        len = 0;
        while (cin >> edge[len].u >> edge[len].v >> edge[len].w)
        {
            if (edge[len].u == 0 && edge[len].v == 0 && edge[len].w == 0)
                break;

            len++;
        }

        suma = 0;
        sort (edge, edge + len, Cmpa);
        kruskal ();

        sumb = suma;
        suma = 0;
        sort (edge, edge + len, Cmpb);
        kruskal ();

        int tot = suma + sumb;
        if (tot % 2 == 0)
            cout << tot / 2 << endl;

        else
        {
            int temp = gcd (max (tot, 2), min (tot, 2));
            cout << tot / temp << "/" << 2 / temp << endl;
        }
    }

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

133

134

135

136

137

138

139

140

141

142

143

144

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 16000;

struct Node

{

int u, v, w;

};

Node edge[maxn];

int len, suma, sumb, parent[666];

int n;

void Init ()

{

int i;

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

parent[i] = i;

}

int UnFind (int val)

{

if (parent[val] == val)

return val;

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

}

void kruskal ()

{

Init ();

int i, 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);

remain--;

suma += edge[i].w;

}

int gcd (int a, int b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

bool Cmpa (Node a, Node b)

{

return a.w < b.w;

}

bool Cmpb (Node a, Node b)

{

return a.w > b.w;

}

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

cin >> n;

n++;

len = 0;

while (cin >> edge[len].u >> edge[len].v >> edge[len].w)

{

if (edge[len].u == 0 && edge[len].v == 0 && edge[len].w == 0)

break;

len++;

}

suma = 0;

sort (edge, edge + len, Cmpa);

kruskal ();

sumb = suma;

suma = 0;

sort (edge, edge + len, Cmpb);

kruskal ();

int tot = suma + sumb;

if (tot % 2 == 0)

cout << tot / 2 << endl;

else

{

int temp = gcd (max (tot, 2), min (tot, 2));

cout << tot / temp << "/" << 2 / temp << endl;

}

return 0;

}

lightoj1020

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

27 8月 2015

1020 - A Childhood Game

Both Alice and Bob know the number of marbles initially. Now the game can be started by any one. But the winning condition depends on the player who starts it. If Alice starts first, then the player who takes the last marble looses the game. If Bob starts first, then the player who takes the last marble wins the game.Alice and Bob are playing a game with marbles; you may have played this game in childhood. The game is playing by alternating turns. In each turn a player can take exactly one or two marbles.

Now you are given the initial number of marbles and the name of the player who starts first. Then you have to find the winner of the game if both of them play optimally.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer n (1 ≤ n < 2³¹) and the name of the player who starts first.

Output

For each case, print the case number and the name of the winning player.

Sample Input	Output for Sample Input
31 Alice2 Alice3 Bob	Case 1: BobCase 2: AliceCase 3: Alice

题目类型：Bash博弈变形

算法分析：当Bob先手时，本题可以看做是Bash博弈问题，因为求解谁拿走最后一个石头和求解留给对方没法选石子的状态这两个问题是等价的。而当Alice先手时，由于谁拿走最后一个石子会输，所以初始时石子的个数%3 == 1的话，那个先手的人就会输，这可由Bash博弈推得

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

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        int n;
        char s[16];

        scanf ("%d%s", &n, s);

        if (!strcmp (s, "Alice"))
        {
            if (n % 3 == 1)
                printf ("Bob\n");

            else
                printf ("Alice\n");
        }

        else
        {
            if (n % 3 == 0)
                printf ("Alice\n");

            else
                printf ("Bob\n");
        }
    }

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

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int n;

char s[16];

scanf ("%d%s", &n, s);

if (!strcmp (s, "Alice"))

{

if (n % 3 == 1)

printf ("Bob\n");

else

printf ("Alice\n");

}

else

{

if (n % 3 == 0)

printf ("Alice\n");

else

printf ("Bob\n");

}

return 0;

}

lightoj1019

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

27 8月 2015

1019 - Brush (V)

The city they live in is divided by some junctions. The junctions are connected by two way roads. They live in different junctions. And they can go to one junction to other by using the roads only.Tanvir returned home from the contest and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found that there is no brush in him room. So, he called Atiq to get a brush. But as usual Atiq refused to come. So, Tanvir decided to go to Atiq's house.

Now you are given the map of the city and the distances of the roads. You have to find the minimum distance Tanvir has to travel to reach Atiq's house.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line. The next line contains two integers N (2 ≤ N ≤ 100) and M (0 ≤ M ≤ 1000), means that there are N junctions and M two way roads. Each of the next Mlines will contain three integers u v w (1 ≤ u, v ≤ N, w ≤ 1000), it means that there is a road between junction u and v and the distance is w. You can assume that Tanvir lives in the 1^stjunction and Atiq lives in the N^th junction. There can be multiple roads between same pair of junctions.

Output

For each case print the case number and the minimum distance Tanvir has to travel to reach Atiq's house. If it's impossible, then print 'Impossible'.

Sample Input

Output for Sample Input

23 21 2 50

2 3 10

3 1

1 2 40

Case 1: 60Case 2: Impossible

题目类型：单源最短路(Bellman-ford)

算法分析：直接使用Bellman-ford算法迭代求解即可，注意对于无向图来说要将无向图看作(u,v),(v,u)同属于边集E的有向图

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

struct Node
{
    int u, v, w;
};

Node edge[maxn*2];
int dis[maxn];
int n, m, len;


void bellman_ford (int s)
{
    int i;
    for (i = 1; i <= n; i++)
    {
        dis[i] = INF;
    }

    dis[s] = 0;

    for (i = 1; i < n; i++)
    {
        int j;
        for (j = 0; j < len; j++)
        {
            if (dis[edge[j].u] < INF)
            {
                dis[edge[j].v] = min (dis[edge[j].v], dis[edge[j].u] + edge[j].w);
            }
        }
    }
}

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

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        cin >> n >> m;

        int i, temp_u, temp_v, temp_w;
        len = 0;

        for (i = 0; i < m; i++)
        {
            cin >> temp_u >> temp_v >> temp_w;
            edge[len].u = temp_u, edge[len].v = temp_v, edge[len].w = temp_w;
            len++;
            edge[len].u = temp_v, edge[len].v = temp_u, edge[len].w = temp_w;
            len++;
        }

        bellman_ford (1);

        if (dis[n] == INF)
            cout << "Impossible" << endl;

        else
            cout << dis[n] << endl;
    }

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 double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1666;

struct Node

{

int u, v, w;

};

Node edge[maxn*2];

int dis[maxn];

int n, m, len;

void bellman_ford (int s)

{

int i;

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

{

dis[i] = INF;

}

dis[s] = 0;

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

{

int j;

for (j = 0; j < len; j++)

{

if (dis[edge[j].u] < INF)

{

dis[edge[j].v] = min (dis[edge[j].v], dis[edge[j].u] + edge[j].w);

}

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

cin >> n >> m;

int i, temp_u, temp_v, temp_w;

len = 0;

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

{

cin >> temp_u >> temp_v >> temp_w;

edge[len].u = temp_u, edge[len].v = temp_v, edge[len].w = temp_w;

len++;

edge[len].u = temp_v, edge[len].v = temp_u, edge[len].w = temp_w;

len++;

}

bellman_ford (1);

if (dis[n] == INF)

cout << "Impossible" << endl;

else

cout << dis[n] << endl;

}

return 0;

}

lightoj1016

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

27 8月 2015

1016 - Brush (II)

You can assume that the rope is sufficiently large. Now Samee wants to clean the room with minimum number of moves. Since he already had a contest, his head is messy. So, help him.After the long contest, Samee returned home and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found a brush in his room which has width w. Dusts are defined as 2D points. And since they are scattered everywhere, Samee is a bit confused what to do. So, he attached a rope with the brush such that it can be moved horizontally (in X axis) with the help of the rope but in straight line. He places it anywhere and moves it. For example, the y co-ordinate of the bottom part of the brush is 2 and its width is 3, so the y coordinate of the upper side of the brush will be 5. And if the brush is moved, all dusts whose y co-ordinates are between 2 and 5 (inclusive) will be cleaned. After cleaning all the dusts in that part, Samee places the brush in another place and uses the same procedure. He defined a move as placing the brush in a place and cleaning all the dusts in the horizontal zone of the brush.

Input

Input starts with an integer T (≤ 15), denoting the number of test cases.

Each case starts with a blank line. The next line contains two integers N (1 ≤ N ≤ 50000) and w (1 ≤ w ≤ 10000), means that there are N dust points. Each of the next N lines will contain two integers: x_i y_i, denoting coordinates of the dusts. You can assume that (-10⁹ ≤ x_i, y_i ≤ 10⁹) and all points are distinct.

Output

For each case print the case number and the minimum number of moves.

Sample Input

Output for Sample Input

23 20 0

20 2

30 2

3 1

0 0

20 2

30 2

Case 1: 1Case 2: 2

Note

Data set is huge, so use faster I/O methods.

题目类型：贪心

算法分析：由于刷子可以水平扫过所有的长度，所以点的横坐标没有用，只需考虑纵坐标，显然这是一个区间覆盖点问题，直接贪心选择即可

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

int ans[maxn];

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        int n, w;
        scanf ("%d%d", &n, &w);

        int temp, i;
        for (i = 0; i < n; i++)
            scanf ("%d%d", &temp, &ans[i]);

        sort (ans, ans + n);

        int sum = 1, p = ans[0];
        for (i = 1; i < n; i++)
        {
            if (ans[i] > w + p)
            {
                sum++;
                p = ans[i];
            }
        }

        printf ("%d\n", sum);
    }

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 = 66666;

int ans[maxn];

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int n, w;

scanf ("%d%d", &n, &w);

int temp, i;

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

scanf ("%d%d", &temp, &ans[i]);

sort (ans, ans + n);

int sum = 1, p = ans[0];

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

{

if (ans[i] > w + p)

{

sum++;

p = ans[i];

}

printf ("%d\n", sum);

}

return 0;

}

lightoj1014

maksyuki 发表于 oj 分类，标签: 数论-因子个数

27 8月 2015

1014 - Ifter Party

Now you have to find the number of piaju's each contestant ate.I have an Ifter party at the 5^th day of Ramadan for the contestants. For this reason I have invited C contestants and arranged P piaju's (some kind of food, specially made for Ifter). Each contestant ate Q piaju's and L piaju's were left (L < Q).

Input

Input starts with an integer T (≤ 325), denoting the number of test cases.

Each case contains two non-negative integers P and L (0 ≤ L < P < 2³¹).

Output

For each case, print the case number and the number of possible integers in ascending order. If no such integer is found print 'impossible'.

Sample Input	Output for Sample Input
410 013 2300 981000 997	Case 1: 1 2 5 10Case 2: 11Case 3: 101 202Case 4: impossible

题目类型：因子个数

算法分析：直接枚举小于sqrt(P - L)的所有因子，然后生成大于sqrt (P – L)的所有因子，注意枚举因子中的下标i必须使用long long类型，否则会RE

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

long long ans[maxn], len;


int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:", flag++);

        long long P, L;
        scanf ("%lld%lld", &P, &L);

        long long val = P - L;

        if (val <= L)
        {
            puts (" impossible");
            continue ;
        }

        len = 0;
        for (long long i = 1; i * i <= val; i++)
        {
            if (val % i == 0)
            {
                if (i > L)
                    printf (" %lld", i);

                if (i * i == val)
                    continue;

                ans[len++] = i;
            }
        }

        for (long long i = len - 1; i >= 0; i--)
            if (val / ans[i] > L)
                printf (" %lld", val / ans[i]);


        puts ("");
    }

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

long long ans[maxn], len;

int main()

{

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

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:", flag++);

long long P, L;

scanf ("%lld%lld", &P, &L);

long long val = P - L;

if (val <= L)

{

puts (" impossible");

continue ;

}

len = 0;

for (long long i = 1; i * i <= val; i++)

{

if (val % i == 0)

{

if (i > L)

printf (" %lld", i);

if (i * i == val)

continue;

ans[len++] = i;

}

for (long long i = len - 1; i >= 0; i--)

if (val / ans[i] > L)

printf (" %lld", val / ans[i]);

puts ("");

}

return 0;

}

lightoj1012

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

27 8月 2015

1012 - Guilty Prince

For simplicity, you can consider the place as a rectangular grid consisting of some cells. A cell can be a land or can contain water. Each time the prince can move to a new cell from his current position if they share a side.Once there was a king named Akbar. He had a son named Shahjahan. For an unforgivable reason the king wanted him to leave the kingdom. Since he loved his son he decided his son would be banished in a new place. The prince became sad, but he followed his father's will. In the way he found that the place was a combination of land and water. Since he didn't know how to swim, he was only able to move on the land. He didn't know how many places might be his destination. So, he asked your help.

Now write a program to find the number of cells (unit land) he could reach including the cell he was living.

Input

Input starts with an integer T (≤ 500), denoting the number of test cases.

Each case starts with a line containing two positive integers W and H; W and H are the numbers of cells in the x and y directions, respectively. W and H are not more than 20.

There will be H more lines in the data set, each of which includes W characters. Each character represents the status of a cell as follows.

1) '.' - land

2) '#' - water

3) '@' - initial position of prince (appears exactly once in a dataset)

Output

For each case, print the case number and the number of cells he can reach from the initial position (including it).

Sample Input

Output for Sample Input

46 9....#......#

......

#@...#

.#..#.

11 9

.#.........

.#.#######.

.#.#.....#.

.#.#.###.#.

.#.#..@#.#.

.#.#####.#.

.#.......#.

.#########.

...........

11 6

..#..#..#..

..#..#..###

..#..#..#@.

..#..#..#..

7 7

..#.#..

###.###

...@...

###.###

..#.#..

Case 1: 45Case 2: 59Case 3: 6Case 4: 13

题目类型：DFS/BFS

算法分析：调用DFS/BFS计算连通的’.’数量即可

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

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

char ans[maxn][maxn];
bool visited[maxn][maxn];

int sum, row, col, flag = 1, s_x, s_y;

inline bool OkMove (int x, int y)
{
    if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && !visited[x][y] && ans[x][y] != '#')
        return true;

return false;
}


void DFS (int x, int y)
{
    int i;
    for (i = 0; i < 4; i++)
    {
        if (OkMove (x + dx[i], y + dy[i]))
        {
            int val_x = x + dx[i], val_y = y + dy[i];

            visited[val_x][val_y] = true;
            sum++;
            DFS (val_x, val_y);
        }
    }
}
int main()
{
//    ifstream cin ("aaa.txt");

    int t;
    cin >> t;

    while (t--)
    {
        cin >> col >> row;

        int i, j;
        for (i = 0; i < row; i++)
        {
            for (j = 0; j < col; j++)
            {
                cin >> ans[i][j];

                if (ans[i][j] == '@')
                {
                    s_x = i;
                    s_y = j;
                }
            }
        }

        memset (visited, false, sizeof (visited));
        sum = 1;

        visited[s_x][s_y] = true;

        DFS (s_x, s_y);

        cout << "Case " << flag++ << ": " << sum << 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 = 66 + 6;

const int dx[] = {0, 0, -1, 1};

const int dy[] = {-1, 1, 0, 0};

char ans[maxn][maxn];

bool visited[maxn][maxn];

int sum, row, col, flag = 1, s_x, s_y;

inline bool OkMove (int x, int y)

{

if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && !visited[x][y] && ans[x][y] != '#')

return true;

return false;

}

void DFS (int x, int y)

{

int i;

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

{

if (OkMove (x + dx[i], y + dy[i]))

{

int val_x = x + dx[i], val_y = y + dy[i];

visited[val_x][val_y] = true;

sum++;

DFS (val_x, val_y);

}

int main()

{

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

int t;

cin >> t;

while (t--)

{

cin >> col >> row;

int i, j;

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

{

for (j = 0; j < col; j++)

{

cin >> ans[i][j];

if (ans[i][j] == '@')

{

s_x = i;

s_y = j;

}

memset (visited, false, sizeof (visited));

sum = 1;

visited[s_x][s_y] = true;

DFS (s_x, s_y);

cout << "Case " << flag++ << ": " << sum << endl;

}

return 0;

}

lightoj1010

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1010 - Knights in Chessboard

Those who are not familiar with chess knights, note that a chess knight can attack 8 positions in the board as shown in the picture below.Given an m x n chessboard where you want to place chess knights. You have to find the number of maximum knights that can be placed in the chessboard such that no two knights attack each other.

Input

Input starts with an integer T (≤ 41000), denoting the number of test cases.

Each case contains two integers m, n (1 ≤ m, n ≤ 200). Here m and n corresponds to the number of rows and the number of columns of the board respectively.

Output

For each case, print the case number and maximum number of knights that can be placed in the board considering the above restrictions.

Sample Input	Output for Sample Input
38 83 74 10	Case 1: 32Case 2: 11Case 3: 20

题目类型：找规律

算法分析：维持row <= col，然后当row == 1时，直接输出col。当row == 2时，那么可以一次性把一个田字格全部放上马，然后间隔一个田字格，然后再放马。当row >= 3时，则直接判断棋盘上黑白格最大的那一个的个数即可(因为同一个颜色的格子中的马不会相互攻击)

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

int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);
        int row, col;
        scanf ("%d%d", &row, &col);

        if (row > col)
            swap (row, col);

        if (row == 1)
        {
            printf ("%d\n", col);
        }

        else if (row == 2)
        {
            int sum = 4 * (col / 4);
            int temp = col % 4;
            if (temp < 3)
                sum += temp * 2;

            else
                sum += 4;

            printf ("%d\n", sum);
        }

        else
        {
            int tot = row * col;
            if (tot % 2)
                printf ("%d\n", tot / 2 + 1);

            else
                printf ("%d\n", tot / 2);
        }
    }

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 = 66666;

int main()

{

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

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int row, col;

scanf ("%d%d", &row, &col);

if (row > col)

swap (row, col);

if (row == 1)

{

printf ("%d\n", col);

}

else if (row == 2)

{

int sum = 4 * (col / 4);

int temp = col % 4;

if (temp < 3)

sum += temp * 2;

else

sum += 4;

printf ("%d\n", sum);

}

else

{

int tot = row * col;

if (tot % 2)

printf ("%d\n", tot / 2 + 1);

else

printf ("%d\n", tot / 2);

}

return 0;

}

lightoj1008

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1008 - Fibsieve`s Fantabulous Birthday

Among these gifts there was an N x N glass chessboard that had a light in each of its cells. When the board was turned on a distinct cell would light up every second, and then go dark.Fibsieve had a fantabulous (yes, it's an actual word) birthday party this year. He had so many gifts that he was actually thinking of not having a party next year.

The cells would light up in the sequence shown in the diagram. Each cell is marked with the second in which it would light up.

In the first second the light at cell (1, 1) would be on. And in the 5th second the cell (3, 1) would be on. Now, Fibsieve is trying to predict which cell will light up at a certain time (given in seconds). Assume that N is large enough.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case will contain an integer S (1 ≤ S ≤ 10¹⁵) which stands for the time.

Output

For each case you have to print the case number and two numbers (x, y), the column and the row number.

Sample Input	Output for Sample Input
382025	Case 1: 2 3Case 2: 5 4Case 3: 1 5

题目类型：简单递推

算法分析：首先得到对角线上数的递推公式，然后求得最接近输入数S的对角线上的数ans，然后判断S是否在[ans – (temp - 1), ans + (temp + 1)]中，其中temp表示对角线元素的坐标(temp,temp)，然后再分类讨论即可

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

long long F (long long val)
{
    return val * val - val + 1;
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        printf ("Case %d: ", flag++);

        long long val, ans;
        scanf ("%lld", &val);

        long long temp = (long long) sqrt ((double) val);

        while (1)
        {
            ans = F (temp);
            if (val >= ans - (temp - 1) && val <= ans + (temp - 1))
                break;

            if (val < ans - (temp - 1))
                temp--;

            else
                temp++;
        }

        if (temp % 2)
        {
            if (val >= ans - (temp - 1) && val <= ans)
                printf ("%lld %lld\n", temp, temp - (ans - val));

            else
                printf ("%lld %lld\n", temp - (val - ans), temp);
        }

        else
        {
            if (val >= ans - (temp - 1) && val <= ans)
                printf ("%lld %lld\n", temp - (ans - val), temp);

            else
                printf ("%lld %lld\n", temp, temp - (val - ans));
        }
    }

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

long long F (long long val)

{

return val * val - val + 1;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

cin >> t;

while (t--)

{

printf ("Case %d: ", flag++);

long long val, ans;

scanf ("%lld", &val);

long long temp = (long long) sqrt ((double) val);

while (1)

{

ans = F (temp);

if (val >= ans - (temp - 1) && val <= ans + (temp - 1))

break;

if (val < ans - (temp - 1))

temp--;

else

temp++;

}

if (temp % 2)

{

if (val >= ans - (temp - 1) && val <= ans)

printf ("%lld %lld\n", temp, temp - (ans - val));

else

printf ("%lld %lld\n", temp - (val - ans), temp);

}

else

{

if (val >= ans - (temp - 1) && val <= ans)

printf ("%lld %lld\n", temp - (ans - val), temp);

else

printf ("%lld %lld\n", temp, temp - (val - ans));

}

return 0;

}

lightoj1007

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

1007 - Mathematically Hard

In this problem, you will be given two integers a and b. You have to find the summation of the scores of the numbers from a to b (inclusive). The score of a number is defined as the following function.Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.

score (x) = n², where n is the number of relatively prime numbers with x, which are smaller than x

For example,

For 6, the relatively prime numbers with 6 are 1 and 5. So, score (6) = 2² = 4.

For 8, the relatively prime numbers with 8 are 1, 3, 5 and 7. So, score (8) = 4² = 16.

Now you have to solve this task.

Input

Input starts with an integer T (≤ 10⁵), denoting the number of test cases.

Each case will contain two integers a and b (2 ≤ a ≤ b ≤ 5 * 10⁶).

Output

For each case, print the case number and the summation of all the scores from a to b.

Sample Input	Output for Sample Input
36 68 82 20	Case 1: 4Case 2: 16Case 3: 1237

题目类型：欧拉函数

算法分析：使用递推的方法将5e6以内的欧拉函数值算出来，进而求前缀和，最后直接查询即可，注意本题数据比较大，只能使用unsigned long long定义euler数组

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

unsigned long long euler[maxn];

void GetEuler ()
{
    for (int i = 0; i < maxn; i++)
        euler[i] = i;

    for (int i = 2; i < maxn; i += 2)
        euler[i] >>= 1;

    for (int i = 3; i < maxn; i += 2)
    {
        if (euler[i] == i)
        {
            for (int j = i; j < maxn; j += i)
                euler[j] = euler[j] - euler[j] / i;
        }
    }
}

void init ()
{
   euler[1] = euler[1] * euler[1];

    for (int i = 2; i < maxn; i++)
        euler[i] = euler[i-1] + euler[i] * euler[i];

}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    GetEuler ();

    init ();

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        int a, b;
        scanf ("%d%d", &a, &b);

        printf ("%llu\n", euler[b] - euler[a-1]);
    }

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

unsigned long long euler[maxn];

void GetEuler ()

{

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

euler[i] = i;

for (int i = 2; i < maxn; i += 2)

euler[i] >>= 1;

for (int i = 3; i < maxn; i += 2)

{

if (euler[i] == i)

{

for (int j = i; j < maxn; j += i)

euler[j] = euler[j] - euler[j] / i;

}

void init ()

{

euler[1] = euler[1] * euler[1];

for (int i = 2; i < maxn; i++)

euler[i] = euler[i-1] + euler[i] * euler[i];

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

GetEuler ();

init ();

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int a, b;

scanf ("%d%d", &a, &b);

printf ("%llu\n", euler[b] - euler[a-1]);

}

return 0;

}

lightoj1002

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

27 8月 2015

1002 - Country Roads

For example, in the above picture, if we want to go from 0 to 4, then we can chooseI am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of my city t where I belong. Now from each city you have to find the minimum cost to go to my city. The cost is defined by the cost of the maximum road you have used to go to my city.

1) 0 - 1 - 4 which costs 8, as 8 (1 - 4) is the maximum road we used

2) 0 - 2 - 4 which costs 9, as 9 (0 - 2) is the maximum road we used

3) 0 - 3 - 4 which costs 7, as 7 (3 - 4) is the maximum road we used

So, our result is 7, as we can use 0 - 3 - 4.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line and two integers n (1 ≤ n ≤ 500) and m (0 ≤ m ≤ 16000). The next m lines, each will contain three integers u, v, w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 20000)indicating that there is a road between u and v with cost w. Then there will be a single integer t (0 ≤ t < n). There can be multiple roads between two cities.

Output

For each case, print the case number first. Then for all the cities (from 0 to n-1) you have to print the cost. If there is no such path, print 'Impossible'.

Sample Input

Output for Sample Input

25 60 1 5

0 1 4

2 1 3

3 0 7

3 4 6

3 1 8

5 4

0 1 5

0 1 4

2 1 3

3 4 7

Case 1:403

Case 2:

Impossible

Note

Dataset is huge, user faster I/O methods.

题目类型：最大容量路(bellman-ford)

算法分析：使用边表存储边的信息，然后使用bellman-ford迭代n – 1次计算dis数组的值，dis[i]表示节点i到目标节点的最大容量值，递推公式为

dis[edge[j].u] = min (dis[edge[j].u], max (edge[j].w, dis[edge[j].v]));注意使用Floyd会TLE

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 16000;

struct Node
{
    int u, v, w;
};

Node edge[maxn];

int dis[666];
int n, m;

void bellman_ford (int val)
{
    int i;
    for (i = 0; i < n; i++)
        dis[i] = INF;

    dis[val] = 0;
    for (i = 1; i < n; i++)
    {
        int j;
        for (j = 0; j < m; j++)
        {
            dis[edge[j].u] = min (dis[edge[j].u], max (edge[j].w, dis[edge[j].v]));
            dis[edge[j].v] = min (dis[edge[j].v], max (edge[j].w, dis[edge[j].u]));
        }
    }
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        cout << "Case " << flag++ << ":" << endl;

        scanf ("%d%d", &n, &m);

        int i;
        for (i = 0; i < m; i++)
        {
            scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
        }

        int tar;
        scanf ("%d", &tar);

        bellman_ford (tar);

        for (i = 0; i < n; i++)
        {
            if (i == tar)
                printf ("0\n");

            else if (dis[i] < INF)
                printf ("%d\n", dis[i]);

            else
                printf ("Impossible\n");
        }
    }

return 0;
}

100

101

102

103

104

105

106

107

108

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 16000;

struct Node

{

int u, v, w;

};

Node edge[maxn];

int dis[666];

int n, m;

void bellman_ford (int val)

{

int i;

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

dis[i] = INF;

dis[val] = 0;

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

{

int j;

for (j = 0; j < m; j++)

{

dis[edge[j].u] = min (dis[edge[j].u], max (edge[j].w, dis[edge[j].v]));

dis[edge[j].v] = min (dis[edge[j].v], max (edge[j].w, dis[edge[j].u]));

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

cout << "Case " << flag++ << ":" << endl;

scanf ("%d%d", &n, &m);

int i;

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

{

scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);

}

int tar;

scanf ("%d", &tar);

bellman_ford (tar);

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

{

if (i == tar)

printf ("0\n");

else if (dis[i] < INF)

printf ("%d\n", dis[i]);

else

printf ("Impossible\n");

}

return 0;

}

bzoj3229

maksyuki 发表于 oj 分类，标签: DP-区间DP

27 8月 2015

3229: [Sdoi2008]石子合并

Description

在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将N堆石子合并成一堆的最小得分。

阅读全文 »

bzoj2818

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

2818: Gcd

Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

Input

一个整数N

阅读全文 »

bzoj2705

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

2705: [SDOI2012]Longge的问题

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数，为N。

阅读全文 »

bzoj2190

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

27 8月 2015

2190: [SDOI2008]仪仗队

Description

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

阅读全文 »

sgu112

maksyuki 发表于 oj 分类，标签: 基础算法-高精度

27 8月 2015

a^b-b^a

You are given natural numbers a and b. Find a^b-b^a.

Input

Input contains numbers a and b (1≤a,b≤100).

阅读全文 »

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

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

Input

Output

Sample Input

Output for Sample Input

Notes

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Note

3229: [Sdoi2008]石子合并

Description

2818: Gcd

Description

Input

2705: [SDOI2012]Longge的问题

Description

Input

2190: [SDOI2008]仪仗队

Description

分类目录

标签云

书签

近期评论