4001 模拟题，仔细一点可以1A。我的代码有点长，但思路很清楚。
#include<stdio.h>
#include<string.h>
bool vis[11][11];
int dir[4][2] = {1, 0, -1, 0, 0, -1, 0, 1};
int d[8][2] = {2, 1, 2, -1, -2, 1, -2, -1, 1, 2, 1, -2, -1, 2, -1, -2};
int dd[8][2] = {1, 0, 1, 0, -1, 0, -1, 0, 0, 1, 0, -1, 0, 1, 0, -1};
int main()
{
int x[8], y[8], kind[8], xx, yy;
int i, j, u;
char buf[5];
int n;
while( ~scanf("%d%d%d", &n, &xx, &yy))
{
if(!n && !xx && !yy) break;
memset(vis, 0, sizeof(vis));
for(i = 0; i < n; i++)
{
scanf("%s%d%d",buf, &x[i], &y[i]);
if(buf[0] == 'G') kind[i] = 0, u = i;
if(buf[0] == 'R') kind[i] = 1;
if(buf[0] == 'H') kind[i] = 2;
if(buf[0] == 'C') kind[i] = 3;
vis[x[i]][y[i]] = 1;
}
if(u != 0)
{
int tmp;
tmp = kind[u]; kind[u] = kind[0]; kind[0] = tmp;
tmp = x[u]; x[u] = x[0]; x[0] = tmp;
tmp = y[u]; y[u] = y[0]; y[0] = tmp;
}
if(y[0] == yy)
{
for(i = xx + 1; i < x[0] && !vis[i][yy]; i++);
if(i == x[0]) {puts("NO"); continue;}
}
bool ok = 0, flag;
for(i = 0; i < 4; i++)
{
int fx = xx + dir[i][0];
int fy = yy + dir[i][1];
if(fx < 1 || fx > 3 || fy < 4 || fy > 6)
continue;
flag = 0;
for(j = 0; j < n; j++)
{
if(fx == x[j] && fy == y[j]) continue;
if(kind[j] == 0)
{
if(y[j] == fy)
{
for(u = fx + 1; u < x[j] && !vis[u][fy]; u++);
if(u == x[j]) { flag = 1; break; }
}
}
if(kind[j] == 1)
{
if(y[j] == fy)
{
if(fx < x[j])
{
for(u = fx + 1; u < x[j] && ! vis[u][fy]; u++);
if(u == x[j]){ flag = 1; break; }
}
else
{
for(u = x[j] + 1; u < fx && !vis[u][fy]; u++);
if(u == fx) { flag = 1; break; }
}
}
if(x[j] == fx)
{
if(y[j] < fy)
{
for(u = y[j] + 1; u < fy && !vis[fx][u]; u++);
if(u == fy) { flag = 1; break; }
}
else
{
for(u = fy + 1; u < y[j] && !vis[fx][u]; u++);
if(u == y[j]) { flag = 1; break; }
}
}
}
if(kind[j] == 2)
{
for(u = 0; u < 8; u++)
{
int dx = x[j] + d[u][0];
int dy = y[j] + d[u][1];
if(dx <= 0 || dx > 10 || dy <= 0 || dy > 9) continue;
int ddx = x[j] + dd[u][0];
int ddy = y[j] + dd[u][1];
if(vis[ddx][ddy]) continue;
if(dx == fx && dy == fy) {flag = 1; break;}
}
if(flag) break;
}
if(kind[j] == 3)
{
int cnt = 0;
if(x[j] == fx)
{
if(y[j] < fy)
{
for(u = y[j] + 1; u < fy; u++)
if(vis[fx][u]) cnt++;
if(cnt == 1) {flag = 1; break;}
}
else
{
for(u = fy + 1; u < y[j]; u++)
if(vis[fx][u]) cnt++;
if(cnt == 1) {flag = 1; break;}
}
}
if(y[j] == fy)
{
if(x[j] < fx)
{
for(u = x[j] + 1; u < fx; u++)
if(vis[u][fy]) cnt++;
if(cnt == 1) {flag = 1; break;}
}
else
{
for(u = fx + 1; u < x[j]; u++)
if(vis[u][fy]) cnt++;
if(cnt == 1) {flag = 1; break;}
}
}
}
if(flag) break;
}
if(flag) continue;
else { puts("NO"); ok = 1; break; }
}
if(!ok) puts("YES");
}
return 0;
}
4002 计算时间函数 + 单调队列
#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
struct node
{
int time, num;
}cus[2504];
int n, m;
int t, s;
//计算时间
char month[13][5] = { "123", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov" ,"Dec"};
int find(char s[])
{
int i;
for(i = 1; i <= 12; i++)
if(strcmp(s, month[i]) == 0) return i;
}
int run(int x)
{
return x % 400 == 0 || x % 4 == 0 && x % 100 ;
}
int day[2][13] = { { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
, { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 } };
int solve(int x, int y, int z, int w)//x, y, z, w 年，月，日，时
{
bool flag;
int ret = 0;
int i;
for(i = 2000; i < x ; i++)
{
flag = run(i);
ret += 365 * 24;
if(flag) ret += 24;
}
flag = run(x);
for(i = 1; i < y; i++)
ret += day[flag][i] * 24;
ret += (z - 1) * 24 + w;
return ret;
}
struct DEQUE
{
int pos, val;
}que[2504];
int main()
{
int i, j;
int x, y, z, w;
char buf[5];
while( ~scanf("%d%d", &n, &m))
{
if(!n && !m) break;
for(i = 0; i < n; i++)
{
scanf("%s%d%d%d%d", buf, &z, &x, &w, &cus[i].num);
cus[i].time = solve(x, find(buf), z, w);
}
scanf("%d%d", &t, &s);
int tail = -1, head = 0;
int k = 0;
__int64 ans = 0;
for(i = 0; i < m; i++)
{
scanf("%d", &x);
while(head <= tail && que[tail].val + (i - que[tail].pos ) * s >= x)
tail--;
que[++tail].pos = i;
que[tail].val = x;
while(k < n && cus[k].time == i)
{
while(head <= tail && i - que[head].pos > t) head++;
ans += ( que[head].val + (i - que[head].pos) * s )* cus[k].num;
k++;
}
}
printf("%I64d\n", ans);
}
return 0;
}
4003 树形DP + （单调队列 或 RMQ）
树形DP 跟 HDU 2196 完全一样。
http://www.cnblogs.com/ACMan/archive/2012/10/05/2712425.html
我用了单调队列，RMQ正在学习中
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 50003
int f1[maxn], f2[maxn];
int g1[maxn], g2[maxn];
int n, m;
struct E
{
int v, next, w;
}edge[maxn<<1];
int head[maxn], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof(int)*(n+1));
}
void add(int s, int t, int w)
{
edge[tot].v = t;
edge[tot].w = w;
edge[tot].next = head[s];
head[s] = tot++;
}
int maxz(int a, int b)
{
return a > b ? a : b;
}
int minz(int a, int b)
{
return a < b ? a : b;
}
void dfs1(int u, int pre)
{
int i;
f1[u] = f2[u] = 0;
for(i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(v == pre) continue;
int w = edge[i].w;
dfs1(v, u);
if(f2[u] < f1[v] + w)
{
f2[u] = f1[v] + w;
g2[u] = v;
if(f2[u] > f1[u])
{
swap(f2[u], f1[u]);
swap(g2[u], g1[u]);
}
}
}
}
void dfs2(int u, int pre)
{
int i;
for(i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(v == pre) continue;
int w = edge[i].w;
if(g1[u] == v)
{
if(f2[v] < f2[u] + w)
{
f2[v] = f2[u] + w;
g2[v] = u;
if(f1[v] < f2[v])
{
swap(f1[v], f2[v]);
swap(g1[v], g2[v]);
}
}
}
else
{
if(f2[v] < f1[u] + w)
{
f2[v] = f1[u] + w;
g2[v] = u;
if(f1[v] < f2[v])
{
swap(f1[v], f2[v]);
swap(g1[v], g2[v]);
}
}
}
dfs2(v, u);
}
}
struct DEQUE
{
int pos, val;
}que1[maxn], que2[maxn];
int main()
{
int i, j;
int x, y, z;
int Q;
while( ~scanf("%d%d", &n, &m))
{
if(!n && !m) break;
init();
for(i = 2; i <= n; i++)
{
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
dfs1(1, -1);
//for(i = 1; i <= n; i++)
// printf("f1[%d] = %d f2[%d] = %d\n", i, f1[i], i , f2[i]);
dfs2(1, -1);
//for(i = 1; i <= n; i++)
// printf("f1[%d] = %d\n", i, f1[i]);
int h1, h2, t1, t2;
int ans;
while(m--)
{
scanf("%d", &Q);
h1 = h2 = 1; t1 = t2 = 0; ans = 1;
for(i = 1; i <= n; i++)
{
while(h1 <= t1 && que1[t1].val >= f1[i])
t1--;
que1[++t1].pos = i;
que1[t1].val = f1[i];
while(h1 <= t1 && abs(que1[t1].val - que1[h1].val) > Q)
h1++;
while(h2 <= t2 && que2[t2].val <= f1[i])
t2--;
que2[++t2].pos = i;
que2[t2].val = f1[i];
while(h2 <= t2 && abs(que2[t2].val - que2[h2].val) > Q)
h2++;
ans = maxz(ans, i - maxz(que1[h1-1].pos, que2[h2-1].pos));
}
printf("%d\n", ans);
}
}
return 0;
}
需要努力，好多东西需要学.....加油