普及-简单的模拟

开始普及组的训练!所谓模拟,就是直接根据题意编写,思维难度简单。

P1003 铺地毯

题目描述

为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 n 张地毯,编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

说明

【样例解释1】

如下图,111 号地毯用实线表示,222 号地毯用虚线表示,333 号用双实线表示,覆盖点(2,2)(2,2)(2,2)的最上面一张地毯是 333 号地毯。

img

【数据范围】

对于30% 的数据,有 n≤2 ;
对于50% 的数据,0≤a,b,g,k≤100;
对于100%的数据,有 0≤n≤10,000,0≤a,b,g,k≤100,000。

noip2011提高组day1第1题

Code $O(n)$

纯模拟的话直接开个地面数组,用每个地毯给地面赋值,$O(nS)$(S是平均地毯面积)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

struct Carpet //地毯
{
int x; int x_len;
int y; int y_len;
};

bool coverd(Carpet now, int x, int y){ //是否被覆盖?
if(x - now.x >= 0 && (x - now.x) <= now.x_len && (y - now.y) >= 0 && (y - now.y) <= now.y_len)
return 1;
return 0;
}

int main() {
int n, x, y;
vector<Carpet> ca;
cin>>n;
for(int i = 0; i < n; ++i){
Carpet tmp;
cin>>tmp.x>>tmp.y>>tmp.x_len>>tmp.y_len;
ca.push_back(tmp);
}
cin>>x>>y;

int ans=0;
for(int i = 0; i < n; ++i){
if(coverd(ca[i], x, y)) ans = max(ans, i+1); //保留最上面的地毯
}
printf("%d\n", ans==0?-1:ans);
}

如果逆序查找可以提前退出,优化最好情况的复杂度。

P1067 多项式输出

题目描述

一元nnn次多项式可用如下的表达式表示:

img

其中,$a_ix^i​$称为i次项,a_i 称为i次项的系数。给出一个一元多项式各项的次数和系数,请按照如下规定的格式要求输出该多项式:

  1. 多项式中自变量为x,从左到右按照次数递减顺序给出多项式。
  2. 多项式中只包含系数不为0的项。
  3. 如果多项式n次项系数为正,则多项式开头不出现“+”号,如果多项式n次项系数为负,则多项式以“−”号开头。
  4. 对于不是最高次的项,以“+”号或者“−”号连接此项与前一项,分别表示此项系数为正或者系数为负。紧跟一个正整数,表示此项系数的绝对值(如果一个高于0次的项,其系数的绝对值为1,则无需输出1)。如果x的指数大于1,则接下来紧跟的指数部分的形式为“$x^b$”,其中b为x的指数;如果x的指数为1,则接下来紧跟的指数部分形式为“x”;如果 x 的指数为0,则仅需输出系数即可。
  5. 多项式中,多项式的开头、结尾不含多余的空格。

说明

NOIP 2009 普及组 第一题

对于100%数据,0≤n≤100, -100≤系数≤100

Code

咋这么烦呢。

要考虑的边界情况很多。照题目依次实现较好。辣鸡模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;

int main() {
int n, tmp;
bool flag=0;
cin>>n;

while(n>=0){
cin>>tmp;
if(tmp==0){
n--;
continue;
}
if(flag==0) flag=1;
else if(tmp>0) cout<<"+";

if(tmp==-1){
if(n==0)cout<<"-1";
else cout<<"-";
}
else if(tmp!=1) cout<<tmp;

if(n==0 &&tmp==1) cout<<tmp;

if(n!=0){
if(n==1) cout<<"x";
else cout<<"x^"<<n;
}
n--;
}
return 0;
}

P1540 机器翻译 循环队列+缓存原理

题目背景

小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。

题目描述

这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。

假设内存中有M个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M−1,软件会将新单词存入一个未使用的内存单元;若内存中已存入M个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。

假设一篇英语文章的长度为N个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。

说明

每个测试点1s

对于10%的数据有M=1,N≤5。

对于100%的数据有0≤M≤100,0≤N≤1000。

整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况:

空:内存初始状态为空。

1.1 :查找单词1并调入内存。

2. 12:查找单词2并调入内存。

3. 12:在内存中找到单词1。

4. 125:查找单词5并调入内存。

5. 254:查找单词4并调入内存替代单词1。

6.254:在内存中找到单词4。

7.541:查找单词1并调入内存替代单词2。

共计查了5次词典。

Code

循环队列

用取模模拟循环队列。(模N的剩余类加群是循环群)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;

int main() {
int M,N;
cin>>M>>N;
int *cache = new int [M];
int base = 0, top = 0;

while(N--){
int tmp;
cin>>tmp;
bool write = 1;
for(int i = base; i < top; ++i){
if(cache[(base+i)%M] == tmp) write = 0; //命中,不写入
}
if(write){
if(top-base < M){ //内存未满,写入
cache[top++] = tmp;
}
else{ //内存已满,覆盖首项
cache[top++%M] = tmp; base++;
}
}
}

cout<<base+M; //总不命中次数 = 热不命中 + 冷启动

delete[] cache;
return 0;
}

P1056 排座椅 多重排序

题目描述

上课的时候总会有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的D对同学上课时会交头接耳。

同学们在教室中坐成了M行N列,坐在第i行第j列的同学的位置是(i,j),为了方便同学们进出,在教室中设置了K条横向的通道,L条纵向的通道。

于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了2个会交头接耳的同学,那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生的对数最少。

说明

img

上图中用符号*、※、+标出了3对会交头接耳的学生的位置,图中3条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。

2008年普及组第二题

Code

重点就是统计、筛选+排序(可以直接排两次)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define MAXN 2005

struct answer{
int site; //走廊位置
int ans; //有多少交头接耳的学生对
};

bool cmp (answer x, answer y){
return x.ans > y.ans;
}

bool cmp2 (answer x, answer y){
return x.site < y.site;
}

int main() {
int M,N,K,L,D;
cin>>M>>N>>K>>L>>D;
int x[MAXN], y[MAXN], p[MAXN], q[MAXN];
answer ans_U[1005], ans_V[1005];
for(int i = 0; i < 1005; i++){
ans_U[i].site = ans_V[i].site = i;
ans_U[i].ans = ans_V[i].ans = 0;
}

for(int i = 0; i < D; ++i){ //边输入边统计
cin>>x[i]>>y[i]>>p[i]>>q[i];
if(x[i] == p[i]){
ans_V[min(y[i], q[i])].ans++;
}
else ans_U[min(x[i], p[i])].ans++;
}
sort(ans_U, ans_U + 1005,cmp); //按大小排序,确保要输出的部分在前面
sort(ans_V, ans_V + 1005,cmp);

sort(ans_U, ans_U + K,cmp2); //要输出的部分按位置排序
sort(ans_V, ans_V + L,cmp2);
for(int i = 0; i < K; ++i){
cout<<ans_U[i].site<<" \n"[i==K-1];
}
for(int i = 0; i < L; ++i){
cout<<ans_V[i].site<<" \n"[i==L-1];
}

return 0;
}

P1328 生活大爆炸版石头剪刀布 循环队列

题目描述

石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一 样,则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势:

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。

img

现在,小 A小 B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的,但周期长度不一定相等。例如:如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 6 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”,而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为 5 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”

已知小 A小 B 一共进行 NNN 次猜拳。每一次赢的人得 1 分,输的得 0 分;平局两人都得 0 分。现请你统计 N 次猜拳结束之后两人的得分。

说明

对于100%的数据,0<N≤200,0<NA≤200,0<NB≤200。

Code

循环队列模拟一下~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int table[5][5];
table[0][0] = table[1][1] = table[2][2] = table[3][3] = table[4][4] = 0;
table[0][1] = -1; table[1][0] = 1;
table[0][2] = 1; table[2][0] = -1;
table[0][3] = 1; table[3][0] = -1;
table[0][4] = -1; table[4][0] = 1;
table[1][2] = -1; table[2][1] = 1;
table[1][3] = 1; table[3][1] = -1;
table[1][4] = -1; table[4][1] = 1;
table[2][3] = -1; table[3][2] = 1;
table[2][4] = 1; table[4][2] = -1;
table[3][4] = 1; table[4][3] = -1;

int N,A,B;
cin>>N>>A>>B;
int a[205],b[205];
for(int i = 0; i < A; ++i)
cin>>a[i];
for(int i = 0; i < B; ++i)
cin>>b[i];

int AnsA=0, AnsB=0;
for(int i = 0; i < N; ++i){ //循环队列猜拳
if(table[a[i%A]][b[i%B]] == 0) continue;
else if(table[a[i%A]][b[i%B]] == 1) AnsA++;
else AnsB++;
}

cout<<AnsA<<" "<<AnsB;

return 0;
}

P1563 玩具谜题 异或

题目描述

小南有一套可爱的玩具小人, 它们各有不同的职业。

有一天, 这些玩具小人把小南的眼镜藏了起来。 小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:

img

这时singer告诉小南一个谜題: “眼镜藏在我左数第3个玩具小人的右数第1个玩具小人的左数第2个玩具小人那里。 ”

小南发现, 这个谜题中玩具小人的朝向非常关键, 因为朝内和朝外的玩具小人的左右方向是相反的: 面朝圈内的玩具小人, 它的左边是顺时针方向, 右边是逆时针方向; 而面向圈外的玩具小人, 它的左边是逆时针方向, 右边是顺时针方向。

小南一边艰难地辨认着玩具小人, 一边数着:

singer朝内, 左数第3个是archer。

archer朝外,右数第1个是thinker。

thinke朝外, 左数第2个是writer。

所以眼镜藏在writer这里!

虽然成功找回了眼镜, 但小南并没有放心。 如果下次有更多的玩具小人藏他的眼镜, 或是谜題的长度更长, 他可能就无法找到眼镜了 。 所以小南希望你写程序帮他解决类似的谜題。 这样的谜題具体可以描述为:

有 n个玩具小人围成一圈, 已知它们的职业和朝向。现在第1个玩具小人告诉小南一个包含m条指令的谜題, 其中第 z条指令形如“左数/右数第s个玩具小人”。 你需要输出依次数完这些指令后,到达的玩具小人的职业。

说明

【样例1说明】

这组数据就是【题目描述】 中提到的例子。

【子任务】

子任务会给出部分测试数据的特点。 如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表:

img

其中一些简写的列意义如下:

全朝内: 若为“√”, 表示该测试点保证所有的玩具小人都朝向圈内;

全左数:若为“√”,表示该测试点保证所有的指令都向左数,即对任意的1≤z≤m,ai=0;

s=1:若为“√”,表示该测试点保证所有的指令都只数1个,即对任意的1≤z≤m,si=1;

职业长度为1 :若为“√”,表示该测试点保证所有玩具小人的职业一定是一个长度为1的字符串。

Code

指令数组可以就地执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

struct Person{ //小人
bool der; //朝向
string name; //代号
};

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n,m;
Person person[100005];
cin>>n>>m;

for(int i = 0; i < n; ++i){
cin>>person[i].der;
cin>>person[i].name;
}

int ans=0;
for(int i = 0; i < m; ++i){
bool a; int s;
cin>>a>>s; //指令数组可以就地执行
if(person[ans].der ^ a) ans+=s; //利用异或快速判断
else ans-=s;
ans%=n;
if(ans < 0) ans+=n; //模运算小于0时似乎要偏置
}
cout<<person[ans].name<<endl;
return 0;
}
0%