正文
2011 Asia Fuzhou Regional Contest
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Xiangqi http://acm.hdu.edu.cn/showproblem.php?pid=4121
模拟,用高内聚低耦合的思想来写模拟题还是很好的，提高了函数的可重用性，程序的可读性，正确性，总而言之，写函数麻烦，总比debug麻烦来的好。
#include<cstdio>
const int M=;
struct point{
int x,y;
}p[M];
char has[M][M],op[M];
bool vis[M][M];
int dx[]={-,,,};
int dy[]={,,-,};
bool insidemap(const point &a){
if(a.x>=&&a.x<=&&a.y>=&&a.y<=) return true;return false;
}
void flag(const point &a){
vis[a.x][a.y]=true;
}
bool had(const point &a){
if(has[a.x][a.y]!='.') return true;return false;
}
void step(point &a,int dir){
a.x+=dx[dir];
a.y+=dy[dir];
}
void solveG(point a){
while(true){
step(a,);
if(!insidemap(a)) return ;
flag(a);
if(had(a)) return ;
}
}
void solveR(const point &b){
for(int i=;i<;i++){
point a=b;
while(true){
step(a,i);
if(!insidemap(a)) break;
flag(a);
if(had(a)) break;
}
}
}
void solveH(const point &b){
for(int i=;i<;i++){
point a=b;
step(a,i);
if(had(a)) continue;
step(a,i);
if(i<){
for(int j=;j<;j++){
point c=a;
step(c,j);
if(insidemap(c)) flag(c);
}
}
else{
for(int j=;j<;j++){
point c=a;
step(c,j);
if(insidemap(c)) flag(c);
}
}
}
}
void solveC(const point &b){
for(int i=;i<;i++){
point a=b;
while(true){
step(a,i);
if(!insidemap(a)||had(a)) break;
}
while(true){
step(a,i);
if(!insidemap(a)) break;
flag(a);
if(had(a)) break;
}
}
}
bool insidehouse(const point &a){
if(a.x>=&&a.x<=&&a.y>=&&a.y<=) return true;return false;
}
bool judge(const point &b){
for(int i=;i<;i++){
point a=b;
step(a,i);
if(insidehouse(a)&&!vis[a.x][a.y]) return false;
}
return true;
}
int main(){
int n;
while(~scanf("%d%d%d",&n,&p[].x,&p[].y),n|p[].x|p[].y){
for(int i=;i<=;i++){
for(int j=;j<=;j++){
has[i][j]='.';
vis[i][j]=false;
}
}
for(int i=;i<=n;i++){
scanf("%s%d%d",op,&p[i].x,&p[i].y);
has[p[i].x][p[i].y]=op[];
}
for(int i=;i<=n;i++){
op[]=has[p[i].x][p[i].y];
if(op[]=='G'){
solveG(p[i]);
}
else if(op[]=='R'){
solveR(p[i]);
}
else if(op[]=='H'){
solveH(p[i]);
}
else{
solveC(p[i]);
}
}
puts(judge(p[])?"YES":"NO");
}
return ;
}
Alice's mooncake shop http://acm.hdu.edu.cn/showproblem.php?pid=4122
订单按顺序来，然后对第一个订单，暴力算，然后记录一下最小的id，第二个就可以从上一个订单时刻往后找，因为前面已经找过了，单调队列的思想。
#include<cstdio>
#include<cstring>
typedef __int64 LL;
const LL inf=0x3f3f3f3f3f3f3f3fLL;
const int M=;
struct Date {
int year, month, day;
}now;
int days[]= {,,,,,,,,,,,}; //日期函数
class DATE {
public:
int leap(int year) { //判闰年
return (year%==&&year%!=)||year%==;
}
int date2int(Date a) { //日期转天数偏移
int ret=a.year*+(a.year-)/-(a.year-)/+(a.year-)/;
days[]+=leap(a.year);
for(int i=; i<a.month-; ret+=days[i++]);
days[]=;
return ret+a.day;
}
} help;
char yuefen[M][M]={"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov" , "Dec"};
char month[M];
struct IN{
LL time,R;
}in[];
int cost[];
int main(){
int n,m,data,year,H,R;
LL T,S;
now.year=;
now.month=now.day=;
int preday=help.date2int(now);
while(~scanf("%d%d",&n,&m),n|m){
int s=,t=;
for(int i=;i<n;i++){
scanf("%s%d%d%d%I64d",month,&now.day,&now.year,&H,&in[i].R);
for(int j=;j<;j++){
if(!strcmp(yuefen[j],month)){
now.month=j+;
break;
}
}
in[i].time=(help.date2int(now)-preday)*+H+;
}
scanf("%I64d%I64d",&T,&S);
for(int i=;i<=m;i++){
scanf("%d",&cost[i]);
}
LL ans=;
for(int i=;i<n;i++){
int id=;
LL sma=inf;
for(int j=t;j<=in[i].time;j++){
if(j+T<in[i].time) continue;
LL c=(cost[j]+(in[i].time-j)*S)*in[i].R;
if(sma>c){
sma=c;
id=j;
}
}
if(s+T>=in[i].time){
LL c=(cost[s]+(in[i].time-s)*S)*in[i].R;
if(sma>c){
sma=c;
id=s;
}
}
ans+=sma;
s=id;
t=in[i].time;
}
printf("%I64d\n",ans);
}
return ;
}
Bob’s Race http://acm.hdu.edu.cn/showproblem.php?pid=4123
用树上最长路，就是树的直径，然后求出每个点能到最远距离数组，对其rmq预处理，然后单调队列求。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
const int M=;
struct G{
struct E{
int v,w,next;
}e[M<<];
int le,head[M];
void init(){
le=;
mt(head,-);
}
void add(int u,int v,int w){
e[le].v=v;
e[le].w=w;
e[le].next=head[u];
head[u]=le++;
}
}g;
bool vis[M];
int n;
queue<int> q;
void bfs(int s,int dist[]){
for(int i=;i<=n;i++){
dist[i]=inf;
vis[i]=false;
}
vis[s]=true;
dist[s]=;
while(!q.empty()) q.pop();
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=g.head[u];~i;i=g.e[i].next){
int v=g.e[i].v;
if(vis[v]) continue;
vis[v]=true;
dist[v]=dist[u]+g.e[i].w;
q.push(v);
}
}
}
int getfarid(int dist[]){
int res,big=;
for(int i=;i<=n;i++){
if(big<dist[i]){
big=dist[i];
res=i;
}
}
return res;
}
int d1[M],d2[M],a[M];
class Range_Maximum_Query{///区间最值查询离线算法init_o(nlogn),query_o(1)
int LOG[M],dpmax[M][],dpmin[M][];
public:
void init(){///使用类前调用一次即可
LOG[]=-;
for(int i=;i<M;i++){
LOG[i]=LOG[i>>]+;
}
}
void Make_RMQ(int n,int a[]){///传入点的个数，下标1开始
for(int i=;i<=n;i++){
dpmax[i][]=dpmin[i][]=a[i];
}
for(int j=;j<=LOG[n];j++){
for(int i=;i+(<<j)-<=n;i++){
dpmax[i][j]=max(dpmax[i][j-],dpmax[i+(<<(j-))][j-]);
dpmin[i][j]=min(dpmin[i][j-],dpmin[i+(<<(j-))][j-]);
}
}
}
int get_RMQ(int a,int b,bool big){///传入1返回max，传入0返回min
int k=LOG[b-a+];
if(big)
return max(dpmax[a][k],dpmax[b-(<<k)+][k]);
return min(dpmin[a][k],dpmin[b-(<<k)+][k]);
}
}rmq;
int main(){
int m,u,v,w;
rmq.init();
while(~scanf("%d%d",&n,&m),n|m){
g.init();
for(int i=;i<n-;i++){
scanf("%d%d%d",&u,&v,&w);
g.add(u,v,w);
g.add(v,u,w);
}
bfs(,d1);
int ss=getfarid(d1);
bfs(ss,d2);
int tt=getfarid(d2);
bfs(tt,d1);
for(int i=;i<=n;i++){
a[i]=max(d1[i],d2[i]);
}
rmq.Make_RMQ(n,a);
while(m--){
scanf("%d",&w);
int s=,t=,ans=;
while(true){
if(rmq.get_RMQ(s,t,)-rmq.get_RMQ(s,t,)<=w){
ans=max(ans,t-s+);
t++;
}
else{
s++;
}
if(t>n) break;
}
printf("%d\n",ans);
}
}
return ;
}
end
