<前言>

前几天cz大佬给我们出了一套模拟题.毒瘤不多说，就来讲讲Day2 T1吧（一道实际上的水题我一直没做出来）。

<正文>

T1.landmine

Mys_C_K认为现在的扫雷都太简单了，想要造一局超级难的扫雷。
一局超级难的扫雷在一个 $n\times m$ 的网格上进行。当然，扫雷也不能太难，为此他希望
没有5个雷连成一串，即对于水平方向、竖直方向、左上-右下方向和左下-右上方向
来说没有连续5个雷。

同时他希望最大化雷的数目。

landmine_sample0.in: 5 5 

讯享网landmine_sample0.out: 5 00001 10000 00100 00010 01000 

【数据规模与约定】
对于$10\%$的数据$n，m<=5$ 。
对于另外$20\%$的数据$m<5$。
对于另外$20\%$的数据$n,m<=100$。
对于$100\%$的数据，$n,m<=500$

这题一看就让人很懵逼，构造题嘛，奇奇怪怪的。

乍一看之下容易让人想出一种思想：让雷多，就是让空位少，但是要保证每隔四个就要有空地。这貌似和八皇后差不多嘛，就是多了一个距离限制。所以你可以去写一个爆搜。

但是——看到了500的数据范围，我沉默了。于是考场上我果断放弃，写了第一、二个部分分，没想到最后输出的时候0与1之间多输出了一个空格，结果本来能拿分的也没分了，最后完美爆零。

不扯淡了，开始将正解。

之所以要自己构造，是因为如果你用样例的，会当场去世，因为样例如果一直复制会有一种情况对角线连成一线。自己构造的数据最好也验证一下不会导致连成一线。

真是神奇，考场上觉得要分类讨论啊什么什么好难啊就是想不到这个，考完后觉得就是个签到题。

可能是因为我之前没做过构造题吧。

代码：

#include<bits/stdc++.h> #define ll long long using namespace std; int n,m; int a[510][510]={ 
   }; int t[5][5]={ 
   { 
   0,0,0,1,0},{ 
   0,1,0,0,0},{ 
   0,0,0,0,1},{ 
   0,0,1,0,0},{ 
   1,0,0,0,0}}; int main() { 
    freopen("landmine.in","r",stdin); freopen("landmine.out","w",stdout); scanf("%d%d",&n,&m); if(n<5&&m<5){ 
   puts("0");for(int i=1;i<=n;++i){ 
   for(int j=1;j<=m;++j)printf("0");puts("");}} { 
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) a[i][j]=t[i%5][j%5]; } ll ans=0; for(int i=0;i<n;++i) for(int j=0;j<m;++j) ans+=a[i][j]; printf("%lld\n",ans); for(int i=0;i<n;++i){ 
   for(int j=0;j<m;++j)printf("%d",a[i][j]);puts("");} return 0; } 

T2.jump

【问题描述】
Mys_C_K擅长左右横跳技术(雾)。
将世界抽象成一个一维数轴(大雾)，其上有 共 个点。一开始
Mys_C_K在位置 ，要跳到位置 ，每次从 位置可以跳到 中
的某个位置 ，这次跳跃所花的代价是 。
然而左右横跳技术名不符实，因为Mys_C_K只能向左跳: 具体地，总是有
且 。
求Mys_C_K左右横跳的最大代价。

【输入格式】
第一行一个正整数 。
第二行 个数，第 个数字表示 。
【输出格式】
输出最大代价。
【输入输出样例】

讯享网jump_sample0.in: 5 0 1 1 3 3 

jump_sample0.out: 4 

【数据规模与约定】
对于$30\%$的数据$n\le 1000$ 。
对于$70\%$的数据$n\le 2\times 10^5$。
对于$100\%$的数据$n\le 5\times 10^6$。
保证$0\le l_x\le r_x=x-1$。

考场上：

我一开始看到这题：这不就是这纯模拟题吗，每次不会有比跳尽量远更优的啦呀。然后还自己“证明了一下”：

讯享网

• 设x>y>z,要满足$(x-y)(x-y-1)+(y-z)(y-z-1)>(x-z)(x-z-1)$
• 可以推得$y^2-xy-yz+xz>0$,因式分解得$(z-y)(x-y)>0$
• 显然，上式不成立，所以结论成立。

然而，我忘了这是建立在$l[x]<=z$的前提下。

然而我当时也想到了错误的情况下，因为大样例过不了，所以又写了一个最长路。

令人震惊的时最长路的结果和贪心一模一样！！

然后我就没辙了，乖乖等死。果然爆零。

考完后：

斜率优化dp？？？我$\ast \ast \ast$这玩意我只写过板子题，现在也早忘了。

朴素的暴力dp：

• 设$f[i]$为到i的最大代价，容易得$f[i]=max(f[j],cost)(j>=i,cost=(j-i)(j-i-1))$
  这样是$n^2$的，绝对过不了。

然后，一位高中dalao（邱姓）作为全场唯一A掉此题的人，说了一种神奇的做法：

qt：我就是没思路嘛，就打开大样例一看，发现$l[i]$不仅单调递升而且还有很多重复的，于是就考虑加一个玄学优化。

如果第i个的$l[i]$与上一个i-1一样，我们发现

因为k是上次的决策点，说明$f[i]<f[k]>f[j]$，再考虑cost,发现$cos{t}_i>cos{t}_k>cos{t}_j$

因此，选择j一定是不优的，抛弃j，从k向i去枚举，更新答案，注意从后往前更新，从前往后会错，原因未明。

所以就是这个奇奇怪怪的做法，和正解跑的一样快。但是正解就是一个奇奇怪怪的切分线段+斜率优化，正常的斜率优化还会死掉的，所以我果断放弃。

qt还是太强了啊

代码：

讯享网#include<bits/stdc++.h> #define N  #define ll long long using namespace std; int n; int a[N]={ 
   }; ll f[N]={ 
   }; // queue<int>q; int q[N*2]={ 
   }; int read(){ 
   int s=0,w=1;char ch=getchar();while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;} int main() { 
    freopen("jump.in","r",stdin); freopen("jump.out","w",stdout); n=read(); for(int i=1;i<=n;++i) a[i]=read(); int h=1,x,t=0; for(int i=1;i<=n;++i){ 
    if(a[i]!=a[i-1]||i==1) { 
    q[++t]=i-1; //队列就是一个值域，没有什么单调队列优化的操作（虽然看起来还真像） while(h<=t&&a[i]>=h)++h; q[--h]=a[i]; x=t; } for(int j=x;j>=h;--j){ 
    if(f[i]<f[q[j]]+1ll*(i-q[j])*(i-q[j]-1)) f[i]=f[q[j]]+(i-q[j])*(i-q[j]-1),x=j; } } printf("%d\n",f[n]); return 0; } 

<后记>

差不多就这样，顺便再次吐槽一句标算代码压行真的恐怖，虽然也想学学压行听说这样有好处，但是这样就没人给你改代码了吧（\kk）

这几天的题不是我说，是真的毒瘤，Day1T2还能写写，如果能意识到要用高精说不定就有个八九十分了，但是昨天的T2实在非人哉了。

再见再见不送不送。