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

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;

}

poj2891

maksyuki 发表于 oj 分类，标签: 数论-线性同余方程(组)

15 9月 2015

Strange Way to Express Integers

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

Choose k different positive integers a₁, a₂, …, a_k. For some non-negative m, divide it by every a_i (1 ≤ i ≤ k) to find the remainder r_i. If a₁, a₂, …, a_k are properly chosen, m can be determined, then the pairs (a_i, r_i) can be used to express m.

“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”

Since Elina is new to programming, this problem is too difficult for her. Can you help her?

Input

The input contains multiple test cases. Each test cases consists of some lines.

Line 1: Contains the integer k.
Lines 2 ~ k + 1: Each contains a pair of integers a_i, r_i (1 ≤ i ≤ k).

Output

Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one. If there are no possible values, output -1.

Sample Input

8 7

11 9

Sample Output

Hint

All integers in the input and the output are non-negative and can be represented by 64-bit integral types.

Source

POJ Monthly--2006.07.30, Static

题目类型：线性同余方程组

算法分析：直接使用线性同余方程组求解的方法计算即可

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

long long ans[maxn], r[maxn];

long long n;


long long gcd_ex (long long a, long long b, long long &x, long long &y)
{
    if (b == 0) { x = 1; y = 0; return a; }
    long long d = gcd_ex (b, a % b, y, x);
    y = y - a / b * x;
    return d;
}



long long mod_equ_set ()
{
    long long M = ans[0], R = r[0], x, y, d;

    for (int i = 1; i < n; i++)
    {
        d = gcd_ex (M, ans[i], x, y);

        if ((r[i] - R) % d)
        return -1;

        x = (r[i] - R) / d * x % (ans[i] / d);
        R += x * M;
        M = M / d * ans[i];
        R %= M;
    }

return R > 0 ? R : R + M;
}

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

    while (scanf ("%lld", &n) != EOF)
    {
        int i;
        for (i = 0; i < n; i++)
            scanf ("%lld%lld", &ans[i], &r[i]);

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

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

long long ans[maxn], r[maxn];

long long n;

long long gcd_ex (long long a, long long b, long long &x, long long &y)

{

if (b == 0) { x = 1; y = 0; return a; }

long long d = gcd_ex (b, a % b, y, x);

y = y - a / b * x;

return d;

}

long long mod_equ_set ()

{

long long M = ans[0], R = r[0], x, y, d;

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

{

d = gcd_ex (M, ans[i], x, y);

if ((r[i] - R) % d)

return -1;

x = (r[i] - R) / d * x % (ans[i] / d);

R += x * M;

M = M / d * ans[i];

R %= M;

}

return R > 0 ? R : R + M;

}

int main()

{

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

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

{

int i;

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

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

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

}

return 0;

}

poj2823

maksyuki 发表于 oj 分类，标签: 数据结构-队列\双端\单调\优先

15 9月 2015

Sliding Window

An array of size n ≤ 10⁶ is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position	Minimum value	Maximum value
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Sample Input

8 3

1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3

3 3 5 5 6 7

Source

POJ Monthly--2006.04.28, Ikki

题目类型：单调队列

算法分析：这是一道使用单调队列解决的经典问题。维护一个严格单调增和一个严格单调减队列，重点是判断队头元素何时出队列，方法是向队列中添加元素的同时将元素的下标也添加进去，之后直接比较下标之间的关系即可

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

struct Node
{
    int val, id;
};

Node ans[maxn], out_inq[maxn], out_deq[maxn];
int inq_len, deq_len;

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

    int n, k;

    while (scanf ("%d%d", &n, &k) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf ("%d", &ans[i].val);
            ans[i].id = i;
        }

        deque <Node> inq, deq;

        for (int i = 1; i <= k; i++)
        {
            while (!inq.empty () && inq.back ().val <= ans[i].val)
                inq.pop_back ();

            inq.push_back (ans[i]);

            while (!deq.empty () && deq.back ().val >= ans[i].val)
                deq.pop_back ();

            deq.push_back (ans[i]);
        }

        inq_len = deq_len = 0;
        out_inq[inq_len++] = inq.front ();
        out_deq[deq_len++] = deq.front ();

        for (int i = k + 1; i <= n; i++)
        {
            if (inq.front ().id + k == ans[i].id)
                inq.pop_front ();

            while (!inq.empty () && inq.back ().val < ans[i].val)
                inq.pop_back ();

            inq.push_back (ans[i]);
            out_inq[inq_len++] = inq.front ();

            if (deq.front ().id + k == ans[i].id)
                deq.pop_front ();

            while (!deq.empty () && deq.back ().val >= ans[i].val)
                deq.pop_back ();

            deq.push_back (ans[i]);
            out_deq[deq_len++] = deq.front ();
        }

        for (int i = 0; i < deq_len; i++)
        {
            if (i == 0)
                printf ("%d", out_deq[i].val);

            else
                printf (" %d", out_deq[i].val);
        }
        puts ("");


        for (int i = 0; i < inq_len; i++)
        {
            if (i == 0)
                printf ("%d", out_inq[i].val);

            else
                printf (" %d", out_inq[i].val);
        }

        puts ("");

    }

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>

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const int MOD = 32767;

const int maxn = 1000000 + 66;

struct Node

{

int val, id;

};

Node ans[maxn], out_inq[maxn], out_deq[maxn];

int inq_len, deq_len;

int main()

{

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

int n, k;

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

{

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

{

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

ans[i].id = i;

}

deque <Node> inq, deq;

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

{

while (!inq.empty () && inq.back ().val <= ans[i].val)

inq.pop_back ();

inq.push_back (ans[i]);

while (!deq.empty () && deq.back ().val >= ans[i].val)

deq.pop_back ();

deq.push_back (ans[i]);

}

inq_len = deq_len = 0;

out_inq[inq_len++] = inq.front ();

out_deq[deq_len++] = deq.front ();

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

{

if (inq.front ().id + k == ans[i].id)

inq.pop_front ();

while (!inq.empty () && inq.back ().val < ans[i].val)

inq.pop_back ();

inq.push_back (ans[i]);

out_inq[inq_len++] = inq.front ();

if (deq.front ().id + k == ans[i].id)

deq.pop_front ();

while (!deq.empty () && deq.back ().val >= ans[i].val)

deq.pop_back ();

deq.push_back (ans[i]);

out_deq[deq_len++] = deq.front ();

}

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

{

if (i == 0)

printf ("%d", out_deq[i].val);

else

printf (" %d", out_deq[i].val);

}

puts ("");

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

{

if (i == 0)

printf ("%d", out_inq[i].val);

else

printf (" %d", out_inq[i].val);

}

puts ("");

}

return 0;

}

poj2785

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

15 9月 2015

4 Values whose Sum is 0

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2²⁸ ) that belong respectively to A, B, C and D .

Output

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample Input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

Sample Output

Hint

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

Source

Southwestern Europe 2005

题目类型：数字型Hash查找

算法分析：直接使用暴力枚举是一定会TLE的，这里使用的Hash可以将时间复杂度降到O(2*N^2)，将输入的前两列数字枚举和并插入到Hash表中，然后对于输入的后两列数字枚举和并查询和的相反数是否在表中，如果在则累加sum，最后输出sum即可

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

const int maxn = 4000 + 66;


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

Node edge[3999972];

int head[3999972];

int Hash (int val)
{
    return (val + 3899971) % 3999971;
}

int tot;

void add_edge (int val)
{
    int key = Hash (val);

    for (int i = head[key]; i != -1; i = edge[i].next)
    {
        if (edge[i].v == val)
        {
            edge[i].num++;
            return ;
        }
    }

    edge[tot].v = val;
    edge[tot].num = 1;
    edge[tot].next = head[key];
    head[key] = tot++;
}

int Find (int val)
{
    int key = Hash (val);

    for (int i = head[key]; i != -1; i = edge[i].next)
    {
        if (edge[i].v == val)
        {
            return edge[i].num;
        }
    }

return 0;
}

int a[maxn],b[maxn],c[maxn],d[maxn];

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

    int n, i, j;

    while (scanf("%d", &n) != EOF)
    {
        tot = 0;
        memset (head,-1,sizeof(head));

        for (i = 1; i <= n; i++)
            scanf ("%d%d%d%d",&a[i], &b[i], &c[i], &d[i]);

        for (i = 1; i <= n; i++)
        {
            for(j = 1; j <= n; j++)
            {
                add_edge (a[i] + b[j]);
            }
        }

        long long ans = 0;
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= n; j++)
            {
                ans += Find (-c[i] - d[j]);
            }
        }

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

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

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

const int maxn = 4000 + 66;

struct Node

{

int v, next, num;

};

Node edge[3999972];

int head[3999972];

int Hash (int val)

{

return (val + 3899971) % 3999971;

}

int tot;

void add_edge (int val)

{

int key = Hash (val);

for (int i = head[key]; i != -1; i = edge[i].next)

{

if (edge[i].v == val)

{

edge[i].num++;

return ;

}

edge[tot].v = val;

edge[tot].num = 1;

edge[tot].next = head[key];

head[key] = tot++;

}

int Find (int val)

{

int key = Hash (val);

for (int i = head[key]; i != -1; i = edge[i].next)

{

if (edge[i].v == val)

{

return edge[i].num;

}

return 0;

}

int a[maxn],b[maxn],c[maxn],d[maxn];

int main ()

{

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

int n, i, j;

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

{

tot = 0;

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

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

scanf ("%d%d%d%d",&a[i], &b[i], &c[i], &d[i]);

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

{

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

{

add_edge (a[i] + b[j]);

}

long long ans = 0;

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

{

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

{

ans += Find (-c[i] - d[j]);

}

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

}

return 0;

}

poj2777

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

15 9月 2015

Count Color

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem. There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, ... L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:

1. "C A B C" Color the board from segment A to segment B with color C.
2. "P A B" Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, ... color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Output

Ouput results of the output operation in order, each line contains a number.

Sample Input

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

Sample Output

Source

POJ Monthly--2006.03.26,dodo

题目类型：线段树(区间染色)

算法分析：这是一个不覆盖的区间染色问题，需要使用Lazy-Tag标记，使用lazy数组表示当前区间是否已经完全被覆盖。由于颜色数量比较小，所以可以使用位运算来压缩空间

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

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

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

int sum[maxn<<2];
bool lazy[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<<1|1] = lazy[rt];
        sum[rt<<1] = sum[rt<<1|1] = sum[rt];
        lazy[rt] = false;
	}
}

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

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

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

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

	PushUp (rt);
}

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

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

    if (L <= m)
		res |= Query (lson, L, R);

	if (R > m)
		res |= Query (rson, L, R);

return res;
}


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

	int n, vv, q;
	while (scanf ("%d%d%d",&n, &vv, &q) != EOF)
	{
        memset (lazy, false, sizeof (lazy));
		memset (sum, 0, sizeof (sum));
		sum[1] = 1;
		lazy[1] = true;

		char cmd[6];
		for (int i = 1; i <= q; i++)
		{
			scanf ("%s", cmd);
            if (!strcmp (cmd, "P"))
			{
                int a, b;
                scanf ("%d%d", &a, &b);

                if (a > b)
					swap (a, b);

                long long tt = Query (1, 1, n, a, b);
                int cnt = 0;
                for (int i = 0; i < vv; i++)
					if (tt & (1 << i))
						cnt++;

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

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

				if (a > b)
					swap (a, b);

				UpDate (1, 1, n, a, b, c);
			}
		}
	}
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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

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

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100000 + 66;

int sum[maxn<<2];

bool lazy[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<<1|1] = lazy[rt];

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

lazy[rt] = false;

}

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

{

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

{

sum[rt] = 1 << (v - 1);

lazy[rt] = true;

return ;

}

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

PushDown(rt, l, m, r);

if (L <= m)

UpDate (lson, L, R, v);

if (R > m)

UpDate (rson, L, R, v);

PushUp (rt);

}

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

{

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

{

return sum[rt];

}

long long res = 0;

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

PushDown(rt, l, m, r);

if (L <= m)

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

if (R > m)

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

return res;

}

int main()

{

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

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

int n, vv, q;

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

{

memset (lazy, false, sizeof (lazy));

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

sum[1] = 1;

lazy[1] = true;

char cmd[6];

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

{

scanf ("%s", cmd);

if (!strcmp (cmd, "P"))

{

int a, b;

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

if (a > b)

swap (a, b);

long long tt = Query (1, 1, n, a, b);

int cnt = 0;

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

if (tt & (1 << i))

cnt++;

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

}

else

{

int a, b, c;

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

if (a > b)

swap (a, b);

UpDate (1, 1, n, a, b, c);

}

return 0;

}

poj2752

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

15 9月 2015

Seek the Name, Seek the Fame

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:

Step1. Connect the father's name and the mother's name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).

Example: Father='ala', Mother='la', we have S = 'ala'+'la' = 'alala'. Potential prefix-suffix strings of S are {'a', 'ala', 'alala'}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)

Input

The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.

Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.

Output

For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby's name.

Sample Input

ababcababababcabab

aaaaa

Sample Output

2 4 9 18

1 2 3 4 5

Source

POJ Monthly--2006.01.22,Zeyuan Zhu

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

算法分析：直接将读入字符串的Next数组求出，然后从后向前将不是0的Next[len]的值记录下来，然后对所有的记录排序并输出

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int INF = 0x7FFFFFFF;
const int maxn = 400000 + 66;

int Next[maxn], len;
int output[maxn], out_len;

string s;

void Build ()
{
    Next[0] = -1, Next[1] = 0;
    int k = 0, i;

    for (i = 2; i <= len; i++)
    {
        while (k >= 0 && s[i-1] != s[k])
            k = Next[k];

        Next[i] = ++k;
    }
}

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

    while (cin >> s)
    {
        len = s.length ();
        out_len = 0;

        Build ();

        while (Next[len] != -1)
        {
            if (Next[len] != 0)
                output[out_len++] = Next[len];

            len = Next[len];
        }

        sort (output, output + out_len);

        int i;
        for (i = 0; i < out_len; i++)
            cout << output[i] << " ";

        cout << s.length () << endl;
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 400000 + 66;

int Next[maxn], len;

int output[maxn], out_len;

string s;

void Build ()

{

Next[0] = -1, Next[1] = 0;

int k = 0, i;

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

{

while (k >= 0 && s[i-1] != s[k])

k = Next[k];

Next[i] = ++k;

}

int main()

{

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

while (cin >> s)

{

len = s.length ();

out_len = 0;

Build ();

while (Next[len] != -1)

{

if (Next[len] != 0)

output[out_len++] = Next[len];

len = Next[len];

}

sort (output, output + out_len);

int i;

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

cout << output[i] << " ";

cout << s.length () << endl;

}

return 0;

}

poj2709

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

15 9月 2015

Painter

The local toy store sells small fingerpainting kits with between three and twelve 50ml bottles of paint, each a different color. The paints are bright and fun to work with, and have the useful property that if you mix X ml each of any three different colors, you get X ml of gray. (The paints are thick and "airy", almost like cake frosting, and when you mix them together the volume doesn't increase, the paint just gets more dense.) None of the individual colors are gray; the only way to get gray is by mixing exactly three distinct colors, but it doesn't matter which three. Your friend Emily is an elementary school teacher and every Friday she does a fingerpainting project with her class. Given the number of different colors needed, the amount of each color, and the amount of gray, your job is to calculate the number of kits needed for her class.

Input

The input consists of one or more test cases, followed by a line containing only zero that signals the end of the input. Each test case consists of a single line of five or more integers, which are separated by a space. The first integer N is the number of different colors (3 <= N <= 12). Following that are N different nonnegative integers, each at most 1,000, that specify the amount of each color needed. Last is a nonnegative integer G <= 1,000 that specifies the amount of gray needed. All quantities are in ml.

Output

For each test case, output the smallest number of fingerpainting kits sufficient to provide the required amounts of all the colors and gray. Note that all grays are considered equal, so in order to find the minimum number of kits for a test case you may need to make grays using different combinations of three distinct colors.

Sample Input

3 40 95 21 0
7 25 60 400 250 0 60 0 500
4 90 95 75 95 10
4 90 95 75 95 11
5 0 0 0 0 0 333
0

Sample Output

Source

Mid-Central USA 2005

题目类型：贪心

算法分析：首先将读入的颜料按照体积的大小递增排序，然后得到初始的颜料套装数，并计算出使用初始套装后，每种颜料还剩的体积。接着每次取体积最大的三种颜料1毫升配成灰色染料，直到灰色染料已经配完或者是再使用一个颜料套装。注意这里只能每次枚举1毫升，否则会WA

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


int ans[maxn], g, temp[maxn];

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

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

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

        cin >> g;

        sort (ans, ans + n);

        int sum;
        if (ans[n-1] % 50 == 0)
            sum = ans[n-1] / 50;

        else
            sum = ans[n-1] / 50 + 1;

        for (int i = 0; i < n; i++)
            temp[i] = sum * 50 - ans[i];

        while (g > 0)
        {
            sort (temp, temp + n, greater <int> () );
            if (temp[2] <= 0)
            {
                sum++;
                for (int i = 0; i < n; i++)
                    temp[i] += 50;
            }

            temp[0]--, temp[1]--, temp[2]--;
            g--;
        }

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

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 600 + 66;

int ans[maxn], g, temp[maxn];

int main()

{

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

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

int n;

while (cin >> n)

{

if (n == 0)

break;

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

cin >> ans[i];

cin >> g;

sort (ans, ans + n);

int sum;

if (ans[n-1] % 50 == 0)

sum = ans[n-1] / 50;

else

sum = ans[n-1] / 50 + 1;

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

temp[i] = sum * 50 - ans[i];

while (g > 0)

{

sort (temp, temp + n, greater <int> () );

if (temp[2] <= 0)

{

sum++;

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

temp[i] += 50;

}

temp[0]--, temp[1]--, temp[2]--;

g--;

}

cout << sum << endl;

}

return 0;

}

poj2689

maksyuki 发表于 oj 分类，标签: 数论-筛法

15 9月 2015

Prime Distance

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality 阅读全文 »

poj2585

maksyuki 发表于 oj 分类，标签: 图论-拓扑排序

15 9月 2015

Window Pains

Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux's windows would be represented by the following 2 x 2 windows:

1	1	.	.
1	1	.	.
.	.	.	.
.	.	.	.

.	2	2	.
.	2	2	.
.	.	.	.
.	.	.	.

.	.	3	3
.	.	3	3
.	.	.	.
.	.	.	.

.	.	.	.
4	4	.	.
4	4	.	.
.	.	.	.

.	.	.	.
.	5	5	.
.	5	5	.
.	.	.	.

.	.	.	.
.	.	6	6
.	.	6	6
.	.	.	.

.	.	.	.
.	.	.	.
7	7	.	.
7	7	.	.

.	.	.	.
.	.	.	.
.	8	8	.
.	8	8	.

.	.	.	.
.	.	.	.
.	.	9	9
.	.	9	9

When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window 1and then window 2were brought to the foreground, the resulting representation would be:

1	2	2	?
1	2	2	?
?	?	?	?
?	?	?	?

If window 4 were then brought to the foreground:

1	2	2	?
4	4	2	?
4	4	?	?
?	?	?	?

. . . and so on . . .
Unfortunately, Boudreaux's computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:

Start line - A single line:
START
Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux's screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers on each line will be delimited by a single space.
End line - A single line:
END

After the last data set, there will be a single line:
ENDOFINPUT

Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.

Output

For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux's screen, the output will be a single line with the statement:

THESE WINDOWS ARE CLEAN

Otherwise, the output will be a single line with the statement:
THESE WINDOWS ARE BROKEN

Sample Input

START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT

Sample Output

THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN

Source

South Central USA 2003

题目类型：拓扑排序

算法分析：由于输入中的窗口是最靠外面的，且题目中说调动了所有的窗口。这就意味着最外面的窗口中的数字覆盖了其他在该位置处的数字，使用这种覆盖关系构造有向图。首先构造9个窗口，然后对于输入的窗口中的每一个位置处的数字a遍历所有的9个窗口在该位置的取值vi，如果在该处存在值vi且不与a相等，则构造一条有向边，起点为a，终点为vi。最后对于构造好的有向图使用拓扑排序即可

#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int maxn = 16;

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

int ans[maxn][maxn];
int num[maxn][maxn][maxn];
int indegree[maxn];

bool is_valid;

vector <int> vec[maxn];

void Build ()
{
	int i;
	for (i = 0; i < 9; i++)
	{
		int val_x = i / 3, val_y = i % 3, j; // important!!!!!!
		
		for (j = 0; j < 4; j++)
			num[i][val_x+dx[j]][val_y+dy[j]] = i + 1;
	}
}

void Solve ()
{
	int i, j, k;
	for (i = 0; i < 4; i++)
		for (j = 0; j < 4; j++)
			for (k = 0; k < 9; k++)
			{
				if (num[k][i][j] && ans[i][j] != num[k][i][j])
				{
					indegree[num[k][i][j]]++;
					vec[ans[i][j]].push_back (num[k][i][j]);
				}
			}
}

void Topo ()
{
	is_valid = true;
	queue <int> q;

	int i;
	for (i = 1; i <= 9; i++)
		if (!indegree[i])
			q.push (i);

	while (!q.empty ())
	{
		int temp = q.front ();
		q.pop ();

		for (i = 0; i < vec[temp].size (); i++)
		{
			indegree[vec[temp][i]]--;
			
			if (!indegree[vec[temp][i]])
				q.push (vec[temp][i]);
		}
	}

	for (i = 1; i <= 9; i++)
		if (indegree[i])
			break;

	if (i <= 9)
		is_valid = false;

}


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

	char input[36];
	
	memset (num, 0, sizeof (num));
	Build ();

	while (cin >> input)
	{
		if (!strcmp (input, "ENDOFINPUT"))
			break;

		int i;
		for (i = 0; i < 4; i++)
		{
			int j;
			for (j = 0; j < 4; j++)
				cin >> ans[i][j];
		}

		cin >> input;
		
		for (i = 0; i < maxn; i++)
			vec[i].clear ();

		memset (indegree, 0, sizeof (indegree));

		Solve ();
		
		Topo ();

		if (is_valid)
			cout << "THESE WINDOWS ARE CLEAN" << endl;

		else
			cout << "THESE WINDOWS ARE BROKEN" << 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

#include <iostream>

#include <fstream>

#include <cstring>

#include <queue>

#include <vector>

using namespace std;

const int maxn = 16;

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

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

int ans[maxn][maxn];

int num[maxn][maxn][maxn];

int indegree[maxn];

bool is_valid;

vector <int> vec[maxn];

void Build ()

{

int i;

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

{

int val_x = i / 3, val_y = i % 3, j; // important!!!!!!

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

num[i][val_x+dx[j]][val_y+dy[j]] = i + 1;

}

void Solve ()

{

int i, j, k;

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

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

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

{

if (num[k][i][j] && ans[i][j] != num[k][i][j])

{

indegree[num[k][i][j]]++;

vec[ans[i][j]].push_back (num[k][i][j]);

}

void Topo ()

{

is_valid = true;

queue <int> q;

int i;

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

if (!indegree[i])

q.push (i);

while (!q.empty ())

{

int temp = q.front ();

q.pop ();

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

{

indegree[vec[temp][i]]--;

if (!indegree[vec[temp][i]])

q.push (vec[temp][i]);

}

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

if (indegree[i])

break;

if (i <= 9)

is_valid = false;

}

int main()

{

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

char input[36];

memset (num, 0, sizeof (num));

Build ();

while (cin >> input)

{

if (!strcmp (input, "ENDOFINPUT"))

break;

int i;

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

{

int j;

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

cin >> ans[i][j];

}

cin >> input;

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

vec[i].clear ();

memset (indegree, 0, sizeof (indegree));

Solve ();

Topo ();

if (is_valid)

cout << "THESE WINDOWS ARE CLEAN" << endl;

else

cout << "THESE WINDOWS ARE BROKEN" << endl;

}

return 0;

}

poj2576

maksyuki 发表于 oj 分类，标签: DP-背包

15 9月 2015

Tug of War

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

Input

The first line of input contains n the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 450. There are at most 100 people at the picnic.

Output

Your output will be a single line containing 2 numbers: the total weight of the people on one team, and the total weight of the people on the other team. If these numbers differ, give the lesser first.

Sample Input

100

200

Sample Output

190 200

Source

Waterloo local 2000.09.30

题目类型：二维01背包

算法分析：每一个人都可以看做是一个物品，然后对于每一个物品，有一个重量的限制(总重量的一半)和一个人数的限制(总人数的一半)，可以直接使用二维01背包求解

#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 = 1000000000 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1000 + 66;

int dp[166][466*100];

int ans[maxn];

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

    int n;
    while (cin >> n)
    {
        memset (dp, 0, sizeof (dp));
        int all = 0;

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

        int num = n, w = all / 2;
        if (n % 2 == 0)
            n /= 2;

        else
            n = n / 2 + 1;

        for (int i = 0; i < num; i++)
        {
            for (int u = n; u >= 1; u--)
            {
                for (int v = w; v >= ans[i]; v--)
                    dp[u][v] = max (dp[u][v], dp[u-1][v-ans[i]] + ans[i]);
            }
        }

        int tempa = dp[n][w], tempb = all - dp[n][w];
        if (tempa > tempb)
            swap (tempa, tempb);

        cout << tempa << " " << tempb << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1000000000 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

int dp[166][466*100];

int ans[maxn];

int main()

{

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

int n;

while (cin >> n)

{

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

int all = 0;

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

{

cin >> ans[i];

all += ans[i];

}

int num = n, w = all / 2;

if (n % 2 == 0)

n /= 2;

else

n = n / 2 + 1;

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

{

for (int u = n; u >= 1; u--)

{

for (int v = w; v >= ans[i]; v--)

dp[u][v] = max (dp[u][v], dp[u-1][v-ans[i]] + ans[i]);

}

int tempa = dp[n][w], tempb = all - dp[n][w];

if (tempa > tempb)

swap (tempa, tempb);

cout << tempa << " " << tempb << endl;

}

return 0;

}

poj2570

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

15 9月 2015

Fiber Network

Several startup companies have decided to build a better Internet, called the "FiberNet". They have already installed many nodes that act as routers all around the world. Unfortunately, they started to quarrel about the connecting lines, and ended up with every company laying its own set of cables between some of the nodes. Now, service providers, who want to send data from node A to node B are curious, which company is able to provide the necessary connections. Help the providers by answering their queries.

Input

The input contains several test cases. Each test case starts with the number of nodes of the network n. Input is terminated by n=0. Otherwise, 1<=n<=200. Nodes have the numbers 1, ..., n. Then follows a list of connections. Every connection starts with two numbers A, B. The list of connections is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the unidirectional connection, respectively. For every connection, the two nodes are followed by the companies that have a connection from node A to node B. A company is identified by a lower-case letter. The set of companies having a connection is just a word composed of lower-case letters.
After the list of connections, each test case is completed by a list of queries. Each query consists of two numbers A, B. The list (and with it the test case) is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the query. You may assume that no connection and no query contains identical start and end nodes.

Output

For each query in every test case generate a line containing the identifiers of all the companies, that can route data packages on their own connections from the start node to the end node of the query. If there are no companies, output "-" instead. Output a blank line after each test case.

Sample Input

3
1 2 abc
2 3 ad
1 3 b
3 1 de
0 0
1 3
2 1
3 2
0 0
2
1 2 z
0 0
1 2
2 1
0 0
0

Sample Output

Source

Ulm Local 2001

题目类型：全源最短路思想(Floyd)

算法分析：使用Floyd算法的迭代思想，矩阵ans[i][j]中存放的是节点i到节点j中存在的公司集合(字符串)。使用位运算的相关技巧，用从低到高的26个二进制位表示两点之间存在的公司(1位)的情况。对于每一次迭代，使用ans[i][j] = 集合或运算(ans[i][j], ans[i][k] 集合与运算ans[k][j])。然后对于每个查询直接输出结果即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 666 + 66;

int ans[maxn][maxn];
int n;

void floyd ()
{
    int i, j, k;
    for (k = 1; k <= n; k++)
    {
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                ans[i][j] |= (ans[i][k] & ans[k][j]);
            }
        }
    }
}


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

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

        int i;
        int val_a, val_b;
        char input[36];

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

        while (cin >> val_a >> val_b)
        {
            if (val_a == 0 && val_b == 0)
                break;

            cin >> input;

            int j;
            for (j = 0; input[j]; j++)
                ans[val_a][val_b] |= 1 << (input[j] - 'a');
        }

        floyd ();

        while (cin >> val_a >> val_b)
        {
            if (val_a == 0 && val_b == 0)
                break;

            for (i = 0; i < 26; i++)
            {
                if (ans[val_a][val_b] & (1 << i))
                    cout << (char) (i + 'a');
            }

            if (!ans[val_a][val_b])
                cout << "-" << endl;

            else
                cout << endl;
        }
        cout << endl;
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 666 + 66;

int ans[maxn][maxn];

int n;

void floyd ()

{

int i, j, k;

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

{

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

{

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

{

ans[i][j] |= (ans[i][k] & ans[k][j]);

}

int main()

{

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

while (cin >> n)

{

if (n == 0)

break;

int i;

int val_a, val_b;

char input[36];

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

while (cin >> val_a >> val_b)

{

if (val_a == 0 && val_b == 0)

break;

cin >> input;

int j;

for (j = 0; input[j]; j++)

ans[val_a][val_b] |= 1 << (input[j] - 'a');

}

floyd ();

while (cin >> val_a >> val_b)

{

if (val_a == 0 && val_b == 0)

break;

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

{

if (ans[val_a][val_b] & (1 << i))

cout << (char) (i + 'a');

}

if (!ans[val_a][val_b])

cout << "-" << endl;

else

cout << endl;

}

cout << endl;

}

return 0;

}

poj2559

maksyuki 发表于 oj 分类，标签: 数据结构-队列\双端\单调\优先

15 9月 2015

Largest Rectangle in a Histogram

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles: Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that1<=n<=100000. Then follow n integers h₁,...,h_n, where 0<=h_i<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3

4 1000 1000 1000 1000

Sample Output

4000

Hint

Huge input, scanf is recommended.

Source

Ulm Local 2003

题目类型：单调队列

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

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

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

const int maxn = 100000 + 66;


struct Node
{
    long long h, w;
    Node (long long hh, long long ww) : h (hh), w (ww) {}
    Node () {h = 0, w = 0;}
};

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

    int n;
    while (scanf ("%d", &n) != EOF)
    {
        if (n == 0)
            break;

        deque <Node> deq;

        long long maxval = -INF, cnt;
        int i, input;

        for (i = 0; i < n; i++)
        {
            scanf ("%d", &input);

            cnt = 0;
            while (!deq.empty() && deq.back().h >= input)
            {
                Node temp = deq.back ();
                deq.pop_back();
                if (maxval < temp.h * (temp.w + cnt))
                        maxval = temp.h * (temp.w + cnt);

                cnt += temp.w;
            }

            deq.push_back (Node (input, 1 + cnt));
        }

        cnt = 0;
        while (!deq.empty ())
        {
            Node temp = deq.back ();
            deq.pop_back ();
            if (maxval < temp.h * (temp.w + cnt))
                maxval = temp.h * (temp.w + cnt);

            cnt += temp.w;
        }

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

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000007;

const int maxn = 100000 + 66;

struct Node

{

long long h, w;

Node (long long hh, long long ww) : h (hh), w (ww) {}

Node () {h = 0, w = 0;}

};

int main()

{

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

int n;

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

{

if (n == 0)

break;

deque <Node> deq;

long long maxval = -INF, cnt;

int i, input;

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

{

scanf ("%d", &input);

cnt = 0;

while (!deq.empty() && deq.back().h >= input)

{

Node temp = deq.back ();

deq.pop_back();

if (maxval < temp.h * (temp.w + cnt))

maxval = temp.h * (temp.w + cnt);

cnt += temp.w;

}

deq.push_back (Node (input, 1 + cnt));

}

cnt = 0;

while (!deq.empty ())

{

Node temp = deq.back ();

deq.pop_back ();

if (maxval < temp.h * (temp.w + cnt))

maxval = temp.h * (temp.w + cnt);

cnt += temp.w;

}

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

}

return 0;

}

poj2528

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

15 9月 2015

Mayor's posters

The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:

Every candidate can place exactly one poster on the wall.
All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
The wall is divided into segments and the width of each segment is one byte.
Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections. Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall.

Input

The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l_i and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l_i <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l_i, l_i+1 ,... , ri.

Output

For each input data set print the number of visible posters after all the posters are placed.

The picture below illustrates the case of the sample input.

Sample Input

1 4

2 6

8 10

3 4

7 10

Sample Output

Source

Alberta Collegiate Programming Contest 2003.10.18

题目类型：离散化+线段树(区间染色)

算法分析：这是一道会发生覆盖的区间染色问题，由于输入数据范围比较大，所以需要使用离散化操作。然后使用Lazy-Tag标记，lazy数组表示区间被覆盖到的海报的标号。最后累加整个离散化后的区间中存在的不同的海报的标号的个数即可

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

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

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

struct Node
{
	int x, y;
};

Node a[maxn];
int xx[maxn*3], xxlen, lazy[maxn<<4];
bool have[maxn];
long long res;

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

void UpDate (int rt, int l, int r, int L, int R, int id)
{
    if (L <= l && r <= R)
	{
        lazy[rt] = id;
        return ;
	}

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);
    if (L <= m)
		UpDate (lson, L, R, id);

	if (R > m)
		UpDate (rson, L, R, id);
}

void Query (int rt, int l, int r)
{
   	if (lazy[rt] != -1)
	{
		if (!have[lazy[rt]])
		{
			have[lazy[rt]] = true;
			res++;
		}
		return ;
	}

	if (l == r)
		return ;

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

	Query (lson);
	Query (rson);
}

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

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

	while (t--)
	{
        int n;
        scanf ("%d", &n);

		xxlen= 0;
        for (int i = 1; i<= n; i++)
		{
			scanf ("%d%d", &a[i].x, &a[i].y);
			xx[xxlen++] = a[i].x, xx[xxlen++] = a[i].y;
		}

        sort (xx, xx + xxlen);
        xxlen = unique (xx, xx + xxlen) - xx;

        for (int i = xxlen - 1; i >= 1; i--)
            if (xx[i] != xx[i-1] + 1)
                xx[xxlen++] = xx[i-1] + 1;

		sort (xx, xx  + xxlen);
//		for (int i = 0; i < xxlen;i++)
//			cout << xx[i] << endl;

		fill (lazy, lazy + (maxn<<4), -1);

        for (int i = 1; i <= n; i++)
		{
            int sx = lower_bound (xx, xx + xxlen, a[i].x) - xx;
            int sy = lower_bound (xx, xx + xxlen, a[i].y) - xx;
 //           cout << sx << " " << sy << endl;

            UpDate (1, 0, xxlen, sx, sy, i);
		}

		memset (have, false, sizeof (have));

		res = 0;
        Query (1, 0, xxlen);
        printf ("%lld\n", res);
	}
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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

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

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 20000 + 6666;

struct Node

{

int x, y;

};

Node a[maxn];

int xx[maxn*3], xxlen, lazy[maxn<<4];

bool have[maxn];

long long res;

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

{

if (lazy[rt] != -1)

{

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

lazy[rt] = -1;

}

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

{

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

{

lazy[rt] = id;

return ;

}

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

PushDown (rt, l, m, r);

if (L <= m)

UpDate (lson, L, R, id);

if (R > m)

UpDate (rson, L, R, id);

}

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

{

if (lazy[rt] != -1)

{

if (!have[lazy[rt]])

{

have[lazy[rt]] = true;

res++;

}

return ;

}

if (l == r)

return ;

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

// PushDown (rt, l, m, r);

Query (lson);

Query (rson);

}

int main()

{

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

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

int t;

scanf ("%d", &t);

while (t--)

{

int n;

scanf ("%d", &n);

xxlen= 0;

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

{

scanf ("%d%d", &a[i].x, &a[i].y);

xx[xxlen++] = a[i].x, xx[xxlen++] = a[i].y;

}

sort (xx, xx + xxlen);

xxlen = unique (xx, xx + xxlen) - xx;

for (int i = xxlen - 1; i >= 1; i--)

if (xx[i] != xx[i-1] + 1)

xx[xxlen++] = xx[i-1] + 1;

sort (xx, xx + xxlen);

// for (int i = 0; i < xxlen;i++)

// cout << xx[i] << endl;

fill (lazy, lazy + (maxn<<4), -1);

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

{

int sx = lower_bound (xx, xx + xxlen, a[i].x) - xx;

int sy = lower_bound (xx, xx + xxlen, a[i].y) - xx;

// cout << sx << " " << sy << endl;

UpDate (1, 0, xxlen, sx, sy, i);

}

memset (have, false, sizeof (have));

res = 0;

Query (1, 0, xxlen);

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

}

return 0;

}

poj2513

maksyuki 发表于 oj 分类，标签: 图论-欧拉回路

15 9月 2015

Colored Sticks

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

Input 阅读全文 »

poj2480

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

15 9月 2015

Longge's problem

Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N.

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

Input

Input contain several test case.
A number N per line.

Output

For each N, output ,∑gcd(i, N) 1<=i <=N, a line

Sample Input

Sample Output

Source

POJ Contest,Author:Mathematica@ZSU

题目类型：素因子分解+积性函数

算法分析：由于n比较大，直接使用sigma (i * Euler(n/i)), i |n会TLE，此时应该进行进一步的推导。简单来说就是可以将积性函数f(x)=x和g(x)=Euler(x)进行一次狄利克雷卷积。而积性函数的狄利克雷卷积仍旧是积性函数。记卷积的结果是G(n)，由积性函数的性质可得：G(n) = G(p1 ^ a1) * G(p2 ^ a2) * G(p3 ^ a3) * ……G(pn ^ an)。将公式进行化简最后可得G(n) =

[(a1+1) * p1 ^ a1 - a1 * p1 ^ (a1-1)] * [(a2+1) * p2 ^ a2 - a2 * p2 ^ (a2-1)] * [(a3+1) * p3 ^ a3 – a3 * p3 ^ (a3-1)] * …… * [(an+1) * pn ^ an - an * pn ^ (an-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;

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

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

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

    long long n;
    while (cin>>n)
	{
        long long res = n;
        for (long long i = 2; i * i <= n; i++)
		{
            if(n % i == 0)
			{
                long long p = i, cnt = 0;
                while (n % p == 0)
				{
                    cnt++;
                    n /= p;
				}

				res += res * cnt * (p - 1) / p;
			}
		}

		if (n != 1)
			res = res * (n * 2 - 1) / n;

		printf("%lld\n", res);
	}
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 lson rt << 1, l, m

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

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 50000 + 66;

int main()

{

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

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

long long n;

while (cin>>n)

{

long long res = n;

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

{

if(n % i == 0)

{

long long p = i, cnt = 0;

while (n % p == 0)

{

cnt++;

n /= p;

}

res += res * cnt * (p - 1) / p;

}

if (n != 1)

res = res * (n * 2 - 1) / n;

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

}

return 0;

}

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

超客的水墨烟雨

poj2992

poj2955

poj2891

poj2823

poj2785

poj2777

poj2752

poj2709

poj2689

poj2585

poj2576

poj2570

poj2559

poj2528

poj2513

poj2480

分类目录

标签云

书签

近期评论

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