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

poj3646

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

15 9月 2015

The Dragon of Loowater

Once upon a time, in the Kingdom of Loowater, a minor nuisance turned into a major problem.The shores of Rellau Creek in central Loowater had always been a prime breeding ground for geese. Due to the lack of predators, the geese population was out of control. The people of Loowater mostly kept clear of the geese. Occasionally, a goose would attack one of the people, and perhaps bite off a finger or two, but in general, the people tolerated the geese as a minor nuisance.One day, a freak mutation occurred, and one of the geese spawned a multi-headed fire-breathing dragon. When the dragon grew up, he threatened to burn the Kingdom of Loowater to a crisp. Loowater had a major problem. The king was alarmed, and called on his knights to slay the dragon and save the kingdom.The knights explained: "To slay the dragon, we must chop off all its heads. Each knight can chop off one of the dragon's heads. The heads of the dragon are of different sizes. In order to chop off a head, a knight must be at least as tall as the diameter of the head. The knights' union demands that for chopping off a head, a knight must be paid a wage equal to one gold coin for each centimetre of the knight's height." Would there be enough knights to defeat the dragon? The king called on his advisors to help him decide how many and which knights to hire. After having lost a lot of money building Mir Park, the king wanted to minimize the expense of slaying the dragon. As one of the advisors, your job was to help the king. You took it very seriously: if you failed, you and the whole kingdom would be burnt to a crisp!

Input

The input contains several test cases. The first line of each test case contains two integers between 1 and 20000 inclusive, indicating the number n of heads that the dragon has, and the number m of knights in the kingdom. The next n lines each contain an integer, and give the diameters of the dragon's heads, in centimetres. The following m lines each contain an integer, and specify the heights of the knights of Loowater, also in centimetres.

The last test case is followed by a line containing:

0 0

Output

For each test case, output a line containing the minimum number of gold coins that the king needs to pay to slay the dragon. If it is not possible for the knights of Loowater to slay the dragon, output the line:

Loowater is doomed!

Sample Input

2 3
5
4
7
8
4
2 1
5
5
10
0 0

Sample Output

Loowater is doomed!

Source

Waterloo Local Contest, 2007.9.29

题目类型：贪心

算法分析：直接将骑士的能力值和龙的头直径按照从小到大排序，然后对于每一个龙的头判断是否有骑士能够砍下它(骑士能力从小到大枚举)，如果最终龙的头没有被砍完，则输，否则输出累加的骑士的能力值

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

int a[maxn], b[maxn];

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

    int n, m;
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0)
            break;

        int i;
        for (i = 0; i < n; i++)
            cin >> a[i];

        for (i = 0; i < m; i++)
            cin >> b[i];

        sort (a, a + n);
        sort (b, b + m);

        int j, sum = 0;
        for (i = 0, j = 0; i < n && j < m; )
        {
            if (b[j] >= a[i])
            {
                sum += b[j];
                i++;
                j++;
            }

            else
            {
                j++;
            }
        }

        if (i == n)
            cout << sum << endl;

        else
            cout << "Loowater is doomed!" << 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>

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

int a[maxn], b[maxn];

int main()

{

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

int n, m;

while (cin >> n >> m)

{

if (n == 0 && m == 0)

break;

int i;

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

cin >> a[i];

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

cin >> b[i];

sort (a, a + n);

sort (b, b + m);

int j, sum = 0;

for (i = 0, j = 0; i < n && j < m; )

{

if (b[j] >= a[i])

{

sum += b[j];

i++;

j++;

}

else

{

j++;

}

if (i == n)

cout << sum << endl;

else

cout << "Loowater is doomed!" << endl;

}

return 0;

}

poj3641

maksyuki 发表于 oj 分类，标签: 数论-费马小定理

15 9月 2015

Pseudoprime numbers

Fermat's theorem states that for any prime number p and for any integer a > 1, a^p = a (mod p). That is, if we raise a to the p^th power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.) Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

Output

For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Sample Input

3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

Sample Output

yes

Source

Waterloo Local Contest, 2007.9.23

题目类型：伪素数测试

算法分析：按照以a为基的伪素数的定义判断即可，也就是判断是否p为合数，且对于任意的正整数a，满足a ^ p = a (mod p)

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

const int testnum = 8; //随机算法判定次数，一般8~10就够了
// 计算ret = (a*b)%c a,b,c < 2^63
long long mult_mod (long long a,long long b,long long mod)
{
    a %= mod;
    b %= mod;
    long long ans = 0;
    long long temp = a;

    while (b)
    {
        if (b & 1)
        {
            ans += temp;
            if (ans > mod)
                ans -= mod;//直接取模慢很多
        }

        temp <<= 1;
        if (temp > mod)
            temp -= mod;
        b >>= 1;
    }

return ans;
}

long long pow_mod (long long a,long long n,long long mod)
{
    long long ans = 1;
    long long temp = a % mod;
    while (n)
    {
        if (n & 1)
            ans = mult_mod (ans, temp, mod);

        temp = mult_mod (temp, temp, mod);
        n >>= 1;
    }

return ans;
}

bool IsPrime (long long val)
{
    if (val == 1 || val == 2)
        return true;

    for (long long i = 2; i * i <= val; i++)
        if (val % i == 0)
            return false;

return true;
}


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

    long long a, p;

    while (cin >> p >> a)
    {
        if (a == 0 && p == 0)
            break;

        if (IsPrime (p))
            cout << "no" << endl;

        else
        {
            long long ans = pow_mod (a, p, p);

            if (ans == a)
                cout << "yes" << endl;

            else
                cout << "no" << 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

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

const int testnum = 8; //随机算法判定次数，一般8~10就够了

// 计算ret = (a*b)%c a,b,c < 2^63

long long mult_mod (long long a,long long b,long long mod)

{

a %= mod;

b %= mod;

long long ans = 0;

long long temp = a;

while (b)

{

if (b & 1)

{

ans += temp;

if (ans > mod)

ans -= mod;//直接取模慢很多

}

temp <<= 1;

if (temp > mod)

temp -= mod;

b >>= 1;

}

return ans;

}

long long pow_mod (long long a,long long n,long long mod)

{

long long ans = 1;

long long temp = a % mod;

while (n)

{

if (n & 1)

ans = mult_mod (ans, temp, mod);

temp = mult_mod (temp, temp, mod);

n >>= 1;

}

return ans;

}

bool IsPrime (long long val)

{

if (val == 1 || val == 2)

return true;

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

if (val % i == 0)

return false;

return true;

}

int main()

{

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

long long a, p;

while (cin >> p >> a)

{

if (a == 0 && p == 0)

break;

if (IsPrime (p))

cout << "no" << endl;

else

{

long long ans = pow_mod (a, p, p);

if (ans == a)

cout << "yes" << endl;

else

cout << "no" << endl;

}

return 0;

}

poj3468

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

15 9月 2015

A Simple Problem with Integers

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

Hint

The sums may exceed the range of 32-bit integers.

Source

POJ Monthly--2007.11.25, Yang Yi

题目类型：线段树

算法分析：这是一道线段树成段更新和区间求和的问题，要使用lazy标记，注意结果可能超过int范围，所以应该使用long long来存储结果

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

const int maxn = 100000 + 66;

long long lazy[maxn<<2];
long long sum[maxn<<2];

void PushUp (int rt)
{
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void PushDown (int rt, int l, int m, int r)
{
    if (lazy[rt])
    {
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        sum[rt<<1] += lazy[rt] * (m - l + 1);
        sum[rt<<1|1] += lazy[rt] * (r - m);
        lazy[rt] = 0;
    }
}

void Build (int rt, int l, int r)
{
    lazy[rt] = 0;

    if (l == r)
    {
        scanf ("%lld", &sum[rt]);
        return ;
    }

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);

	Build (lson);
	Build (rson);
	PushUp (rt);
}

void UpDate (int rt, int l, int r, int L, int R, int add)
{
	if (L <= l && r <= R)
    {
		lazy[rt] += add;
		sum[rt] += add * (r - l + 1);
		return ;
	}

	int m = (l + r) >> 1;
    PushDown (rt, l, m, r);

    if (L <= m)
        UpDate (lson, L, R, add);

    if (R > m)
        UpDate (rson, L, R, add);

	PushUp (rt);
}

long long Query (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
    {
        return sum[rt];
    }

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);
    long long 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, q;
    while (scanf ("%d%d", &n, &q) != EOF)
    {
        Build (1, 1, n);

        int i, val_a, val_b, val;
        char cmd[6];

        for (i = 0; i < q; i++)
        {
            scanf ("%s%d%d", cmd, &val_a, &val_b);

            if (cmd[0] == 'Q')
                printf ("%lld\n", Query (1, 1, n, val_a, val_b));


            else
            {
                scanf ("%d", &val);
                UpDate (1, 1, n, val_a, val_b, val);
            }
        }
    }

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

145

146

147

148

149

150

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

const int maxn = 100000 + 66;

long long lazy[maxn<<2];

long long sum[maxn<<2];

void PushUp (int rt)

{

sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void PushDown (int rt, int l, int m, int r)

{

if (lazy[rt])

{

lazy[rt<<1] += lazy[rt];

lazy[rt<<1|1] += lazy[rt];

sum[rt<<1] += lazy[rt] * (m - l + 1);

sum[rt<<1|1] += lazy[rt] * (r - m);

lazy[rt] = 0;

}

void Build (int rt, int l, int r)

{

lazy[rt] = 0;

if (l == r)

{

scanf ("%lld", &sum[rt]);

return ;

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

Build (lson);

Build (rson);

PushUp (rt);

}

void UpDate (int rt, int l, int r, int L, int R, int add)

{

if (L <= l && r <= R)

{

lazy[rt] += add;

sum[rt] += add * (r - l + 1);

return ;

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

if (L <= m)

UpDate (lson, L, R, add);

if (R > m)

UpDate (rson, L, R, add);

PushUp (rt);

}

long long Query (int rt, int l, int r, int L, int R)

{

if (L <= l && r <= R)

{

return sum[rt];

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

long long 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, q;

while (scanf ("%d%d", &n, &q) != EOF)

{

Build (1, 1, n);

int i, val_a, val_b, val;

char cmd[6];

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

{

scanf ("%s%d%d", cmd, &val_a, &val_b);

if (cmd[0] == 'Q')

printf ("%lld\n", Query (1, 1, n, val_a, val_b));

else

{

scanf ("%d", &val);

UpDate (1, 1, n, val_a, val_b, val);

}

return 0;

}

poj3320

maksyuki 发表于 oj 分类，标签: 其他-追逐法

15 9月 2015

Jessica's Reading Problem

Jessica's a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.A very hard-working boy had manually indexed for her each page of Jessica's text-book with what idea each page is about and thus made a big progress for his courtship. Here you come in to save your skin: given the index, help Jessica decide which contiguous part she should read. For convenience, each idea has been coded with an ID, which is a non-negative integer.

Input

The first line of input is an integer P (1 ≤ P ≤ 1000000), which is the number of pages of Jessica's text-book. The second line contains P non-negative integers describing what idea each page is about. The first integer is what the first page is about, the second integer is what the second page is about, and so on. You may assume all integers that appear can fit well in the signed 32-bit integer type.

Output

Output one line: the number of pages of the shortest contiguous part of the book which contains all ideals covered in the book.

Sample Input

1 8 8 8 1

Sample Output

Source

POJ Monthly--2007.08.05, Jerry

题目类型：追逐法

算法分析：动态维护两个指针p1和p2，然后判断指针之间的区间内部的元素个数是否已经到达总的元素种数，最后直接使用追逐法的思路解决即可

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

int ans[maxn];

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

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

    int n;
    while (scanf ("%d", &n) != EOF)
    {
        int i;
        set <int> s;

        for (i = 1; i <= n; i++)
        {
            scanf ("%d", &ans[i]);
            if (!s.count (ans[i]))
                s.insert (ans[i]);
        }

        int tot = s.size ();
        int p1 = 1, p2 = 1, minval = n, sum = 0;
        map <int, int> ma;

        while (1)
        {
            while (sum < tot && p2 <= n)
            {
                if (ma[ans[p2]] == 0)
                    sum++;

                ma[ans[p2]]++;
                p2++;
            }

            if (sum < tot)
                break;

            minval = min (minval, p2 - p1);

            if (ma[ans[p1]] == 1)
                sum--;

            ma[ans[p1]]--;
            p1++;
        }

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

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

int ans[maxn];

int main()

{

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

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

int n;

while (scanf ("%d", &n) != EOF)

{

int i;

set <int> s;

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

{

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

if (!s.count (ans[i]))

s.insert (ans[i]);

}

int tot = s.size ();

int p1 = 1, p2 = 1, minval = n, sum = 0;

map <int, int> ma;

while (1)

{

while (sum < tot && p2 <= n)

{

if (ma[ans[p2]] == 0)

sum++;

ma[ans[p2]]++;

p2++;

}

if (sum < tot)

break;

minval = min (minval, p2 - p1);

if (ma[ans[p1]] == 1)

sum--;

ma[ans[p1]]--;

p1++;

}

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

}

return 0;

}

poj3268

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

15 9月 2015

Silver Cow Party

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires T_i (1 ≤ T_i ≤ 100) units of time to traverse. Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way. Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: A_i, B_i, and T_i. The described road runs from farm A_i to farm B_i, requiring T_i time units to traverse.

Output

Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Sample Output

Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

Source

USACO 2007 February Silver

题目类型：单源最短路(SPFA)

算法分析：构建邻接表和逆邻接表，分别计算从x点到其他各个点的最短路径(使用邻接表)，然后计算从各个点到x点的最短路径(使用逆邻接表)。然后对于每个点累加起两次距离，求最后累加之后的距离中最大的即可。注意求该问题使用其他算法时间复杂度可能会偏高

#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 = 3600;
const int INF = 66666666;

struct Node
{
    int v, w;
    Node (int vv, int ww) : v (vv), w (ww) {}
    Node () {}
};

int ans[maxn], dis[maxn];
bool inq[maxn];
int n, m, x;

vector <Node> edge[maxn], redge[maxn];

void spfa (int dir)
{
    int i;
    for (i = 1; i <= n; i++)
        dis[i] = INF;

    memset (inq, false, sizeof (inq));
    dis[x] = 0;
    inq[x] = true;

    queue <int> q;

    q.push (x);

    if (dir == 0)
    {
        while (!q.empty ())
        {
            int temp = q.front ();
            q.pop ();
            inq[temp] = false;

            int i;
            for (i = 0; i < edge[temp].size (); i++)
            {
                if (dis[edge[temp][i].v] > dis[temp] + edge[temp][i].w)
                {
                    dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w;
                    if (!inq[edge[temp][i].v])
                    {
                        q.push (edge[temp][i].v);
                        inq[edge[temp][i].v] = true;
                    }
                }
            }
        }
    }

    else
    {
         while (!q.empty ())
        {
            int temp = q.front ();
            q.pop ();
            inq[temp] = false;

            int i;
            for (i = 0; i < redge[temp].size (); i++)
            {
                if (dis[redge[temp][i].v] > dis[temp] + redge[temp][i].w)
                {
                    dis[redge[temp][i].v] = dis[temp] + redge[temp][i].w;
                    if (!inq[redge[temp][i].v])
                    {
                        q.push (redge[temp][i].v);
                        inq[redge[temp][i].v] = true;
                    }
                }
            }
        }
    }
}


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

    while (cin >> n >> m >> x)
    {
        int i;
        for (i = 0; i < maxn; i++)
        {
            edge[i].clear ();
            redge[i].clear ();
        }

        int val_a, val_b, val_w;
        for (i = 0; i < m; i++)
        {
            cin >> val_a >> val_b >> val_w;
            edge[val_a].push_back (Node (val_b, val_w));
            redge[val_b].push_back (Node (val_a, val_w));
        }

        spfa (0);

        memset (ans, 0, sizeof (ans));

        for (i = 1; i <= n; i++)
        {
            if (i == x)
                continue;

            ans[i] += dis[i];
        }

        spfa (1);

        int maxval = -INF;
        for (i = 1; i <= n; i++)
        {
            if (i == x)
                continue;

            ans[i] += dis[i];
            if (ans[i] > maxval)
                maxval = ans[i];
        }

        cout << maxval << 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

145

146

147

148

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

const int INF = 66666666;

struct Node

{

int v, w;

Node (int vv, int ww) : v (vv), w (ww) {}

Node () {}

};

int ans[maxn], dis[maxn];

bool inq[maxn];

int n, m, x;

vector <Node> edge[maxn], redge[maxn];

void spfa (int dir)

{

int i;

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

dis[i] = INF;

memset (inq, false, sizeof (inq));

dis[x] = 0;

inq[x] = true;

queue <int> q;

q.push (x);

if (dir == 0)

{

while (!q.empty ())

{

int temp = q.front ();

q.pop ();

inq[temp] = false;

int i;

for (i = 0; i < edge[temp].size (); i++)

{

if (dis[edge[temp][i].v] > dis[temp] + edge[temp][i].w)

{

dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w;

if (!inq[edge[temp][i].v])

{

q.push (edge[temp][i].v);

inq[edge[temp][i].v] = true;

}

else

{

while (!q.empty ())

{

int temp = q.front ();

q.pop ();

inq[temp] = false;

int i;

for (i = 0; i < redge[temp].size (); i++)

{

if (dis[redge[temp][i].v] > dis[temp] + redge[temp][i].w)

{

dis[redge[temp][i].v] = dis[temp] + redge[temp][i].w;

if (!inq[redge[temp][i].v])

{

q.push (redge[temp][i].v);

inq[redge[temp][i].v] = true;

}

int main()

{

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

while (cin >> n >> m >> x)

{

int i;

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

{

edge[i].clear ();

redge[i].clear ();

}

int val_a, val_b, val_w;

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

{

cin >> val_a >> val_b >> val_w;

edge[val_a].push_back (Node (val_b, val_w));

redge[val_b].push_back (Node (val_a, val_w));

}

spfa (0);

memset (ans, 0, sizeof (ans));

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

{

if (i == x)

continue;

ans[i] += dis[i];

}

spfa (1);

int maxval = -INF;

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

{

if (i == x)

continue;

ans[i] += dis[i];

if (ans[i] > maxval)

maxval = ans[i];

}

cout << maxval << 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;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define i64 long long

const int INF = 0x7FFFFFFF - 6;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1000 + 66;

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

Node edge[maxn*maxn];
int head[maxn], edgelen;

Node redge[maxn*maxn];
int rhead[maxn], redgelen;

void Init ()
{
    memset (head, -1, sizeof (head));
    memset (edge, -1, sizeof (edge));
    memset (rhead, -1, sizeof (rhead));
    memset (redge, -1, sizeof (redge));
    edgelen = 0;
    redgelen = 0;
}

void AddEdge (int u, int v, int w)
{
    edge[edgelen].v = v;
    edge[edgelen].w = w;
    edge[edgelen].next = head[u];
    head[u] = edgelen++;

    redge[redgelen].v = u;
    redge[redgelen].w = w;
    redge[redgelen].next = rhead[v];
    rhead[v] = redgelen++;
}

//分别表示节点到源点的最距离和顶点个数
int dis[maxn], inq[maxn], rdis[maxn], rinq[maxn];
int n, m, x;

//数组下标从1开始
void spfa (int s)
{
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        inq[i] = 0;
    }

    dis[s] = 0;
    queue <int> qu;
    qu.push (s);
    inq[s]++;
    while (!qu.empty ())
    {
        int tt = qu.front(); qu.pop (); inq[tt]--;
        int pa = head[tt];
        while (pa != -1)
        {
            int pb = edge[pa].v;
            if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w)
            {
                dis[pb] = dis[tt] + edge[pa].w;
                if (!inq[pb])
                {
                    qu.push (pb);
                    inq[pb]++;
                }
            }
            pa = edge[pa].next;
        }
    }
}


void rspfa (int s)
{
    for (int i = 1; i <= n; i++)
    {
        rdis[i] = INF;
        rinq[i] = 0;
    }

    rdis[s] = 0;
    queue <int> qu;
    qu.push (s);
    rinq[s]++;
    while (!qu.empty ())
    {
        int tt = qu.front(); qu.pop (); rinq[tt]--;
        int pa = rhead[tt];
        while (pa != -1)
        {
            int pb = redge[pa].v;
            if (rdis[tt] < INF && rdis[pb] > rdis[tt] + redge[pa].w)
            {
                rdis[pb] = rdis[tt] + redge[pa].w;
                if (!rinq[pb])
                {
                    qu.push (pb);
                    rinq[pb]++;
                }
            }
            pa = redge[pa].next;
        }
    }
}

int main()
{
//    CPPFF;
//    CFF;

    while (scanf ("%d%d%d", &n, &m, &x) != EOF)
    {
        Init ();
        int u, v, w;
        for (int i = 1; i <= m; i++)
        {
            scanf ("%d%d%d", &u, &v, &w);
            AddEdge (u, v, w);
        }

        spfa (x);
        rspfa (x);
        int maxval = 0;
        for (int i = 1; i <= n; i++)
            if (dis[i] < INF && rdis[i] < INF && i != x)
                maxval = max (maxval, dis[i] + rdis[i]);

        printf ("%d\n", maxval);
    }
    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

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define i64 long long

const int INF = 0x7FFFFFFF - 6;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

struct Node

{

int v, w, next;

};

Node edge[maxn*maxn];

int head[maxn], edgelen;

Node redge[maxn*maxn];

int rhead[maxn], redgelen;

void Init ()

{

memset (head, -1, sizeof (head));

memset (edge, -1, sizeof (edge));

memset (rhead, -1, sizeof (rhead));

memset (redge, -1, sizeof (redge));

edgelen = 0;

redgelen = 0;

}

void AddEdge (int u, int v, int w)

{

edge[edgelen].v = v;

edge[edgelen].w = w;

edge[edgelen].next = head[u];

head[u] = edgelen++;

redge[redgelen].v = u;

redge[redgelen].w = w;

redge[redgelen].next = rhead[v];

rhead[v] = redgelen++;

}

//分别表示节点到源点的最距离和顶点个数

int dis[maxn], inq[maxn], rdis[maxn], rinq[maxn];

int n, m, x;

//数组下标从1开始

void spfa (int s)

{

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

{

dis[i] = INF;

inq[i] = 0;

}

dis[s] = 0;

queue <int> qu;

qu.push (s);

inq[s]++;

while (!qu.empty ())

{

int tt = qu.front(); qu.pop (); inq[tt]--;

int pa = head[tt];

while (pa != -1)

{

int pb = edge[pa].v;

if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w)

{

dis[pb] = dis[tt] + edge[pa].w;

if (!inq[pb])

{

qu.push (pb);

inq[pb]++;

}

pa = edge[pa].next;

}

void rspfa (int s)

{

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

{

rdis[i] = INF;

rinq[i] = 0;

}

rdis[s] = 0;

queue <int> qu;

qu.push (s);

rinq[s]++;

while (!qu.empty ())

{

int tt = qu.front(); qu.pop (); rinq[tt]--;

int pa = rhead[tt];

while (pa != -1)

{

int pb = redge[pa].v;

if (rdis[tt] < INF && rdis[pb] > rdis[tt] + redge[pa].w)

{

rdis[pb] = rdis[tt] + redge[pa].w;

if (!rinq[pb])

{

qu.push (pb);

rinq[pb]++;

}

pa = redge[pa].next;

}

int main()

{

// CPPFF;

// CFF;

while (scanf ("%d%d%d", &n, &m, &x) != EOF)

{

Init ();

int u, v, w;

for (int i = 1; i <= m; i++)

{

scanf ("%d%d%d", &u, &v, &w);

AddEdge (u, v, w);

}

spfa (x);

rspfa (x);

int maxval = 0;

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

if (dis[i] < INF && rdis[i] < INF && i != x)

maxval = max (maxval, dis[i] + rdis[i]);

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

}

return 0;

}

poj3264

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

15 9月 2015

Balanced Lineup

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

Source

USACO 2007 January Silver

题目类型：线段树

算法分析：线段树的直接应用，每一个节点动态维护区间的两个端点和最小值minval最大值maxval。递归建树的过程中将叶节点的最大值和最小值进行初始化。然后对于每一个区间查询，使用两个全局变量maxval和minval来记录在查找的区间中的最大值和最小值。最后直接输出两者之差即可

#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 root = 1;
const int INF = 66666666;
const int maxn = 50000 + 66;

int maxval, minval;

struct Node
{
	int L, R;
	int maxval, minval;
};

Node tree[maxn*3];

void BuildTree (int pos, int L, int R)
{
	tree[pos].L = L;
	tree[pos].R = R;

	if (L == R)
	{
		scanf ("%I64d", &tree[pos].maxval);
		tree[pos].minval = tree[pos].maxval;
		return ;
	}

	int mid = (L + R) >> 1;

	BuildTree (pos * 2, L, mid);
	BuildTree (pos * 2 + 1, mid + 1, R);

    tree[pos].minval = min (tree[pos*2].minval, tree[pos*2+1].minval);
    tree[pos].maxval = max (tree[pos*2].maxval, tree[pos*2+1].maxval);
}


void Query (int pos, int L, int R)
{
    int mid = (tree[pos].L + tree[pos].R) >> 1;

	if (L == tree[pos].L && R == tree[pos].R)
	{
	    maxval = max (maxval, tree[pos].maxval);
	    minval = min (minval, tree[pos].minval);
	}

	else if (R <= mid)
        Query (pos << 1, L, R);

	else if (L > mid)
		Query ((pos << 1) + 1, L, R);

	else
    {
        Query (pos << 1, L, mid);
        Query ((pos << 1) + 1, mid + 1, R);
    }
}
/*
void Update (int pos, int k, int add)
{
	if (k >= tree[pos].L && k <= tree[pos].R)
	{
		tree[pos].sum += add;
		if (tree[pos].L == tree[pos].R)
			return ;

		Update (pos * 2, k, add);
		Update (pos * 2 + 1, k, add);
	}

return ;
}*/

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

    int n, q;

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

    BuildTree (root, 1, n);

    int i, temp_a, temp_b;

    for (i = 0; i < q; i++)
    {
        scanf ("%d%d", &temp_a, &temp_b);

        maxval = -INF, minval = INF;
        Query (root, temp_a, temp_b);

        printf ("%d\n", maxval - minval);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#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 root = 1;

const int INF = 66666666;

const int maxn = 50000 + 66;

int maxval, minval;

struct Node

{

int L, R;

int maxval, minval;

};

Node tree[maxn*3];

void BuildTree (int pos, int L, int R)

{

tree[pos].L = L;

tree[pos].R = R;

if (L == R)

{

scanf ("%I64d", &tree[pos].maxval);

tree[pos].minval = tree[pos].maxval;

return ;

}

int mid = (L + R) >> 1;

BuildTree (pos * 2, L, mid);

BuildTree (pos * 2 + 1, mid + 1, R);

tree[pos].minval = min (tree[pos*2].minval, tree[pos*2+1].minval);

tree[pos].maxval = max (tree[pos*2].maxval, tree[pos*2+1].maxval);

}

void Query (int pos, int L, int R)

{

int mid = (tree[pos].L + tree[pos].R) >> 1;

if (L == tree[pos].L && R == tree[pos].R)

{

maxval = max (maxval, tree[pos].maxval);

minval = min (minval, tree[pos].minval);

}

else if (R <= mid)

Query (pos << 1, L, R);

else if (L > mid)

Query ((pos << 1) + 1, L, R);

else

{

Query (pos << 1, L, mid);

Query ((pos << 1) + 1, mid + 1, R);

}

void Update (int pos, int k, int add)

{

if (k >= tree[pos].L && k <= tree[pos].R)

{

tree[pos].sum += add;

if (tree[pos].L == tree[pos].R)

return ;

Update (pos * 2, k, add);

Update (pos * 2 + 1, k, add);

}

return ;

}*/

int main()

{

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

int n, q;

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

BuildTree (root, 1, n);

int i, temp_a, temp_b;

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

{

scanf ("%d%d", &temp_a, &temp_b);

maxval = -INF, minval = INF;

Query (root, temp_a, temp_b);

printf ("%d\n", maxval - minval);

}

return 0;

}

poj3259

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

15 9月 2015

Wormholes

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes. As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself 🙂 . To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output

Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

Sample Output

YES

Hint

For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

Source

USACO 2006 December Gold

题目类型：单源最短路(SPFA)判负圈

算法分析：按照题目的要求建好邻接表，然后使用SPFA算法计算并统计每一个点入队列的次数，如果有点的入队次数大于n-1次，则可直接判断图中存在负权值回路

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

struct Node
{
    int v, w;
    Node (int vv, int ww) : v (vv), w (ww) {}
    Node () {}
};

bool inq[maxn];
int dis[maxn], cnt[maxn];
int n, m, w;

vector <Node> edge[maxn];

bool spfa ()
{
    int i;
    memset (inq, false, sizeof (inq));
    memset (cnt, 0, sizeof (cnt));

    for (i = 0; i < maxn; i++)
        dis[i] = INF;

    dis[1] = 0;
    inq[1] = true;

    queue <int> q;
    q.push (1);
    cnt[1]++;

    while (!q.empty ())
    {
        int temp = q.front ();
        q.pop ();
        inq[temp] = false;

        if (cnt[temp] >= n)
            return true;


        int i;
        for (i = 0; i < edge[temp].size (); i++)
        {
            if (dis[edge[temp][i].v] > dis[temp] + edge[temp][i].w)
            {
                dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w;
                if (!inq[edge[temp][i].v])
                {
                    q.push (edge[temp][i].v);
                    inq[edge[temp][i].v] = true;
                    cnt[edge[temp][i].v]++;
                }
            }
        }
    }

return false;
}


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

    int t;
    cin >> t;

    while (t--)
    {
        cin >> n >> m >> w;

        int i;
        for (i = 0; i < maxn; i++)
            edge[i].clear ();


        int val_u, val_v, val_w;
        for (i = 0; i < m; i++)
        {
            cin >> val_u >> val_v >> val_w;
            edge[val_u].push_back (Node (val_v, val_w));
            edge[val_v].push_back (Node (val_u, val_w));
        }

        for (i = 0; i < w; i++)
        {
            cin >> val_u >> val_v >> val_w;
            edge[val_u].push_back (Node (val_v, -val_w));
        }

        if (spfa ())
            cout << "YES" << endl;

        else
            cout << "NO" << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

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

struct Node

{

int v, w;

Node (int vv, int ww) : v (vv), w (ww) {}

Node () {}

};

bool inq[maxn];

int dis[maxn], cnt[maxn];

int n, m, w;

vector <Node> edge[maxn];

bool spfa ()

{

int i;

memset (inq, false, sizeof (inq));

memset (cnt, 0, sizeof (cnt));

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

dis[i] = INF;

dis[1] = 0;

inq[1] = true;

queue <int> q;

q.push (1);

cnt[1]++;

while (!q.empty ())

{

int temp = q.front ();

q.pop ();

inq[temp] = false;

if (cnt[temp] >= n)

return true;

int i;

for (i = 0; i < edge[temp].size (); i++)

{

if (dis[edge[temp][i].v] > dis[temp] + edge[temp][i].w)

{

dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w;

if (!inq[edge[temp][i].v])

{

q.push (edge[temp][i].v);

inq[edge[temp][i].v] = true;

cnt[edge[temp][i].v]++;

}

return false;

}

int main()

{

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

int t;

cin >> t;

while (t--)

{

cin >> n >> m >> w;

int i;

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

edge[i].clear ();

int val_u, val_v, val_w;

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

{

cin >> val_u >> val_v >> val_w;

edge[val_u].push_back (Node (val_v, val_w));

edge[val_v].push_back (Node (val_u, val_w));

}

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

{

cin >> val_u >> val_v >> val_w;

edge[val_u].push_back (Node (val_v, -val_w));

}

if (spfa ())

cout << "YES" << endl;

else

cout << "NO" << endl;

}

return 0;

}

poj3250

maksyuki 发表于 oj 分类，标签: 数据结构-栈/单调

15 9月 2015

Bad Hair Day

Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads. Each cow i has a specified height h_i (1 ≤ h_i≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

=
=       =
=   -   =         Cows facing right -->
=   =   =
= - = = =
= = = = = =
1 2 3 4 5 6

Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow's hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow's hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!

Let c_i denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c₁ through c_N.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

Input

Line 1: The number of cows, N.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.

Output

Line 1: A single integer that is the sum of c₁ through c_N.

Sample Input

Sample Output

Source

USACO 2006 November Silver

题目类型：单调栈

算法分析：本题可以转换为求所有的牛能被多少在其左边的牛看到，可以维护一个单调递减栈(严格递减)，然后每次更新完栈后，累加栈中元素的个数- 1即可

#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 int MOD = 32767;

const int maxn = 80000 + 66;;

int ans[maxn];

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

	int n;
	while (cin >> n)
	{
        int i;
        for (i = 0; i < n; i++)
			cin >> ans[i];

        long long sum = 0;
        stack <int> sta;

        for (i = 0; i < n; i++)
		{
			while (!sta.empty () && sta.top () <= ans[i])
				sta.pop ();

			sta.push (ans[i]);
			sum += (sta.size () - 1);
		}

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

const int MOD = 32767;

const int maxn = 80000 + 66;;

int ans[maxn];

int main()

{

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

int n;

while (cin >> n)

{

int i;

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

cin >> ans[i];

long long sum = 0;

stack <int> sta;

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

{

while (!sta.empty () && sta.top () <= ans[i])

sta.pop ();

sta.push (ans[i]);

sum += (sta.size () - 1);

}

cout << sum << endl;

}

return 0;

}

poj3243

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

15 9月 2015

Clever Y

Little Y finds there is a very interesting formula in mathematics:

X^Y mod Z = K

Given X, Y, Z, we all know how to figure out K fast. However, given X, Z, K, could you figure out Y fast?

Input 阅读全文 »

poj3233

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举, 数值-矩阵快速幂取模

15 9月 2015

Matrix Power Series

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

2 2 4

0 1

1 1

Sample Output

1 2

2 3

Source

POJ Monthly--2007.06.03, Huang, Jinsong

题目类型：矩阵快速幂 + 二分

算法分析：直接计算每一个矩阵的幂然后求和取模会TLE，此时考虑到A ^ 1 + A ^ 2 + A ^ 3 + A ^ 4 = (A ^ 1 + A ^ 2) + (A ^ 1 + A ^ 2) * A ^ 2，可以使用二分的思想先将A ^ 1 + A ^ 2 + ……A ^ n划分成{A ^ 1 + A ^ 2 + A ^ (k / 2)} + A ^(k / 2)] + {A ^ (k / 2 + 1) + A ^ + ……A ^ n}三部分，由于第三部分可以由第一部分每一项乘以A ^ (k / 2)得到，所以可以先计算出第一部分，再直接乘方求和

#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 int MOD = 10000;

const int maxn = 36 + 6;

struct Mat
{
    int mat[maxn][maxn];
};

int n, k, mod;
Mat A, ans;


Mat operator * (Mat a, Mat b)
{
    Mat c;
    memset (c.mat, 0, sizeof (c.mat));
    int i, j, k;

    for (k = 0; k < n; k++)
    {
        for (i = 0; i < n; i++)
        {
            if (a.mat[i][k] == 0) continue;

            for (j = 0; j < n; j++)
            {
                if (b.mat[k][j] == 0) continue;

                c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j]) % mod) % mod;
            }
        }
    }
return c;
}

Mat operator ^ (Mat a, int k)
{
    Mat c;
    int i, j;
    for (i = 0; i < n; i++)
        for(j = 0; j < n; j++)
        c.mat[i][j] = (i == j);

    while (k)
    {
        if(k & 1)
            c = c * a;

        a = a * a;
        k >>= 1;
    }

return c;
}

Mat operator + (Mat a, Mat b)
{
    Mat c;
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            c.mat[i][j] = ((a.mat[i][j] % mod) + (b.mat[i][j] % mod)) % mod;
        }
    }

return c;
}

Mat MatrixSum (int k)
{
    if (k == 1)
        return A;

    Mat temp, b;

    temp = MatrixSum (k / 2);

    if (k & 1)
    {
        b = A ^ (k / 2 + 1);
        temp = temp + (temp * b);
        temp = temp + b;
    }

    else
    {
        b = A ^ (k / 2);
        temp = temp + (temp * b);
    }

return temp;
}


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

    scanf ("%d%d%d", &n, &k, &mod);


    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf ("%d", &A.mat[i][j]);


    ans = MatrixSum (k);

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (j == 0)
                cout << ans.mat[i][j];

            else
                cout << " " << ans.mat[i][j];
        }
        cout << 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

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

#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 int MOD = 10000;

const int maxn = 36 + 6;

struct Mat

{

int mat[maxn][maxn];

};

int n, k, mod;

Mat A, ans;

Mat operator * (Mat a, Mat b)

{

Mat c;

memset (c.mat, 0, sizeof (c.mat));

int i, j, k;

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

{

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

{

if (a.mat[i][k] == 0) continue;

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

{

if (b.mat[k][j] == 0) continue;

c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j]) % mod) % mod;

}

return c;

}

Mat operator ^ (Mat a, int k)

{

Mat c;

int i, j;

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

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

c.mat[i][j] = (i == j);

while (k)

{

if(k & 1)

c = c * a;

a = a * a;

k >>= 1;

}

return c;

}

Mat operator + (Mat a, Mat b)

{

Mat c;

int i, j;

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

{

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

{

c.mat[i][j] = ((a.mat[i][j] % mod) + (b.mat[i][j] % mod)) % mod;

}

return c;

}

Mat MatrixSum (int k)

{

if (k == 1)

return A;

Mat temp, b;

temp = MatrixSum (k / 2);

if (k & 1)

{

b = A ^ (k / 2 + 1);

temp = temp + (temp * b);

temp = temp + b;

}

else

{

b = A ^ (k / 2);

temp = temp + (temp * b);

}

return temp;

}

int main()

{

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

scanf ("%d%d%d", &n, &k, &mod);

int i, j;

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

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

scanf ("%d", &A.mat[i][j]);

ans = MatrixSum (k);

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

{

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

{

if (j == 0)

cout << ans.mat[i][j];

else

cout << " " << ans.mat[i][j];

}

cout << endl;

}

return 0;

}

poj3126

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

15 9月 2015

Prime Path

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033
1733
3733
3739
3779
8779
8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

1033 8179

1373 8017

1033 1033

Sample Output

Source

Northwestern Europe 2006

题目类型：素数+BFS

算法分析：首先将四位数的所有素数找出来，然后从开始的素数每次进行一次BFS搜索，转移的条件是下一个素数的与当前素数只有一位不同，注意每次判断素数的范围是1000~9999!!!

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

struct Node
{
	int v, s;
	Node () {}
	Node (int vv, int ss) : v (vv), s (ss) {}
};

bool prime[maxn+66], v[maxn+66];

long long res;

int aa[16], lena, bb[16], lenb;

bool Ok (int a, int b)
{
	lena = 0;
	do
	{
        aa[lena++] = a % 10;
        a /= 10;
	} while (a);

	lenb = 0;
	do
	{
		bb[lenb++] = b % 10;
		b /= 10;
	} while (b);

    int cnt = 0;
    for (int i = 0; i < lena; i++)
        if (aa[i] != bb[i])
			cnt++;

	if (cnt == 1)
		return true;

	return false;
}


bool bfs (int a, int b)
{

	res = 0;
	memset (v, false, sizeof (v));
    v[a] = true;
	queue <Node> qu;
	qu.push(Node (a, 0));
    while (!qu.empty ())
    {
        Node tt = qu.front(); qu.pop();

        if (tt.v == b)
		{
			res = tt.s;
			return true;
		}

		for (int i = 1000; i < 10000; i++)
		{
            if (prime[i] && !v[i] && Ok (tt.v, i))
			{
				v[i] = true;
                qu.push(Node (i, tt.s + 1));
			}
		}
    }
    return false;
}

void Get ()
{
    memset (prime, true, sizeof (prime));
    for (int i = 2; i <= maxn; i++)
	{
        if (prime[i])
		{
            for (int j = 2; j * i <= maxn; j++)
                prime[j*i] = false;
		}
	}
}


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

	Get ();
	int t;
	cin >> t;

	while (t--)
	{
        int a, b;
        cin >> a >> b;
        if(a > b)
			swap (a, b);

        if (bfs (a, b))
			cout << res << endl;

		else
			cout << "Impossible" << 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>

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

struct Node

{

int v, s;

Node () {}

Node (int vv, int ss) : v (vv), s (ss) {}

};

bool prime[maxn+66], v[maxn+66];

long long res;

int aa[16], lena, bb[16], lenb;

bool Ok (int a, int b)

{

lena = 0;

{

aa[lena++] = a % 10;

a /= 10;

} while (a);

lenb = 0;

{

bb[lenb++] = b % 10;

b /= 10;

} while (b);

int cnt = 0;

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

if (aa[i] != bb[i])

cnt++;

if (cnt == 1)

return true;

return false;

}

bool bfs (int a, int b)

{

res = 0;

memset (v, false, sizeof (v));

v[a] = true;

queue <Node> qu;

qu.push(Node (a, 0));

while (!qu.empty ())

{

Node tt = qu.front(); qu.pop();

if (tt.v == b)

{

res = tt.s;

return true;

}

for (int i = 1000; i < 10000; i++)

{

if (prime[i] && !v[i] && Ok (tt.v, i))

{

v[i] = true;

qu.push(Node (i, tt.s + 1));

}

return false;

}

void Get ()

{

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

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

{

if (prime[i])

{

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

prime[j*i] = false;

}

int main()

{

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

Get ();

int t;

cin >> t;

while (t--)

{

int a, b;

cin >> a >> b;

if(a > b)

swap (a, b);

if (bfs (a, b))

cout << res << endl;

else

cout << "Impossible" << endl;

}

return 0;

}

poj3122

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

15 9月 2015

Pie

My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though. My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size. What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

Input

One line with a positive integer: the number of test cases. Then for each test case:

One line with two integers N and F with 1 ≤ N, F ≤ 10 000: the number of pies and the number of friends.
One line with N integers ri with 1 ≤ ri ≤ 10 000: the radii of the pies.

Output

For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10⁻³.

Sample Input

3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

Sample Output

25.1327
3.1416
50.2655

Source

Northwestern Europe 2006

题目类型：二分法

算法分析：直接二分每个人(包括主人在内)可以拿到的派的体积，然后对于每一个体积判断能够满足多少人的需求

#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 double EPS = 1e-6;
const double PI = 3.14159265359;

const int maxn = 10000 + 66;

int r[maxn];

int n, f;

bool Calc (double val)
{
    int i, cnt = 0;
    for (i = 0; i < n; i++)
    {
        double sum = PI * r[i] * r[i];

        while (sum > val + EPS)
        {
            if (cnt == f + 1)
                return true;

            sum -= val;
            cnt++;
        }

        if (cnt == f + 1)
            return true;
    }

return false;
}


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

    int t;
    cin >> t;

    while (t--)
    {

        cin >> n >> f;

        int i;
        double temp = 0;
        for (i = 0; i < n; i++)
        {
            cin >> r[i];
            temp += PI * r[i] * r[i];
        }


        double low = 0, high = temp, mid;

        while (low + EPS <= high)
        {
            mid = low + (high - low) / 2;

            if (Calc (mid))
                low = mid;

            else
                high = mid;
        }

        cout << fixed << setprecision (4) << low << 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 double EPS = 1e-6;

const double PI = 3.14159265359;

const int maxn = 10000 + 66;

int r[maxn];

int n, f;

bool Calc (double val)

{

int i, cnt = 0;

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

{

double sum = PI * r[i] * r[i];

while (sum > val + EPS)

{

if (cnt == f + 1)

return true;

sum -= val;

cnt++;

}

if (cnt == f + 1)

return true;

}

return false;

}

int main()

{

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

int t;

cin >> t;

while (t--)

{

cin >> n >> f;

int i;

double temp = 0;

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

{

cin >> r[i];

temp += PI * r[i] * r[i];

}

double low = 0, high = temp, mid;

while (low + EPS <= high)

{

mid = low + (high - low) / 2;

if (Calc (mid))

low = mid;

else

high = mid;

}

cout << fixed << setprecision (4) << low << endl;

}

return 0;

}

poj3090

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

15 9月 2015

Visible Lattice Points

A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 ≤ x, y ≤ 5 with lines from the origin to the visible points. Write a program which, given a value for the size, N, computes the number of visible points (x, y) with 0 ≤ x, y ≤ N.

Input

The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.

Each dataset consists of a single line of input containing a single integer N (1 ≤ N ≤ 1000), which is the size.

Output

For each dataset, there is to be one line of output consisting of: the dataset number starting at 1, a single space, the size, a single space and the number of visible points for that size.

Sample Input

231

Sample Output

1 2 5
2 4 13
3 5 21
4 231 32549

Source

Greater New York 2006

题目类型：法雷级数

算法分析：所有可见的点的坐标(x, y)满足gcd (x, y) = 1，本题的坐标关系恰好可以使用法雷级数来表示，由于坐标位置存在顺序，所以总的个数等于2倍的F(n)再减去多算的对角线上的一个坐标

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

long long euler[maxn];

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

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

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

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

    GetEuler ();

    for (long long i = 1; i < maxn; i++)
        euler[i] += euler[i-1];

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

    while (t--)
    {
        long long val;
        cin >> val;
        cout << flag++ << " " << val << " " << euler[val] * 2 + 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>

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

long long euler[maxn];

void GetEuler ()

{

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

euler[i] = i;

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

euler[i] >>= 1;

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

{

if (euler[i] == i)

{

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

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

}

int main()

{

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

GetEuler ();

for (long long i = 1; i < maxn; i++)

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

long long t, flag = 1;

cin >> t;

while (t--)

{

long long val;

cin >> val;

cout << flag++ << " " << val << " " << euler[val] * 2 + 1<< endl;

}

return 0;

}

poj3061

maksyuki 发表于 oj 分类，标签: 其他-追逐法

15 9月 2015

Subsequence

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Sample Output

Source

Southeastern Europe 2006

题目类型：追逐法

算法分析：维护两个指针p1和p2，如果sum < s，则p2++；反之则更新最小长度minval并减去ans[p1]，p1++，接着循环判断

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

int ans[maxn];

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

    int t;
    cin >> t;

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

        int i;
        for (i = 1; i <= n; i++)
            cin >> ans[i];

        int p1 = 1, p2 = 1, minval = INF, sum = 0;

        while (1)
        {
            while (p2 <= n && sum < s)
            {
                sum += ans[p2++];
            }

            if (sum < s)
                break;

            minval = min (minval, p2 - p1);
            sum -= ans[p1++];
        }

        if (minval == INF)
            cout << "0" << endl;

        else
            cout << minval << 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>

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

int ans[maxn];

int main()

{

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

int t;

cin >> t;

while (t--)

{

int n, s;

cin >> n >> s;

int i;

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

cin >> ans[i];

int p1 = 1, p2 = 1, minval = INF, sum = 0;

while (1)

{

while (p2 <= n && sum < s)

{

sum += ans[p2++];

}

if (sum < s)

break;

minval = min (minval, p2 - p1);

sum -= ans[p1++];

}

if (minval == INF)

cout << "0" << endl;

else

cout << minval << endl;

}

return 0;

}

poj2992

maksyuki 发表于 oj 分类，标签: 组合数学-计数

15 9月 2015

Divisors

Your task in this problem is to determine the number of divisors of C_n^k. Just for fun -- or do you need any special reason for such a useful computation?

Input

The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.

Output

For each instance, output a line containing exactly one integer -- the number of distinct divisors of C_n^k. For the input instances, this number does not exceed 2⁶³ - 1.

Sample Input

5 1

6 3

10 4

Sample Output

Source

CTU Open 2005

题目类型：阶乘素因子分解

算法分析：将440以内的阶乘的素因子求出来，使用f[i][j]表示阶乘i的素因子j的个数有多少个，然后对于每个n和k，计算f[n][i] - f[n-k][i] - f[k][i]表示组合(n,k)中素因子为i的指数个数，然后直接累乘起来

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

bool prime[maxn];
int primelist[maxn], num;
int f[maxn][maxn];


void GetPrime ()
{
    memset (prime, true, sizeof (prime));
    num = 0;

    int i;
    for (i = 2; i <= maxn; i++)
    {
        if (prime[i])
            primelist[num++] = i;

        int j;
        for (j = 0; j < num; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
}

int Solve (int val, int fa)
{
    int sum = 0, temp = fa;

    while (val / fa)
    {
        sum += val / fa;
        fa *= temp;
    }

return sum;
}

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

    GetPrime ();

    for (int i = 1; i <= 440; i++)
    {
        for (int j = 0; j < num; j++)
            f[i][j] = Solve (i, primelist[j]);
    }

    long long n, k;
    while (scanf ("%d%d", &n, &k) != EOF)
    {
        long long ans = 1;

        for (int i = 0; i < num && primelist[i] <= n; i++)
            ans *= (f[n][i] - f[n-k][i] - f[k][i] + 1);

        printf ("%lld\n", ans);
    }

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

bool prime[maxn];

int primelist[maxn], num;

int f[maxn][maxn];

void GetPrime ()

{

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

num = 0;

int i;

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

{

if (prime[i])

primelist[num++] = i;

int j;

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

{

if (i * primelist[j] > maxn)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

int Solve (int val, int fa)

{

int sum = 0, temp = fa;

while (val / fa)

{

sum += val / fa;

fa *= temp;

}

return sum;

}

int main()

{

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

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

GetPrime ();

for (int i = 1; i <= 440; i++)

{

for (int j = 0; j < num; j++)

f[i][j] = Solve (i, primelist[j]);

}

long long n, k;

while (scanf ("%d%d", &n, &k) != EOF)

{

long long ans = 1;

for (int i = 0; i < num && primelist[i] <= n; i++)

ans *= (f[n][i] - f[n-k][i] - f[k][i] + 1);

printf ("%lld\n", ans);

}

return 0;

}

poj2955

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

15 9月 2015

Brackets

We give the following inductive definition of a “regular brackets” sequence:

the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a₁a₂ … a_n, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest msuch that for indices i₁, i₂, …, i_m where 1 ≤ i₁ < i₂ < … < i_m ≤ n, a_i₁a_i₂ … a_i_m is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((()))

()()()

([]])

)[)(

([][][)

end

Sample Output

Source

Stanford Local 2004

题目类型：区间DP

算法分析：使用数组dp[i][j]表示下标从ai~aj中匹配的括号的个数，然后对于每一个ak(i <= k <= j)，如果ai和ak是匹配的，则dp[i][j] = max (dp[i][j], dp[i+1][k-1] + dp[k+1][j] + 2)

否则dp[i][j] = max (dp[i][j], dp[i+1][j])，初始时dp[i][i] = 0，最后输出dp[0][len-1]，其中len表示字符串的长度

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

char ans[maxn];
int dp[maxn][maxn];

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

    while (cin >> ans)
    {
        if (!strcmp (ans, "end"))
            break;

        int len = strlen (ans);
        memset (dp, 0, sizeof (dp));

        for (int i = 2; i <= len; i++)
        {
            for (int j = 0; j + i - 1 < len; j++)
            {
                int temp = j + i - 1;
                for (int k = j; k <= temp; k++)
                {
                    if ((ans[j] == '(' && ans[k] == ')') || (ans[j] == '[' && ans[k] == ']'))
                        dp[j][temp] = max (dp[j][temp], dp[j+1][k-1] + dp[k+1][temp] + 2);

                    else
                        dp[j][temp] = max (dp[j][temp], dp[j+1][temp]);
                }
            }
        }


        cout << dp[0][len-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>

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

char ans[maxn];

int dp[maxn][maxn];

int main()

{

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

while (cin >> ans)

{

if (!strcmp (ans, "end"))

break;

int len = strlen (ans);

memset (dp, 0, sizeof (dp));

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

{

for (int j = 0; j + i - 1 < len; j++)

{

int temp = j + i - 1;

for (int k = j; k <= temp; k++)

{

if ((ans[j] == '(' && ans[k] == ')') || (ans[j] == '[' && ans[k] == ']'))

dp[j][temp] = max (dp[j][temp], dp[j+1][k-1] + dp[k+1][temp] + 2);

else

dp[j][temp] = max (dp[j][temp], dp[j+1][temp]);

}

cout << dp[0][len-1] << endl;

}

return 0;

}

1 2 3 4 5 下一页最后一页

超客的水墨烟雨

poj3646

poj3641

poj3468

poj3320

poj3268

poj3264

poj3259

poj3250

poj3243

poj3233

poj3126

poj3122

poj3090

poj3061

poj2992

poj2955

分类目录

标签云

书签

近期评论

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