NOIP2017模拟赛（十一）解题报告
T1：
飞镖
题目描述
奶牛Bessie在玩飞镖游戏。在飞镖板上共有N个环，编号从1到N。如果飞镖扔中第i环，那么讲得到score[i]的分数。注意这N个环的分数的范围都是【1,N】，而且没有重复，也就是score[1..N]数组其实是1..N的某个排列。现在由于某些原因，某些环的分数被盖住，看不清楚了。Bessie扔飞镖的技术一流，以至于它想扔中哪个环就可以扔中那个环，Bessie可以还选择多次扔中某个环。Bessie的目标是使得自己的总得分至少达到P分，那么Bessie至少要扔多少次飞镖就一定可以达到目的？当然，Bessie会以最优策略去扔飞镖。
输入格式 1912.in
多组测试数据。
第一行，一个整数g, 表示有g组测试数据， 1 <= g <= 10。
每组测试数据格式如下：
第一行，两个整数N，P。1<=N<=50, 1 <= P <= 1000000000。
接下来有N行，第i个整数代表score[i]，如果score[i]=0则表示该环的得分被盖住了；如果1<=score[i]<=N,则表示这个环的得分。
输出格式 1912.out
共g行，每行一个整数。
输入样例 1912.in
3
5 8
0 3 4 0 0
5 15
0 0 0 0 0
8 2012
4 7 8 1 3 2 6 5
输出样例 1912.out
2
5
252
样例解释
第一组测试数据解释：Bessie可以连续2次都扔中第3个环，那么得分是2×4=8。
第二组测试数据解释：所有的环的得分都被盖住了，但是我们知道这5个环中，得分肯定有一个1，一个2，一个3，一个4，一个5，所以Bessie扔5次飞镖，而且每次选择扔中的都是不同的环，那么得分一定是1+2+3+4+5=15，如果扔飞镖的次数少于5，Bessie不能保证得分一定达到15分，因为环的得分都被盖住了，不能指望每次扔中的都是最高分。
题目分析：T1又是一道送分题。我们很容易发现，如果我们投了一个分数未知的环，就肯定要将剩下所有未知的地方都投一遍，才能使每次投的得分平均数最高（前提是当前分数还没有超过P）。我们称将每个未知的环都投一遍称为投一轮。那么假设未知数有x个，它们的总和为sum，已知的数中最大值为y。当x*y>=sum的时候，我们不停地投y最优；否则我们先投尽可能多的轮数，然后剩余的部分看一下投未知的环还是不停投y更优。时间O(1)。
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;
bool vis[maxn];
int x[maxn];
int cur,sum,y;
int g,N,P;
int ans;
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&g);
while (g--)
{
scanf("%d%d",&N,&P);
for (int i=1; i<=N; i++) vis[i]=false;
cur=sum=y=ans=0;
for (int i=1; i<=N; i++)
{
int val;
scanf("%d",&val);
if (val) vis[val]=true,y=max(y,val);
}
for (int i=1; i<=N; i++)
if (!vis[i]) x[++cur]=i,sum+=i;
if (y*cur>=sum) ans=(P+y-1)/y;
else
{
ans=P/sum;
P-=(ans*sum);
ans*=cur;
int temp=0,tail=0;
while (temp<P) tail++,temp+=x[tail];
if (y) tail=min(tail, (P+y-1)/y );
ans+=tail;
}
printf("%d\n",ans);
}
return 0;
}
T2：
战役地图
题目描述
Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。
由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。
具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。
输入格式 1913.in
输入文件的第一行包含一个正整数n。
以下n行，每行包含n个正整数，表示第一张战役地图的代表矩阵。
再以下n行，每行包含n个正整数，表示第二张战役地图的代表矩阵。
输出格式 1913.out
输出文件仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。
输入样例 1913.in
3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4
输出样例 1913.out
2
样例解释
子矩阵：
5 6
8 9
为两个地图的最大公共矩阵
约定：
n<=50
题目分析：我考场上做这题的时候，主要是想怎么优化暴力，没去想DP，然后想了个O(n^4log(n))的算法。首先看完题之后，我条件反射般地想到二分边长len，然后我在左边的地图枚举横坐标的起始位置x1，右边也枚举起始位置x2，然后通过双哈希将每一行纵坐标压成一个值，如图：
然后我再枚举一个y，看一下u数组中是否有v_y至v_y+len-1，这可以通过KMP匹配判断。
后来考试结束的时候，我听见lhx_QAQ用n^5的方法A掉了，Ab.Ever用n^4的DP过了，kekxy写了二维hash（其实就是将我的那个KMP再改成hash），还有人用n^6log(n)的方法，加一些剪枝就A掉了（这数据弱得……）。方法层出不穷，目测最好的就只能做到O(n^4)。然后我回去再想了想，其实我hash掉一维之后，就是在求u，v数组的最长公共子串长度是否>=len，这可以写一个后缀数组嘛……于是时间O(n^3log^2(n))。
CODE(hash+KMP)：
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=55;
const long long M1=998585857LL;
const long long M2=333333331LL;
typedef long long LL;
LL a[2][maxn][maxn];
int b[2][maxn][maxn];
struct data
{
int id,x,y;
} cnt[(maxn*maxn)<<1];
int cur=0,temp;
LL w1[maxn];
LL w2[maxn];
LL val1[2][maxn][maxn];
LL val2[2][maxn][maxn];
LL Hash1[maxn];
LL Hash2[maxn];
LL u1[maxn];
LL u2[maxn];
LL v1[maxn];
LL v2[maxn];
int Next[maxn];
int n;
bool Comp(data X,data Y)
{
return a[X.id][X.x][X.y]<a[Y.id][Y.x][Y.y];
}
LL Get1(int id,int i,int lj,int rj)
{
return (val1[id][i][rj]-val1[id][i][lj-1]*w1[rj-lj+1]%M1+M1)%M1;
}
LL Get2(int id,int i,int lj,int rj)
{
return (val2[id][i][rj]-val2[id][i][lj-1]*w2[rj-lj+1]%M2+M2)%M2;
}
bool KMP(int h,int len)
{
for (int i=1; i<=len; i++)
v1[i]=Hash1[h+i-1],
v2[i]=Hash2[h+i-1];
v1[h+len]=M1;
Next[0]=Next[1]=0;
int k=0;
for (int i=2; i<=len; i++)
{
while ( k && ( v1[i]!=v1[k+1] || v2[i]!=v2[k+1] ) ) k=Next[k];
if ( v1[i]==v1[k+1] && v2[i]==v2[k+1] ) k++;
Next[i]=k;
}
k=0;
for (int i=1; i<=n; i++)
{
while ( k && ( u1[i]!=v1[k+1] || u2[i]!=v2[k+1] ) ) k=Next[k];
if ( u1[i]==v1[k+1] && u2[i]==v2[k+1] ) k++;
if (k>=len) return true;
}
return false;
}
bool Judge(int len)
{
for (int i=1; i<=n-len+1; i++)
{
for (int j=1; j<=n; j++)
Hash1[j]=Get1(0,j,i,i+len-1),
Hash2[j]=Get2(0,j,i,i+len-1);
for (int j=1; j<=n-len+1; j++)
{
for (int k=1; k<=n; k++)
u1[k]=Get1(1,k,j,j+len-1),
u2[k]=Get2(1,k,j,j+len-1);
for (int k=1; k<=n-len+1; k++)
if ( KMP(k,len) ) return true;
}
}
return false;
}
int Binary()
{
int L=0,R=n+1;
while (L+1<R)
{
int mid=(L+R)>>1;
if ( Judge(mid) ) L=mid;
else R=mid;
}
return L;
}
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d",&n);
for (int i=0; i<=1; i++)
for (int j=1; j<=n; j++)
for (int k=1; k<=n; k++)
{
scanf("%I64d\n",&a[i][j][k]);
cur++;
cnt[cur].id=i;
cnt[cur].x=j;
cnt[cur].y=k;
}
sort(cnt+1,cnt+cur+1,Comp);
temp=1;
b[ cnt[1].id ][ cnt[1].x ][ cnt[1].y ]=1;
for (int i=2; i<=cur; i++)
{
if ( Comp(cnt[i-1],cnt[i]) ) temp++;
b[ cnt[i].id ][ cnt[i].x ][ cnt[i].y ]=temp;
}
temp++;
w1[0]=w2[0]=1;
for (int i=1; i<maxn; i++)
w1[i]=w1[i-1]*temp%M1,
w2[i]=w2[i-1]*temp%M2;
for (int i=0; i<=1; i++)
for (int j=1; j<=n; j++)
{
val1[i][j][0]=val2[i][j][0]=0;
for (int k=1; k<=n; k++)
val1[i][j][k]=(val1[i][j][k-1]*temp+(long long)b[i][j][k])%M1,
val2[i][j][k]=(val2[i][j][k-1]*temp+(long long)b[i][j][k])%M2;
}
int ans=Binary();
printf("%d\n",ans);
return 0;
}
T3：
排序
题目描述
给你一个整数数列data[0..N-1],现在你需要把这N个数重新排列,使得满足:
result[ i ] + 1 不等于 result[i + 1] , 对于0 <= i < n-1成立, 如果存在多种方案, 返回result字典序最小的.
输入格式 1914.in
多组测试数据。
第一行：一个整数ng, 1 <= ng <= 5。 表示有ng组测试数据。
每组测试数据格式如下：
第一行,一个整数N, 1<=N<=50。
接下来一行,有N个整数(在[0,1000]范围内), 空格分开, 则题目说的data[0..N-1].
输出格式 1914.out
ng行，每行对应一组输入数据。
返回result字典序最小的. 一行,共N个整数,空格分开。
输入样例 1914.in
3
2
1 2
3
1 2 3
9
1 1 1 1 2 2 2 2 2
输出样例 1914.out
2 1
1 3 2
2 2 2 2 2 1 1 1 1
题目分析：这题我已经无力吐槽，这难度居然是第三题（感觉和T1差不多）？这就是一个很水的贪心嘛。我们先将所有数从小到大排好序，假设是1 1 2 2 3 3 4 4。我们发现第二，三个数不符合要求，于是我们在后面找一个最小的（就是3）插入他们中间，得到1 1 3 2 2 3 4 4，然后我们发现第六，七个数不符合要求，而后面有没有数了。为了保证答案正确，我们直接将所有的3，4互换，得到1 1 3 2 2 4 4 3，即为答案。（这题我在考场看完题上不到20分钟就做完了。）
CODE：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxm=1010;
int cnt[maxm];
int ng,N;
void Print(int x)
{
for (int i=1; i<=cnt[x]; i++) printf("%d ",x);
cnt[x]=0;
}
int Find(int x)
{
for (int i=x; i<maxm; i++)
if (cnt[i]) return i;
return -1;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d",&ng);
while (ng--)
{
scanf("%d",&N);
for (int i=1; i<=N; i++)
{
int x;
scanf("%d",&x);
cnt[x]++;
}
for (int i=0; i<maxm; i++)
if (cnt[i])
if (!cnt[i+1]) Print(i);
else
{
int j=Find(i+2);
if (j==-1) Print(i+1),Print(i);
else
{
Print(i);
printf("%d ",j);
cnt[j]--;
}
}
printf("\n");
}
return 0;
}
总结：这次比赛题目很水，所以AK了没什么大不了的，我只是想说说比赛过程中的时间分配问题。一开始我预计T1 40min（SB模拟），T2 60min（满满的套路），T3 70min（感觉是玄学DP？）然后我25min切掉T1，30min码完T2。我感觉我T2一定要对拍啊，又是hash又是KMP的，万一写错了怎么办？于是我调过样例之后也不出几个数据或浏览一下代码，直奔暴力程序和数据生成器，开始对拍。
咦？第一个数据就有问题？我赶忙调试我的hash+KMP程序，调试了好久我发现……是我的暴力程序写错了！改过来之后对拍毫无问题（看来我还是很稳的嘛）。但现在只剩下40min做T3了，我感觉有些后悔花在T2太多时间了，我好浪啊……幸好最后一题很水，不然落下一题，可就不知滚到多少名去了。以后写完代码应该先手造几个数据喂一下，浏览一下代码，看看有没有写错。如果做完了所有题再考虑对拍，优先对拍那些最有可能写错的程序。这样或许会更优吧。
这次初三和我们高一的一起考，初三有2个人AK，高一只有我一个AK，其他人都莫名其妙地炸了某些地方。感觉初三的要把我们吊打啊……（高二Splay学长曾说过一句名言：正所谓——一届更被一届吊打）