CCF-NOIP-2018 提高组(复赛) 模拟试题(四)

来源：cnblogs　　作者：迷失の风之旅人　　时间：2018/11/1 9:38:57　　对本文有异议

T1 贪吃蛇

【问题描述】

贪吃蛇是一个好玩的游戏。在本题中，你需要对这个游戏进行模拟。

这个游戏在一个 $n$ 行 $m$ 列的二维棋盘上进行。我们用 $(x, y)$ 来表示第 $x$ 行第 $y$ 列的格子，那么左上角为 $(1, 1)$，右下角为 $(n, m)$。

我们用一个长度为 $k$ 的不重复的坐标的序列（形如 $(x_1,y_1 )$， $(x_2 , y_2 )$， ... , $(x_k , y_k )$）来表示一条长度为 $k$ 的蛇，其中 $(x_1 , y_1 )$ 称为蛇的头部。在游戏的任何时刻，都满足 $k > 1$。

游戏开始时，蛇的长度为 $1$，坐标为 $(x_s , y_s )$。接下来会进行个操作，每个操作是以下两种类型之

$l$ $1$ $d:$ 蛇的头部往 $d$ 方向伸长一格，其中 $d$ 为 $U D L R$ 之一，分别表示 “上” 、“下” 、 “左” 、 “右” 。
$l$ $2:$ 蛇的尾部缩短一格，保证该操作前蛇的长度大于 $1$。

棋盘上还有 $t (0 ≤ t < nm)$ 个障碍物，分别位于 $(u_i , v_i )$ $(1 ≤ i ≤ t)$，保证没有两个障碍物占据同一个格子。

在任何时候，如果蛇的头部碰到蛇的身体（即蛇的其他格子），或碰到棋盘上的障碍物，或移动到棋盘的边界之外，那蛇会立即死亡。

你的任务是，输入游戏配置以及 $q$ 个操作，判断蛇是否会死亡。

【输入格式】

输入的第一行包含四个非负整数 $n, m, t, q$，具体含义见问题描述。

接下来 $t$ 行，每行两个整数，表示一个障碍物的坐标。保证每个坐标都在棋盘上，即在 $(1, 1)$ 到 $(n, m)$ 之间，且不存在重复的坐标。

接下来一行两个整数，表示游戏开始时蛇的坐标 $(x_s , y_s)$。保证该坐标在棋盘上，且不是任何一个障碍物的坐标。

接下来 $q$ 行，每行给出一个操作，具体格式和含义见问题描述。

【输出格式】

如果在 $q$ 个操作后蛇没有死亡，输出 $-1$，否则输出一个整数 $k$，表示蛇在第
$k$ 个操作之后死亡。

【样例1】

样例输入
3 4 2 10
1 3
3 3
1 1
1 D
1 R
2
1 R
2
1 R
1 U
1 L
1 L
1 L

样例输出
8

数据规模与约定

在所有测试点中，有20%的测试点$n = 1$。
在所有测试点中，有40%的测试点$t = 0$。
在所有测试点中，有20%的测试点满足任何时候蛇的长度不超过$2$。
以上三类特殊的测试点可能存在交叉。
对于全部测试点，$1 ≤ n, m ≤ 100，0 ≤ t < nm，1 ≤ q ≤ 10000$。

题解

简单模拟题，~~甚至不需要思考~~。用一个集合保存所有访问后会导致蛇死掉的点，并使用一个队列保存整只蛇的位置。每当贪吃蛇伸长身子时在队列尾端push入伸长后到达的新位置，并将新位置加入集合。当贪吃蛇缩短时则弹出队首元素，并删除集合中的该点。
ps:需要注意的是，$n$代表的是地图的行数，而$m$代表的是地图的列数。因此，事实上题面里的$x_1$代表的实际上是纵向坐标，$y_1$则代表横向坐标。因此，我们需要先读入变量$y$再读入变量$x$。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    register char c=getchar();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();
    return _*f;
}
int n,m,t,q;
set<pair<int,int> > stone;
queue<pair<int,int> > snake;
int nowy,nowx;
int cmd;
bool init(){
    if(nowx<=0 || nowx>m)return false;
    if(nowy<=0 || nowy>n)return false;
    if(stone.count(make_pair(nowy,nowx)))return false;
    return true;
}
int step=0;
bool sc=1;
int main(){
    freopen("snake.in","r",stdin);
    freopen("snake.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    n=read();m=read();t=read();q=read(); 
    //cout<<"max y:"<<n<<" max x:"<<m<<endl;
    int y,x;
    for(register int i=0;i<t;i++){
        y=read();x=read();
        stone.insert(make_pair(y,x));
        //cout<<"stone:"<<x<<" "<<y<<endl;
    }
    y=read();x=read();
    //cout<<"snakenow:"<<x<<" "<<y<<endl;
    snake.push(make_pair(y,x));
    stone.insert(make_pair(y,x));
    nowx=x,nowy=y;
    //cout<<x<<" "<<y;
    while(q--){
        step++;
        cmd=read();
        if(cmd==1){
            char cas=' ';
            while(cas==' ')cas=getchar();
            //cout<<cmd<<" "<<cas<<endl;
            if(cas=='U'){
                nowy-=1;
                if(!init()){
                    sc=0;
                    break;
                }
                snake.push(make_pair(nowy,nowx));
                stone.insert(make_pair(nowy,nowx));
            }
            if(cas=='D'){
                nowy+=1;
                if(!init()){
                    sc=0;
                    break;
                }
                snake.push(make_pair(nowy,nowx));
                stone.insert(make_pair(nowy,nowx));
            }
            if(cas=='L'){
                nowx-=1;
                if(!init()){
                    sc=0;
                    break;
                }
                snake.push(make_pair(nowy,nowx));
                stone.insert(make_pair(nowy,nowx));
            }
            if(cas=='R'){
                nowx+=1;
                if(!init()){
                    sc=0;
                    break;
                }
                snake.push(make_pair(nowy,nowx));
                stone.insert(make_pair(nowy,nowx));
            }
            //cout<<nowx<<" "<<nowy<<endl;
        }
        else{
            stone.erase(snake.front());
            snake.pop();
        }
        //cout<<"snakenow:"<<nowx<<" "<<nowy<<endl;
    }
    if(sc)cout<<-1<<endl;
    else cout<<step<<endl;
    return 0;
}

T2 分糖果

【问题描述】

到了学期末，在幼儿园工作的刘老师要为自己所带班级的小朋友分发糖果。
刘老师的班上共有$n$名小朋友，第 i 位小朋友对糖果的喜爱程度为$a_i$，他在本学期的表现评分为$b_i$。刘老师分配糖果的方法如下：
1. 以某个顺序安排这$n$位小朋友排成一排，刘老师从头到尾逐一分配糖果。
2. 队伍中的第$i$位小朋友至少获得的糖果数量为前$i$位小朋友对糖果的喜爱程度之和。
3. 由于第$i$位小朋友可以看见第$i-1$位小朋友获得的糖果数量，为了不让第$i$位小朋友觉得不公平，刘老师保证第$i$位小朋友获得的糖果不少于第$i-1$位小朋友。
4. 在为第 i 位小朋友分配完糖果后，刘老师将额外再奖励第 i 位小朋友数量为$b_i$的糖果。
我们设第$i$位小朋友获得的糖果数量为$c_i$，形式化地讲：
\[c_i = \begin{cases} a_1+b_1 & i=1 \max(c_{i-1},\sum\limits_{j=1}^{i}a_j)+b_i & i + j \leq n \end{cases}\]
由于预算有限，刘老师希望你能帮她安排这$n$位小朋友的顺序，使得获得糖果最多的小朋友，所获得的糖果数量尽可能少。

【输入格式】

第一行包含一个正整数$T$，表示测试数据的组数。
接下来描述这$T$组测试数据，每组数组的第一行包含一个正整数$n$，表示刘老师班上小朋友的数量。
每组数据接下来$n$行中，每行两个正整数，分别为$a_i和b_i$，含义如问题描述中所述。

【输出格式】

共$T$行，每行包含一个整数，表示被分配到最多糖果的那位小朋友最少获得的糖果数量。

【样例1】

样例输入
1
3
4 1
2 2
1 2

样例输出
8

【样例2】

样例输入
1
12
9 68
18 45
52 61
39 83
63 67
45 99
52 54
82 100
23 54
99 94
63 100
52 68

样例输出
902

数据规模与约定

$n \le 50000,1 \le a_i,b_i \le 10^9$。

题解

简单题，很明显的贪心。有两种贪心的方法，先讲部分分的半错误贪心。
对于整个序列来说，我们考虑每个节点的$a_i$和其$b_i$对答案的影响。因为任取一个节点$i$，其答案的值都是$b_i+x$的形式，因此我们排除$b_i$对答案的影响。（这种常见思路只能得部分分的原因就在这里，后文说明）则因此，对答案有影响的只剩下$a_i$。因为第$i$个人一定可以得到至少$i-1$个人得到的糖的数量，因此我们可以确定一个序列的最大值一定在序列末尾。此时要求$\sum\limits_{j=1}^ia_j$的值最小，因此我们将整个序列按$a_i$的值从小到大排序即可。最后得到的答案总会满足其$\sum\limits_{j=1}^ia_j$最小。

贴出代码。

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
    register char c=get();register long long f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
struct edge{
    long long a,b;
}E[maxn];
bool cmp(edge a,edge b){
    return a.a<b.a;
}
long long n;
long long tot[maxn];
long long pre[maxn];
int main(){
    //freopen("candy.in","r",stdin);
    //freopen("candy.out","w",stdout);
    long long t;
    t=read();
    while(t--){
        n=read();
        for(register long long i=1;i<=n;i++)E[i].a=read(),E[i].b=read();
        sort(E+1,E+1+n,cmp);
        pre[1]=E[1].a;
        for(register int i=2;i<=n;i++)pre[i]=pre[i-1]+E[i].a;
        tot[1]=E[1].a+E[1].b;
        for(register long long i=2;i<=n;i++){
            tot[i]=max(tot[i-1],pre[i])+E[i].b;
        }
        printf("%lld\n",tot[n]);
    }
    return 0;
}

部分分贪心错误性的证明

事实上，在考虑之前的贪心时，我们完全忽略了$b_i$对答案的影响。事实上，当$b_i$足够大导致$c_i$足够大时，其将对往后的答案造成影响，因为整个序列的值应该单调上升。我们考虑让两个数$i和j$中的$b$均对答案产生影响，则应该考虑在排序时将$a$和$b$同时纳入一个不等式中。我们通过构造数据可以发现，$a_i和b_j$以及$a_j和b_i$可以互相影响，再造几组样例自测，因此我们将上述代码中的排序稍作修改即可。

bool cmp(edge a,edge b){
    return min(a.a,b.b)<min(b.a,a.b);
}

T3 序列

【问题描述】

已知一个正整数数组中包含 n 个正整数，依次为 $a_1$ , $a_2$ , $…$ , $a_n$ 。

我们将进行 $m$ 次操作。对于第 $j$ 次操作，会指定一个位置 $p_j$ ，将所有位置 $k$ 满足 $p_j ≤ k ≤ n$ 且大小满足 $a_k ≤ a$， $p_j$ 的正整数 $a_k$ 从数组中拿出，并将这些正整数按照从小到大的顺序进行排序，之后重新放回数组中。

举一个例子，对于正整数数组 $1$ $4$ $2$ $5$ $ 3$ 而言，若选择位置 $p_j = 2$，则拿出的正整数为 $4$ $2$ $3$，分别对应 $k = 2$, $k = 3$, $k = 5$，拿出的正整数排序以后变为 $2$ $3$ $4$，再将它们放回到数组中，数组变成 $1$ $2$ $3$ $5$ $4$。

在每次操作以后，你需要回答整个数组中逆序对的总数。正整数 $a_i$ 与 $a_j$ 构成一个逆序对，当且仅当 $a_i > a_j$ 且 $1 ≤ i < j ≤ n$。

【输入格式】

输入第一行包含两个正整数 $n$ 和 $m$，其中 $n$ 表示数组的长度，$m$ 表示操作的次数。

接下来一行包括$n$个正整数，依次表示正整数数组中的元素 $a_1 , a_ 2 ,…, a_ n$ 。

接下来一行包括$m$个正整数，依次表示询问的位置 $p _1 , p _2 ,…, p_ m$ 。

【输出格式】

输出文件共包括 $m$ 行，其中第 $ j $ 行表示第 $j$ 次操作以后整个数组的逆序对总数。

【样例输入1】

5 3
1 4 2 5 3
5 2 4

【样例输出1】

样例输出
3
1
0

【样例输入2】

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

【样例输出2】

样例输出
12
10
5
0

【数据规模与约定】

$1\le n \le 500000,1\le m \le 500000,1\le a_i \le 10^9,1\le p_j \le n$。

【题解】

每次把拿出来的数暴力排序，然后塞回去，
每次操作时候都重新求一次逆序对。使用$O(n^2)$复杂度算法进行排序和求逆序对，期望得分 20 分。使用 $O(n logn)$复杂度的算法进行排序和求逆序对则可以得到45~50分。这里给出45分的做法。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int tmp[maxn], t[maxn];
int n, m, a[maxn], b[maxn];
long long ans = 0;
inline bool my_cmp(int a, int b) {
    return a > b;
}
inline void merge_sort(int l, int r) {
    int p1, p2, p, mid;
    if (l == r) return ;
    mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    p1 = l, p2 = mid + 1, p = 0;
    while (p1 <= mid || p2 <= r) {
        if (p1 <= mid && (p2 > r || a[p1] <= a[p2])) {
            b[++p] = a[p1];
            p1++;
        } else {
            b[++p] = a[p2];
            p2++;
            ans += mid - p1 + 1;
        }
    }
    for (register int i = 1; i <= p; i++) a[l + i - 1] = b[i];
}
int main() {
    //freopen("sort.in", "r", stdin);
    //freopen("sort.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= n; i++) cin >> a[i];
    while (m--) {
        int p;
        ans = 0;
        int c = 0;
        scanf("%d", &p);
        vector<int> vec;
        memset(t, 0, sizeof t);
        for (register int i = p; i <= n; i++) {
            if (a[i] <= a[p]) {
                vec.push_back(i);
                t[c] = a[i];
                c += 1;
            }
        }
        sort(t, t + n + 1, my_cmp);
        int cnt = 0;
        for (register int i = vec.size() - 1; i >= 0; i--) {
            a[vec[i]] = t[cnt];
            cnt += 1;
        }
        for (register int i = 1; i <= n; i++) tmp[i] = a[i];
        ans = 0;
        merge_sort(1, n);
        printf("%d\n", ans);
        for (register int i = 1; i <= n; i++) a[i] = tmp[i];
    }
    return 0;
}

AC的思路也很容易想到
使用线段树或平衡树维护对答案仍有贡献的$b[i]$即可，每次删掉一个数，就把这个数在线段树中改成无穷大。线段树的每次操作相当于在区间$[p_j,n]$中求最小值的下标。每个数均摊被访问$1$次，总复杂度$O((n + m)logn)$

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long maxn = 500010;
long long a[maxn];
long long minv[4 * maxn];
bool vis[maxn];
long long num[maxn];
long long ans[maxn];
long long to[maxn];
long long back[maxn];
inline void pushup(long long id) {
    minv[id] = minv[id << 1] + minv[id << 1 | 1];
}
inline void build(long long id, long long l, long long r) {
    if (l == r) {
        minv[id] = a[l];
        return;
    }
    long long mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}
inline void update(long long id, long long l, long long r, long long x, long long v) {
    if (l == r) {
        minv[id] += v;
        return;
    }
    long long mid = (l + r) >> 1;
    if (x <= mid) {
        update(id << 1, l, mid, x, v);
    } else {
        update(id << 1 | 1, mid + 1, r, x, v);
    }
    pushup(id);
}
inline long long query(long long id, long long l,long long r,long long x,long long y){
  if(x <= l && r <= y){
    return minv[id];
  }
  long long mid = (l + r) >> 1;
  long long ans = 0;
  if(x <= mid){
    ans = ans + query(id << 1, l, mid, x, y);
  }
  if(y > mid){
    ans = ans + query(id << 1 | 1, mid + 1, r, x, y);
  }
  return ans;
}
long long aim1[maxn];
long long aim2[maxn];
int main() {
    /*freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);*/
    long long n,m;
    scanf("%lld%lld",&n,&m);
    //cin >> n >> m;
    for(register int i = 1;i <= n;i++){
        scanf("%lld",&num[i]);
        //cin >> num[i];
        aim1[i] = num[i];
    }
    sort(aim1+1,aim1+1+n);
    int mm = unique(aim1+1,aim1+1+n) - aim1 - 1;
    for(register int i=1;i<=n;i++){
        num[i] = lower_bound(aim1+1,aim1+1+mm,num[i]) - aim1;
    }
    //cout << "haha";
    /*for(register int i = 1;i <= n;i++){
        scanf("%lld",&aim1[i]);
        //cin >> aim1[i];
        aim2[i] = aim1[i];
    }
    sort(aim1+1,aim1+1+n);
    map<long long,long long> MM;
    for(register long long i = 1;i <= n;i++){
        if(MM[aim1[i]] != 0){
            continue;
        }
        MM[aim1[i]] = i;
    }
    for(register long long i = 1;i <= n;i++){
        num[i] = MM[aim2[i]];
        //cout << num[i] << " ";
    }
    //cout << endl;*/
    memset(a,0,sizeof(a));
    build(1, 1, n);
    for (register long long i = n; i >= 1; i--) {
        if(num[i] == 1){
            ans[i] = 0;
            update(1,1,n,num[i],1);
            continue;
        }
        ans[i] = query(1,1,n,1,num[i]-1);
        update(1,1,n,num[i],1);
    }
    long long now = 0;
    for(register long long i = 1;i <= n;i++){
        now += ans[i];
        to[i] = i+1;
        back[i] = i-1;
    }
    back[n+1] = n;
    to[0] = 1;
    memset(vis,false,sizeof(vis));
    while(m--){
        long long p;
        scanf("%lld",&p);
        //cin >> p;
        if(vis[p] == true){
            cout << now << endl;
            continue;
        }
        for(register long long i = p;i <= n;i = to[i]){
            //cout << i << " ";
            if(num[i] <= num[p]){
                now -= ans[i];
                vis[i] = true;
                ans[i] = 0;
                long long ff = back[i];
                to[ff] = to[i];
                back[to[i]] = ff;
                //back[to[i]] = back[i];
                //to[back[i]] = to[i];
                /*for(int i = 1;i <= n;i++){
                    cout << to[i] << " ";
                }
                cout << endl;*/
            }
        }
        //cout << endl;
        printf("%lld\n",now);
        //cout << now << endl;
    }
    return 0;
}