9.17NOIP模拟赛

Mushroom的序列（seq.cpp/c/pas）
【问题描述】
Mushroom手中有n个数排成一排，现在Mushroom想取一个连续的子序列，使得这个子序列满足：最多只改变一个数，使得这个连续的子序列是严格上升子序列，Mushroom想知道这个序列的最长长度是多少。
【输入格式】
第一行一个整数n，表示有n个数。
第二行为n个数。
【输出格式】
一个数，为最长长度。
【输入样例】
6
7 2 3 1 5 6
【输出样例】
5
【样例解释】
选择第2个数到第6个数，把1改变成4即可。
【数据范围】
对于30%的数据，n<=10
对于60%的数据，n<=1000
对于100%的数据，n<=100000

题解：由于题目说了是连续的子序列（考试时又没看到。。。），所以就从每个点贪心地往两边找，最后能凑到一块儿就凑到一块儿更新答案即可，完了，就这么简单，没写对。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
const int MAXN=1e5+4,INF=INT_MAX;
int n,a[MAXN],f[MAXN],g[MAXN],ans=0;
struct Node {
    int val,id;
}s[MAXN];
inline int read() {
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int main() {
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    n=read();
    for (register int i=1;i<=n;++i) a[i]=read();
    a[0]=0,a[n+1]=INF;
    for (register int i=1;i<=n;++i)
        f[i]=a[i]>a[i-1]?f[i-1]+1:1,ans=max(ans,f[i]);
    for (register int i=n;i;--i)
        g[i]=a[i]<a[i+1]?g[i+1]+1:1,ans=max(ans,g[i]);
    ans=min(ans+1,n);
    for (register int i=1;i<=n;++i) {
        if (a[i+1]-a[i-1]>1)
            ans=max(ans,f[i-1]+g[i+1]+1);
    }
    printf("%d\n",ans);
    return 0;
}

Mushroom的区间（seg.cpp/c/pas）
【题目描述】
Mushroom有一行数，初始时全部是0。现在Mushroom有m个区间[L,R]，他希望用以下操作得到新的序列。
从m个给定区间中选择一个区间[s,t]，把区间中的数对应元素全部翻转。（0变1,1变0）
请告诉Mushroom他能得到多少区间。（模10^9+7）
【输入格式】
第一行包含两个整数n，m。表示n个数和m个区间。
接下来m行是所表示的区间。
【输出格式】
一个整数，表示能得到的区间数。
【样例输入】
3 3
1 1
2 2
3 3
【样例输出】
8
【数据范围】
对于30%的数据，n,m<=20
对于60%的数据，n,m<=100
对于100%的数据，n,m<=100000
【样例解释】
每个位置都可以单个修改，所以有8种可能。

题解：不知道从哪里可以看出来每个区间可以选多次。。。如果两个区间无交集且它们并起来另一个已知（给定）区间，那么这样的区间无效。有效的区间对答案的贡献为答案的一倍，然后一边并查集，一边乘2就行了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int MAXN=1e5+4,MOD=1e9+7;
int n,m,ans=1,fa[MAXN];
int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main() {
    freopen("seg.in","r",stdin);
    freopen("seg.out","w",stdout);
    scanf("%d",&n);
    for (register int i=0;i<=n;++i) fa[i]=i;
    scanf("%d",&m);
    for (register int i=0;i<m;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        u=find(u-1),v=find(v);
        if (u^v) {
            ans=(ans<<1)%MOD;
            fa[u]=v;
        }
    }
    printf("%d\n",ans);
    return 0;
}

来自风平浪静的明天（calm.cpp/c/pas）
【题目描述】
冬眠了五年，光终于从梦中醒来。
千咲、要，大家都在。
隐约记得“昨天”的海船祭，爱花意外成为贡女，沉入海底。
海面冰封，却有丝丝暖流在冰面之下涌动。
此时，爱花沉睡在祭海女神的墓地。她的胞衣在一点点脱落，化作一簇簇暖流，夹杂着她的感情，向海面上涌去。
爱花，你在哪里？
五年之后，纺已经成为海洋学研究科的大学生。
在纺的帮助下，光得知了海面下海流的情况。
纺告诉光，暖流一旦产生，就会不断地向四周扩散，直到遇到海中的岩石。
红腹海牛，快告诉光，爱花在哪里。
纺帮你绘制了一张海流情况图，长度为N，宽度为M。
海很大，一边有沙滩，一边一望无际，但长度和宽度都不会超过300。沙滩是金黄色的，所以用Y表示。海是蓝色的，所以用B表示。暖流很暖和，所以用H表示
海中有大大小小的石头。石头很危险，所以用X表示
光相信自己一定能找到爱花（爱花的位置只有一种可能）
【输入格式】
第一行包括两个整数N,M。
接下来N行，每行M个字符。
【输出格式】
仅一行，表示爱花的位置（如果你无能为力，请输出 -1 ，只要你尽力，光不会责怪你）
【样例输入】
5 5
YYYHB
YYHHH
YHHXB
BBHBB
BBBBB
【样例输出】
2 3
【数据范围】
对于30%的数据，n,m<=10
对于70%的数据，n,m<=100
对于100%的数据，n,m<=300
【样例解释】
在(2,3)出现第一个H后，经过3s后，出现样例输入的地图。
P.S. Mushroom拜托他GF出的这题= =

题解：f[dep][i][j]表示从(i,j)往前走dep步是否可行，记忆化搜索即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=302;
int n,m,nm;
char mp[MAXN][MAXN];
bool vis[MAXN<<1][MAXN][MAXN],f[MAXN<<1][MAXN][MAXN];
bool dfs(int dep,int x,int y) {
    if (x==0||x==n+1||y==0||y==m+1||mp[x][y]=='X'||mp[x][y]=='Y') return true;
    if (vis[dep][x][y]) return f[dep][x][y];
    if (dep==0) {
        vis[dep][x][y]=true;
        return f[dep][x][y]=(mp[x][y]=='H');
    }
    if (mp[x][y]=='B') {
        vis[dep][x][y]=true;
        return f[dep][x][y]=false;
    }
    vis[dep][x][y]=true;
    return f[dep][x][y]=dfs(dep-1,x+1,y)&&dfs(dep-1,x,y+1)&&dfs(dep-1,x-1,y)&&dfs(dep-1,x,y-1);
}
int main() {
    freopen("calm.in","r",stdin);
    freopen("calm.out","w",stdout);
    scanf("%d%d",&n,&m);
    nm=n+m;
    for (int i=1;i<=n;++i)
        scanf("%s",mp[i]+1);
    for (int k=1;k<=nm;++k)
        for (int i=1;i<=n;++i)
            for (int j=1;j<=m;++j)
                if (mp[i][j]=='H') dfs(k,i,j);
    int x=0,y=0;
    for (int k=nm;k;--k)
        for (int i=1;i<=n;++i)
            for (int j=1;j<=m;++j)
                if (f[k][i][j]) {
                    printf("%d %d\n",x=i,y=j);
                    return 0;
                }
    if (x+y==0) puts("-1");
    return 0;
}

总结：
考完复盘发现这场考试是半个月来最贴近NOIP风格的一场，但是反而是我考的最差的。每道题各反映出一个问题：简单题把握不住，思维题想不出来，搜索题写不出来。其中最严重的是第一个和第三个（如果第二题明确说了一个区间可以选多次，应该能做出来，当时已经往这个方向考虑过），毕竟NOIP考的即使变得再难也脱离不了这些。后面个人训练的方向要偏基础一点，不能一味追求算法，要增大dp训练力度，抽空练搜索题，还要注意一些简单算法的灵活运用（如并查集，双指针扫描等……）