CCF-NOIP-2018 提高组(复赛) 模拟试题(四)
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; }