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

poj3669

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

01 10月 2015

Meteor Shower

Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.

The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (X_i, Y_i) (0 ≤ X_i≤ 300; 0 ≤ Y_i≤ 300) at time T_i (0 ≤ T_i ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.

Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).

Determine the minimum time it takes Bessie to get to a safe place.

Input

* Line 1: A single integer: M
* Lines 2..M+1: Line i+1 contains three space-separated integers: X_i, Y_i, and T_i

Output

* Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

Sample Input

4
0 0 2
2 1 2
1 1 2
0 3 5

Sample Output

Source

USACO 2008 February Silver

题目类型：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 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;

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

struct node
{
    int x, y, t;
    node (int xx, int yy, int tt) : x (xx), y (yy), t (tt) {}
    node () {}
};

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

int pp;
node aa[maxn];
bool vis[366][366], vvis[366][366];

inline bool Ok (int x, int y)
{
    if (x >= 0 && y >= 0 && !vis[x][y])
        return true;

    return false;
}

void PP (int t)
{
    while (aa[pp].t <= t)
    {
        vis[aa[pp].x][aa[pp].y] = true;
        for (int i = 0; i < 4; i++)
        {
            int tx = aa[pp].x + dx[i], ty = aa[pp].y + dy[i];
            if (tx >= 0 && ty >= 0)
                vis[tx][ty] = true;
        }
        pp++;
    }
}


int bfs (int x, int y, int t)
{
    memset (vis, false, sizeof (vis));
    queue <node> qu;
    qu.push (node (x, y, t));
    vis[x][y] = true;
    pp = 1;
    PP (0);
    while (!qu.empty ())
    {
        node temp = qu.front ();
        qu.pop ();

        PP (temp.t+1);

        if (!vvis[temp.x][temp.y])
        {
            return temp.t;
        }

        for (int i = 0; i < 4; i++)
        {
            int tx = temp.x + dx[i], ty = temp.y + dy[i];
            if (Ok (tx, ty))
            {
                qu.push (node (tx, ty, temp.t + 1));
                vis[tx][ty] = true;
            }
        }
    }
    return -1;
}


int main()
{
//    CFF;
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        memset (vvis, false, sizeof (vvis));
        for (int i = 1; i <= n; i++)
        {
            scanf ("%d%d%d", &aa[i].x, &aa[i].y, &aa[i].t);
            vvis[aa[i].x][aa[i].y] = true;
            for (int j = 0; j < 4; j++)
            {
                int tx = aa[i].x + dx[j], ty = aa[i].y + dy[j];
                if (tx >= 0 && ty >= 0)
                    vvis[tx][ty] = true;
            }
        }
        sort (aa + 1, aa + 1 + n);
        printf ("%d\n", bfs (0, 0, 0));
    }
    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

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

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

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

struct node

{

int x, y, t;

node (int xx, int yy, int tt) : x (xx), y (yy), t (tt) {}

node () {}

};

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

int pp;

node aa[maxn];

bool vis[366][366], vvis[366][366];

inline bool Ok (int x, int y)

{

if (x >= 0 && y >= 0 && !vis[x][y])

return true;

return false;

}

void PP (int t)

{

while (aa[pp].t <= t)

{

vis[aa[pp].x][aa[pp].y] = true;

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

{

int tx = aa[pp].x + dx[i], ty = aa[pp].y + dy[i];

if (tx >= 0 && ty >= 0)

vis[tx][ty] = true;

}

pp++;

}

int bfs (int x, int y, int t)

{

memset (vis, false, sizeof (vis));

queue <node> qu;

qu.push (node (x, y, t));

vis[x][y] = true;

pp = 1;

PP (0);

while (!qu.empty ())

{

node temp = qu.front ();

qu.pop ();

PP (temp.t+1);

if (!vvis[temp.x][temp.y])

{

return temp.t;

}

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

{

int tx = temp.x + dx[i], ty = temp.y + dy[i];

if (Ok (tx, ty))

{

qu.push (node (tx, ty, temp.t + 1));

vis[tx][ty] = true;

}

return -1;

}

int main()

{

// CFF;

int n;

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

{

memset (vvis, false, sizeof (vvis));

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

{

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

vvis[aa[i].x][aa[i].y] = true;

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

{

int tx = aa[i].x + dx[j], ty = aa[i].y + dy[j];

if (tx >= 0 && ty >= 0)

vvis[tx][ty] = true;

}

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

printf ("%d\n", bfs (0, 0, 0));

}

return 0;

}

poj2431

maksyuki 发表于 oj 分类，标签: 基础算法-贪心, 数据结构-队列\双端\单调\优先

01 10月 2015

Expedition

A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck's fuel tank. The truck 阅读全文 »

poj3069

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

01 10月 2015

Saruman's Army

Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir 阅读全文 »

poj3617

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

01 10月 2015

Best Cow Line

FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.

The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows' names.

FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.

FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he's finished, FJ takes his cows for registration in this new order.

Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single initial ('A'..'Z') of the cow in the ith position in the original line

Output

The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the new line.

Sample Input

Sample Output

ABCBCD

Source

USACO 2007 November Silver

题目类型：贪心

算法分析：如果头的字符比末尾的字符小，则输出头的字符，如果头的字符大于末尾的字符，则输出末尾的字符。如果相等，则需要找到第一个不相等的字符，然后输出这个字符是从头尾所走到的那个相同字符，注意最后输出的格式！！！

#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 = 2e3 + 6;

char aa[maxn];

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

        int pa = 1, pb = n;
        int cnt = 0;
        while (pa <= pb)
        {
            bool is_left = false;
            for (int i = 0; pa + i <= pb; i++)
            {
                if (aa[pa+i] < aa[pb-i]) {is_left = true; break;}
                if (aa[pa+i] > aa[pb-i]) {is_left = false; break;}
            }

            if (cnt && cnt % 80 == 0)
                puts ("");

            if (is_left) printf ("%c", aa[pa++]);
            else printf ("%c", aa[pb--]);
            cnt++;
        }
        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 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 = 2e3 + 6;

char aa[maxn];

int main()

{

// CFF;

int n;

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

{

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

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

int pa = 1, pb = n;

int cnt = 0;

while (pa <= pb)

{

bool is_left = false;

for (int i = 0; pa + i <= pb; i++)

{

if (aa[pa+i] < aa[pb-i]) {is_left = true; break;}

if (aa[pa+i] > aa[pb-i]) {is_left = false; break;}

}

if (cnt && cnt % 80 == 0)

puts ("");

if (is_left) printf ("%c", aa[pa++]);

else printf ("%c", aa[pb--]);

cnt++;

}

puts ("");

}

return 0;

}

超客的水墨烟雨

poj3669

poj2431

poj3069

poj3617

分类目录

标签云

书签

近期评论

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