hdu1394

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

18 9月 2015

Minimum Inversion Number

Problem Description

The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.

For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:

a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)

You are asked to write a program to find the minimum inversion number out of the above sequences.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.

Output

For each case, output the minimum inversion number on a single line.

Sample Input

1 3 6 9 0 8 5 7 4 2

Sample Output

Author

CHEN, Gaoli

Source

ZOJ Monthly, January 2003

题目类型：线段树

算法分析：先求出初始序列的逆序对数，然后对于后面的序列可以通过递推得到，这是因为每次都是将第一个数取出来放到最后，则可以知道取出这个数会使总的逆序对数损失aa[i]个，而放到最后会使总的逆序对数增加n - aa[i] - 1个

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

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

LL sum[maxn<<2];

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

void UpDate (int rt, int l, int r, int v)
{
    if (l == r)
    {
        sum[rt]++;
        return ;
    }

    int m = (l + r) >> 1;
    if (v <= m)
        UpDate (lson, v);

    else
        UpDate (rson, v);

    PushUp (rt);
}

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

    int m = (l + r) >> 1;
    LL res = 0;
    if (L <= m)
        res += Query (lson, L, R);

    if (m < R)
        res += Query (rson, L, R);

    return res;
}

int aa[maxn];

int main()
{
//    CPPFF;
    int n;
    while (cin >> n)
    {
        LL res = 0, minval = INF;
        memset (sum, 0, sizeof (sum));
        for (int i = 1; i <= n; i++)
        {
            cin >> aa[i];
            res += Query (1, 0, n - 1, aa[i] + 1, n - 1);
            UpDate (1, 0, n - 1, aa[i]);
        }
        minval = min (minval, res);

        for (int i = 1; i <= n; i++)
        {
            res += n - aa[i] - aa[i] - 1;
            minval = min (minval, res);
        }
        cout << minval << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e4 + 66;

#define lson rt << 1, l, m

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

LL sum[maxn<<2];

void PushUp (int rt)

{

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

}

void UpDate (int rt, int l, int r, int v)

{

if (l == r)

{

sum[rt]++;

return ;

}

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

if (v <= m)

UpDate (lson, v);

else

UpDate (rson, v);

PushUp (rt);

}

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

{

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

return sum[rt];

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

LL res = 0;

if (L <= m)

res += Query (lson, L, R);

if (m < R)

res += Query (rson, L, R);

return res;

}

int aa[maxn];

int main()

{

// CPPFF;

int n;

while (cin >> n)

{

LL res = 0, minval = INF;

memset (sum, 0, sizeof (sum));

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

{

cin >> aa[i];

res += Query (1, 0, n - 1, aa[i] + 1, n - 1);

UpDate (1, 0, n - 1, aa[i]);

}

minval = min (minval, res);

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

{

res += n - aa[i] - aa[i] - 1;

minval = min (minval, res);

}

cout << minval << endl;

}

return 0;

}

hdu1512

maksyuki 发表于 oj 分类，标签: 数据结构-可并堆(斜堆), 数据结构-并查集

17 9月 2015

Monkey King

Problem Description

Once in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can't avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted. Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2). And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.

Input

There are several test cases, and each case consists of two parts. First part: The first line contains an integer N(N<=100,000), which indicates the number of monkeys. And then N lines follows. There is one number on each line, indicating the strongness value of ith monkey(<=32768). Second part: The first line contains an integer M(M<=100,000), which indicates there are M conflicts happened. And then M lines follows, each line of which contains two integers x and y, indicating that there is a conflict between the Xth monkey and Yth.

Output

For each of the conflict, output -1 if the two monkeys know each other, otherwise output the strongness value of the strongest monkey in all friends of them after the duel.

Sample Input

5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5

Sample Output

-1

Author

JIANG, Yanyan

Source

ZOJ 3rd Anniversary Contest

题目类型：并查集+可并堆(斜堆)

算法分析：先将每个节点看成是一个堆，然后使用并查集来查询当前输入的两个节点的父节点，如果两个节点的父节点相同，则表明两个猴子在一个群体中，直接输出-1，否则使用斜堆将每个堆的堆顶元素的值更新(先删除堆顶元素，然后再插入一个值为原来堆顶元素一半的元素)。最后将两个堆合并成一个堆并返回堆顶元素即可

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

struct node
{
    int key, lson, rson;
};

node tr[maxn];
int par[maxn];

void Init ()
{
    memset (tr, 0, sizeof (tr));
    for (int i = 0; i < maxn; i++)
        par[i] = i;
}

int Merge (int a, int b)
{
    if (!a) return b;
    if (!b) return a;

    if (tr[a].key < tr[b].key) swap (a, b);

    tr[a].rson = Merge (tr[a].rson, b);
    par[tr[a].rson] = a;
    swap (tr[a].rson, tr[a].lson);
    return a;
}

int Del (int a)
{
    int lch = tr[a].lson, rch = tr[a].rson;
    par[lch] = lch, par[rch] = rch;
    tr[a].lson = tr[a].rson = 0;
    return Merge (lch, rch);
}

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

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

int main()
{
//    CPPFF;
    int n;
    while (cin >> n)
    {
        Init ();
        for (int i = 1; i <= n; i++)
            cin >> tr[i].key;

        int q;
        cin >>q;
        for (int i = 1; i <= q; i++)
        {
            int u, v;
            cin >> u >> v;
            u = UnFind (u);
            v = UnFind (v);
            if(u == v)
                cout << "-1" << endl;

            else
            {
                int ta = Del (u);
                int tb = Del (v);
                tr[u].key /= 2;
                tr[v].key /= 2;
                ta = Merge (u, ta);
                tb = Merge (v, tb);
                int tt = Merge (ta, tb);
                cout << tr[tt].key << 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

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 66;

struct node

{

int key, lson, rson;

};

node tr[maxn];

int par[maxn];

void Init ()

{

memset (tr, 0, sizeof (tr));

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

par[i] = i;

}

int Merge (int a, int b)

{

if (!a) return b;

if (!b) return a;

if (tr[a].key < tr[b].key) swap (a, b);

tr[a].rson = Merge (tr[a].rson, b);

par[tr[a].rson] = a;

swap (tr[a].rson, tr[a].lson);

return a;

}

int Del (int a)

{

int lch = tr[a].lson, rch = tr[a].rson;

par[lch] = lch, par[rch] = rch;

tr[a].lson = tr[a].rson = 0;

return Merge (lch, rch);

}

int UnFind (int val)

{

if (par[val] == val)

return val;

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

}

int main()

{

// CPPFF;

int n;

while (cin >> n)

{

Init ();

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

cin >> tr[i].key;

int q;

cin >>q;

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

{

int u, v;

cin >> u >> v;

u = UnFind (u);

v = UnFind (v);

if(u == v)

cout << "-1" << endl;

else

{

int ta = Del (u);

int tb = Del (v);

tr[u].key /= 2;

tr[v].key /= 2;

ta = Merge (u, ta);

tb = Merge (v, tb);

int tt = Merge (ta, tb);

cout << tr[tt].key << endl;

}

return 0;

}

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;

}

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

超客的水墨烟雨

hdu1394

Minimum Inversion Number

hdu1512

Monkey King

poj3646

poj3641

poj3468

poj3320

poj3268

poj3264

poj3259

poj3250

poj3243

poj3233

poj3126

poj3122

poj3090

poj3061

分类目录

标签云

书签

近期评论

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