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

poj1426

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

31 10月 2015

Find The Multiple

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

Sample Input

6
2
19
0

Sample Output

10
100100100100100100
111111111111111111

Source

Dhaka 2002

题目类型：BFS

算法分析：从最高位”1”开始搜索，每次向低位扩展(0或者1)，然后判断最后的结果是否能够整除n

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

int n;

LL bfs ()
{
    queue <LL> qu;
    qu.push (1LL);
    while (!qu.empty ())
    {
        LL tt = qu.front (); qu.pop ();
        if (tt * 10 % n == 0)
            return tt * 10;

        if ((tt * 10 + 1) % n == 0)
            return tt * 10 + 1;

        qu.push ((tt * 10));
        qu.push ((tt * 10 + 1));
    }
    return -1;
}

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

        printf ("%lld\n", bfs ());
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2e6 + 6666;

int n;

LL bfs ()

{

queue <LL> qu;

qu.push (1LL);

while (!qu.empty ())

{

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

if (tt * 10 % n == 0)

return tt * 10;

if ((tt * 10 + 1) % n == 0)

return tt * 10 + 1;

qu.push ((tt * 10));

qu.push ((tt * 10 + 1));

}

return -1;

}

int main()

{

// CFF;

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

{

if (n == 0)

break;

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

}

return 0;

}

题目类型：BFS+同余

算法分析：对于上面的算法进行优化(每次计算利用前面计算好的余数)，最后得到进行*10操作的数量，反推回去就是结果

代码：http://blog.csdn.net/lyy289065406/article/details/6647917

poj1376

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

30 10月 2015

Robot

The Robot Moving Institute is using a robot in their local store to transport different items. Of course the robot should spend only the minimum time necessary when travelling from one place in the store to another. The robot can move only along a straight line (track). All tracks form a rectangular grid. Neighbouring tracks are one meter apart. The store is a rectangle N x M meters and it is entirely covered by this grid. The distance of the track closest to the side of the store is exactly one meter. The robot has a circular shape with diameter equal to 1.6 meter. The track goes through the center of the robot. The robot always faces north, south, west or east. The tracks are in the south-north and in the west-east directions. The robot can move only in the direction it faces. The direction in which it faces can be changed at each track crossing. Initially the robot stands at a track crossing. The obstacles in the store are formed from pieces occupying 1m x 1m on the ground. Each obstacle is within a 1 x 1 square formed by the tracks. The movement of the robot is controlled by two commands. These commands are GO and TURN.
The GO command has one integer parameter n in {1,2,3}. After receiving this command the robot moves n meters in the direction it faces.

The TURN command has one parameter which is either left or right. After receiving this command the robot changes its orientation by 90o in the direction indicated by the parameter.

The execution of each command lasts one second.

Help researchers of RMI to write a program which will determine the minimal time in which the robot can move from a given starting point to a given destination.

Input

The input consists of blocks of lines. The first line of each block contains two integers M <= 50 and N <= 50 separated by one space. In each of the next M lines there are N numbers one or zero separated by one space. One represents obstacles and zero represents empty squares. (The tracks are between the squares.) The block is terminated by a line containing four positive integers B1 B2 E1 E2 each followed by one space and the word indicating the orientation of the robot at the starting point. B1, B2 are the coordinates of the square in the north-west corner of which the robot is placed (starting point). E1, E2 are the coordinates of square to the north-west corner of which the robot should move (destination point). The orientation of the robot when it has reached the destination point is not prescribed. We use (row, column)-type coordinates, i.e. the coordinates of the upper left (the most north-west) square in the store are 0,0 and the lower right (the most south-east) square are M - 1, N - 1. The orientation is given by the words north or west or south or east. The last block contains only one line with N = 0 and M = 0.

Output

The output contains one line for each block except the last block in the input. The lines are in the order corresponding to the blocks in the input. The line contains minimal number of seconds in which the robot can reach the destination point from the starting point. If there does not exist any path from the starting point to the destination point the line will contain -1.

Sample Input

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 south
0 0

Sample Output

Source

Central Europe 1996

题目类型：BFS

算法分析：先将所给的障碍的位置在图中标记，后面直接调用BFS即可。注意这里要比一般的BFS多加一个方向的状态，vis[x][y][dir]表示以dir这个方向走到(x, y)这个位置的最小时间。注意BFS一定要遍历完所有合理的状态之后才能得到最终的结果！！！注意机器人是不能走边界的！！！

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

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

struct node
{
    int x, y, cnt;
    string cur;
    node (int xx, int yy, string ccur, int ccnt) : x (xx), y (yy), cur (ccur), cnt (ccnt) {}
    node () {}
};

int g[66][66], aa[66][66], sx, sy, ex, ey, row, col;
string dir;
int vis[66][66][66];
map <string, int> ma;
queue <node> qu;

bool OK (int x, int y)
{
    if (x >= 1 && x <= row - 1 && y >= 1 && y <= col - 1)
        return true;
    return false;
}

int PP (node &s, int len, int flag)
{
    int tt = ma[s.cur];
    int tx = s.x + len * dx[tt], ty = s.y + len * dy[tt];
    if (!flag) return tx;
    else return ty;
}

void SS (node &tt)
{
    for (int i = 1; i <= 3; i++)
    {
        int tx = PP (tt, i, 0), ty = PP (tt, i, 1);
        if (OK (tx, ty) && g[tx][ty]) return ;

        else if (OK (tx, ty) && !g[tx][ty] && vis[tx][ty][ma[tt.cur]] > tt.cnt + 1)
        {
            vis[tx][ty][ma[tt.cur]] = tt.cnt + 1;
            qu.push (node (tx, ty, tt.cur, tt.cnt + 1));
        }
    }
}

node change (string s, node tt)
{
    node res = tt;
    if (s == "left")
    {
        if (ma[tt.cur] == 0) res.cur = "west";
        if (ma[tt.cur] == 1) res.cur = "east";
        if (ma[tt.cur] == 2) res.cur = "south";
        if (ma[tt.cur] == 3) res.cur = "north";
    }

    else if (s == "right")
    {
        if (ma[tt.cur] == 0) res.cur = "east";
        if (ma[tt.cur] == 1) res.cur = "west";
        if (ma[tt.cur] == 2) res.cur = "north";
        if (ma[tt.cur] == 3) res.cur = "south";
    }
    res.cnt++;
    return res;
}

int minval;

void bfs ()
{
    for (int i = 0; i < 66; i++)
        for (int j = 0; j < 66; j++)
            for (int k = 0; k < 66; k++)
                vis[i][j][k] = INF;

    vis[sx][sy][ma[dir]] = 0;
    while (!qu.empty ()) qu.pop ();

    qu.push (node (sx, sy, dir, 0));
    while (!qu.empty ())
    {
        node tt = qu.front (); qu.pop ();
        if (tt.x == ex && tt.y == ey)
            minval = min (minval, tt.cnt);

        node ta = change ("left", tt);
        node tb = change ("left", ta);
        node tc = change ("right", tt);
        SS (tt);
        SS (ta);
        SS (tb);
        SS (tc);
    }
}

int main()
{
    ma["north"] = 0; ma["south"] = 1; ma["west"] = 2; ma["east"] = 3;
//    CPPFF;
    while (cin >> row >> col)
    {
        if (row == 0 && col == 0)
            break;

        memset (g, 0, sizeof (g));
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
            {
                cin >> aa[i][j];
                if (aa[i][j] == 1)
                {
                    g[i][j] = g[i][j+1] = g[i+1][j] = g[i+1][j+1] = 1;
                }
            }
        cin >> sx >> sy >> ex >> ey >> dir;

        minval = INF;
        bfs ();
        if (minval == INF)
            cout << "-1" << endl;

        else
            cout << minval << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6666;

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

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

struct node

{

int x, y, cnt;

string cur;

node (int xx, int yy, string ccur, int ccnt) : x (xx), y (yy), cur (ccur), cnt (ccnt) {}

node () {}

};

int g[66][66], aa[66][66], sx, sy, ex, ey, row, col;

string dir;

int vis[66][66][66];

map <string, int> ma;

queue <node> qu;

bool OK (int x, int y)

{

if (x >= 1 && x <= row - 1 && y >= 1 && y <= col - 1)

return true;

return false;

}

int PP (node &s, int len, int flag)

{

int tt = ma[s.cur];

int tx = s.x + len * dx[tt], ty = s.y + len * dy[tt];

if (!flag) return tx;

else return ty;

}

void SS (node &tt)

{

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

{

int tx = PP (tt, i, 0), ty = PP (tt, i, 1);

if (OK (tx, ty) && g[tx][ty]) return ;

else if (OK (tx, ty) && !g[tx][ty] && vis[tx][ty][ma[tt.cur]] > tt.cnt + 1)

{

vis[tx][ty][ma[tt.cur]] = tt.cnt + 1;

qu.push (node (tx, ty, tt.cur, tt.cnt + 1));

}

node change (string s, node tt)

{

node res = tt;

if (s == "left")

{

if (ma[tt.cur] == 0) res.cur = "west";

if (ma[tt.cur] == 1) res.cur = "east";

if (ma[tt.cur] == 2) res.cur = "south";

if (ma[tt.cur] == 3) res.cur = "north";

}

else if (s == "right")

{

if (ma[tt.cur] == 0) res.cur = "east";

if (ma[tt.cur] == 1) res.cur = "west";

if (ma[tt.cur] == 2) res.cur = "north";

if (ma[tt.cur] == 3) res.cur = "south";

}

res.cnt++;

return res;

}

int minval;

void bfs ()

{

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

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

for (int k = 0; k < 66; k++)

vis[i][j][k] = INF;

vis[sx][sy][ma[dir]] = 0;

while (!qu.empty ()) qu.pop ();

qu.push (node (sx, sy, dir, 0));

while (!qu.empty ())

{

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

if (tt.x == ex && tt.y == ey)

minval = min (minval, tt.cnt);

node ta = change ("left", tt);

node tb = change ("left", ta);

node tc = change ("right", tt);

SS (tt);

SS (ta);

SS (tb);

SS (tc);

}

int main()

{

ma["north"] = 0; ma["south"] = 1; ma["west"] = 2; ma["east"] = 3;

// CPPFF;

while (cin >> row >> col)

{

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

break;

memset (g, 0, sizeof (g));

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

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

{

cin >> aa[i][j];

if (aa[i][j] == 1)

{

g[i][j] = g[i][j+1] = g[i+1][j] = g[i+1][j+1] = 1;

}

cin >> sx >> sy >> ex >> ey >> dir;

minval = INF;

bfs ();

if (minval == INF)

cout << "-1" << endl;

else

cout << minval << endl;

}

return 0;

}

poj3684

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

21 10月 2015

Physics Experiment

Simon wants to know where are the N balls after T seconds. Can you help him?Simon is doing a physics experiment with N identical balls with the same radius of R centimeters. Before the experiment, all N balls are fastened within a vertical tube one by one and the lowest point of the lowest ball is H meters above the ground. At beginning of the experiment, (at second 0), the first ball is released and falls down due to the gravity. After that, the balls are released one by one in every second until all balls have been released. When a ball hits the ground, it will bounce back with the same speed as it hits the ground. When two balls hit each other, they with exchange their velocities (both speed and direction).

In this problem, you can assume that the gravity is constant: g = 10 m/s².

Input

The first line of the input contains one integer C (C ≤ 20) indicating the number of test cases. Each of the following lines contains four integers N, H, R, T.
1≤ N ≤ 100.
1≤ H ≤ 10000
1≤ R ≤ 100
1≤ T ≤ 10000

Output

For each test case, your program should output N real numbers indicating the height in meters of the lowest point of each ball separated by a single space in a single line. Each number should be rounded to 2 digit after the decimal point.

Sample Input

2
1 10 10 100
2 10 10 100

Sample Output

4.95

4.95 10.20

Source

POJ Founder Monthly Contest – 2008.08.31, Simon

题目类型：简单数学

算法分析：可以先考虑将每个球的起点设置在高度H处，然后小球之间的碰撞可以看做是互不影响地相交而过。其实就是计算T时刻每个小球的位置，由于这里小球是有半径的，每个小球(从下到上的第i个球)的最终位置都要加上2Ri，注意若小球的最终时刻小于0，则表示还没有出发，位置为H！！！

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

double aa[maxn];
int N, H, R, T;

double PP (int t)
{
    double tt = sqrt (2 * H / 10.0);
    if (t < 0) return H;

    int k = t / tt;
    if (k & 1)
        tt = k * tt + tt - t;

    else
        tt = t - k * tt;

    return H - 10.0 / 2 * (tt * tt);
}


void SS ()
{
    for (int i = 0; i < N; i++)
        aa[i] = PP (T - i);

    sort (aa, aa + N);
}


int main()
{
//    CFF;
    int t;
    scanf ("%d", &t);
    while(t--)
    {
        scanf ("%d%d%d%d", &N, &H, &R, &T);
        SS ();
        for (int i = 0; i < N; i++)
        {
            if (i == 0)
                printf("%.2lf", aa[i] + 2 * R * i / 100.0);
            else
                printf (" %.2lf", aa[i] + 2 * R * i / 100.0);
        }
        puts ("");
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6666;

double aa[maxn];

int N, H, R, T;

double PP (int t)

{

double tt = sqrt (2 * H / 10.0);

if (t < 0) return H;

int k = t / tt;

if (k & 1)

tt = k * tt + tt - t;

else

tt = t - k * tt;

return H - 10.0 / 2 * (tt * tt);

}

void SS ()

{

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

aa[i] = PP (T - i);

sort (aa, aa + N);

}

int main()

{

// CFF;

int t;

scanf ("%d", &t);

while(t--)

{

scanf ("%d%d%d%d", &N, &H, &R, &T);

SS ();

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

{

if (i == 0)

printf("%.2lf", aa[i] + 2 * R * i / 100.0);

else

printf (" %.2lf", aa[i] + 2 * R * i / 100.0);

}

puts ("");

}

return 0;

}

poj1190

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

21 10月 2015

生日蛋糕

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，阅读全文 »

poj2739

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

15 10月 2015

Sum of Consecutive Prime Numbers

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime
numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.
Your mission is to write a program that reports the number of representations for the given positive integer.

Input

The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.

Output

The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.

Sample Input

2
3
17
41
20
666
12
53
0

Sample Output

Source

Japan 2005

题目类型：追逐法

算法分析：维护两个指针分别指向区间的头和尾，当前区间(素数序列)的和小于n，则移动尾指针并加上尾指针所指向的数，否则从区间删去头指针所指向的数

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

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

void PP ()
{
    memset (prime, true, sizeof (prime));
    len = 0;
    prime[0] = prime[1] = false;
    for (int i = 2; i < maxn; i++)
    {
        if (prime[i])
            primelist[len++] = i;

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

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

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

        int res = 0, pa = 0, pb = 0, sum = 0;
        while (1)
        {
            while (pb < len && sum < n)
            {
                sum += primelist[pb++];
            }

            if (sum == n) res++;

            if (pa == pb) break;
            sum -= primelist[pa++];
        }

        printf ("%d\n", res);
    }
    return 0;
}

100

101

102

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6666;

int primelist[maxn], len;

bool prime[maxn];

void PP ()

{

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

len = 0;

prime[0] = prime[1] = false;

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

{

if (prime[i])

primelist[len++] = i;

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

{

if (i * primelist[j] > maxn)

break;

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

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

break;

}

int main()

{

// CFF;

PP ();

int n;

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

{

if (n == 0)

break;

int res = 0, pa = 0, pb = 0, sum = 0;

while (1)

{

while (pb < len && sum < n)

{

sum += primelist[pb++];

}

if (sum == n) res++;

if (pa == pb) break;

sum -= primelist[pa++];

}

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

}

return 0;

}

poj3421

maksyuki 发表于 oj 分类，标签: 数论-素因子分解, 组合数学-计数

15 10月 2015

X-factor Chains

Given a positive integer X, an X-factor chain of length m is a sequence of integers, 1 = X₀, X₁, X₂, …, X_m = X satisfying X_i < X_i₊₁ and X_i | X_i₊₁ where a | b means a perfectly divides into b. Now we are interested in the maximum length of X-factor chains and the number of chains of such length.

Input

The input consists of several test cases. Each contains a positive integer X (X ≤ 2²⁰).

Output

For each test case, output the maximum length and the number of such X-factors chains.

Sample Input

2
3
4
10
100

Sample Output

1 1

2 1

2 2

4 6

Source

POJ Monthly--2007.10.06, ailyanlu@zsu

题目类型：整数素因子分解+组合计数

算法分析：为了得到最长的序列，除了头尾1和n之外，其他的约数应该按照递增排列且后一个约数要比前一个恰好多一个素因子，这样才能保证得到的序列是最长的。最长序列的数目是素因子幂和的可重排列(即素因子幂之和的阶乘/每个素因子幂的阶乘)

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

LL fac[27];

void PP ()
{
    fac[1] = 1;
    for (LL i = 2; i <= 21; i++)
        fac[i] = fac[i-1] * i;
}

int aa[maxn], len;

int main()
{
//    CFF;
    PP ();
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        int res = 0;
        len = 0;
        for (int i = 2; i * i <= n; i++)
        {
            while (n % i == 0)
            {
                n /= i;
                aa[len++] = i;
                res++;
            }
        }

        if (n > 1)
        {
            aa[len++] = n;
            res++;
        }

        LL ans = fac[res], tt = 0;
        for (int i = 1; i < len; )
        {
            if (aa[i-1] == aa[i])
            {
                while (i < len && aa[i-1] == aa[i])
                {
                    tt++;
                    i++;
                }
            }

            else
            {
                ans /= fac[tt+1];
                tt = 0;
                i++;
            }
        }

        if (tt)
            ans /= fac[tt+1];

        printf ("%d %lld\n", res, ans);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e7 + 48579;

LL fac[27];

void PP ()

{

fac[1] = 1;

for (LL i = 2; i <= 21; i++)

fac[i] = fac[i-1] * i;

}

int aa[maxn], len;

int main()

{

// CFF;

PP ();

int n;

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

{

int res = 0;

len = 0;

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

{

while (n % i == 0)

{

n /= i;

aa[len++] = i;

res++;

}

if (n > 1)

{

aa[len++] = n;

res++;

}

LL ans = fac[res], tt = 0;

for (int i = 1; i < len; )

{

if (aa[i-1] == aa[i])

{

while (i < len && aa[i-1] == aa[i])

{

tt++;

i++;

}

else

{

ans /= fac[tt+1];

tt = 0;

i++;

}

if (tt)

ans /= fac[tt+1];

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

}

return 0;

}

poj3292

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

15 10月 2015

Semi-prime H-numbers

An H-number is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,... are the H-numbers. For this problem we pretend that these are the only numbers. The H-numbers are closed under multiplication.This problem is based on an exercise of David Hilbert, who pedagogically suggested that one study the theory of 4n+1 numbers. Here, we do only a bit of that.

As with regular integers, we partition the H-numbers into units, H-primes, and H-composites. 1 is the only unit. An H-number h is H-prime if it is not the unit, and is the product of two H-numbers in only one way: 1 × h. The rest of the numbers are H-composite.

For examples, the first few H-composites are: 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81, 5 × 17 = 85.

Your task is to count the number of H-semi-primes. An H-semi-prime is an H-number which is the product of exactly two H-primes. The two H-primes may be equal or different. In the example above, all five numbers are H-semi-primes. 125 = 5 × 5 × 5 is not an H-semi-prime, because it's the product of three H-primes.

Input

Each line of input contains an H-number ≤ 1,000,001. The last line of input contains 0 and this line should not be processed.

Output

For each inputted H-number h, print a line stating h and the number of H-semi-primes between 1 and h inclusive, separated by one space in the format shown in the sample.

Sample Input

21
85
789
0

Sample Output

21 0

85 5

789 62

Source

Waterloo Local Contest, 2006.9.30

题目类型：Euler筛法

算法分析：将每个H-素数定义好后，使用类似Euler筛法的思想预打表，维护前缀和并查询

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

int primelist[maxn], len, sum[maxn];
bool prime[maxn];

void PP()
{
    memset (sum, 0, sizeof (sum));
    memset (prime, true, sizeof (prime));
    len = 0;
    prime[0] = prime[1] = false;
    for (int i = 5; i < maxn; i += 4)
    {
        if (prime[i])
            primelist[len++] = i;

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

            if (prime[i] && prime[primelist[j]])
                sum[i*primelist[j]] = 1;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
    for (int i = 1; i < maxn; i++)
        sum[i] += sum[i-1];
}

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

        printf ("%d %d\n", n, sum[n]);
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

int primelist[maxn], len, sum[maxn];

bool prime[maxn];

void PP()

{

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

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

len = 0;

prime[0] = prime[1] = false;

for (int i = 5; i < maxn; i += 4)

{

if (prime[i])

primelist[len++] = i;

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

{

if (i * primelist[j] > maxn)

break;

if (prime[i] && prime[primelist[j]])

sum[i*primelist[j]] = 1;

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

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

break;

}

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

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

}

int main()

{

// CFF;

PP ();

int n;

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

{

if (n == 0)

break;

printf ("%d %d\n", n, sum[n]);

}

return 0;

}

poj3273

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

15 10月 2015

Monthly Expense

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ money_i≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

Input

Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day

Output

Line 1: The smallest possible monthly limit Farmer John can afford to live with.

Sample Input

7 5
100
400
300
100
500
101
400

Sample Output

500

Hint

If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.

Source

USACO 2007 March Silver

题目类型：二分搜索

算法分析：直接二分每个fajmoonth的最大钱数，注意二分部分的写法！！！

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

int aa[maxn], n, m;

bool PP (int val)
{
    int res = 1, tt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (tt + aa[i] <= val)
        {
            tt += aa[i];
        }

        else
        {
            res++;
            tt = aa[i];
        }
    }

    if (res > m) return true;
    else return false;
}

int main()
{
//    CFF;
    while (scanf ("%d%d", &n, &m) != EOF)
    {
        int l = 0, r = 0, mid;
        for (int i = 1; i <= n; i++)
        {
            scanf ("%d", &aa[i]);
            r += aa[i];
            if (l < aa[i]) l = aa[i];
        }
        r += 5;
        while (l < r)
        {
            mid = (l + r) >> 1;
            if (PP (mid)) l = mid + 1;
            else r = mid - 1;
        }
        printf ("%d\n", r);
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

int aa[maxn], n, m;

bool PP (int val)

{

int res = 1, tt = 0;

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

{

if (tt + aa[i] <= val)

{

tt += aa[i];

}

else

{

res++;

tt = aa[i];

}

if (res > m) return true;

else return false;

}

int main()

{

// CFF;

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

{

int l = 0, r = 0, mid;

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

{

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

r += aa[i];

if (l < aa[i]) l = aa[i];

}

r += 5;

while (l < r)

{

mid = (l + r) >> 1;

if (PP (mid)) l = mid + 1;

else r = mid - 1;

}

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

}

return 0;

}

poj3258

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

15 10月 2015

River Hopscotch

Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance D_i from the start (0 < D_i < L).

To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.

Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).

FJ wants to know exactly how much he can increase the shortest distance *before* he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.

Input

Line 1: Three space-separated integers: L, N, and M
Lines 2..N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.

Output

Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks

Sample Input

25 5 2
2
14
11
21
17

Sample Output

Hint

Before removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25).

Source

USACO 2006 December Silver

题目类型：二分搜索

算法分析：二分两个石块之间的最小值，每次计算以这个值是否能够安排n-m个石块

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

int aa[maxn], L, n, m;

bool PP (int val)
{
    int res = 2, tt = 0;
    aa[n+1] = L;
    for (int i = 1; i <= n + 1; i++)
    {
        if (aa[i] - aa[tt] >= val)
        {
            res++;
            tt = i;
        }
    }

    if (res > n - m + 2) return true;
    else return false;
}

int main()
{
//    CFF;
    while (scanf ("%d%d%d", &L, &n, &m) != EOF)
    {
        for (int i = 1; i <= n; i++)
            scanf ("%d", &aa[i]);
        sort (aa + 1, aa + 1 + n);
        int l = 0, r = L + 6, mid;
        while (r - l > 1)
        {
            mid = (l + r) >> 1;
            if (PP(mid)) l = mid;
            else r = mid;
        }

        printf ("%d\n", l);
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

int aa[maxn], L, n, m;

bool PP (int val)

{

int res = 2, tt = 0;

aa[n+1] = L;

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

{

if (aa[i] - aa[tt] >= val)

{

res++;

tt = i;

}

if (res > n - m + 2) return true;

else return false;

}

int main()

{

// CFF;

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

{

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

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

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

int l = 0, r = L + 6, mid;

while (r - l > 1)

{

mid = (l + r) >> 1;

if (PP(mid)) l = mid;

else r = mid;

}

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

}

return 0;

}

BestCoder Round #59(Div.2) (0/4) (Div.1) (0/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

13 10月 2015

poj2395

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

13 10月 2015

Out of Hay

The cows have run out of hay, a horrible event that must be remedied immediately. Bessie intends to visit the other farms to survey their hay situation. There are N (2 <= N <= 2,000) farms (numbered 1..N); Bessie starts at Farm 1. She'll traverse some or all of the M (1 <= M <= 10,000) two-way roads whose length does not exceed 1,000,000,000 that connect the farms. Some farms may be multiply connected with different length roads. All farms are connected one way or another to Farm 1.

Bessie is trying to decide how large a waterskin she will need. She knows that she needs one ounce of water for each unit of length of a road. Since she can get more water at each farm, she's only concerned about the length of the longest road. Of course, she plans her route between farms such that she minimizes the amount of water she must carry.

Help Bessie know the largest amount of water she will ever have to carry: what is the length of longest road she'll have to travel between any two farms, presuming she chooses routes that minimize that number? This means, of course, that she might backtrack over a road in order to minimize the length of the longest road she'll have to traverse.

Input

* Line 1: Two space-separated integers, N and M.

* Lines 2..1+M: Line i+1 contains three space-separated integers, A_i, B_i, and L_i, describing a road from A_i to B_i of length L_i.

Output

* Line 1: A single integer that is the length of the longest road required to be traversed.

Sample Input

3 3
1 2 23
2 3 1000
1 3 43

Sample Output

Hint

OUTPUT DETAILS:

In order to reach farm 2, Bessie travels along a road of length 23. To reach farm 3, Bessie travels along a road of length 43. With capacity 43, she can travel along these roads provided that she refills her tank to maximum capacity before she starts down a road.

Source

USACO 2005 March Silver

题目类型：MST

算法分析：由题意可知直接输出MST中最大的边权即可

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

struct node {LL u, v, w;};
bool operator < (const node &a, const node &b) {return a.w < b.w;}

node edge[maxn];
LL par[maxn];
LL n, m;

LL UnFind(LL val)
{
    if(par[val] == val) return val;
    else return par[val] = UnFind (par[val]);
}

LL PP ()
{
    LL re = n, maxval = -INF;
    for (LL i = 1; i <= m && re > 1; i++)
    {
        if (UnFind(edge[i].u) != UnFind(edge[i].v))
        {
            par[UnFind(edge[i].u)] = UnFind(edge[i].v);
            maxval = max (maxval, edge[i].w);
            re--;
        }
    }
    return maxval;
}

int main()
{
//    CFF;
    while (scanf ("%lld %lld", &n, &m) != EOF)
    {
        for (int i = 1; i <= m; i++)
            scanf ("%lld%lld%lld", &edge[i].u, &edge[i].v, &edge[i].w);

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

        sort (edge + 1, edge + 1 + m);
        printf ("%lld\n", PP());
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

struct node {LL u, v, w;};

bool operator < (const node &a, const node &b) {return a.w < b.w;}

node edge[maxn];

LL par[maxn];

LL n, m;

LL UnFind(LL val)

{

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

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

}

LL PP ()

{

LL re = n, maxval = -INF;

for (LL i = 1; i <= m && re > 1; i++)

{

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

{

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

maxval = max (maxval, edge[i].w);

re--;

}

return maxval;

}

int main()

{

// CFF;

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

{

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

scanf ("%lld%lld%lld", &edge[i].u, &edge[i].v, &edge[i].w);

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

par[i] = i;

sort (edge + 1, edge + 1 + m);

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

}

return 0;

}

poj2377

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

13 10月 2015

Bad Cowtractors

Bessie has been hired to build a cheap internet network among Farmer John's N (2 <= N <= 1,000) barns that are conveniently numbered 1..N. FJ has already done some surveying, and found M (1 <= M <= 20,000) possible connection routes between pairs of barns. Each possible connection route has an associated cost C (1 <= C <= 100,000). Farmer John wants to spend the least amount on connecting the network; he doesn't even want to pay Bessie.

Realizing Farmer John will not pay her, Bessie decides to do the worst job possible. She must decide on a set of connections to install so that (i) the total cost of these connections is as large as possible, (ii) all the barns are connected together (so that it is possible to reach any barn from any other barn via a path of installed connections), and (iii) so that there are no cycles among the connections (which Farmer John would easily be able to detect). Conditions (ii) and (iii) ensure that the final set of connections will look like a "tree".

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Each line contains three space-separated integers A, B, and C that describe a connection route between barns A and B of cost C.

Output

* Line 1: A single integer, containing the price of the most expensive tree connecting all the barns. If it is not possible to connect all the barns, output -1.

Sample Input

5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17

Sample Output

Hint

OUTPUT DETAILS:

The most expensive tree has cost 17 + 8 + 10 + 7 = 42. It uses the following connections: 4 to 5, 2 to 5, 2 to 3, and 1 to 3.

Source

USACO 2004 December Silver

题目类型：MST

算法分析：仿照MST每次将最大权的边加入到图中即可

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

struct node {int u, v, w;};
bool operator < (const node &a, const node &b) {return a.w > b.w;}

node edge[maxn];
int par[maxn];
int n, m;

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

int PP ()
{
    int re = n, res = 0;
    for (int i = 1; i <= m && re > 1; i++)
    {
        if (UnFind(edge[i].u) != UnFind(edge[i].v))
        {
            par[UnFind(edge[i].u)] = UnFind(edge[i].v);
            res += edge[i].w;
            re--;
        }
    }
    if (re > 1) return -1;
    else return res;
}

int main()
{
//    CFF;
    while (scanf ("%d %d", &n, &m) != EOF)
    {
        for (int i = 1; i <= m; i++)
            scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);

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

        sort (edge + 1, edge + 1 + m);
        printf ("%d\n", PP());
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

struct node {int u, v, w;};

bool operator < (const node &a, const node &b) {return a.w > b.w;}

node edge[maxn];

int par[maxn];

int n, m;

int UnFind(int val)

{

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

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

}

int PP ()

{

int re = n, res = 0;

for (int i = 1; i <= m && re > 1; i++)

{

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

{

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

res += edge[i].w;

re--;

}

if (re > 1) return -1;

else return res;

}

int main()

{

// CFF;

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

{

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

scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);

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

par[i] = i;

sort (edge + 1, edge + 1 + m);

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

}

return 0;

}

poj3723

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

11 10月 2015

Conscription

Windy has a country, and he wants to build an army to protect his country. He has picked up N girls and M boys and wants to collect them to be his soldiers. To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these relationships to reduce his cost. If girl x and boy y have a relationship dand one of them has been collected, Windy can collect the other one with 10000-d RMB. Now given all the relationships between girls and boys, your assignment is to find the least amount of money Windy has to pay. Notice that only one relationship can be used when collecting one soldier.

Input

The first line of input is the number of test case.
The first line of each test case contains three integers, N, M and R.
Then R lines followed, each contains three integers x_i, y_i and d_i.
There is a blank line before each test case.

1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ x_i < N
0 ≤ y_i < M
0 < d_i < 10000

Output

For each test case output the answer in a single line.

Sample Input

5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781

5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133

Sample Output

71071

54223

Source

POJ Monthly Contest – 2009.04.05, windy7926778

题目类型：MST

算法分析：看上去需要使用二分图来求，事实上直接将每个边权取负，求解一个MST即可

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

struct node{ int u, v, w;};

bool operator < (const node &a, const node &b) {return a.w < b.w;}

node aa[maxn];
int parent[maxn], n1, n2, m, t;

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

int PP ()
{
    int re = n1 + n2, res = 0;
    for (int i = 1; i <= m && re > 1; i++)
    {
        if (UnFind (aa[i].u) != UnFind(aa[i].v))
        {
            parent[UnFind(aa[i].u)] = UnFind (aa[i].v);
            res += aa[i].w;
            re--;
        }
    }
    return res;
}


int main()
{
//    CFF;
    scanf ("%d", &t);
    while (t--)
    {
        for (int i = 0; i < maxn; i++) parent[i] = i;

        scanf ("%d %d %d", &n1, &n2, &m);
        for (int i = 1; i <= m; i++)
        {
            scanf ("%d %d %d", &aa[i].u, &aa[i].v, &aa[i].w);
            aa[i].v += n1;
            aa[i].w = -aa[i].w;
        }

        sort (aa + 1, aa + 1 + m);
        printf ("%d\n", 10000 * (n1 + n2) + PP ());
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5e5 + 66;

struct node{ int u, v, w;};

bool operator < (const node &a, const node &b) {return a.w < b.w;}

node aa[maxn];

int parent[maxn], n1, n2, m, t;

int UnFind (int val)

{

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

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

}

int PP ()

{

int re = n1 + n2, res = 0;

for (int i = 1; i <= m && re > 1; i++)

{

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

{

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

res += aa[i].w;

re--;

}

return res;

}

int main()

{

// CFF;

scanf ("%d", &t);

while (t--)

{

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

scanf ("%d %d %d", &n1, &n2, &m);

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

{

scanf ("%d %d %d", &aa[i].u, &aa[i].v, &aa[i].w);

aa[i].v += n1;

aa[i].w = -aa[i].w;

}

sort (aa + 1, aa + 1 + m);

printf ("%d\n", 10000 * (n1 + n2) + PP ());

}

return 0;

}

poj3255

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

11 10月 2015

Roadblocks

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

Input

Line 1: Two space-separated integers: N and R
Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

Output

Line 1: The length of the second shortest path between node 1 and node N

Sample Input

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

Hint

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

Source

USACO 2006 November Gold

题目类型：次短路

算法分析：直接使用Dijkstra算法同时维护最短路和次短路，若能够更新最短路则先更新最短路，然后再更新次短路

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

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

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

vector <PII> edge[maxn];
int n, dis[maxn][2];//n表示节点的个数，dis[i][0]表示从源点到i的最短路，dis[i][1]表示从源点到i的次短路

void Dijkstra (int s)
{
    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < 2; j++)
            dis[i][j] = INF;

    dis[s][0] = 0;//源点到自己的最短路是0，十分重要!!!
    priority_queue <PII, vector <PII>, greater <PII> > qu;
    qu.push (PII (0, s));
    while (!qu.empty ())
    {
        PII ta = qu.top (); qu.pop ();
        int v1 = ta.second, d1 = ta.first;
        if (dis[v1][1] < d1) continue;
        for (int i = 0; i < edge[v1].size (); i++)
        {
            PII tb = edge[v1][i];
            int v2 = tb.first, w2 = tb.second;
            int d2 = d1 + w2;
            if (dis[v2][0] > d2)
            {
                swap (dis[v2][0], d2);
                qu.push (PII (dis[v2][0], v2));
            }

            if (dis[v2][0] < d2 && dis[v2][1] > d2)
            {
                dis[v2][1] = d2;
                qu.push (PII (dis[v2][1], v2));
            }
        }
    }
}


int main()
{
//    CFF;
    int m;
    while (scanf ("%d %d", &n, &m) != EOF)
    {
        for (int i = 0; i < maxn; i++) edge[i].clear ();

        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            scanf ("%d %d %d", &u, &v, &w);
            edge[u].PB (PII (v, w));
            edge[v].PB (PII (u, w));
        }

        Dijkstra (1);
        printf ("%d\n", dis[n][1]);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

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

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5e3 + 66;

vector <PII> edge[maxn];

int n, dis[maxn][2];//n表示节点的个数，dis[i][0]表示从源点到i的最短路，dis[i][1]表示从源点到i的次短路

void Dijkstra (int s)

{

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

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

dis[i][j] = INF;

dis[s][0] = 0;//源点到自己的最短路是0，十分重要!!!

priority_queue <PII, vector <PII>, greater <PII> > qu;

qu.push (PII (0, s));

while (!qu.empty ())

{

PII ta = qu.top (); qu.pop ();

int v1 = ta.second, d1 = ta.first;

if (dis[v1][1] < d1) continue;

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

{

PII tb = edge[v1][i];

int v2 = tb.first, w2 = tb.second;

int d2 = d1 + w2;

if (dis[v2][0] > d2)

{

swap (dis[v2][0], d2);

qu.push (PII (dis[v2][0], v2));

}

if (dis[v2][0] < d2 && dis[v2][1] > d2)

{

dis[v2][1] = d2;

qu.push (PII (dis[v2][1], v2));

}

int main()

{

// CFF;

int m;

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

{

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

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

{

int u, v, w;

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

edge[u].PB (PII (v, w));

edge[v].PB (PII (u, w));

}

Dijkstra (1);

printf ("%d\n", dis[n][1]);

}

return 0;

}

poj2393

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

10 10月 2015

Yogurt factory

The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the next N (1 <= N <= 10,000) weeks, the price of milk and labor will fluctuate weekly such that it will cost the company C_i (1 <= C_i <= 5,000) cents to produce one unit of yogurt in week i. Yucky's factory, being well-designed, can produce arbitrarily many units of yogurt each week.

Yucky Yogurt owns a warehouse that can store unused yogurt at a constant fee of S (1 <= S <= 100) cents per unit of yogurt per week. Fortuitously, yogurt does not spoil. Yucky Yogurt's warehouse is enormous, so it can hold arbitrarily many units of yogurt.

Yucky wants to find a way to make weekly deliveries of Y_i (0 <= Y_i <= 10,000) units of yogurt to its clientele (Y_i is the delivery quantity in week i). Help Yucky minimize its costs over the entire N-week period. Yogurt produced in week i, as well as any yogurt already in storage, can be used to meet Yucky's demand for that week.

Input

* Line 1: Two space-separated integers, N and S.

* Lines 2..N+1: Line i+1 contains two space-separated integers: C_i and Y_i.

Output

* Line 1: Line 1 contains a single integer: the minimum total cost to satisfy the yogurt schedule. Note that the total might be too large for a 32-bit integer.

Sample Input

4 5
88 200
89 400
97 300
91 500

Sample Output

126900

Hint

OUTPUT DETAILS:
In week 1, produce 200 units of yogurt and deliver all of it. In week 2, produce 700 units: deliver 400 units while storing 300 units. In week 3, deliver the 300 units that were stored. In week 4, produce and deliver 500 units.

Source

USACO 2005 March Gold

题目类型：贪心

算法分析：首先第一个用户需求一定要使用第一周生产的，之后的比较(aa[i-1] + s)和aa[i]的大小，选择其中较小的乘上第i周的用户需求即可

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

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

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

LL aa[maxn], bb[maxn];

int main()
{
//    CFF;
    LL n, s;
    while (scanf("%lld%lld", &n, &s) != EOF)
    {
        for (LL i = 1; i <= n; i++)
            scanf ("%lld %lld", &aa[i], &bb[i]);

        LL res = aa[1] * bb[1];
        for (LL i = 2; i <= n; i++)
        {
            if (aa[i-1] + s < aa[i])
                res += (aa[i-1] + s) * bb[i];

            else res += aa[i] * bb[i];
        }

        printf ("%lld\n", res);
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

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

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5e4 + 66;

LL aa[maxn], bb[maxn];

int main()

{

// CFF;

LL n, s;

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

{

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

scanf ("%lld %lld", &aa[i], &bb[i]);

LL res = aa[1] * bb[1];

for (LL i = 2; i <= n; i++)

{

if (aa[i-1] + s < aa[i])

res += (aa[i-1] + s) * bb[i];

else res += aa[i] * bb[i];

}

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

}

return 0;

}

Codeforces Round #324(Div.2) (2/5)

maksyuki 发表于比赛分类，标签: 比赛-codeforces

10 10月 2015

A Olesya and Rodion

Olesya loves numbers consisting of n digits, and Rodion only likes numbers that are divisible by t. Find some number that satisfies both of them.Your task is: given the n and t print an integer strictly larger than zero consisting of n digits that is divisible by t. If such number doesn't exist, print - 1.

Input

The single line contains two numbers, n and t (1 ≤ n ≤ 100, 2 ≤ t ≤ 10) — the length of the number and the number it should be divisible by.

Output

Print one such positive number without leading zeroes, — the answer to the problem, or - 1, if such number doesn't exist. If there are multiple possible answers, you are allowed to print any of them.

Sample test(s)

input

3 2

output

712

题目类型：简单数学

算法分析：若t小于10，则一定存在满足条件的n位数，此时直接输出即可，若t等于10，且此时n为1，则输出-1，否则按照条件输出

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

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

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

int main()
{
//    CPPFF;
    int n, t;
    cin >> n >>t;
    if (t >= 2 && t <= 9)
    {
        for (int i = 1; i <= n; i++)
            cout << t;
        cout << endl;
    }

    else
    {
        if (n == 1)
            cout << "-1" << endl;

        else
        {
            for (int i = 1; i <= n / 2; i++)
                cout << t;

            if (n & 1)
                cout << "0";

            cout << endl;
        }
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

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

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6666;

int main()

{

// CPPFF;

int n, t;

cin >> n >>t;

if (t >= 2 && t <= 9)

{

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

cout << t;

cout << endl;

}

else

{

if (n == 1)

cout << "-1" << endl;

else

{

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

cout << t;

if (n & 1)

cout << "0";

cout << endl;

}

return 0;

}

B Kolya and Tanya

Kolya loves putting gnomes at the circle table and giving them coins, and Tanya loves studying triplets of gnomes, sitting in the vertexes of an equilateral triangle.

More formally, there are 3n gnomes sitting in a circle. Each gnome can have from 1 to 3 coins. Let's number the places in the order they occur in the circle by numbers from 0 to 3n - 1, let the gnome sitting on the i-th place havea_i coins. If there is an integer i (0 ≤ i < n) such that a_i + a_i_+ n + a_i_+ 2n ≠ 6, then Tanya is satisfied.

Count the number of ways to choose a_i so that Tanya is satisfied. As there can be many ways of distributing coins, print the remainder of this number modulo 10⁹ + 7. Two ways, a and b, are considered distinct if there is index i(0 ≤ i < 3n), such that a_i ≠ b_i (that is, some gnome got different number of coins in these two ways).

Input

A single line contains number n (1 ≤ n ≤ 10⁵) — the number of the gnomes divided by three.

Output

Print a single number — the remainder of the number of variants of distributing coins that satisfy Tanya modulo10⁹ + 7.

Sample test(s)

input

output

input

output

680

Note

20 ways for n = 1 (gnome with index 0 sits on the top of the triangle, gnome 1 on the right vertex, gnome 2 on the left vertex):

题目类型：组合计数

算法分析：简单分析可以推出公式为(27 ^ n - 7 ^ n) % MOD，注意最后相减时要先加上一个MOD再取模，防止结果出现负数！！！

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

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

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

LL mod_f (LL a, LL b, LL mod)
{
    LL res = 1;
    LL tt = (a + mod) % mod;
    while (b)
    {
        if (b & 1)
            res = res * tt % mod;

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

int main()
{
//    CPPFF;
    LL n;
    cin >> n;
    LL resa = mod_f ((LL) 27, n, MOD);
    LL resb = mod_f ((LL) 7, n, MOD);
    cout << (resa - resb + MOD) % MOD << endl;
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

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

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e4 + 6666;

LL mod_f (LL a, LL b, LL mod)

{

LL res = 1;

LL tt = (a + mod) % mod;

while (b)

{

if (b & 1)

res = res * tt % mod;

b >>= 1;

tt = tt * tt % mod;

}

return res;

}

int main()

{

// CPPFF;

LL n;

cin >> n;

LL resa = mod_f ((LL) 27, n, MOD);

LL resb = mod_f ((LL) 7, n, MOD);

cout << (resa - resb + MOD) % MOD << endl;

return 0;

}

1 2 下一页最后一页

超客的水墨烟雨

poj1426

poj1376

poj3684

poj1190

poj2739

poj3421

poj3292

poj3273

poj3258

BestCoder Round #59(Div.2) (0/4) (Div.1) (0/4)

poj2395

poj2377

poj3723

poj3255

poj2393

Codeforces Round #324(Div.2) (2/5)

分类目录

标签云

书签

近期评论

2015年10月
一	二	三	四	五	六	日
« 9月				11月 »
			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	31