[POJ 4001-4010][2011 Asia Fuzhou Regional Contact]2011 ACM福州競技区現地試合題解(更新継続)
12947 ワード
A:Xiangqi(http://poj.org/problem?id=4001)
気持ち悪い模擬問題です.書く時は気をつけてください.リストボード上の全ての点で、黒を落とすかどうかを判断して、次の位置に着けばいいです.考えは簡単ですが、ACも難しいです.
単調な隊列で,この問題はまだはっきりしていないので,構想を書かない.
最小生成ツリーは、Q回の問い合わせに対して、最小生成ツリー＋1回のDFSを実行して、最小生成ツリー上の2つの隣接ノードの非樹端のうちの最短辺を求めて、Q回の問い合わせに対して、更新された端が木の端にある場合は、ツリーの端以外の最短辺または更新後の辺を選択して、ツリー上の既存辺の代わりに選択します.O(Q)の複雑さで解決できます.
暴挙する.試合の時はコントで展開して、逆康で展開して重さを判定すると思っていましたが、実際には裸IDA*でも大丈夫です.IDA*が検索する前にまず一回flook操作をしてください.でないと、サイクルが死にます.気がふさぎます.
気持ち悪い模擬問題です.書く時は気をつけてください.リストボード上の全ての点で、黒を落とすかどうかを判断して、次の位置に着けばいいです.考えは簡単ですが、ACも難しいです.
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXN 100
using namespace std;
int map[MAXN][MAXN],N; //map[x][y]=kind (x,y), kind ,1-> 2-> 3-> 4-> 5-> , x, y
int xx[]={1,-1,0,0},yy[]={0,0,1,-1}; //
int mx[]={-2, -2, -1, 1, 2, 2, 1, -1},my[]= {1, -1, 2, 2, 1, -1, -2, -2} ;//
bool inScope(int x,int y) // (x,y)
{
if(y<4||y>6||x<1||x>3) return false;
return true;
}
bool inMap(int x,int y) // (x,y)
{
if(x<1||x>10||y<1||y>9) return false;
return true;
}
int getNum(int x1,int y1,int x2,int y2) // (x1,y1) (x2,y2)
{
if((x1==x2&&y1==y2)||(x1!=x2&&y1!=y2)) return -1;
if(x1==x2)
{
int cnt=0;
if(y1>y2) swap(y1,y2);
for(int i=y1+1;i<y2;i++)
if(map[x1][i]) cnt++;
return cnt;
}
if(y1==y2)
{
int cnt=0;
if(x1>x2) swap(x1,x2);
for(int i=x1+1;i<x2;i++)
if(map[i][y1]) cnt++;
return cnt;
}
}
bool check(int x,int y) // (x,y), true， false
{
for(int i=1;i<=10;i++)
for(int j=1;j<=9;j++)
{
switch(map[i][j])
{
case 5:break;
case 1: //
{
if(getNum(x,y,i,j)==0)
{
//cout<<x<<' '<<y<<' '<<endl<<i<<' '<<j<<' '<<map[i][j]<<endl;
return true;
}
break;
}
case 2: //
{
if(getNum(x,y,i,j)==0)
{
//cout<<x<<' '<<y<<' '<<endl<<i<<' '<<j<<' '<<map[i][j]<<endl;
return true;
}
break;
}
case 4: //
{
if(getNum(x,y,i,j)==1)
{
//cout<<x<<' '<<y<<' '<<endl<<i<<' '<<j<<' '<<map[i][j]<<endl;
return true;
}
break;
}
case 3: //
{
for(int dir=0;dir<8;dir++)
{
int tx=i+mx[dir],ty=j+my[dir]; // (tx,ty)
if(!inMap(tx,ty)) continue;
if(map[tx][ty]!=5) continue; //
if(mx[dir]==2) if(inMap(i+1,j)&&map[i+1][j]) break; //
if(mx[dir]==-2) if(inMap(i-1,j)&&map[i-1][j]) break;
if(my[dir]==2) if(inMap(i,j+1)&&map[i][j+1]) break;
if(my[dir]==-2) if(inMap(i,j-1)&&map[i][j-1]) break;
//cout<<x<<' '<<y<<' '<<endl<<i<<' '<<j<<' '<<map[i][j]<<endl;
return true;
}
break;
}
}
}
return false;
}
int main()
{
while(1)
{
memset(map,0,sizeof(map));
int hx,hy,x,y,flag=1,now=0; // (hx,hy), ,flag=0
char s[3];
scanf("%d%d%d",&N,&hx,&hy);
if(N==0&&hx==0&&hy==0) return 0;
map[hx][hy]=5;
for(int i=0;i<N;i++)
{
scanf("%s%d%d",s,&x,&y);
switch(s[0])
{
case 'G':{map[x][y]=1; break;}
case 'R':{map[x][y]=2; break;}
case 'H':{map[x][y]=3; break;}
case 'C':{map[x][y]=4; break;}
}
}
for(int dir=0;dir<4;dir++)
{
int bak; //
int tx=hx+xx[dir],ty=hy+yy[dir]; // (tx,ty)
if(!inScope(tx,ty)) continue;
bak=map[tx][ty];
map[tx][ty]=5;
map[hx][hy]=0;
if(!check(tx,ty)) {flag=0; break;} //
map[tx][ty]=bak;
map[hx][hy]=5;
}
if(flag) printf("YES
");
else printf("NO
");
}
return 0;
}単調な隊列で,この問題はまだはっきりしていないので,構想を書かない.
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAXT 3000
using namespace std;
struct Node
{
int num,time; // : t num； : t num
}q[MAXT*4],order[MAXT];
int MonDay[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; //
int mon(char *s)
{
if(strcmp(s,"Jan")==0) return 1;
if(strcmp(s,"Feb")==0) return 2;
if(strcmp(s,"Mar")==0) return 3;
if(strcmp(s,"Apr")==0) return 4;
if(strcmp(s,"May")==0) return 5;
if(strcmp(s,"Jun")==0) return 6;
if(strcmp(s,"Jul")==0) return 7;
if(strcmp(s,"Aug")==0) return 8;
if(strcmp(s,"Sep")==0) return 9;
if(strcmp(s,"Oct")==0) return 10;
if(strcmp(s,"Nov")==0) return 11;
if(strcmp(s,"Dec")==0) return 12;
}
bool isLeapYear(int year) //
{
return year%4==0&&(year%100||year%400==0);
}
int getHour(int year,int month,int day,int hour) //
{
int tot=0;
for(int i=2000;i<year;i++)
{
if(isLeapYear(i)) tot+=366; // 366
else tot+=365; // 365
}
for(int i=1;i<month;i++)
{
if(isLeapYear(year)&&i==2) tot+=29; // 2 29
else tot+=MonDay[i];
}
tot+=day-1; //
return tot=tot*24+hour;
}
int main()
{
while(1)
{
char s[10];
int n,m,year,month,day,hour,T,S,cost,h=0,t=0,p=0;
long long int sum=0;
scanf("%d%d",&n,&m);
if(n==0&&m==0) return 0;
for(int i=0;i<n;i++)
{
scanf("%s%d%d%d%d",s,&day,&year,&hour,&order[i].num);
order[i].time=getHour(year,mon(s),day,hour); // ，
}
scanf("%d%d",&T,&S);
for(int i=0;i<m;i++)
{
scanf("%d",&cost);
while(h<t&&q[t-1].num+S*(i-q[t-1].time)>=cost) t--; // x , j， i， s, cost[x]+(j-i)*s，
q[t].num=cost,q[t++].time=i; //
while(p<n&&i==order[p].time) // p
{
while(q[h].time+T<i) h++; // ( )，
sum+=(q[h].num+S*(i-q[h].time))*order[p++].num; //
}
}
printf("%lld
",sum);
}
return 0;
}最小生成ツリーは、Q回の問い合わせに対して、最小生成ツリー＋1回のDFSを実行して、最小生成ツリー上の2つの隣接ノードの非樹端のうちの最短辺を求めて、Q回の問い合わせに対して、更新された端が木の端にある場合は、ツリーの端以外の最短辺または更新後の辺を選択して、ツリー上の既存辺の代わりに選択します.O(Q)の複雑さで解決できます.
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define INF 1000000000
#define MAXM 3010 //
#define MAXN 9000100 //
using namespace std;
vector<int>mst[MAXM];
struct edge
{
int u,v,c;
bool operator<(const edge&rhs)const
{
return c<rhs.c;
}
}edges[MAXN];
int nCount=0; //total edges
int num[MAXM][MAXM],best[MAXM][MAXM];
int f[MAXM];
int inTree[MAXM][MAXM];
int min(int a,int b)
{
if(a<b) return a;
return b;
}
int findSet(int x)
{
if(f[x]==x) return x;
return f[x]=findSet(f[x]);
}
void Union(int a,int b)
{
f[a]=b;
}
double Kruscal(int n,int m)
{
int i,j;
double ans=0;
sort(edges,edges+m);
for(i=0;i<m;i++)
{
int t1=findSet(edges[i].u);
int t2=findSet(edges[i].v);
if(t1!=t2)
{
Union(t1,t2);
ans+=edges[i].c;
mst[edges[i].u].push_back(edges[i].v);
mst[edges[i].v].push_back(edges[i].u);
inTree[edges[i].u][edges[i].v]=1;
inTree[edges[i].v][edges[i].u]=1;
}
}
return ans;
}
int dfs(int rt,int u,int fa)
{
int i,j,s=INF;
for(i=0;i<mst[u].size();i++) // u i
{
int v=mst[u][i]; // u v
if(v==fa) continue;
int tmp=dfs(rt,v,u);
s=min(s,tmp);
best[u][v]=best[v][u]=min(best[u][v],tmp);
}
if(rt!=fa) //
s=min(num[rt][u],s);
return s;
}
int main()
{
int i,j;
int N,M,X,Y,C,Q;
while(1)
{
double ANS=0;
for(i=0;i<MAXM;i++)
{
mst[i].clear();
f[i]=i;
for(j=0;j<MAXM;j++)
{
num[i][j]=best[i][j]=INF;
inTree[i][j]=0;
}
}
scanf("%d%d",&N,&M);
if(N==0&&M==0)
return 0;
for(i=0;i<M;i++)
{
scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].c);
num[edges[i].u][edges[i].v]=num[edges[i].v][edges[i].u]=edges[i].c;
}
double minDis=Kruscal(N,M);
for(i=0;i<N;i++)
dfs(i,i,-1);
scanf("%d",&Q);
for(i=1;i<=Q;i++)
{
scanf("%d%d%d",&X,&Y,&C);
if(!inTree[X][Y]) ANS+=minDis; // ，
else // , X<->Y C
{
ANS+=minDis-num[X][Y]+min(best[X][Y],C);
}
}
printf("%.4lf
",ANS/(Q*1.0));
}
return 0;
}
暴挙する.試合の時はコントで展開して、逆康で展開して重さを判定すると思っていましたが、実際には裸IDA*でも大丈夫です.IDA*が検索する前にまず一回flook操作をしてください.でないと、サイクルが死にます.気がふさぎます.
//IDA*
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAXN 10
using namespace std;
int map[MAXN][MAXN],xx[4]={1,-1,0,0},yy[4]={0,0,1,-1},status[MAXN][MAXN]; //status[i][j]=1 (i,j) , ,2 (i,j) , ,3 (i,j) ，
int N,depth;
bool check(int x,int y) // (x,y) , false
{
if(x>N||x<1||y>N||y<1) return false;
return true;
}
void flood(int x,int y,int col) // (x,y), col flood
{
status[x][y]=1; //
for(int dir=0;dir<4;dir++)
{
int tx=x+xx[dir]; // (tx,ty)
int ty=y+yy[dir];
if(!check(tx,ty)) continue; //
if(status[tx][ty]==1) continue; // ，
if(map[tx][ty]==col) //
flood(tx,ty,col);
else status[tx][ty]=2; // ， (tx,ty)
}
}
int get_cnt(int col) // col ，
{
int cnt=0;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
if(status[i][j]==2&&map[i][j]==col) // col ， , status ，
{
cnt++; //
flood(i,j,col);
}
}
return cnt;
}
int h() // , ， ，
{
int tot=0;
bool flag[6];
memset(flag,false,sizeof(flag));
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
if(status[i][j]!=1&&!flag[map[i][j]]) // ，
{
tot++;
flag[map[i][j]]=true;
}
}
return tot;
}
bool IDAstar(int dep) // dep , true, false
{
if(dep==depth) return h()==0; // ，
if(dep+h()>depth) return false; // ， false
for(int i=0;i<6;i++) // i
{
int now[MAXN][MAXN]; //now status
memcpy(now,status,sizeof(status));
if(get_cnt(i)==0) // ，
continue;
if(IDAstar(dep+1)) return true; // ， true
memcpy(status,now,sizeof(now)); // status
}
return false; // ，
}
int main()
{
while(1)
{
memset(map,0,sizeof(map));
memset(status,0,sizeof(status));
scanf("%d",&N);
if(N==0) return 0;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
scanf("%d",&map[i][j]);
flood(1,1,map[1][1]); //
depth=h();
while(1)
{
if(IDAstar(0)) break; //
depth++; // ， ( )
}
printf("%d
",depth); //
}
return 0;
}