/************************************************
* Author :Running_Time
* Created Time :2015/10/12 星期一 16:49:42
* File Name :A.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e2 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int a[N];
int main(void) {
int n; scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
}
int ans = 0, i = 1;
bool fir = true;
while (i <= n) {
if (a[i] == 0) {
if (fir) {
i++; continue;
}
else {
int j = i + 1;
while (j <= n) {
if (a[j] == 0) {
j++;
}
else break;
}
if (j == n + 1) break;
if (j - i >= 2) {
i = j; continue;
}
else {
ans += j - i;
i = j;
}
}
}
else { //a[i] = 1;
fir = false;
ans++; i++;
}
}
printf ("%d
", ans);
return 0;
}
/************************************************
* Author :Running_Time
* Created Time :2015/10/12 星期一 16:49:42
* File Name :B.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 55;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int a1[N], a2[N], b[N];
int sum1[N], sum2[N];
bool vis[N];
int main(void) {
int n; scanf ("%d", &n);
for (int i=1; i<n; ++i) {
scanf ("%d", &a1[i]);
}
for (int i=1; i<n; ++i) {
scanf ("%d", &a2[i]);
}
for (int i=1; i<=n; ++i) {
scanf ("%d", &b[i]);
}
if (n == 2) {
printf ("%d
", a1[1] + a2[1] + b[1] + b[2]);
return 0;
}
for (int i=1; i<n; ++i) {
sum1[i] = sum1[i-1] + a1[i];
}
for (int i=n-1; i>=1; --i) {
sum2[i] = sum2[i+1] + a2[i];
}
int mn = INF, id = 0;
int ans = 0;
for (int i=0; i<n; ++i) {
if (sum1[i] + b[i+1] + sum2[i+1] < mn) {
mn = sum1[i] + b[i+1] + sum2[i+1];
id = i;
}
}
vis[id] = true; ans += mn;
mn = INF, id = 0;
for (int i=0; i<n; ++i) {
if (sum1[i] + b[i+1] + sum2[i+1] < mn && !vis[i]) {
mn = sum1[i] + b[i+1] + sum2[i+1];
id = i;
}
}
ans += mn;
printf ("%d
", ans);
return 0;
}
暴力+队列 C - Gennady the Dentist
题意：小孩子排队看医生，有一定的连锁反应，问医生最后能治好多少人
分析：开始想用D保存d[]的和，无奈被hack掉了，还是老老实实用队列吧
/************************************************
* Author :Running_Time
* Created Time :2015/10/12 星期一 16:49:42
* File Name :C.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 4e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int v[N], d[N], p[N];
bool dead[N];
int main(void) {
int n; scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%d%d%d", &v[i], &d[i], &p[i]);
dead[i] = false;
}
vector<int> ans;
queue<int> Q;
for (int i=1; i<=n; ++i) {
if (!dead[i]) {
ans.push_back (i);
for (int j=i+1; j<=n; ++j) {
if (dead[j]) continue;
p[j] -= v[i]; v[i]--;
if (p[j] < 0) {
dead[j] = true;
Q.push (j);
}
if (v[i] <= 0) break;
}
}
while (!Q.empty ()) {
int x = Q.front (); Q.pop ();
for (int j=x+1; j<=n; ++j) {
if (dead[j]) continue;
p[j] -= d[x];
if (p[j] < 0) {
dead[j] = true;
Q.push (j);
}
}
}
}
printf ("%d
", ans.size ());
for (int i=0; i<ans.size (); ++i) {
printf ("%d%c", ans[i], i == ans.size () - 1 ? '
' : ' ');
}
return 0;
}
题意：一个人从左边走到右边，同时有列车从右边开过来，问这个人能否达到右边没有碰到列车
分析：简答的BFS，车看作不动，人相对车有一个相对运动，还是要用vis标记已访问过的点，比赛时这点忘了，MLE了
/************************************************
* Author :Running_Time
* Created Time :2015/10/12 星期一 16:49:42
* File Name :D.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e2 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
char maze[4][N];
bool vis[4][N];
int dx[3] = {-1, 0, 1};
int n, k;
bool BFS(int sx, int sy) {
queue<pair<int, int> > Q; Q.push (make_pair (sx, sy));
memset (vis, false, sizeof (vis)); vis[sx][sy] = true;
while (!Q.empty ()) {
int x = Q.front ().first, y = Q.front ().second; Q.pop ();
if (y >= n) return true;
if (y + 1 <= n && maze[x][y+1] != '.') continue;
for (int i=0; i<3; ++i) {
int tx = x + dx[i], ty = y + 1;
if (tx < 1 || tx > 3 || maze[tx][ty] != '.') continue;
ty += 1;
if (ty <= n && maze[tx][ty] != '.') continue;
ty += 1;
if (ty <= n && maze[tx][ty] != '.') continue;
if (vis[tx][ty]) continue;
vis[tx][ty] = true;
Q.push (make_pair (tx, ty));
}
}
return false;
}
int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d%d", &n, &k);
for (int i=1; i<=3; ++i) {
scanf ("%s", maze[i] + 1);
}
int sx = 0, sy = 0;
for (int i=1; i<=3; ++i) {
if (maze[i][1] == 's') {
sx = i; sy = 1;
break;
}
}
for (int i=n+1; i<=n+6; ++i) {
maze[1][i] = maze[2][i] = maze[3][i] = '.';
}
printf ("%s
", BFS (sx, sy) ? "YES" : "NO");
}
return 0;
}