2017 9.17 NOIP模拟 胡策题总结

Mushroom的序列

【问题描述】
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

这道题很简单， 因为只是求连续只改一个数的LIS， 那么我们对于每个数看以他结尾能有多长(后缀)， 以他开头能有多长(前缀)， 我们再枚举每个数改变和不改变， 来连接每个数的前缀和后缀. ans取max即可， 复杂度O(n).

#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 2e9;
const int maxn = 100005;
int a[maxn], n, ans;
int fr[maxn],bac[maxn];
int main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%d",&n);ans = 1;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    a[0] = inf; a[n + 1] = -inf;
    for(int i = 1; i <= n; i++) fr[i] = a[i - 1] < a[i] ? fr[i - 1] + 1 : 1;
    for(int i = n; i >= 1; i--) bac[i] = a[i] < a[i + 1] ? bac[i + 1] + 1 : 1;
    for(int i=1;i<=n;i++){
        ans = max(ans, fr[i - 1] + 1);
        ans = max(ans, bac[i + 1] + 1);
        if(a[i + 1] - a[i - 1] >= 2) ans = max(ans, fr[i - 1] + bac[i + 1] + 1);
    }
    printf("%d\n", ans);
    return 0;
}

---

Mushroom的区间

【题目描述】
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种可能。

说的是可以得到多少区间， 实际上是多少个序列…要不然样例出不来8… 对于加入一个l， r， 如果说已经有i ~ l - 1， r + 1 ~ j， i ~j的话， 那么这个区间就可以被其他区间表示出来. 发现实际上就是个连通性的问题， 如果l和r已经能被表达， 那么ans就不变， 否则ans * 2(因为说明他一定能都表达自己， 能表达自己的那部分只有0， 1两种type， 所以在原来的基础上 * 2）. 上面说的i~l-1， r + 1~j可以是很多区间连起来表达的.
对于这种判联通的当然是用并查集啦…每次合并l， r+1， 本来就在集合里不管， 不再就合并同时ans * 2.
如果没搞懂联通的话， 可以模拟这组数据， 配合程序你就能明白.
4 3
1 2
3 4
1 4

ans: 4 (0011， 1100， 0000， 1111).

#include<stdio.h>
#define Mercer register int
const int mod = 1e9 + 7;
const int maxn = 100005;
int n, m, fa[maxn], l, r, ans;
int find(int x) {return (fa[x] == x) ? x : fa[x] = find(fa[x]);}
inline bool uni(int p, int q){
    p = find(p), q = find(q);
    if(find(p) == find(q)) return false;
    fa[p] = q; return true;
}
int main(){
    freopen("seg.in", "r", stdin);
    freopen("seg.out", "w", stdout);
    ans = 1;
    scanf("%d%d", &n, &m);
    for(Mercer i = 1; i <= n; ++i) fa[i] = i;
    for(Mercer i = 1; i <= m; ++i){
        scanf("%d%d", &l, &r);
        if(uni(l, r + 1)) ans = ans * 2 % mod;
    }
    printf("%d\n", ans);
    return 0;
}

---

来自风平浪静的明天

【题目描述】
冬眠了五年，光终于从梦中醒来。
千咲、要，大家都在。
隐约记得“昨天”的海船祭，爱花意外成为贡女，沉入海底。
海面冰封，却有丝丝暖流在冰面之下涌动。
此时，爱花沉睡在祭海女神的墓地。她的胞衣在一点点脱落，化作一簇簇暖流，夹杂着她的感情，向海面上涌去。
爱花，你在哪里？
五年之后，纺已经成为海洋学研究科的大学生。
在纺的帮助下，光得知了海面下海流的情况。
纺告诉光，暖流一旦产生，就会不断地向四周扩散，直到遇到海中的岩石。
红腹海牛，快告诉光，爱花在哪里。
纺帮你绘制了一张海流情况图，长度为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出的这题= =

题读了好久… 一开始感觉是个H都可以啊…后面发现不是这样的. 如(2, 4)开始扩张， 第3s的话右上角的B就应该被覆盖成H了…所以说所有的边界H到爱花的位置应该同样的距离.
所以准备爆搜…后面发现记忆化搜索可以稳过， 设dp[x][y][res]表示在x， y位置上还剩res步走下去是否合法.
因为最多n * m * (n+m)种状态， 所以记忆化搜索就过.

#include<stdio.h>
#include<cstring>
#define clear(a) memset(a, -1, sizeof(a))
const int maxn = 305;
char ss[maxn];
int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
int n, m, dp[maxn][maxn][maxn * 2], mp[maxn][maxn];
bool dfs(int x, int y, int res){
    bool ok = true;
    if(dp[x][y][res] != -1) return dp[x][y][res];
    if(mp[x][y] == -1) return dp[x][y][res] = 1;
    if(!res) return dp[x][y][res] = (mp[x][y] == 1);
    for(int k = 0; k < 4; ++k)
        if(!mp[x + dx[k]][y + dy[k]]) return dp[x][y][res] = 0;
    for(int k = 0; k < 4; ++k)
        if(ok) ok = dfs(x + dx[k], y + dy[k], res - 1);
    return dp[x][y][res] = ok;
}
int main(){
    freopen("calm.in", "r", stdin);
    freopen("calm.out", "w", stdout);
    clear(mp), clear(dp);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%s", ss + 1);
        for(int j = 1; j <= m; ++j){
            if(ss[j] == 'B') mp[i][j] = 0; 
            if(ss[j] == 'H') mp[i][j] = 1;
        }
    }
    for(int p = n + m; p >= 0; --p)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(mp[i][j] == 1 && dfs(i, j, p)){
                    printf("%d %d\n", i, j);
                    return 0;
                }
    puts("-1");
    return 0;
}

总结

AK! 撒花留念!
这次的考试策略还是不错的， 先20分钟通读， 开始写t1， t1一开始dp没写出来， 过了20分钟没有新思路， 先去看t2. 摸索了5分钟大概想到了并查集， 写了代码验证了几组没有问题就去写t3. t3花了很大时间， 因为读题蛮费力， 并且很多东西要考虑， 后面想到dfs记忆化搜索可过就写了t3. 最后回来重写了t1.

总结一下以后的考试策略. 先20分钟通读， 再想最拿手的某题开始写. 若十分钟没有思路就换题想. 都想不到就先写最拿手的暴力， 以后也可以拿来做对拍用. 每道题写完了先出几组有特殊情况的小数据， 验证算法. 三道题写完了若有空余时间， 就再检查每道题， 通读一遍感觉没错再开始对拍. 最后30分钟除非有绝对把握不写新程序， 没有把握不改程序. 最后5分钟绝对不改， 检查每道题是否放在目录下等问题.

爆搜以后还得再练练~