NOIP模拟赛 2017-03-12

本文移植自个人的原博客（原文）

Blue

题目描述

Blue 是个动物学家，不仅喜欢研究猫和老鼠，还喜欢研究青蛙。

他最近开始研究青蛙过河的问题，可以简化成：数轴上 $0$ 为岸边，$L$ 为河对岸。$(0,L)$中间存在 $n$ 个石子。已知青蛙一跳可以跳距离 $D$，而且不能沾水。求问能不能跳到河对岸。

当然他觉得这个问题非常 naïve，于是在思考如果青蛙有$m$个，且石头被踩过之后就会沉下去，$m$ 个青蛙还能不能依次安全过河。如果不能则问最多能有多少个过河。

输入第一行为一个正整数 $T$ 代表数据组数。每组数据第一行四个正整数：$n、m、D、L$。

第二行 $n$ 个升序正整数 $a_i$ 代表第 $i$ 个石子坐标为 $a_i$。保证没有重复且都小于 $L$。

输出 $T$ 行”Excited”代表全部能过河或者一个整数代表有多少个能过河的。

样例输入

5
10 9 16 30
2 4 6 9 11 15 18 19 25 27 
10 1 23 30
10 11 13 14 15 16 18 26 27 29 
10 7 28 30
2 3 7 9 12 15 20 24 27 28 
10 3 18 30
1 6 9 14 18 19 22 27 28 29 
10 7 10 30
1 2 4 6 18 19 20 22 23 26 

样例输出

5
Excited
Excited
Excited
0

数据范围

对于$10 \ percent$的数据保证 $m=1$

对于另外$10 \ percent$的数据保证 $D=L$

对于另外$10 \ percent$的数据保证 $n=L−1$

对于另外$30 \ percent$的数据保证 $n<=100,L<=10^5$

对于$100 \ percent$的数据保证 $m<=n<=10^6,D<=L<=10^9$

数据范围中的 $n、m$ 皆代表题目描述中 $n、m$ 的总和。

题解

这题就是比较简单的二分答案+贪心，一开始想到了这种思路，但一直没有正确的贪心策略，后来开始尝试树状数组，看到$D<=L<=10^9$的数据范围后，又写了回离散化，然后又想到还要记录离散化的前的相对位置和$d$的关系，然后就掉进了深坑中无法自拔。最后半小时重新推了下贪心，（伪）A掉了这题。教训就是不要浮躁，做题要静下心来。

具体的策略就是，每次针对不同答案进行贪心的时，记录一下这些青蛙的位置，然后就没了…

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N =1e6+1;
inline void read(int &x)
{
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}
int tt,n,m,d,l,a[N],b[N];
bool can(int ans)
{
    for(int i=1;i<=ans;++i)b[i]=0;
    int anss=0;
    for(int now=1;now<=n;++now)
    {
        if(a[now]-b[++anss]<=d)b[anss]=a[now];
        if(anss==ans)anss=0;
    }
    for(int i=1;i<=ans;++i)
    if(l-b[i]>d)return 0;
    return 1;
}
int main()
{
//    freopen("Blue.in","r",stdin);
//    freopen("Blue.out","w",stdout);
    read(tt);
    while(tt--)
    {
        read(n),read(m),read(d),read(l);
        for(int i=1;i<=n;++i)read(a[i]);
        int ll=0,rr=m,mid;
        while(ll!=rr)
        {
            mid=ll+rr+1>>1;
            if(can(mid))    ll=mid;
            else            rr=mid-1;
        }
        if(rr==m)    printf("Excited\n");
        else         printf("%d\n",rr);
    }
    return 0;
}

Weed

题目描述

duyege的电脑上面已经长草了，经过辨认上面有金坷垃的痕迹。

为了查出真相，duyege 准备修好电脑之后再进行一次金坷垃的模拟实验。

电脑上面有若干层金坷垃，每次只能在上面撒上一层高度为$v_i$的金坷垃，或者除掉最新$v_i$层（不是量）撒的金坷垃。如果上面只留有不足$v_i$层金坷垃，那么就相当于电脑上面没有金坷垃了。

duyege非常严谨，一开始先给你$m$个上述操作要你依次完成。然后又对实验步骤进行了$q$次更改，每次更改都会改变其中一个操作为另外一个操作。每次修改之后都会询问最终金坷垃的量有多少。

输入第一行为两个正整数$m、q$，接下来$m$行每行$2$个整数$k、v_i$。$k$为$0$时撒金坷垃，为$1$时除金坷垃。接下来$q$行每行$3$个整数$c_i、k、v_i$，$c_i$代表被更改的操作是第$c_i$个，后面$2$个数描述更改为这样的操作。

输出 $q$ 行代表每次金坷垃的量为多少。

样例输入

10 5
0 10
1 5
0 13
0 18
0 2
1 1
0 8
0 9
1 3
0 7
9 0 3
10 1 7
6 0 8
10 0 5
8 1 2

样例输出

58
0
0
66
41

数据范围

对于$30 \ percent$的数据，$m<=1000,q<=1000$

对于另外$20 \ percent$的数据，每次 $k=1$ 时都会将金坷垃清空。

对于$100 \ percent$的数据，$m<=2*10^5,q<=2*10^5,v_i<=10^4$

题解

由于该题涉及中间量的改变，所以要用线段树来记录，一开始想的是链表，每次操作修改一下链表中与更改操作相关的指针，然而最后也没有实现…

题解还是挺巧妙，将每次操作依次进栈，对于每次更改，即为将被更改操作以上的所有操作出栈，将更改后的操作入栈，然后将其余出栈操作按原顺序入栈，我在考场时也仅止步于此，这样的时间复杂度太高，最后并没有尝试这样写。题解便巧妙在用线段树来记录每一段操作的三项信息：执行完这段操作后会删除多少金坷垃，会插入多少，一共又是多少。然后通过一个查找函数来依次向父亲节点更新。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline void read(int &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
const int N =2e5+7;
struct build{int sum,in,out;}tr[8*N];
int n,q,k,a[N],tot;
int find(int x,int pot)
{
    if(pot>=tr[x].in)            return 0;
    if(!pot)                    return tr[x].sum;
    if(pot<=tr[x*2+1].in)
    return tr[x].sum-tr[x*2+1].sum+find(x*2+1,pot);
    return find(x*2,pot-tr[x*2+1].in+tr[x*2+1].out);
}
void update(int x)
{
    tr[x].in=tr[x*2+1].in+max(0,tr[x*2].in-tr[x*2+1].out);
    tr[x].out=tr[x*2].out+max(0,tr[x*2+1].out-tr[x*2].in);
    tr[x].sum=tr[x*2+1].sum+find(x*2,tr[x*2+1].out);
}
void build(int x,int l,int r)
{
    if(l==r)
    {
        if(a[l]<0)    tr[x].out=-a[l];
        else        tr[x].in=1,tr[x].sum=a[l];
    }
    else
    {
        int mid=l+r>>1;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        update(x);
    }
}
void change(int x,int pot,int w,int l,int r)
{
    if(l==r)
    {
        memset(&tr[x],0,sizeof(tr[x]));
        if(w<0)        tr[x].out=-w;
        else        tr[x].in=1,tr[x].sum=w;
    }
    else
    {
        int mid=l+r>>1;
        if(pot>mid)    change(x*2+1,pot,w,mid+1,r);
        else        change(x*2,pot,w,l,mid);
        update(x);
    }
}
int main()
{
//    freopen("weed.in", "r", stdin);
//    freopen("weed.out", "w", stdout);
    read(n),read(q);
    for(int i=1;i<=n;++i)
    {
        read(k),read(a[i]);
        if(k)a[i]*=-1;
    }
    build(1,1,n);
    while(q--)
    {
        int x,w;
        read(x);read(k);read(w);
        if(k)w*=-1;
        change(1,x,w,1,n);
        printf("%d\n",tr[1].sum);
    }
}

Drink

题目描述

在一个遥远的国度有一个腰缠万贯的资本家Link，每一个拜访他的人都可以得到一份丰厚的赏赐。有一名穷困潦倒的旅行者毒液哥来到了Link家。Link智商超群（不然也赚不到这么多资本），所以决定用特殊的方法赏赐毒液哥。

Link的藏宝库是一个$N * M$棋盘，每个格子里都有宝物。Link会对棋盘做$Q$次操作，每次操作会选取棋盘内一个正方形，让其中的宝物顺时针转一圈（旋转$90$度）。毒液哥不仅财富值被Link碾压，智商也同样被碾压（不然怎么会这么穷），但是贪财的他想知道最后棋盘内所有的宝物价值以方便他挑选。

作为建设中国特色社会主义道路上的一颗螺丝钉，你能帮助缩小无产阶级代表（毒液哥）和资产阶级代表（Link）之间的贫富差距么。

输入第一行三个数 $N, M, Q$ 分别表示棋盘的行数、列数和操作个数。

接下来 $N$ 行每行 $M$ 个数表示一开始棋盘上宝物的价值。

接下来 $Q$ 行每行 $3$ 个数 $x, y, c$ 表示操作区域为以第 $x$ 行第 $y$ 列为左上角的边长为 $c$ 的正方形。

输出一个 $N * M$ 的矩阵表示最后的棋盘。

样例输入

4 4 3
1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8
1 1 3
3 3 2
2 2 2

样例输出

1 5 1 4 
2 7 6 8 
3 7 2 3 
5 6 8 4 

数据范围

对于 $30 \ percent$的数据，$N, M, Q <= 100$.

对于另外 $30 \ percent$的数据，保证所有 $Q$ 个正方形两两之间不相交或相等。

对于 $100 \ percent$的数据, $N, M, Q <= 1000$，棋盘内所有数取值都为 $0 ~ 9$。

题解

以前写过类似的模拟题，便套用了之前的思路，即对于每个点，记录其前后左右的点，然后将所有点的朝向初始化为朝前（$p=0$），每次旋转，更改一下最外围点的前后左右点，对于内圈的点，其前后左右的点没有改变，只需要将所有被旋转的点的朝向旋转一下（$p=(p+1)%4$），这一步操作通过二维线段树来实现（然而并不会写）。题解的大体思路相近，只是在处理朝向那里更加巧妙，且也没有用二维数组存储每个点的相对位置，而是用一维数组操作，其他的还有许多处理上的技巧。

/*
* @Author: 閫搁棽
* @Date:   2016-09-25 13:04:44
* @Last Modified by:   閫搁棽
* @Last Modified time: 2016-10-01 10:19:00
*/

#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "algorithm"
#include "cstring"
#include "queue"

using namespace std;

#define INF 0x3F3F3F3F
#define MAX_SIZE 2005
#define Eps
#define Mod
#define Get(x, a) (x ? x -> a : 0)
#define Travel(x) for(typeof(x.begin()) it = x.begin(); it != x.end(); ++it)

inline int Get_Int()
{
    int Num = 0, Flag = 1;
    char ch;
    do
    {
        ch = getchar();
        if(ch == '-')
            Flag = -Flag;
    }
    while(ch < '0' || ch > '9');
    do
    {
        Num = Num * 10 + ch - '0';
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9');
    return Num * Flag;
}

int N, M, Q;
int A[MAX_SIZE * MAX_SIZE][4], Map[MAX_SIZE][MAX_SIZE];

inline void Move(int &Direction, int &Now, int j)
{
    int Next = A[Now][j - Direction + 4 & 3];
    for(Direction = 0; A[Next][j - Direction + 6 & 3] != Now; ++Direction);
    Now = Next;
}

int main()
{
#ifndef ONLINE_JUDGE
//    freopen("drink.in", "r", stdin);
//    freopen("drink.out", "w", stdout);
#endif
    cin >> N >> M >> Q;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            Map[i][j] = Get_Int();
    for(int i = 1; i <= (N + 2) * (M + 2); ++i)
    {
        A[i][0] = i - M - 2;
        A[i][1] = i + 1;
        A[i][2] = i + M + 2;
        A[i][3] = i - 1;
    }
    while(Q--)
    {
        int x = Get_Int(), y = Get_Int(), c = Get_Int();
        int Direction = 0, Now = 1;
        vector< pair<int, int> > Border[4][2];
        for(int i = 1; i <= x; ++i)
            Move(Direction, Now, 2);
        for(int i = 1; i <= y; ++i)
            Move(Direction, Now, 1);
        for(int j = 0; j < 4; ++j)
            for(int i = 1; i <= c; ++i)
            {
                Border[j][0].push_back(make_pair(Direction, Now));
                Move(Direction, Now, j);
                Border[j][1].push_back(make_pair(Direction, Now));
                Move(Direction, Now, j + 2 & 3);
                if(i != c)
                    Move(Direction, Now, j + 1 & 3);
            }
        for(int j = 0; j < 4; ++j)
            for(int i = 0; i < c; ++i)
            {
                pair<int, int> Now = Border[j][1][i];
                A[Now.second][j + 6 - Now.first & 3] = Border[j + 3 & 3][0][i].second;
                Now = Border[j][0][i];
                A[Now.second][j + 4 - Now.first & 3] = Border[j + 1 & 3][1][i].second;
            }
    }
    int Direction = 0, Now = 1;
    for(int i = 1; i <= N; ++i)
    {
        Move(Direction, Now, 2);
        int temp = Direction, Next = Now;
        for(int j = 1; j <= M; ++j)
        {
            Move(temp, Next, 1);
            printf("%d ", Map[(Next - 1) / (M + 2)][(Next - 1) % (M + 2)]);
        }
        printf("\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}