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

poj2019

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

15 9月 2015

Cornfields

FJ has decided to grow his own corn hybrid in order to help the cows make the best possible milk. To that end, he's looking to build the cornfield on the flattest piece of land he can find. FJ has, at great expense, surveyed his square farm of N x N hectares (1 <= N <= 250). Each hectare has an integer elevation (0 <= elevation <= 250) associated with it. FJ will present your program with the elevations and a set of K (1 <= K <= 100,000) queries of the form "in this B x B submatrix, what is the maximum and minimum elevation?". The integer B (1 <= B <= N) is the size of one edge of the square cornfield and is a constant for every inquiry. Help FJ find the best place to put his cornfield.

Input

* Line 1: Three space-separated integers: N, B, and K.

* Lines 2..N+1: Each line contains N space-separated integers. Line 2 represents row 1; line 3 represents row 2, etc. The first integer on each line represents column 1; the second integer represents column 2; etc.

* Lines N+2..N+K+1: Each line contains two space-separated integers representing a query. The first integer is the top row of the query; the second integer is the left column of the query. The integers are in the range 1..N-B+1.

Output

* Lines 1..K: A single integer per line representing the difference between the max and the min in each query.

Sample Input

5 3 1

5 1 2 6 3

1 3 5 2 7

7 2 4 6 1

9 9 8 6 5

0 6 9 3 9

1 2

Sample Output

Source

USACO 2003 March Green

题目类型：二维RMQ

算法分析：直接使用二维ST来预处理，然后对于每一个查询直接输出结果

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

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

using namespace std;

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

int mm[maxn];
int dpmax[maxn][maxn][8][8];//最大值
int dpmin[maxn][maxn][8][8];//最大值

inline void Init ()
{
    mm[0] = -1;
    for (int i = 1; i <= 266; i++)
        mm[i] = ((i & (i - 1)) == 0) ? mm[i-1] + 1 : mm[i-1];
}

void RMQ_ST (int n, int m)
{
    for (int i = 1;i <= n; i++)
        for (int j = 1; j <= m; j++)
            {
                scanf ("%d", &dpmax[i][j][0][0]);
                dpmin[i][j][0][0] = dpmax[i][j][0][0];
            }


    for (int ii = 0; ii <= mm[n]; ii++)
        for (int jj = 0; jj <= mm[m]; jj++)
            if (ii + jj)
                for (int i = 1; i + (1 << ii) - 1 <= n; i++)
                    for (int j = 1; j + (1 << jj) - 1 <= m; j++)
                    {
                        if (ii)
                        {
                            dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-1][jj],dpmax[i+(1<<(ii-1))][j][ii-1][jj]);
                            dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-1][jj],dpmin[i+(1<<(ii-1))][j][ii-1][jj]);
                        }


                        else
                        {
                            dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-1],dpmax[i][j+(1<<(jj-1))][ii][jj-1]);
                            dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-1],dpmin[i][j+(1<<(jj-1))][ii][jj-1]);
                        }

                    }
}

//查询矩形的最大值
inline int RMQ_Findmax (int x1, int y1, int x2, int y2)
{
    int k1 = mm[x2-x1+1];
    int k2 = mm[y2-y1+1];
    x2 = x2 - (1 << k1) + 1;
    y2 = y2 - (1 << k2) + 1;

return max (max (dpmax[x1][y1][k1][k2], dpmax[x1][y2][k1][k2]), max(dpmax[x2][y1][k1][k2], dpmax[x2][y2][k1][k2]));
}

inline int RMQ_Findmin (int x1, int y1, int x2, int y2)
{
    int k1 = mm[x2-x1+1];
    int k2 = mm[y2-y1+1];
    x2 = x2 - (1 << k1) + 1;
    y2 = y2 - (1 << k2) + 1;

return min (min (dpmin[x1][y1][k1][k2], dpmin[x1][y2][k1][k2]), min(dpmin[x2][y1][k1][k2], dpmin[x2][y2][k1][k2]));
}

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

    int x, y, b, n, q;

    Init ();

    while (scanf ("%d%d%d", &n, &b, &q) != EOF)
    {
        RMQ_ST (n, n);

        for (int i = 1; i <= q; i++)
        {
            scanf ("%d%d", &x, &y);
            printf ("%d\n", RMQ_Findmax (x, y, x + b - 1, y + b - 1)
                    - RMQ_Findmin (x, y, x + b - 1, y + b - 1));
        }
    }

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

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

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1000000000 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 266 + 6;

int mm[maxn];

int dpmax[maxn][maxn][8][8];//最大值

int dpmin[maxn][maxn][8][8];//最大值

inline void Init ()

{

mm[0] = -1;

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

mm[i] = ((i & (i - 1)) == 0) ? mm[i-1] + 1 : mm[i-1];

}

void RMQ_ST (int n, int m)

{

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

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

{

scanf ("%d", &dpmax[i][j][0][0]);

dpmin[i][j][0][0] = dpmax[i][j][0][0];

}

for (int ii = 0; ii <= mm[n]; ii++)

for (int jj = 0; jj <= mm[m]; jj++)

if (ii + jj)

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

for (int j = 1; j + (1 << jj) - 1 <= m; j++)

{

if (ii)

{

dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-1][jj],dpmax[i+(1<<(ii-1))][j][ii-1][jj]);

dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-1][jj],dpmin[i+(1<<(ii-1))][j][ii-1][jj]);

}

else

{

dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-1],dpmax[i][j+(1<<(jj-1))][ii][jj-1]);

dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-1],dpmin[i][j+(1<<(jj-1))][ii][jj-1]);

}

//查询矩形的最大值

inline int RMQ_Findmax (int x1, int y1, int x2, int y2)

{

int k1 = mm[x2-x1+1];

int k2 = mm[y2-y1+1];

x2 = x2 - (1 << k1) + 1;

y2 = y2 - (1 << k2) + 1;

return max (max (dpmax[x1][y1][k1][k2], dpmax[x1][y2][k1][k2]), max(dpmax[x2][y1][k1][k2], dpmax[x2][y2][k1][k2]));

}

inline int RMQ_Findmin (int x1, int y1, int x2, int y2)

{

int k1 = mm[x2-x1+1];

int k2 = mm[y2-y1+1];

x2 = x2 - (1 << k1) + 1;

y2 = y2 - (1 << k2) + 1;

return min (min (dpmin[x1][y1][k1][k2], dpmin[x1][y2][k1][k2]), min(dpmin[x2][y1][k1][k2], dpmin[x2][y2][k1][k2]));

}

int main()

{

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

int x, y, b, n, q;

Init ();

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

{

RMQ_ST (n, n);

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

{

scanf ("%d%d", &x, &y);

printf ("%d\n", RMQ_Findmax (x, y, x + b - 1, y + b - 1)

- RMQ_Findmin (x, y, x + b - 1, y + b - 1));

}

return 0;

}

poj2003

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

15 9月 2015

Hire and Fire

In this problem, you are asked to keep track of the hierarchical structure of an organization's changing staff. As the first event in the life of an organization, the Chief Executive Officer (CEO) is named. 阅读全文 »

poj1995

maksyuki 发表于 oj 分类，标签: 数值- 整数快速幂取模

15 9月 2015

Raising Modulo Numbers

People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODáKH. The rules follow:

Each player chooses two numbers Ai and Bi and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions Ai^Bi from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players' experience it is possible to increase the difficulty by choosing higher numbers. You should write a program that calculates the result and is able to find out who won the game.

Input

The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1 <= M <= 45000). The sum will be divided by this number. Next line contains number of players H (1 <= H <= 45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time.

Output

For each assingnement there is the only one line of output. On this line, there is a number, the result of expression

(A₁^B₁+A₂^B₂+ ... +A_H^B_H)mod M.

Sample Input

2 3

3 4

4 5

5 6

36123

2374859 3029382

3 18132

Sample Output

13195

Source

CTU Open 1999

题目类型：整数快速幂

算法分析：直接计算输入中所有的整数幂的和，并边求和边使用模加法运算来计算答案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 = 1000000 + 66;

long long q_mul_mod (long long a, long long b, long long p)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ((ans % p) * (a % p)) % p;
            b--;
        }

        b = b >> 1;
        a = ((a % p) * (a % p)) % p;
    }

return ans;
}


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

    int t;
    cin >> t;

    while (t--)
    {
        long long m, h;
        cin >> m >> h;

        int i;
        long long a, b, sum = 0;
        for (i = 0; i < h; i++)
        {
            cin >> a >> b;
            sum = (sum % m + q_mul_mod (a, b, m) % m) % m;
        }

        cout << sum % m << 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 = 10000007;

const int maxn = 1000000 + 66;

long long q_mul_mod (long long a, long long b, long long p)

{

long long ans = 1;

while (b)

{

if (b & 1)

{

ans = ((ans % p) * (a % p)) % p;

b--;

}

b = b >> 1;

a = ((a % p) * (a % p)) % p;

}

return ans;

}

int main()

{

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

int t;

cin >> t;

while (t--)

{

long long m, h;

cin >> m >> h;

int i;

long long a, b, sum = 0;

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

{

cin >> a >> b;

sum = (sum % m + q_mul_mod (a, b, m) % m) % m;

}

cout << sum % m << endl;

}

return 0;

}

poj1979

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

15 9月 2015

Red and Black

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles. Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

'.' - a black tile
'#' - a red tile
'@' - a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

Sample Output

Source

Japan 2004 Domestic

题目类型：简单DFS/BFS

算法分析：统计调用DFS或者是BFS时走过的节点即可(也就是扩展的节点数)

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

const int maxn = 36 + 6;

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

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

int row, col, s_x, s_y, sum;

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

return false;
}


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


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

	while (cin >> col >> row)
	{
		if (row == 0 && col == 0)
			break;

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

				if (ans[i][j] == '@')
				{
					s_x = i;
					s_y = j;
				}
			}
		}
	
		sum = 1;
		memset (visited, false, sizeof (visited));
		
		visited[s_x][s_y] = true;
		DFS (s_x, s_y);

		cout << sum << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 36 + 6;

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

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

char ans[maxn][maxn];

bool visited[maxn][maxn];

int row, col, s_x, s_y, sum;

inline bool OkMove (int x, int y)

{

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

return true;

return false;

}

void DFS (int x, int y)

{

int i;

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

{

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

{

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

visited[val_x][val_y] = true;

sum++;

DFS (val_x, val_y);

}

int main()

{

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

while (cin >> col >> row)

{

if (row == 0 && col == 0)

break;

int i;

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

{

int j;

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

{

cin >> ans[i][j];

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

{

s_x = i;

s_y = j;

}

sum = 1;

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

visited[s_x][s_y] = true;

DFS (s_x, s_y);

cout << sum << endl;

}

return 0;

}

poj1961

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

15 9月 2015

Period

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we 阅读全文 »

poj1958

maksyuki 发表于 oj 分类，标签: DP-线性DP

15 9月 2015

Strange Towers of Hanoi

Background
Charlie Darkbrown sits in another one of those boring Computer Science lessons: At the moment the teacher just explains the standard 阅读全文 »

poj1887

maksyuki 发表于 oj 分类，标签: DP-线性DP

15 9月 2015

Testing the CATCHER

A military contractor for the Department of Defense has just completed a series of preliminary tests for a new defensive missile called the CATCHER which is capable of intercepting multiple incoming offensive missiles. The CATCHER is supposed to be a remarkable defensive missile. It can move forward, laterally, and downward at very fast speeds, and it can intercept an offensive missile without being damaged. But it does have one major flaw. Although it can be fired to reach any initial elevation, it has no power to move higher than the last missile that it has intercepted. The tests which the contractor completed were computer simulations of battlefield and hostile attack conditions. Since they were only preliminary, the simulations tested only the CATCHER's vertical movement capability. In each simulation, the CATCHER was fired at a sequence of offensive missiles which were incoming at fixed time intervals. The only information available to the CATCHER for each incoming missile was its height at the point it could be intercepted and where it appeared in the sequence of missiles. Each incoming missile for a test run is represented in the sequence only once.The result of each test is reported as the sequence of incoming missiles and the total number of those missiles that are intercepted by the CATCHER in that test. The General Accounting Office wants to be sure that the simulation test results submitted by the military contractor are attainable, given the constraints of the CATCHER. You must write a program that takes input data representing the pattern of incoming missiles for several different tests and outputs the maximum numbers of missiles that the CATCHER can intercept for those tests. For any incoming missile in a test, the CATCHER is able to intercept it if and only if it satisfies one of these two conditions:

The incoming missile is the first missile to be intercepted in this test.
-or-
The missile was fired after the last missile that was intercepted and it is not higher than the last missile which was intercepted.

Input

The input data for any test consists of a sequence of one or more non-negative integers, all of which are less than or equal to 32,767, representing the heights of the incoming missiles (the test pattern). The last number in each sequence is -1, which signifies the end of data for that particular test and is not considered to represent a missile height. The end of data for the entire input is the number -1 as the first value in a test; it is not considered to be a separate test.

Output

Output for each test consists of a test number (Test #1, Test #2, etc.) and the maximum number of incoming missiles that the CATCHER could possibly intercept for the test. That maximum number appears after an identifying message. There must be at least one blank line between output for successive data sets.

Note: The number of missiles for any given test is not limited. If your solution is based on an inefficient algorithm, it may not execute in the allotted time.

Sample Input

389

207

155

300

299

170

158

-1

Sample Output

Test #1: maximum possible interceptions: 6

Test #2: maximum possible interceptions: 2

Source

World Finals 1994

题目类型：线性DP

算法分析：本题要求最长非递增子序列，只需要将输入反向就可以转化为求最长非递减子序列，定义ans[i]为在从后面数第i个最先拦截导弹的位置处一共能够拦截的导弹个数。状态转移方程类似于求最长非递减子序列的方程

#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 INF = 0x7FFFFFFF;
const int maxn = 100000 + 66;

int ans[maxn], val[maxn];

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

    int len, temp, flag = 1;

    while (cin >> temp)
    {
        if (temp == -1)
            break;

        val[0] = temp;
        len = 1;

        while (cin >> temp)
        {
            if (temp == -1)
                break;

            val[len++] = temp;
        }

        int i;
        for (i = 0; i < len; i++)
            ans[i] = 1;

        for (i = len - 1; i >= 0; i--)
        {
            int j;
            for (j = len - 1; j > i; j--)
            {
                if (val[j] <= val[i])
                {
                    ans[i] = max (ans[i], ans[j] + 1);
                }
            }
        }

        int maxval = -INF;
        for (i = 0; i < len; i++)
            if (maxval < ans[i])
                maxval = ans[i];

        if (flag - 1)
            cout << endl;

        cout << "Test #" << flag++ << ":" << endl;
        cout << "  maximum possible interceptions: " << maxval << 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 INF = 0x7FFFFFFF;

const int maxn = 100000 + 66;

int ans[maxn], val[maxn];

int main()

{

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

int len, temp, flag = 1;

while (cin >> temp)

{

if (temp == -1)

break;

val[0] = temp;

len = 1;

while (cin >> temp)

{

if (temp == -1)

break;

val[len++] = temp;

}

int i;

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

ans[i] = 1;

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

{

int j;

for (j = len - 1; j > i; j--)

{

if (val[j] <= val[i])

{

ans[i] = max (ans[i], ans[j] + 1);

}

int maxval = -INF;

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

if (maxval < ans[i])

maxval = ans[i];

if (flag - 1)

cout << endl;

cout << "Test #" << flag++ << ":" << endl;

cout << " maximum possible interceptions: " << maxval << endl;

}

return 0;

}

poj1861

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

15 9月 2015

Network

Andrew is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cables. Since each 阅读全文 »

poj1845

maksyuki 发表于 oj 分类，标签: 数值- 整数快速幂取模, 数论-乘法逆元, 数论-素因子分解

15 9月 2015

Sumdiv

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

Hint

2^3 = 8.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).

Source

Romania OI 2002

题目类型：素因子分解+逆元+整数快速幂取模

算法分析：首先使用Euler筛将素数预打表，然后从小到大判断每个素数在a中出现的指数值，然后带入约数和公式边模边求解，这里使用了一个求逆元非常好的公式：a / b mod (p) = a mod (mb) / m，由于指数比较大，所以要使用整数快速幂来加速运算

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

const int maxn = 10000 + 666;

bool prime[maxn];
int primelist[maxn], prime_len;

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

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

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

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

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

long long GetFactorSum (long long a, long long b, long long mod)
{
    long long ans = 1;

    for (long long i = 0; primelist[i] * primelist[i] <= a; i++)
    {
        if (a % primelist[i] == 0)
        {
            long long tempsum = 0;
            while (a % primelist[i] == 0)
            {
                tempsum++;
                a /= primelist[i];
            }

            long long m = (primelist[i] - 1) * mod;
            ans *= (pow_mod (primelist[i], tempsum * b + 1, m) + m - 1) / (primelist[i] - 1);
            ans %= mod;
        }
    }

    if (a > 1)
    {
        long long m = (a - 1) * mod;
        ans *= (pow_mod (a, b + 1, m) + m - 1) / (a - 1);
        ans %= mod;
    }

return ans;
}


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

    GetPrime ();

    long long a, b;
    while (cin >> a >> b)
    {
        cout << GetFactorSum (a, b, 9901) << 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

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

const int maxn = 10000 + 666;

bool prime[maxn];

int primelist[maxn], prime_len;

void GetPrime ()

{

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

prime_len = 0;

int i;

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

{

if (prime[i])

primelist[prime_len++] = i;

int j;

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

{

if (i * primelist[j] > maxn)

break;

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

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

break;

}

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;

}

long long GetFactorSum (long long a, long long b, long long mod)

{

long long ans = 1;

for (long long i = 0; primelist[i] * primelist[i] <= a; i++)

{

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

{

long long tempsum = 0;

while (a % primelist[i] == 0)

{

tempsum++;

a /= primelist[i];

}

long long m = (primelist[i] - 1) * mod;

ans *= (pow_mod (primelist[i], tempsum * b + 1, m) + m - 1) / (primelist[i] - 1);

ans %= mod;

}

if (a > 1)

{

long long m = (a - 1) * mod;

ans *= (pow_mod (a, b + 1, m) + m - 1) / (a - 1);

ans %= mod;

}

return ans;

}

int main()

{

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

GetPrime ();

long long a, b;

while (cin >> a >> b)

{

cout << GetFactorSum (a, b, 9901) << endl;

}

return 0;

}

poj1811

maksyuki 发表于 oj 分类，标签: 数论-大整数分解, 数论-大素数测试

15 9月 2015

Prime Test

Given a big integer number, you are required to find out whether it's a prime number.

Input

The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 2⁵⁴).

Output

For each test case, if N is a prime number, output a line containing the word "Prime", otherwise, output a line containing the smallest prime factor of N.

Sample Input

Sample Output

Prime

Source

POJ Monthly

题目类型：Miller_Rabin测试和Pollard_Rho大整数分解

算法分析：先判断n是否是素数，如果是则直接输出”Prime”，反之则分解n大整数，生成n所有的素因子，然后找到最小的那一个即可，注意srand()要注销掉，否则会RE

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

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

using namespace std;

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

long long factor[maxn], fac_len;

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

// 通过 a^(n-1)=1(mod n)来判断n是不是素数
// n-1 = x*2^t 中间使用二次判断
// 是合数返回true, 不一定是合数返回false
bool check (long long a, long long n, long long x, long long t)
{
    long long ans = pow_mod (a, x, n);
    long long last = ans;

    for(int i = 1; i <= t; i++)
    {
        ans = mult_mod (ans, ans, n);
        if(ans == 1 && last != 1 && last != n - 1)
            return true;//合数

        last = ans;
    }

    if(ans != 1)
        return true;

    else
        return false;
}

//**************************************************
// Miller_Rabin算法
// 是素数返回true,(可能是伪素数)
// 不是素数返回false
//**************************************************
bool Miller_Rabin (long long n)
{
    if (n < 2)
        return false;

    if (n == 2)
        return true;

    if ((n&1) == 0)
        return false;//偶数

    long long x = n - 1;
    long long t = 0;

    while ((x&1) == 0)
    {
        x >>= 1; t++;
    }

//    srand (time (NULL));

    for (int i = 0; i < testnum; i++)
    {
        long long a = rand () % (n - 1) + 1;
        if (check (a, n, x, t))
            return false;
    }

return true;
}


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

    if (a < 0)
        return gcd (-a, b);

    while (b)
    {
        long long t = a % b;
        a = b;
        b = t;
    }

return a;
}

long long Pollard_Rho (long long x, long long c)
{
    long long i = 1, k = 2;
    long long x0 = rand () % x;
    long long y = x0;

    while (1)
    {
        i++;
        x0 = (mult_mod (x0, x0, x) + c) % x;
        long long d = gcd (y - x0, x);

        if (d != 1 && d != x)
            return d;

        if (y == x0)
            return x;

        if (i == k)
        {
            y = x0;k += k;
        }
    }
}

//对n进行素因子分解
void FindFac (long long n)
{
    if (Miller_Rabin (n))//素数
    {
        factor[fac_len++] = n;
        return ;
    }

    long long p = n;
    while (p >= n)
        p = Pollard_Rho (p, rand () % (n - 1) + 1);

    FindFac (p);
    FindFac (n / p);
}

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

    long long t;

    scanf ("%lld", &t);

    while (t--)
    {
        long long n;
        scanf ("%lld", &n);

        if (Miller_Rabin (n))
            printf ("Prime\n");

        else
        {
            fac_len = 0;
            FindFac (n);
            long long minval = INF;

            for (long long i = 0; i < fac_len; i++)
                minval = min (minval, factor[i]);

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

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

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

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

long long factor[maxn], fac_len;

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;

}

// 通过 a^(n-1)=1(mod n)来判断n是不是素数

// n-1 = x*2^t 中间使用二次判断

// 是合数返回true, 不一定是合数返回false

bool check (long long a, long long n, long long x, long long t)

{

long long ans = pow_mod (a, x, n);

long long last = ans;

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

{

ans = mult_mod (ans, ans, n);

if(ans == 1 && last != 1 && last != n - 1)

return true;//合数

last = ans;

}

if(ans != 1)

return true;

else

return false;

}

//**************************************************

// Miller_Rabin算法

// 是素数返回true,(可能是伪素数)

// 不是素数返回false

//**************************************************

bool Miller_Rabin (long long n)

{

if (n < 2)

return false;

if (n == 2)

return true;

if ((n&1) == 0)

return false;//偶数

long long x = n - 1;

long long t = 0;

while ((x&1) == 0)

{

x >>= 1; t++;

}

// srand (time (NULL));

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

{

long long a = rand () % (n - 1) + 1;

if (check (a, n, x, t))

return false;

}

return true;

}

long long gcd (long long a, long long b)

{

if (a == 0)

return 1;

if (a < 0)

return gcd (-a, b);

while (b)

{

long long t = a % b;

a = b;

b = t;

}

return a;

}

long long Pollard_Rho (long long x, long long c)

{

long long i = 1, k = 2;

long long x0 = rand () % x;

long long y = x0;

while (1)

{

i++;

x0 = (mult_mod (x0, x0, x) + c) % x;

long long d = gcd (y - x0, x);

if (d != 1 && d != x)

return d;

if (y == x0)

return x;

if (i == k)

{

y = x0;k += k;

}

//对n进行素因子分解

void FindFac (long long n)

{

if (Miller_Rabin (n))//素数

{

factor[fac_len++] = n;

return ;

}

long long p = n;

while (p >= n)

p = Pollard_Rho (p, rand () % (n - 1) + 1);

FindFac (p);

FindFac (n / p);

}

int main()

{

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

long long t;

scanf ("%lld", &t);

while (t--)

{

long long n;

scanf ("%lld", &n);

if (Miller_Rabin (n))

printf ("Prime\n");

else

{

fac_len = 0;

FindFac (n);

long long minval = INF;

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

minval = min (minval, factor[i]);

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

}

return 0;

}

poj1808

maksyuki 发表于 oj 分类，标签: 数论-平方剩余

15 9月 2015

Quadratic Residues

Background
In 1801, Carl Friedrich Gauss (1777-1855) published his "Disquisitiones Arithmeticae", which basically created modern number theory and is still being sold today. One of the many topics treated in his book was the problem of quadratic residues. Consider a prime number p and an integer a !≡ 0 (mod p). Then a is called a quadratic residue mod p if there is an integer x such that
x² ≡ a (mod p), and a quadratic non residue otherwise. Lagrange (1752-1833) introduced the following notation, called the "Legendre symbol":For the calculation of these symbol there are the following rules, valid only for distinct odd prime numbers p, q and integers a, b not divisible by p:The statements 1. to 3. are obvious from the definition, 4. is called the Completion Theorem, and 5. is the famous Law of Quadratic Reciprocity for which Gauss himself gave no less than six different proofs in the "Disquisitiones Arithmeticae". Knowing these facts, one can calculate all possible Legendre ymbols as in the following example:

Input

The first line contains the number of scenarios.
For each scenario, there is one line containing the integers a and p separated by a single blank, where 2 < p < 10⁹ is an odd prime, and a satisfies both a !≡ 0 (mod p) and |a| <= 10⁹.

Output

Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing (a/p), followed by a blank line.

Sample Input

29 79

2 29

1 3

Sample Output

Scenario #1:

-1

Scenario #2:

-1

Scenario #3:

Source

TUD Programming Contest 2003, Darmstadt, Germany

题目类型：平方剩余

算法分析：直接使用欧拉判定条件判断即可，注意输入中的a可能是负值，所以在使用整数快速幂取模时要注意先对底数取模，使其转化成正值！！！

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

long long mod_f (long long a, long long b, long long mod)
{
    long long res = 1, tt = a % mod;
    if (tt < 0)
        tt += mod;

    while (b)
    {
        if (b & 1)
            res = res * tt % mod;

        tt = tt * tt % mod;
        b >>= 1;
    }
    return res;
}


int main()
{
//    CPPFF;
    long long a, p, t, flag = 1;
    cin >> t;

    while (t--)
    {
        cin >> a >> p;
        long long ans = mod_f (a, (p - 1) / 2, p);
        cout << "Scenario #" << flag++ << ": " << endl;

        if (ans == 1)
            cout << ans << endl;

        else
            cout << "-1" << endl;
        cout << 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;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

long long mod_f (long long a, long long b, long long mod)

{

long long res = 1, tt = a % mod;

if (tt < 0)

tt += mod;

while (b)

{

if (b & 1)

res = res * tt % mod;

tt = tt * tt % mod;

b >>= 1;

}

return res;

}

int main()

{

// CPPFF;

long long a, p, t, flag = 1;

cin >> t;

while (t--)

{

cin >> a >> p;

long long ans = mod_f (a, (p - 1) / 2, p);

cout << "Scenario #" << flag++ << ": " << endl;

if (ans == 1)

cout << ans << endl;

else

cout << "-1" << endl;

cout << endl;

}

return 0;

}

poj1804

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

15 9月 2015

Brainman

Background
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.

Problem
Here's what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:

Start with: 2 8 0 3
swap (2 8) 8 2 0 3
swap (2 0) 8 0 2 3
swap (2 3) 8 0 3 2
swap (8 0) 0 8 3 2
swap (8 3) 0 3 8 2
swap (8 2) 0 3 2 8
swap (3 2) 0 2 3 8
swap (3 8) 0 2 8 3
swap (8 3) 0 2 3 8
So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:

Start with: 2 8 0 3
swap (8 0) 2 0 8 3
swap (2 0) 0 2 8 3
swap (8 3) 0 2 3 8
The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond's mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.

Input

The first line contains the number of scenarios.
For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.

Output

Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line.

Sample Input

4 2 8 0 3

10 0 1 2 3 4 5 6 7 8 9

6 -42 23 6 28 -100 65537

5 0 0 0 0 0

Sample Output

Scenario #1:

Scenario #2:

Scenario #3:

Scenario #4:

Source

TUD Programming Contest 2003, Darmstadt, Germany

题目类型：逆序对

算法分析：由于n最大只有1000，所以直接暴力枚举同样可以过掉，这里使用了树状数组+离散化求解

#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 double EPS = 1e-10;
const int mod = 1000000000 + 7;
const int maxn = 1000 + 66;

int a[maxn], temp[maxn], tree[maxn], len;

int lowbit (int x)
{
    return x & (-x);
}


int GetSum (int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += tree[x];
        x -= lowbit (x);
    }

return sum;
}

void UpDate (int x)
{
    while (x <= len)
    {
        tree[x]++;
        x += lowbit (x);
    }
}

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

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

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

        for (int i = 1; i <= n; i++)
        {
            scanf ("%d", &a[i]);
            temp[i] = a[i];
        }

        sort (temp + 1, temp + 1 + n);
        len = unique (temp + 1, temp + 1 + n) - (temp + 1);
        for (int i = 1; i <= n; i++)
            a[i] = lower_bound (temp + 1, temp + 1 + len, a[i]) - temp;

        long long res = 0;
        memset (tree, 0, sizeof (tree));

        for (int i = 1; i <= n; i++)
        {
            res += GetSum (len) - GetSum (a[i]);
            UpDate (a[i]);
        }

        cout << "Scenario #" << flag++ << ":" << endl;
        cout << res << endl << endl;
    }
return 0;
}

100

101

102

103

104

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

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

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const int mod = 1000000000 + 7;

const int maxn = 1000 + 66;

int a[maxn], temp[maxn], tree[maxn], len;

int lowbit (int x)

{

return x & (-x);

}

int GetSum (int x)

{

int sum = 0;

while (x > 0)

{

sum += tree[x];

x -= lowbit (x);

}

return sum;

}

void UpDate (int x)

{

while (x <= len)

{

tree[x]++;

x += lowbit (x);

}

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

int n;

scanf ("%d", &n);

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

{

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

temp[i] = a[i];

}

sort (temp + 1, temp + 1 + n);

len = unique (temp + 1, temp + 1 + n) - (temp + 1);

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

a[i] = lower_bound (temp + 1, temp + 1 + len, a[i]) - temp;

long long res = 0;

memset (tree, 0, sizeof (tree));

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

{

res += GetSum (len) - GetSum (a[i]);

UpDate (a[i]);

}

cout << "Scenario #" << flag++ << ":" << endl;

cout << res << endl << endl;

}

return 0;

}

poj1789

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

15 9月 2015

Truck History

Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. The company has its own code describing each type of a truck. 阅读全文 »

poj1785

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

15 9月 2015

Binary Search Heap Construction

Read the statement of problem G for the definitions concerning trees. In the following we define the basic terminology of heaps. A heap is a tree whose internal nodes have each assigned a priority 阅读全文 »

poj1751

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

15 9月 2015

HighwaysThe island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has a very poor system of public highways. The Flatopian government is aware of this problem and has already constructed a number of highways connecting some of the most important towns. However, there are still some towns that you can't reach via a highway. It is necessary to build more highways so that it will be possible to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N and town i has a position given by the Cartesian coordinates (xi, yi). Each highway connects exaclty two towns. All highways (both the original ones and the ones that are to be built) follow straight lines, and thus their length is equal to Cartesian distance between towns. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government wants to minimize the cost of building new highways. However, they want to guarantee that every town is highway-reachable from every other town. Since Flatopia is so flat, the cost of a highway is always proportional to its length. Thus, the least expensive highway system will be the one that minimizes the total highways length.Input

The input consists of two parts. The first part describes all towns in the country, and the second part describes all of the highways that have already been built.

The first line of the input file contains a single integer N (1 <= N <= 750), representing the number of towns. The next N lines each contain two integers, xi and yi separated by a space. These values give the coordinates of i^th town (for i from 1 to N). Coordinates will have an absolute value no greater than 10000. Every town has a unique location.

The next line contains a single integer M (0 <= M <= 1000), representing the number of existing highways. The next M lines each contain a pair of integers separated by a space. These two integers give a pair of town numbers which are already connected by a highway. Each pair of towns is connected by at most one highway.

Output

Write to the output a single line for each new highway that should be built in order to connect all towns with minimal possible total length of new highways. Each highway should be presented by printing town numbers that this highway connects, separated by a space.

If no new highways need to be built (all towns are already connected), then the output file should be created but it should be empty.

Sample Input

1 5

0 0

3 2

4 5

5 1

0 4

5 2

1 2

5 3

1 3

9 7

1 2

Sample Output

1 6

3 7

4 9

5 7

8 3

Source

Northeastern Europe 1999

题目类型：MST

算法分析：读入坐标并计算坐标之间的距离(权值)，然后直接使用kruskal算法计算并记录新增加的边的信息。最后直接输出新增加的边的两个节点即可

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

struct Node
{
    double x, y;
};

Node ans[maxn];

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

Point edge[maxn*maxn/2], output[maxn*maxn/2];;

int parent[maxn], len, len_output;
int n, m;

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

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

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


void kruskal ()
{
    len_output = 0;
    int i;
    int remain = n;

    for (i = 0; i < len && remain > 1; i++)
    {
        if (UnFind (edge[i].u) != UnFind (edge[i].v))
        {
            parent[UnFind(edge[i].u)] = UnFind (edge[i].v);
            output[len_output++] = edge[i];
            remain--;
        }
    }
}
int main()
{
//    freopen ("aaa.txt", "r", stdin);



    while (scanf ("%d", &n) != EOF)
    {
        int i;
        for (i = 0; i < n; i++)
            scanf ("%lf%lf", &ans[i].x, &ans[i].y);

        int j;

        len = 0;

        for (i = 0; i < n - 1; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                edge[len].u = i + 1;
                edge[len].v = j + 1;
                edge[len].w = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2));
                len++;
            }
        }

        sort (edge, edge + len, Cmp);

        cin >> m;
        int temp_a, temp_b;

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

        for (i = 0; i < m; i++)
        {
            cin >> temp_a >> temp_b;
            if (UnFind (temp_a) != UnFind (temp_b))
            {
                parent[UnFind(temp_a)] = UnFind (temp_b);
            }
        }

        kruskal ();

        for (i = 0; i < len_output; i++)
            printf ("%d %d\n", output[i].u, output[i].v);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

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

struct Node

{

double x, y;

};

Node ans[maxn];

struct Point

{

int u, v;

double w;

};

Point edge[maxn*maxn/2], output[maxn*maxn/2];;

int parent[maxn], len, len_output;

int n, m;

int UnFind (int val)

{

if (parent[val] == val)

return val;

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

}

bool Cmp (Point a, Point b)

{

return a.w < b.w;

}

void kruskal ()

{

len_output = 0;

int i;

int remain = n;

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

{

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

{

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

output[len_output++] = edge[i];

remain--;

}

int main()

{

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

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

{

int i;

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

scanf ("%lf%lf", &ans[i].x, &ans[i].y);

int j;

len = 0;

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

{

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

{

edge[len].u = i + 1;

edge[len].v = j + 1;

edge[len].w = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2));

len++;

}

sort (edge, edge + len, Cmp);

cin >> m;

int temp_a, temp_b;

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

parent[i] = i;

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

{

cin >> temp_a >> temp_b;

if (UnFind (temp_a) != UnFind (temp_b))

{

parent[UnFind(temp_a)] = UnFind (temp_b);

}

kruskal ();

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

printf ("%d %d\n", output[i].u, output[i].v);

}

return 0;

}

poj1738

maksyuki 发表于 oj 分类，标签: 其他-GarsiaWachs算法

15 9月 2015

An old Stone Game

There is an old stone game.At the beginning of the game the player picks n(1<=n<=50000) piles of stones in a line. The goal is to merge the stones in one pile observing the following rules:
At each step of the game,the player can merge two adjoining piles to a new pile.The score is the number of stones in the new pile. You are to write a program to determine the minimum of the total score.

Input

The input contains several test cases. The first line of each test case contains an integer n, denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game.
The last test case is followed by one zero.

Output

For each test case output the answer on a single line.You may assume the answer will not exceed 1000000000.

Sample Input

100

3 4 3

1 1 1 1

Sample Output

Source

LouTiancheng@POJ

题目类型：石子合并GarsiaWachs算法

算法分析：直接使用GarsiaWachs算法求解即可，最好使用平衡树优化，否则直接使用O(n ^ 2)的算法很可能会TLE!!!!!!

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

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

using namespace std;

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

int stone[maxn];
int n, t, ans;

void Combine (int k)
{
    int temp = stone[k] + stone[k-1];
    ans += temp;
    for (int i = k; i < t - 1; i++)
        stone[i] = stone[i+1];
    t--;

    int j = 0;
    for(j = k - 1; j > 0 && stone[j-1] < temp; j--)
        stone[j] = stone[j-1];
    stone[j] = temp;

    while (j >= 2 && stone[j] >= stone[j-2])
    {
        int d = t - j;
        Combine (j - 1);
        j = t - d;
    }
}

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

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

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

        t = 1, ans = 0;
        for (int i = 1; i < n; i++)
        {
            stone[t++] = stone[i];
            while (t >= 3 && stone[t-3] <= stone[t-1])
                Combine (t - 2);
        }
        while (t > 1) Combine (t - 1);

        cout << ans << 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 = 500000 + 66;

int stone[maxn];

int n, t, ans;

void Combine (int k)

{

int temp = stone[k] + stone[k-1];

ans += temp;

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

stone[i] = stone[i+1];

t--;

int j = 0;

for(j = k - 1; j > 0 && stone[j-1] < temp; j--)

stone[j] = stone[j-1];

stone[j] = temp;

while (j >= 2 && stone[j] >= stone[j-2])

{

int d = t - j;

Combine (j - 1);

j = t - d;

}

int main()

{

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

while (cin >> n)

{

if (n == 0) break ;

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

cin >> stone[i];

t = 1, ans = 0;

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

{

stone[t++] = stone[i];

while (t >= 3 && stone[t-3] <= stone[t-1])

Combine (t - 2);

}

while (t > 1) Combine (t - 1);

cout << ans << endl;

}

return 0;

}

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

超客的水墨烟雨

poj2019

poj2003

poj1995

poj1979

poj1961

poj1958

poj1887

poj1861

poj1845

poj1811

poj1808

poj1804

poj1789

poj1785

poj1751

poj1738

分类目录

标签云

书签

近期评论

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