NOIP2017模拟赛(11) 总结
前言：这是一篇历史悠久的总结。。由于隔的时间比较久，所以只能称作是回忆了。。那就开始回忆吧：
本次考试我本来是可以AK的，但是T3明明会做但写代码时又脑抽了，最后检查T1没时间复查T3，结果T3只有23分了。。。(这一切都是命运之石门的选择)
a 飞镖
题目描述
奶牛Bessie在玩飞镖游戏。在飞镖板上共有N个环，编号从1到N。如果飞镖扔中第i环，那么讲得到score[i]的分数。注意这N个环的分数的范围都是【1,N】，而且没有重复，也就是score[1..N]数组其实是1..N的某个排列。现在由于某些原因，某些环的分数被盖住，看不清楚了。Bessie扔飞镖的技术一流，以至于它想扔中哪个环就可以扔中那个环，Bessie可以还选择多次扔中某个环。Bessie的目标是使得自己的总得分至少达到P分，那么Bessie至少要扔多少次飞镖就一定可以达到目的？当然，Bessie会以最优策略去扔飞镖。
输入格式
多组测试数据。
第一行，一个整数g, 表示有g组测试数据， 1 <= g <= 10。
每组测试数据格式如下：
第一行，两个整数N，P。1<=N<=50, 1 <= P <= 1000000000。
接下来有N行，第i个整数代表score[i]，如果score[i]=0则表示该环的得分被盖住了；如果1<=score[i]<=N,则表示这个环的得分。
输出格式
共g行，每行一个整数。
输入样例
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
输出样例
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分，因为环的得分都被盖住了，不能指望每次扔中的都是最高分。
解题思路(贪心+完全背包)
这题比较玄学。
考场上想了很多方法，开始想O(1)的，最后发现不靠谱就干脆换了下思路。最我将每一种打法都换算成一种物品(已知的只有分数最大的有用)，每种物品既有次数也有分数。不难发现，一开始肯定用“性价比”高的物品比较划算。剩下多出来的一部分我一开始没有想好处理方法，写完所有题后复查时出数据发现错了。于是我就摒弃了玄学贪心，又写了一个不用证明且不会错的完全背包。这样时间复杂度达到了O(n^2)，不过在数据范围内是允许的。
下面讲讲另一种O(1)的做法，其实和我一开始想的差不多，只用贪心。大家好像都是这么做的(这有我这个sb才去写背包)，不难发现，如果我们投未知的环，只有不断往后投才更优(更可能投到分数高的)，就是说在不超过P的前提下把未知环都投一遍肯定平均得分(性价比)更高。于是我们先投几轮未知环(若已知最大分数比平均得分高就改成投已知最大分数的环)，其实前面和求最大性价比的思想一样。
关键是接下来的。由于我们没有像上面第一种方法一样不知道哪个性价比最高，我们知道一定是投一轮或投已知最大分数的环才优。于是接下来投的必然不超过一轮。于是我们就尝试着投未知的环或者不断投已知最大的环。这里恐怕有疑问了，这也是我考试时没有仔细想清楚的，这样贪心行吗？不可能投一段未知的再去投已知最大的呢？答案是不会的。假设我们未知的就投到
接下来贴第一种方法的代码：
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#define N 60
using namespace std;
int nG, P;
int x, n, cnt, unknown[N], Ans, dp[N][N];
bool vis[N];
struct Data{
int score, cost;
}toy[N];
bool cmp(Data A, Data B){
return A.score * B.cost > B.score * A.cost;
}
int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d", &nG);
while(nG --){
scanf("%d%d", &n, &P);
cnt = unknown[0] = Ans = 0;
memset(vis, false, sizeof(vis));
int x;
for(int i = 1; i <= n; i++){
scanf("%d", &x);
if(x) vis[x] = true;
}
for(int i = 1; i <= n; i++){
if(!vis[i]) unknown[++unknown[0]] = i;
else{
toy[++cnt].score = i;
toy[cnt].cost = 1;
}
}
int sum = 0;
for(int i = 1; i <= unknown[0]; i++){
sum += unknown[i];
toy[++cnt].score = sum;
toy[cnt].cost = i;
}
sort(toy+1, toy+cnt+1, cmp);
Ans = (P / toy[1].score) * toy[1].cost;
P %= toy[1].score;
if(P){
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= cnt; i++)
for(int j = 0; j <= cnt; j++){
dp[i][j] = dp[i-1][j];
if(j >= toy[i].cost)
dp[i][j] = max(dp[i][j], dp[i][j - toy[i].cost] + toy[i].score);
}
for(int i = 0; i <= cnt; i++) if(dp[cnt][i] >= P){
Ans += i;
break;
}
}
printf("%d\n", Ans);
}
return 0;
}b 战役地图
题目描述
Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。
由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。
具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。
输入格式
输入文件的第一行包含一个正整数n。
以下n行，每行包含n个正整数，表示第一张战役地图的代表矩阵。
再以下n行，每行包含n个正整数，表示第二张战役地图的代表矩阵。
输出格式
输出文件仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。
输入样例
3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4
输出样例
2
样例解释
子矩阵：
5 6
8 9
为两个地图的最大公共矩阵
约定：
解题思路(dp)
这题是一道喜闻乐见的送分题。说其送分，不光是因为其简单，更重要的是测试数据十分感人。时限1s，lhx_QAQ用O(n^5)的方法A掉了，这还不算什么，居然还有人用O(n^6logn)的狂暴方法，加一些剪枝(不知道是啥子东西)就过了！！我快疯了，让我这个写O(n^4)的dp的感觉没有了未来。。(暴力踩标程)
说说dp的做法=。=
题目就是让你求最大的两个一样的正方形矩阵的边长。由于是正方形，所以非常好办。对于数组a[]中的x行y列，就记作(x,y)，和b[]中的(k,q)，我们开一个四维数组记录状态为dp[x][y][k][q]。表示a[]中以(x,y)作为正方形的右下角，b[]中以(k,q)作为正方形的右下角，两个正方形所匹配的最大边长是多少。这就非常明朗了：如果a[x][y]和b[k][q]不一样毫无疑问一个0。否则就通过三个状态来转移，即
dp[i][j][k][q] = min(dp[i-1][j][k-1][q], min(dp[i][j-1][k][q-1], dp[i-1][j-1][k-1][q-1])) + 1;
就是说取其对应两个格子的相邻的左上，上，左的最小值再加1。其中的原理不难理解(因为要求是正方形)。然后dp数组一开始清为0，四重循环枚举+O(1)转移，最后扫表求答案，于是时间复杂度就是O(n^4)。
再简单说说另几种种稍微复杂点的方法，二维hash的话我在考场上想过，但写起来较麻烦，还要双hash。就是将每个点hash进行列两个数组(差不多是这样)。最后比较时用部分和O(1)判断。
KsCla大神用了O(n^4logn)的hash+kmp。hash一维再kmp另一维。这种方法基于先二分出长度len。判断时只需枚举断点算出长度为len的一维的hash值然后保存进另一个数组，再在这个数组上进行kmp查找有无在另一维长度也大于或等于len的公共子串就行了，就是再枚举一下并匹配。做法也比较简单，但同样没有dp好写。
ps：求最长公共字串用后缀数组时间可以达到O(n^3logn)。 ——by KsCla
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define N 55
using namespace std;
int n, a[N][N], b[N][N], Ans;
int dp[N][N][N][N];
int main(){
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &b[i][j]);
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
for(int q = 1; q <= n; q++)
if(a[i][j] == b[k][q]) dp[i][j][k][q] = min(dp[i-1][j][k-1][q], min(dp[i][j-1][k][q-1], dp[i-1][j-1][k-1][q-1])) + 1;
Ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
for(int q = 1; q <= n; q++)
Ans = max(dp[i][j][k][q], Ans);
printf("%d\n", Ans);
return 0;
}
c 排序
题目描述
给你一个整数数列data[0..N-1], 现在你需要把这N个数重新排列,使得满足:
result[ i ] + 1 不等于 result[i + 1] , 对于0 <= i < n-1成立, 如果存在多种方案, 返回result字典序最小的.
输入格式
多组测试数据。
第一行：一个整数ng, 1 <= ng <= 5。 表示有ng组测试数据。
每组测试数据格式如下：
第一行,一个整数N, 1<=N<=50。
接下来一行,有N个整数(在[0,1000]范围内), 空格分开, 则题目说的data[0..N-1].
输出格式
ng行，每行对应一组输入数据。
返回result字典序最小的. 一行,共N个整数,空格分开。
输入样例
3
2
1 2
3
1 2 3
9
1 1 1 1 2 2 2 2 2
输出样例
2 1
1 3 2
2 2 2 2 2 1 1 1 1
解题思路(贪心)
又是一道贪心题。其实这题很简单，但是无理由地，我在考试时脑抽写错了。
拿到这题我很快就写完了觉得水得一比，就去检查第一题，结果没时间复查此题了GG。。
我们对数组排完序后能选就选。瞻前顾后一下就知道哪个能选了。
至于如何瞻前顾后就太简单了(见代码)。(考试做这题时的我的智商哪去了。。)
时间复杂度O(n^3)。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#define N 60
#define CC 1005
using namespace std;
int nG, n;
int data[N];
bool Left[N];
bool Judge(int x, int y){
if(x == y - 1) return false;
bool Sol = true;
for(int i = 1; i <= n; i++){
if(!Left[i] || data[i] == y) continue;
Sol = false;
if(data[i] != y + 1) return true;
}
return Sol;
}
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++) scanf("%d", &data[i]), Left[i] = true;
sort(data+1, data+n+1);
int choose = -5;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(Left[j] && Judge(choose, data[j])){
choose = data[j];
Left[j] = false;
break;
}
}
printf("%d ", choose);
}
printf("\n");
}
return 0;
}
总结
这次的题目比较简单，但我还是没有AK，证明我的考试能力是很弱的。这次考试是和初三的后辈们一起考的。结果却是这样的：初三有两个人AK，高一只有尹指导一个。其实很可惜，高一明明有更多的人有机会AK，我第三题炸了，tututu第一题爆零了，kxy第二题hash没过。。总之我们总不能被初三的吊着打，要向尹指导和高二的罗指导看齐。就到这里吧。
感谢给我逆境的众生。
上一篇： UVA 712-S-Trees(满二叉树的简单查询）
下一篇： 9-11NOIP模拟赛总结