模擬是acm算法中基礎但深奧的算法，不容輕視。
本次模擬題練習題為1835，2623，2271，2996，2706，1676，1472，1027，3371。
1835 宇航員：可以以左手，臉，頭三個參量的方向來確定自己的方向。自己比劃比劃即可。
2996：棋盤問題，比較水。
2706：線段相交+DFS，注意線段相交的判斷。
1676：DFS即可。
1472：典型的遞歸題，構建棧。同時可以建立一個class，來表示一個多項式，利用操作符重載來簡化代碼結構。
1027：模擬，代碼不像網上說的那麼繁瑣，我認為還可以。但值得練練。
3371：字符串處理，細心題。
下面將貼出2706，1472，1027代碼，這三題在本次練習中稍繁。
2706代碼：
[cpp]
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
const int N=25,M=255;
const int dx[8]={1,2,2,1,-1,-2,-2,-1};
const int dy[8]={2,1,-1,-2,-2,-1,1,2};
struct point
{
int x,y;
point(int xx=0,int yy=0)
{
x=xx;y=yy;
}
};
struct line
{
point a,b;
line(point aa=point(),point bb=point())
{
a=aa;b=bb;
}
}l[N*N];
int tot,n,m;
bool v[2][N][N],vv[N][N][N][N],vis[N][N];
bool dfs(int x,int y)
{
vis[x][y]=true;
if (x==n) return true;
for (int k=0;k<8;k++)
if (x+dx[k]>=0 && x+dx[k]<=n && y+dy[k]>=0 && y+dy[k]<=n
&& !vis[x+dx[k]][y+dy[k]] &&vv[x][y][x+dx[k]][y+dy[k]])
{
if (dfs(x+dx[k],y+dy[k])) return true;
}
return false;
}
int xmult(point a,point b,point c)
{
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
bool intersect(point p1,point q1,point p2,point q2)
{
return xmult(p2,q1,p1)*xmult(q2,q1,p1)<0 && xmult(p1,q2,p2)*xmult(q1,q2,p2)<0;
}
int main()
{
int i,j,k,x,y,col;
freopen("in.txt","r",stdin);
while (1)
{
ppp:
cin >> n >> m;
if (n==0 && m==0) break;
memset(v,0,sizeof(v));
memset(vv,0,sizeof(vv));
tot=0;
for (i=1;i<=m;i++)
{
cin >> x >> y;
col=i%2;
v[col][x][y]=true;
for (k=0;k<8;k++)
if (x+dx[k]>=0 && x+dx[k]<=n && y+dy[k]>=0 && y+dy[k]<=n && v[col][x+dx[k]][y+dy[k]])
{
point p2=point(x+dx[k],y+dy[k]);
point p1=point(x,y);
bool ff=true;
for (j=1;j<=tot;j++)
if (intersect(l[j].a,l[j].b,p1,p2))
{
ff=false;
break;
}
if (ff)
{
l[++tot]=line(p1,p2);
if (col==1)
{
vv[p1.x][p1.y][p2.x][p2.y]=true;
vv[p2.x][p2.y][p1.x][p1.y]=true;
}
}
}
}
for (i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
if (v[1][0][i] && dfs(0,i))
{
cout << "yes" << endl;
goto ppp;
}
}
cout << "no" << endl;
}
}
1472代碼：
[cpp]
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
class num
{
private:
int a[12];
public:
num()
{
memset(a,0,sizeof(a));
}
num(const num& p)
{
memcpy(a,p.a,sizeof(p.a));
}
num operator+ (string s)
{
int i,tmp;
if (s=="n") a[1]++;
else
{
tmp=0;
for (i=0;i<s.size();i++)
tmp=tmp*10+s[i]-'0';
a[0]+=tmp;
}
return *this;
}
num operator+ (num b)
{
for (int i=0;i<12;i++)
a[i]+=b.a[i];
return *this;
}
num operator* (string s)
{
int i,tmp;
if (s=="n")
{
for (i=11;i>=1;i--)
a[i]=a[i-1];
a[0]=0;
}
else
{
tmp=0;
for (i=0;i<s.size();i++)
tmp=tmp*10+s[i]-'0';
for (i=0;i<12;i++)
a[i]*=tmp;
}
return *this;
}
friend ostream& operator<< (ostream& os,const num& b)
{
int i;
bool ff=false;
for (i=11;i>1;i--)
if (b.a[i]!=0)
{
if (ff) os << "+";
else ff=true;
if (b.a[i]>1)
os << b.a[i] << "*n^" << i;
else
os << "n^" << i;
}
if (b.a[1]>0)
{
if (ff) os << "+";
else ff=true;
if (b.a[1]==1) os << "n";
else os << b.a[1] << "*n";
}
if (b.a[0]>0)
{
if (ff) os << "+";
else ff=true;
os << b.a[0];
}
if (!ff) os << 0;
return os;
}
};
num work(int dep)
{
string order,s;
num ans;
cin >> order;
while (order!="END")
{
if (order=="LOOP")
{
cin >> s;
ans=ans+work(dep+1)*s;
}
else if (order=="OP")
{
cin >> s;
ans=ans+s;
}
cin >> order;
}
return ans;
}
int main()
{
int i,cc;
string s;
freopen("in.txt","r",stdin);
cin >> cc;
for (i=1;i<=cc;i++)
{
cout << "Program #" << i << endl;
cin >> s;
cout << "Runtime = " << work(0) << endl;
if (i<cc) cout << endl;
}
}
1027代碼：
[cpp]
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10,M=15;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int tot,rem,sum;
int ans[100][4];
int a[N+2][M+2];
int fill(int x,int y,bool v[][M+1])
{
int ans=1;
v[x][y]=true;
for (int i=0;i<4;i++)
if (!v[x+dx[i]][y+dy[i]] && a[x+dx[i]][y+dy[i]]==a[x][y])
ans+=fill(x+dx[i],y+dy[i],v);
return ans;
}
void clear(int x,int y)
{
int col=a[x][y];
a[x][y]=0;
for (int i=0;i<4;i++)
if (a[x+dx[i]][y+dy[i]]==col)
clear(x+dx[i],y+dy[i]);
}
void update()
{
int i,j,k,p;
for (j=1;j<=M;j++)
for (i=1;i<=N;i++)
if (a[i][j]==0)
{
k=i;
while (k<=N && a[k][j]==0) k++;
for (p=k;p<=N;p++)
{
a[p-k+i][j]=a[p][j];
a[p][j]=0;
}
}
for (j=1;j<=M;j++)
if (a[1][j]==0)
{
k=j;
while (k<=M && a[1][k]==0) k++;
for (p=k;p<=M;p++)
for (i=1;i<=N;i++)
{
a[i][p-k+j]=a[i][p];
a[i][p]=0;
}
}
}
void work()
{
bool v[N+1][M+1];
int ss,x,y,rr,i,j;
while (1)
{
memset(v,0,sizeof(v));
ss=x=y=rr=0;
for (j=1;j<=M;j++)
for (i=1;i<=N;i++)
if (a[i][j]>0 && !v[i][j])
{
int tmp=fill(i,j,v);
if (tmp>ss) ss=tmp,x=i,y=j;
rr+=tmp;
}
if (ss<=1)
{
rem=rr;
if (rem==0) sum+=1000;
break;
}
sum+=(ss-2)*(ss-2);
ans[++tot][0]=x;ans[tot][1]=y;
ans[tot][2]=ss;
switch(a[x][y])
{
case 1:ans[tot][3]='R';break;
case 2:ans[tot][3]='G';break;
case 3:ans[tot][3]='B';break;
}
clear(x,y);
update();
}
}
int main()
{
int i,j,cc,cas;
char ch;
freopen("in.txt","r",stdin);
cin >> cc;
getchar();
for (cas=1;cas<=cc;cas++)
{
getchar();
memset(a,0,sizeof(a));
tot=sum=rem=0;
for (i=N;i>=1;i--)
{
for (j=1;j<=M;j++)
{
ch=getchar();
switch(ch)
{
case 'R':a[i][j]=1;break;
case 'G':a[i][j]=2;break;
case 'B':a[i][j]=3;break;
}
}
getchar();
}
work();
printf("Game %d:\n\n",cas);
for (i=1;i<=tot;i++)
printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",
i,ans[i][0],ans[i][1],ans[i][2],char(ans[i][3]),(ans[i][2]-2)*(ans[i][2]-2));
printf("Final score: %d, with %d balls remaining.\n",sum,rem);
if (cas<cc) printf("\n");
}
}
作者：ascii991
