NOIP2017模拟赛（七）解题报告
T1：
斯诺克
题目描述
考虑这样一个斯诺克球台，它只有四个袋口，分别在四个角上（如下图所示）。我们把所有桌子边界上的整数点作为击球点（除了4个袋口），在每个击球点我们可以以45度角击球。
每一个击球点你都可以向两个方向击球，例如像下图所示，从S点击球有两种路线。提供桌子的尺寸，你的任务是计算出有多少种不同的击球方式使得球能入袋。球可视为质点，且无任何阻力，反弹时无能量损失。
输入格式 1871.in
仅一行，两个整数m和n，2 ≤ M,N ≤ 10^5，表示球台的长和宽。
输出格式 1871.out
符合以上描述的击球路线。
题目分析：罕见的恶心模拟题……拿到这题的时候，我的第一想法是宽搜，但我感觉太难写了，于是我花了5分钟的时间研究了一下，发现几个性质：
1. 我们可以从桌子的一个角出发往外射，这样射下去必定进入桌子的另一个角，而且路上不会重复经过一个点。为什么？如果我们重复经过一个点，那么就说明有环，从环上某个点的两个方向出发，都必定在这个环上绕。于是没有一种射法可以进入这个环或从这个环出去。这样我们直接模拟一路向前即可，不需要记一个点是否访问过。
2. 我们只要从一个点出发模拟一次就可以了，最后将路上经过的点数*4即为答案。假设我们从A点射到C点，那么B到D的路径必定是对称的（轴对称或中心对称），那么它们路上的点数一模一样，而且不会有重复的点（因为一个点不可能属于两条路径）。而路上的点向2边射都可以，于是*4。
这样写代码就方便多了。而且我发现如果下标从0开始到N，计算起来会很方便。于是画4幅图细心地分类讨论一下，就过了。后来听说AbEver写了宽搜，调了一个多小时（呵呵呵）。
CODE：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct data
{
int x,y,d;
} ;
int n,m;
data Next(data a)
{
data b;
if (a.d==0)
if ( a.x<=m && a.y==0 ) b.x=0,b.y=a.x,b.d=1;
else b.x=a.x+a.y-m,b.y=m,b.d=3;
if (a.d==1)
if ( a.x>=n-m && a.y==0 ) b.x=n,b.y=n-a.x,b.d=0;
else b.x=a.x+m-a.y,b.y=m,b.d=2;
if (a.d==2)
if ( a.x>=n-m && a.y==m ) b.x=n,b.y=a.x-n+m,b.d=3;
else b.x=a.x+a.y,b.y=0,b.d=1;
if (a.d==3)
if ( a.x<=m && a.y==m ) b.x=0,b.y=m-a.x,b.d=2;
else b.x=a.x-a.y,b.y=0,b.d=0;
return b;
}
bool Judge(data p)
{
return ( p.x==0 && p.y==m ) ||
( p.x==n && p.y==m ) ||
( p.x==n && p.y==0 );
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
if (n<m) swap(n,m);
int num=0;
data point;
point.x=point.y=0;
point.d=1;
point=Next(point);
while ( !Judge(point) ) num++,point=Next(point);
num<<=2;
printf("%d\n",num);
return 0;
}
T2：
完美排列
题目描述
排列,相信大家都很熟悉了,给你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.也就是在所有满足题意的完美序列中，看哪个完美序列的孩子序列字典序最小，输出该完美序列。
输入格式 1872.in
多组测试数据，第一行：一个整数ng,表示有1<=ng<=5组测试数据。
每组测试数据格式如下：
第一行：一个整数N, 表示排列的长度。1 <= N<= 50.
第二行：有N个整数，空格分开，表示给出的一个排列，就是对应的P[]数组。
输出格式 1872.out
ng行，每行对应一组测试数据。 每一行，就是满足题意的Q,共N个整数， 空格分开。
输入样例 1872.in
2
3
2 0 1
6
4 0 5 2 1 3
输出样例 1872.out
2 0 1
2 0 5 4 1 3
题目分析：这题面读完就已经让人不想做了（事实上我还看错题了，它说要输出孩子序列字典序最小的完美序列，我以为要输出字典序最小的完美序列）。我们认真研究之后，发现它就是有若干个环(A[i]=j则认为fa[i]=j)，现在我们要将它组成一个大环。最后从0开始按顺序读这个环，读出来的字典序最小，如图：
这样我们每一个环都要拆一条边出来，于是我们贪心。从0开始考虑，如果它当前的父亲是x，我们就在1~x-1中查看是否有和0不在一个环上的，如果有我们就改0的父亲，否则考虑下一个（如上图是3），然后发现3可以连到更优的4去，于是改3的父亲为4。（当然，如果我们已经考虑到了5号点，由于0-3-5这个环必须要向外连边，所以5号点也不得不找一个相对较小的环外的点连边）。
3改连4后，变成了这样：
这样我们就构造出了一条链，这条链上的fa值都已经被固定了。我们跳到8，然后继续找不在链上的值最小的点即可。
考试的时候我已经想到它是若干个环了，然而由于看错题，所以以为很难，不知道怎么贪心。最后想敲个随机化算法结果连代码都没码完……
CODE：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=55;
int vis[maxn];
int tail;
int fa[maxn];
int ng,N;
int Find1(int x)
{
for (int i=0; i<fa[x]; i++) if (!vis[i]) return i;
return -1;
}
int Find2(int x)
{
for (int i=0; i<N; i++) if (!vis[i]) return i;
return -1;
}
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d",&ng);
while (ng--)
{
scanf("%d",&N);
for (int i=0; i<N; i++) scanf("%d",&fa[i]),vis[i]=false;
vis[0]=true;
for (int i=fa[0]; i; i=fa[i]) vis[i]=true;
bool one=true;
for (int i=0; i<N; i++) one&=vis[i];
if (one)
{
for (int i=0; i<N; i++) printf("%d ",fa[i]);
printf("\n");
continue;
}
int last=0;
while ( Find1(last)==-1 && fa[last] ) last=fa[last];
tail=fa[last];
while ( 1 )
{
int x=Find2(last);
if (x==-1) break;
fa[last]=x;
last=x;
vis[last]=true;
while ( !vis[ fa[last] ] ) last=fa[last],vis[last]=true;
}
fa[last]=tail;
for (int i=0; i<N; i++) printf("%d ",fa[i]);
printf("\n");
}
return 0;
}
T3：
拼图
题目描述
FJ最近很烦恼，因为他正在寻找一些拼图块，这些拼图块其实可以拼成N个有顺序的完整的拼图。每个完整的拼图由若干个拼图块组成。
FJ希望把这些完整的拼图按拼出的顺序划分成M个集合，一个拼图集合由若干个完整的拼图组成，并且每个集合总的拼图块的数目不超过T。
并且，构成集合的拼图是不能交叉的，例如，当拼图1与拼图3被放在拼图集合1中之后，拼图2就只能放进拼图集合1或者不放进任何拼图集合。
FJ要找出划分成M个集合后，M个集合中最多能有多少个完整的拼图。
输入格式 1873.in
第一行为三个整数，为N,M,T(1 <= N,M,T <= 1000)
第二行有N个数，按照拼出拼图的顺序给出N个拼图分别含有多少个拼图块（拼图块的个数是不超过T的正整数）。
输出格式 1873.out
输出文件只有一个数字，为M个拼图集合最多包含的完整拼图个数
输入样例 1873.in
62 4
1 1 3 1 2 2
输出样例 1873.out
5
样例解释：
对于样例数据，1个可行的方案如下：
拼图集合1放拼图1和拼图2和拼图4，
拼图集合2放拼图5和拼图6
于是最多可以放5个拼图
并且显然不存在能够放5个以上拼图的方案
【数据规模】
对于30%的数据，有1<=N,M<=100
对于100%的数据，有1<=N,M<=1000
题目分析：这道题很容易想出状态N*M，转移O(N)的DP。我们记f[i][j]表示将前i个物品装进j个集合，最多能装几个。转移的时候枚举上一个集合的末尾k，然后用f[k][j-1]+g[k+1][i]更新f[i][j]就好了。其中g[i][j]表示将i~j的物品装进一个集合，最多能装几个，这是可以用O(N^2*K)的时间预处理的。考场上我先写了这个DP。
然后先讲一下我接下来的想法吧。我想：这肯定是要优化的。通过可持久化线段树+二叉查找+差分可以在O(N^2*log(K))的时间内预处理g数组。那么f数组呢？于是我想了想数据结构优化，单调队列优化，好像都不行啊。这时我想到了平行四边形优化。我记得fzh给我们讲平行四边形优化DP的专题时说：“你们要是实在不会证它是不是有平行四边形的性质，你就猜它有，感性认识一下就好了。”我顿时感觉这有平行四边形性质啊（不知哪来的感性），严格的性质证明已经被我忘得一干二净。我果断写了代码，和之前的程序对拍，结果发现完全不是那么回事……最后只好水30分。
正解则是用了一种完全不同的状态（话说我居然没有想到要优化状态表示……）。我们用f[i][j]存储一个二元组<cnt,num>，表示前i个物品选j个物品，至少需要cnt个集合，而且最后一个集合已经占用了num的空间。然后我们只需要枚举要不要选第i个即可，因为这个二元组显然是可以按双关键字比较大小的。
其实这题和GDKOI第一天第四题很像啊，都是要记一个二元组，只不过那时的我没有认真研究这种解法，导致现在考了还是不会。以后我还是要对每一道做过的题认真总结呀。
CODE：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct data
{
int num,last;
} f[maxn][maxn];
int a[maxn];
int n,m,t;
data Get(data x,int y)
{
x.last+=y;
if (x.last>t) x.num++,x.last=y;
return x;
}
data Get_min(data x,data y)
{
if ( x.num<y.num || ( x.num==y.num && x.last<y.last ) ) return x;
return 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",&a[i]);
for (int j=0; j<=n; j++)
for (int i=0; i<=n; i++)
f[i][j].num=f[i][j].last=maxn;
for (int i=0; i<=n; i++) f[i][0].num=f[i][0].last=0;
for (int j=1; j<=n; j++)
for (int i=j; i<=n; i++)
f[i][j]=Get_min(f[i-1][j], Get(f[i-1][j-1],a[i]) );
int ans=0;
for (int j=1; j<=n; j++)
if (f[n][j].num<m) ans=j;
printf("%d\n",ans);
return 0;
}
总结：这场比赛是我这几场以来最低分的一次：100+0+30=130。第二题主要是读错题，导致完全没分。现在想来GDOI2017Day1T1那道KMP也是读错题，以后对这种题面很复杂或可能有歧义的题一定要多读几遍题。第三题想不出来说明我之前对每道做过的题的总结还不够精细，以后要防止见过的题再考还不会或写不出代码的情况。