信息学科普基地Noip2017%你题第二试总结
题目
题解
1.爬山(mountain)
水题，直接搜索即可。
需要注意的是要用一个vis数组记录是否走过，否则在相等的时候会在两者之间不停地走下去，最后爆炸。我就是因为这个原因只有90分
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int h[205][205],n,m,sx,sy,fx[4]={0,1,0,-1},fy[4]={1,0,-1,0},ans;
bool vis[205][205];
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
void dfs(int x,int y)
{
vis[x][y]=1;
bool hier=0;
for (int i=0;i<4;i++)
{
int tx=x+fx[i],ty=y+fy[i];
if (!vis[tx][ty] && h[tx][ty]>=h[x][y])
{
hier=1;
dfs(tx,ty);
}
}
if (!hier) ans=max(ans,h[x][y]);
return;
}
int main()
{
freopen("mountain.in","r",stdin);
freopen("mountain.out","w",stdout);
n=read(); m=read(); sx=read(); sy=read();
memset(h,-1,sizeof(h));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
h[i][j]=read();
dfs(sx,sy);
printf("%d",ans);
return 0;
}
2.字符串距离(string)
这道题暴力就可以70 要什么正解系列
这道题的正解其实是找规律。显而易见，对于 $ T $ 中每个元素，它都会与 $ S $ 中的部分元素进行比较，只要确定与哪些元素比较即可。
下面就来推一下：
S: a a a b b
T: b a b
a[1]: {1}
a[2]: {2}
a[3]: {3}
这是最开始的情况，其中a[i]代表 $ T $ 中第i个元素需要在 $ S $ 中比较哪几个元素。
S: a a a b b
T: b a b
a[1]: {1,2}
a[2]: {2,3}
a[3]: {3,4}
往后推一步。
S: a a a b b
T: b a b
a[1]: {1,2,3}
a[2]: {2,3,4}
a[3]: {3,4,5}
其实这个测试数据有点误导性，我一开始就搞错了。下面换一组数据再来推一下：
S: a a a b b b b
T: b a b b a
a[1] {1,2,3}
a[2] {2,3,4}
a[3] {3,4,5}
a[4] {4,5,6}
a[5] {5,6,7}
完了。规律应该是显而易见了吧，对于 $ S $ 中第 $ i $ 个元素，它要与 $ T $ 中第 $ i $ ~ $ i+S.length()-T.length() $ 这些元素进行比较。之所以说容易被误导就是搞错成 $ i $ ~ $ i+T.length()-1 $ 进行比较。
我们可以用一个变量sum来记录当前长度为 $ S.length()-T.length()+1 $ 的区间内 $ a $ 的个数。当我们把 $ T $ 中元素往后推时，将区间同时后移一位。而区间中 $ a $ 的个数的变化只会发生在第 $ i-1 $ 和 $ i+T.length() $ 这两个元素中发生，只需要对应加减即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
string s,t;
cin>>s>>t;
int ls=s.length(),lt=t.length();
int sum=0,ans=0,len=ls-lt+1;
for (int i=0;i<len;i++)
if (s[i]=='a') sum++;
int j=0;
if (t[j]=='a') ans+=len-sum;
else ans+=sum;
for (int i=len;i<ls;i++)
{
if (s[i]=='a') sum++;
if (s[i-len]=='a') sum--;
j++;
if (t[j]=='a') ans+=len-sum;
else ans+=sum;
}
printf("%d",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
跳石头(stone)
先 STO cyc大佬。
据大佬们说两次LIS+贪心就可以80分，但我却爆0了，果然还是太蒻了。
cyc大佬给我们讲了一个玄学的做法，至今也没有证明，不过就是能过这道题。而且仔细想想好像也挺有道理，也举不出反例来，所以就把它暂时当作正解吧。
解法就是维护两个数组s1[]和s2[]。对于每一个石头s[i],如果它大于s1[]中的最后一个元素，则把他加在后面；否则就在s1[]中找到一个它能够替换的值，并把它放进去。
能被替换的元素就是刚好要比当前石头s[i]大一些，而且加进去以后不会影响s1[]中单调性的元素，即 被替换元素 的前一个元素要小于s[i]。因为可以保证的是s1[]一定单增，所以这个被替换元素可以通过二分来查找到。
然后，将当前石头放入s1[]，然后将被替换的元素当作当前的石头与s2[]进行操作，与s1[]的操作同理。
最后，s1[]和s2[]中元素个数之和即为答案。
我刚写完cyc大佬就给我讲了证明方法，虽然不能严格证明，但是大致可以明白这个算法的道理。
大致这些操作可以分为两种情况：
对于每一个石头
s[i],如果它大于s1[]中的最后一个元素，则把他加在后面
这种情况下就可以将答案+1，没有任何问题
否则就在
s1[]中找到一个它能够替换的值，并把它放进去
我最开始就产生了疑问：s[i]的位置是肯定在此前就加进去的元素的后面的，如果用它替换掉中间一个值怎么行呢？
其实，在这种情况下，答案是没有变化的。所以，我们其实并没有更新答案，这就是理解这种方法的精髓所在。
当我们将s[i]给替换到 $ left $ 这个位置时，可以保证 $ 1..left $ 这个区间内是真真正正确实可以跳到的石头。前面说过，我们并没有更新答案，所以后面那些元素根本不用管。
在最后一个元素被替换掉之前，后面即使再加入元素也只是之前情况下的答案+1，和当前情况没有任何关系，所以最后就可以取整个数组的元素个数作为答案；如果当前最后一个元素后来被替换掉了，则证明当前情况并不是最优解，而替换最后一个也不会产生顺序上的任何问题。
而第二个数组操作和第一个数组相同，证明也就同理了。
综上，这个算法是正确的，并不是玄学的。不得不感叹这个算法的巧妙性和cyc大佬的强大。
先放我的长但是自认为好懂些的代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int s[1005],n,m,ans,s1[1005],s2[1005];
int main()
{
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
n=read();
for (int i=1;i<=n;i++) s[i]=read();
int cnt1=0,cnt2=0;
s1[++cnt1]=1;
ans=1;
for (int i=2;i<=n;i++)
{
int x=s1[cnt1];
if (s[i]>=s[x]) s1[++cnt1]=i,ans++; //直接放入，在这里就可以顺便统计ans
else
{
int left; //被替换的元素在s1中的便号，注意不是s中的
int l=1,r=cnt1;
while (l<=r) //二分查找被替换元素
{
int mid=(l+r)/2;
if (s[s1[mid]]>s[i]) left=mid,r=mid-1;
else l=mid+1;
}
int leftpos=s1[left]; //这是被替换元素在s中的编号，用来下面比较大小
s1[left]=i; //将当前石头替换进去
int y=s2[cnt2];
if (s[leftpos]>=s[y]) s2[++cnt2]=leftpos,ans++; //直接放入，统计ans
else
{
int left2; //s2中被替换元素的编号
int l=1,r=cnt2;
while (l<=r)
{
int mid=(l+r)/2;
if (s[s2[mid]]>s[leftpos]) left2=mid,r=mid-1;
else l=mid+1;
}
s2[left2]=leftpos; //替换。因为不需要统计更多的，所以到这就行了
}
}
}
printf("%d",ans);
return 0;
}
下面放一个cyc大佬极简代码，据他说他还有更短的版本。 %cyc
// By Dalao cyc,%cyc
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 5005
int n, i, x, t[N];
int q[N][N];
void up(int p, int x) {
if (x >= q[p][t[p]]) { q[p][++t[p]] = x; return; }
int l = 1, r = t[p], mid, u;
while (l <= r) {
if (q[p][mid = (l + r) >> 1] > x) {
u = mid; r = mid - 1;
} else {
l = mid + 1;
}
}
up(p + 1, q[p][u]), q[p][u] = x;
}
int main() {
scanf("%d", &n);
for (i = 1; i <= n; ++ i) scanf("%d",&x), up(1,x);
for (int i = 1; ; ++ i) {
t[i] += t[i - 1];
if (t[i] == n) break;
}
printf("%d", t[2]);
return 0;
}
显而易见，cyc大佬还要统计后续数组的值，时间效率上肯定会差点，空间也会开大点。但是代码又短又巧妙，实在是太强辣！
总结
我个人的第一次提交只有160，得分为90+70+0，使用的算法的最高得分为100+70+80=250.
各题总结：
- 第一题情况考虑不完整，想到了相等的请况却没想到后续的问题
- 第二题没有找出规律，最后暴力没有失分，没什么非知识性的问题
- 第三题想到80分做法但写错，应该是对LIS算法的掌握不够熟练
总体失分原因:
- 对细节的思考不够到位
- 错误地追求每题AC，导致第二题花了很长时间没想到正解就心态比较爆炸，可能也是第三题爆炸的原因
- 对于部分算法掌握还不够熟练，人笨就要多刷题
总体来说这套题打的不理想，但是也发现了很多问题（我太菜了），所以还是很有价值的。
以上。
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/contest-summary-1.html