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

poj2080

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

15 9月 2015

alendar

A calendar is a system for measuring time, from hours and minutes, to months and days, and finally to years and centuries. The terms of hour, day, month, year and century are all units of time measurements of a calender system. According to the Gregorian calendar, which is the civil calendar in use today, years evenly divisible by 4 are leap years, with the exception of centurial years that are not evenly divisible by 400. Therefore, the years 1700, 1800, 1900 and 2100 are not leap years, but 1600, 2000, and 2400 are leap years. Given the number of days that have elapsed since January 1, 2000 A.D, your mission is to find the date and the day of the week.

Input

The input consists of lines each containing a positive integer, which is the number of days that have elapsed since January 1, 2000 A.D. The last line contains an integer −1, which should not be processed.
You may assume that the resulting date won’t be after the year 9999.

Output

For each test case, output one line containing the date and the day of the week in the format of "YYYY-MM-DD DayOfWeek", where "DayOfWeek" must be one of "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday" and "Saturday".

Sample Input

1730

1740

1750

1751

-1

Sample Output

2004-09-26 Sunday
2004-10-06 Wednesday
2004-10-16 Saturday
2004-10-17 Sunday

Source

Shanghai 2004 Preliminary

题目类型：模拟

算法分析：直接进行日期模拟即可

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

int dayofyears (int year)
{
    if (year % 4 == 0 && year % 100 != 0) return 366;
    if (year % 400 == 0) return 366;
    else return 365;
}

int dayofmonths (int month, int year)
{
    if (month == 2)
    {
        if (dayofyears (year) == 366) return 29;
        else return 28;
    }
    else if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8
    || month == 10 || month == 12)
        return 31;

    else return 30;
}
int main()
{
    int N, year, month, day, temp;
    char week[][20] = {"Saturday", "Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday", "Friday"};

    //fstream cin ("aaa.txt");
    cin >> N;

    while (N != -1)
    {
        year = 2000, month = 1, day = 1;
        temp = N;
        while (N >= dayofyears (year))
        {
            N -= dayofyears (year);
            year++;
        }
        while (N >= dayofmonths (month, year))
        {
            N -= dayofmonths (month, year);
            month ++;
        }
        N++;
        if (month >= 10)
        {
            if (N < 10)
                printf ("%d-%d-0%d %s\n", year, month, N, week[temp%7]);
            else printf ("%d-%d-%d %s\n", year, month, N, week[temp%7]);

        }
        else
        {
            if (N < 10)
                printf ("%d-0%d-0%d %s\n", year, month, N, week[temp%7]);
            else printf ("%d-0%d-%d %s\n", year, month, N, week[temp%7]);
        }
        cin >> N;
    }
return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

using namespace std;

int dayofyears (int year)

{

if (year % 4 == 0 && year % 100 != 0) return 366;

if (year % 400 == 0) return 366;

else return 365;

}

int dayofmonths (int month, int year)

{

if (month == 2)

{

if (dayofyears (year) == 366) return 29;

else return 28;

}

else if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8

|| month == 10 || month == 12)

return 31;

else return 30;

}

int main()

{

int N, year, month, day, temp;

char week[][20] = {"Saturday", "Sunday", "Monday", "Tuesday",

"Wednesday", "Thursday", "Friday"};

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

cin >> N;

while (N != -1)

{

year = 2000, month = 1, day = 1;

temp = N;

while (N >= dayofyears (year))

{

N -= dayofyears (year);

year++;

}

while (N >= dayofmonths (month, year))

{

N -= dayofmonths (month, year);

month ++;

}

N++;

if (month >= 10)

{

if (N < 10)

printf ("%d-%d-0%d %s\n", year, month, N, week[temp%7]);

else printf ("%d-%d-%d %s\n", year, month, N, week[temp%7]);

}

else

{

if (N < 10)

printf ("%d-0%d-0%d %s\n", year, month, N, week[temp%7]);

else printf ("%d-0%d-%d %s\n", year, month, N, week[temp%7]);

}

cin >> N;

}

return 0;

}

poj2031

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

15 9月 2015

Building a Space Station

You are a member of the space station engineering team, and are assigned a task in the construction process of the station. You are expected to write a computer program to complete the task. The space station is made up with a number of units, called cells. All cells are sphere-shaped, but their sizes are not necessarily uniform. Each cell is fixed at its predetermined position shortly after the station is successfully put into its orbit. It is quite strange that two cells may be touching each other, or even may be overlapping. In an extreme case, a cell may be totally enclosing another one. I do not know how such arrangements are possible. All the cells must be connected, since crew members should be able to walk from any cell to any other cell. They can walk from a cell A to another cell B, if, (1) A and B are touching each other or overlapping, (2) A and B are connected by a `corridor', or (3) there is a cell C such that walking from A to C, and also from B to C are both possible. Note that the condition (3) should be interpreted transitively. You are expected to design a configuration, namely, which pairs of cells are to be connected with corridors. There is some freedom in the corridor configuration. For example, if there are three cells A, B and C, not touching nor overlapping each other, at least three plans are possible in order to connect all three cells. The first is to build corridors A-B and A-C, the second B-C and B-A, the third C-A and C-B. The cost of building a corridor is proportional to its length. Therefore, you should choose a plan with the shortest total length of the corridors. You can ignore the width of a corridor. A corridor is built between points on two cells' surfaces. It can be made arbitrarily long, but of course the shortest one is chosen. Even if two corridors A-B and C-D intersect in space, they are not considered to form a connection path between (for example) A and C. In other words, you may consider that two corridors never intersect.

Input

The input consists of multiple data sets. Each data set is given in the following format.

n
x1 y1 z1 r1
x2 y2 z2 r2
...
xn yn zn rn

The first line of a data set contains an integer n, which is the number of cells. n is positive, and does not exceed 100.

The following n lines are descriptions of cells. Four values in a line are x-, y- and z-coordinates of the center, and radius (called r in the rest of the problem) of the sphere, in this order. Each value is given by a decimal fraction, with 3 digits after the decimal point. Values are separated by a space character.

Each of x, y, z and r is positive and is less than 100.0.

The end of the input is indicated by a line containing a zero.

Output

For each data set, the shortest total length of the corridors should be printed, each in a separate line. The printed values should have 3 digits after the decimal point. They may not have an error greater than 0.001.

Note that if no corridors are necessary, that is, if all the cells are connected without corridors, the shortest total length of the corridors is 0.000.

Sample Input

3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0

Sample Output

20.000
0.000
73.834

Source

Japan 2003 Domestic

题目类型：MST

算法分析：按照题目中的数据建立边数组edge，然后直接调用kruskal算法计算最小权值和即可。建立边数组edge时，对于两个太空舱的圆心距小于等于两个太空舱的半径之和的情况，这两个太空舱之间的距离定义为0.000，反之，则距离定义为圆心距减去两个半径之和(表面距离)。注意浮点数误差

#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 = 266 + 66;
const int EPS = 1e-6;

struct Node
{
    double x, y, z, r;
};

Node ans[maxn];
int parent[maxn];

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

Point edge[maxn*maxn];

int len, n;
double sum;

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

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

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


void kruskal ()
{
    int i;
    for (i = 0; i < maxn; i++)
        parent[i] = -1;

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


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

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

        int i;
        for (i = 0; i < n; i++)
            cin >> ans[i].x >> ans[i].y >> ans[i].z >> ans[i].r;

        len = 0;

        int j;
        for (i = 0; i < n - 1; i++)
            for (j = i + 1; j < n; j++)
            {
                edge[len].u = i;
                edge[len].v = j;

                double dis = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2)
                                   + pow (ans[i].z - ans[j].z, 2));

                if (dis > ans[i].r + ans[j].r + EPS)
                    edge[len].w = dis - (ans[i].r + ans[j].r);

                else
                    edge[len].w = 0.000;

                len++;
            }

        sort (edge, edge + len, Cmp);
        kruskal ();

        cout << fixed << setprecision (3) << sum << endl;
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

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

const int EPS = 1e-6;

struct Node

{

double x, y, z, r;

};

Node ans[maxn];

int parent[maxn];

struct Point

{

int u, v;

double w;

};

Point edge[maxn*maxn];

int len, n;

double sum;

int UnFind (int val)

{

if (parent[val] == -1)

return val;

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

}

bool Cmp (Point a, Point b)

{

return a.w < b.w;

}

void kruskal ()

{

int i;

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

parent[i] = -1;

sum = 0.000;

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

sum += edge[i].w;

remain--;

}

int main()

{

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

while (cin >> n)

{

if (n == 0)

break;

int i;

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

cin >> ans[i].x >> ans[i].y >> ans[i].z >> ans[i].r;

len = 0;

int j;

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

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

{

edge[len].u = i;

edge[len].v = j;

double dis = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2)

+ pow (ans[i].z - ans[j].z, 2));

if (dis > ans[i].r + ans[j].r + EPS)

edge[len].w = dis - (ans[i].r + ans[j].r);

else

edge[len].w = 0.000;

len++;

}

sort (edge, edge + len, Cmp);

kruskal ();

cout << fixed << setprecision (3) << sum << endl;

}

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 阅读全文 »

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

超客的水墨烟雨

poj2080

poj2031

poj2019

poj2003

poj1995

poj1979

poj1961

poj1958

poj1887

poj1861

poj1845

poj1811

poj1808

poj1804

poj1789

poj1785

分类目录

标签云

书签

近期评论

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