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

作者: 影踪派熊猫人武僧 | 来源:发表于2018-10-31 15:50 被阅读0次

CCF-NOIP-2018 提高组(复赛) 模拟试题(四)
CCF-NOIP-2018 提高组(复赛) 模拟试题(一)
CCF-NOIP-2018 提高组(复赛) 模拟试题(七)
CCF-NOIP-2018 提高组(复赛) 模拟试题(五)
CCF-NOIP-2018 提高组(复赛) 模拟试题(三)
CCF-NOIP-2018 提高组(复赛) 模拟试题(九)(20
用 python 解 NOIP 竞赛题
信息学学习笔记（1）：可怕的图论
2017年信息学奥赛获奖分数线和获奖名额分配方案
【NOIP复赛篇1】上机指南（一）环境搭建和运行

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;
}

CCF-NOIP-2018 提高组(复赛) 模拟试题(四)
T1 贪吃蛇【问题描述】贪吃蛇是一个好玩的游戏。在本题中，你需要对这个游戏进行模拟。这个游戏在一个行 ...
CCF-NOIP-2018 提高组(复赛) 模拟试题(一)
T1 帽子戏法问题描述小 Y 有一个的“帽子立方体” ，即一个!层的立方体，每层的帽子都可以排成!×!的矩阵。...
CCF-NOIP-2018 提高组(复赛) 模拟试题(七)
T1 Adjoin 【问题描述】定义一种合法的串：串中任何一个数字都与相邻。例如长度为串中，是非法的，因为两边的...
CCF-NOIP-2018 提高组(复赛) 模拟试题(五)
T1 相遇【问题描述】在一场奇怪的梦里，小 Y 来到了一个神奇的国度。这个国度可以用一根数轴表示，小 Y 在 ...
CCF-NOIP-2018 提高组(复赛) 模拟试题(三)
T1 取球游戏问题描述现有个小球，依次编号为到，这些小球除了编号以外没有任何区别。从这个小球中取出个，请问有多...
CCF-NOIP-2018 提高组(复赛) 模拟试题(九)(20
T1 Circle 【问题描述】小 w 的男朋友送给小 w 一个 n 个点 m 条边的图，并且刁难小 w 要她找...
用 python 解 NOIP 竞赛题
以下为2017年全国 NOIP 提高组复赛的第1题： --------------------------...
信息学学习笔记（1）：可怕的图论
到了2019年3月份，我学算法已整一年。这个时候我觉得应该看一下提高组的复赛题了。NOIP 2018提高组初赛的题...
2017年信息学奥赛获奖分数线和获奖名额分配方案
提高组一等奖名额分配方案提高组一等奖全国基准分数线: 200分 A：根据复赛人数和省平均分（占90%）计算； B...
【NOIP复赛篇1】上机指南（一）环境搭建和运行
一、复赛说明信息学奥赛分区联赛（NOIP）分初赛和复赛两个部分，初赛和复赛。初赛是笔试题，在每年的10月份的第二...

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

T1 贪吃蛇

【问题描述】

【输入格式】

【输出格式】

【样例1】

数据规模与约定

题解

T2 分糖果

【问题描述】

【输入格式】

【输出格式】

【样例1】

【样例2】

数据规模与约定

题解

部分分贪心错误性的证明

T3 序列

【问题描述】

【输入格式】

【输出格式】

【样例输入1】

【样例输出1】

【样例输入2】

【样例输出2】

【数据规模与约定】

【题解】

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读