NOIP2017提高组模拟赛 7（总结）##
第一题 斯诺克
考虑这样一个斯诺克球台，它只有四个袋口，分别在四个角上（如下图所示）。我们把所有桌子边界上的整数点作为击球点（除了4个袋口），在每个击球点我们可以以45度角击球。
每一个击球点你都可以向两个方向击球，例如像下图所示.
从S点击球有两种路线。提供桌子的尺寸，你的任务是计算出有多少种不同的击球方式使得球能入袋。球可视为质点，且无任何阻力，反弹时无能量损失。
一个简单的证明：当一个球的运动轨迹形成一个环时，那么它必定不会到达四个角。所以对于从一个角开始运动的球，最后必定会进入其他角（唯一的路径）。如此一来，就少了很多情况，枚举从四个角开始，直到到达终点（过程略微繁琐）。
#include<cstdio>
#include<algorithm>
#include<cmath>
#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))
typedef long long ll;
using namespace std;
const int N=100005;
int n,m,ans;
struct data { int w,x; };
bool vis[4][N];
data Q[N<<2];
data run(data X,int dir)
{
data Y;
if(dir==0)
{
if(X.w==2)
{
if(X.x<=n)
{
Y.w=1; Y.x=n-X.x;
if(Y.x==n) Y.w=2,Y.x=0;
} else
{
Y.w=0; Y.x=m+n-X.x;
if(Y.x==m) Y.w=1,Y.x=0;
}
} else
if(X.w==3)
{
Y.w=0; Y.x=n-X.x;
if(Y.x==m) Y.w=1,Y.x=0;
}
} else
if(dir==1)
{
if(X.w==0)
{
if(m-X.x<n)
{
Y.w=1; Y.x=m-X.x;
if(Y.x==n) Y.w=2,Y.x=0;
} else
{
Y.w=2; Y.x=m-X.x-n;
if(Y.w==m) Y.w=3,Y.x=0;
}
} else
if(X.w==3)
{
Y.w=2; Y.x=m-X.x;
if(Y.x==m) Y.w=3,Y.x=0;
}
} else
if(dir==2)
{
if(X.w==0)
{
if(X.x<=n)
{
Y.w=3; Y.x=n-X.x;
if(Y.x==n) Y.w=0,Y.x=0;
} else
{
Y.w=2; Y.x=m+n-X.x;
if(Y.w==m) Y.w=3,Y.x=0;
}
} else
if(X.w==1)
{
Y.w=2; Y.x=n-X.x;
if(Y.x==m) Y.w=3,Y.x=0;
}
} else
if(dir==3)
{
if(X.w==2)
{
if(m-X.x<n)
{
Y.w=3; Y.x=m-X.x;
if(Y.x==n) Y.w=0,Y.x=0;
} else
{
Y.w=0; Y.x=m-X.x-n;
if(Y.w==m) Y.w=1,Y.x=0;
}
} else
if(X.w==1)
{
Y.w=0; Y.x=m-X.x;
if(Y.x==m) Y.w=1,Y.x=0;
}
}
return Y;
}
void bfs(int ww,int xx)
{
data fro,now;
fro.w=ww; fro.x=xx;
vis[fro.w][fro.x]=1; bool ff=1;
for(;ff;)
{
ff=0;
for(int i=0;i<4;i++)
{
if((i!=(fro.w+1)%4) && (i!=(fro.w+2)%4)) continue;
now=run(fro,i);
if(vis[now.w][now.x]) continue;
ans++; vis[now.w][now.x]=1; fro=now; ff=1;
}
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
if(n>m) swap(n,m);
vis[0][0]=vis[1][0]=vis[2][0]=vis[3][0]=1;
bfs(0,0); bfs(1,0); bfs(2,0); bfs(3,0);
printf("%d\n",(ans<<1));
return 0;
}
第二题 完美排列
排列,相信大家都很熟悉了,给你0 到N-1,共 N个数, 那么在排列中,每个数都要出现,而且只出现一次. 对于一个排列A, 有一个与之对应的孩子序列B, 其中B这样定义的:
1、B[0] = 0
2、B[i] = A[B[i-1]], 1 <= i <= N-1.
对于一个排列X, 如果它的孩子序列也是一个排列, 那么X称为“完美排列”。
看下面的例子，N=3时，有6个排列，其中{1, 2, 0}、{2, 0, 1}这两个排列的孩子序列也是一个排列，所有{1, 2, 0}、{2, 0, 1}是完美排列。
给你一个整数N,再给出它的一个排列P,要你找一个完美排列Q,使得Q跟P的差距dif最小，两个排列的差距dif是这样定义的：对于每个下标i，如果P[i] 不等于 Q[i],那么dif加1， 0 <= i < N; 如果Q不唯一，那么请输出孩子序列中字典序最小的Q. 也就是在所有满足题意的完美序列中，看哪个完美序列的孩子序列字典序最小，输出该完美序列。
题目给出的排列，可以看成是i->p[i]的边，构成若干个环，现在要把它们并成一个环，求最小的修改次数，孩子序列字典序小的优先。（一开始理解为序列的字典序最小，WA了好多次）
简单理解，有N个环时，一定要修改N条边，N=1除外。字典序最小可以用贪心来做。先找出x=0所在的环，判断是否存在Q使得Q＜P[x]且Q不与x在同一个块上。若存在，则Q所在的块与x所在的块连通，x=链的尾端（循环）。若不存在，则判断x是否为块的尾端，不是则x=p[x]，否则找一个最小的Q与之相连，x=链的尾端（循环）。
这样找出来的一定是孩子序列字典序最小的。
#include<cstdio>
#include<algorithm>
#include<cmath>
#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))
#define Q(A,B) q[A][B]
typedef long long ll;
using namespace std;
int ng,n,d[56];
int cnt,q[56][56];
int bb[56],fa[56];
bool vis[56],fo[56],fi[56];
int father(int x) { return (fa[x]<0?x:fa[x]=father(fa[x])); }
void uni(int x,int y)
{
int fx=father(x),fy=father(y);
if(fa[fx]>fa[fy]) swap(fx,fy);
fa[fx]+=fa[fy]; fa[fy]=fx;
}
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d",&ng);
while(ng--)
{
scanf("%d",&n); cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&d[i]);
d[i]++; vis[i]=0;
fo[i]=fi[i]=bb[i]=0;
}
for(int i=1;i<=n;i++)
if(!vis[i])
{
fi[i]=1; fo[i]=1; vis[i]=1;
q[++cnt][0]=1; q[cnt][1]=i; bb[i]=cnt;
int x=d[i];
while(!vis[x])
{
q[cnt][++Q(cnt,0)]=x;
vis[x]=1; bb[x]=cnt; x=d[x];
}
}
int need=0;
for(int i=1;i<=cnt;i++) fa[i]=-1;
for(int g=1;1;)
if(fo[g])
{
if(need==cnt-1) break;
bool go=0; int cc;
fo[g]=0; fi[g]=0;
if(d[g]!=-1)
{
for(cc=1;cc<d[g];cc++)
if(fi[cc] && father(bb[g])!=father(bb[cc])) { go=1; break; }
if(!go)
{
if(Q(bb[g],Q(bb[g],0))!=g) { fo[d[g]]=1; g=d[g]; continue; }
for(cc=d[g];cc<=n;cc++)
if(fi[cc] && father(bb[g])!=father(bb[cc])) { go=1; break; }
}
} else
{
for(cc=1;cc<=n;cc++)
if(fi[cc] && father(bb[g])!=father(bb[cc])) { go=1; break; }
}
if(!go) break;
fo[g]=fi[g]=0; need++;
fo[cc]=fi[cc]=0;
fi[d[g]]=1; fo[d[g]]=0;
uni(bb[g],bb[cc]);
int last;
for(int i=1;i<=Q(bb[cc],0);i++)
if(d[Q(bb[cc],i)]==cc)
{
fo[Q(bb[cc],i)]=1; fi[Q(bb[cc],i)]=0;
last=Q(bb[cc],i);
d[Q(bb[cc],i)]=-1; break;
}
d[g]=cc;
g=last;
}
if(cnt>1)
{
int a,b;
for(a=1;a<=n;a++) if(fo[a]==1) break;
for(b=1;b<=n;b++) if(fi[b]==1) break;
d[a]=b;
}
for(int i=1;i<=n;i++) printf("%d ",d[i]-1); printf("\n");
}
return 0;
}
第三题 拼图
FJ最近很烦恼，因为他正在寻找一些拼图块，这些拼图块其实可以拼成N个有顺序的完整的拼图。每个完整的拼图由若干个拼图块组成。
FJ希望把这些完整的拼图按拼出的顺序划分成M个集合，一个拼图集合由若干个完整的拼图组成，并且每个集合总的拼图块的数目不超过T。
并且，构成集合的拼图是不能交叉的，例如，当拼图1与拼图3被放在拼图集合1中之后，拼图2就只能放进拼图集合1或者不放进任何拼图集合。
FJ要找出划分成M个集合后，M个集合中最多能有多少个完整的拼图。
一个很简单的二元组的动态规划（好像之前做过类似的题目）。
F[i][j]=(A,B) 表示到了 i 这个物品，选了 j 个，所用的最小体积（A个拼图块，最后一个用了B的空间）
f[i][j]=imin(f[i][j],imin(f[i-1][j],add(f[i-1][j-1],d[i])));
#include<cstdio>
#include<algorithm>
#include<cmath>
#define Amax(a,b) ((a>b)?(a):(b))
typedef long long ll;
using namespace std;
const int N=1000;
int n,m,T,ans;
int d[N+100];
struct data
{
int x,y;
data(){}
data(int x,int y):x(x),y(y) {}
};
data f[N+100][N+100];
data add(data X,int v)
{
X.y+=v;
if(X.y>T) X.y=v,X.x++;
return X;
}
data imin(data X,data Y)
{
if(X.x==Y.x) return ((X.y<Y.y)?X:Y);
else return ((X.x<Y.x)?X:Y);
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) f[i][j]=data(m+1,0);
f[0][0]=data(1,0); ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=imin(f[i][j],imin(f[i-1][j],add(f[i-1][j-1],d[i])));
//printf("%d %d %d %d\n",i,j,f[i][j].x,f[i][j].y);
if(f[i][j].x<=m) ans=Amax(ans,j);
}
}
printf("%d\n",ans);
return 0;
}