cover

基础算法模拟(超详细)

洛谷模拟题1.P1003铺地毯2. P1067多项式输出3.P1328生活大爆炸版石头剪刀布4.P1563玩具谜题5.P1042 乒乓球超详细解题思路多

unlockjy

1045人浏览 · 2025-04-06 22:21:30

unlockjy · 2025-04-06 22:21:30 发布

前言：

在大家刚刚开始刷题时，肯定会遇到很多的模拟题，模拟是什么呢？就是题目让你干什么，我们就干什么，就写什么样的代码，按题目的要求完成即可！这里就给分别给大家列举几道模拟题，我这个蒟蒻在写模拟就老是想不到很好的办法，尝尝卡壳，有很多时候都要通过题解才能完成，所以在这里分享一下！都是洛谷上的题目，是我在一个题单上面找到的，大家有兴趣可以看

题单网址：https://studyingfather.com/archives/841

1.P1003铺地毯

跳转网址：P1003 [NOIP 2011 提高组] 铺地毯 - 洛谷

题目解读：第一道题目就是铺地毯，通过读题我们可以知道铺n张地毯，给一个坐标(x,y)，地毯会出现覆盖，求出覆盖在最上面的地毯是哪一张

解题思路：

思路1：开始我的想法就是创建一个N*N的二维的数组，然后一个一个去遍历，然后赋值，这个办法是最容易想到的，但是会超空间，不能AC

思路2：首先我们把每个地毯都存进去，然后去遍历一遍数组，每次判断有没有覆盖内个点，如果覆盖了就更新，最后输出即可，成功AC

思路1代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int arr[N][N];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int a, b, g, k;
		cin >> a >> b >> g >> k;
		for (int x = a; x <= a + g; x++)
		{
			for (int y = b; y <= b + k; y++)
			{
				arr[x][y] = i;
			}
		}
	}
	int x, y;
	cin >> x >> y;
	cout << arr[x][y];
}

思路2代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int a[N], b[N], c[N], d[N];
int main()
{
	int n = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	int ret = -1,x = 0, y = 0;
	cin >> x >> y;
	for (int i = 1; i <= n; i++)
	{
		if (x >= a[i] && y >= b[i] && x <= (a[i] + c[i]) && y <= (b[i] + d[i])) ret = i;
	}
	cout << ret;
	return 0;
}

2. P1067多项式输出

跳转网址：P1067 [NOIP 2009 普及组] 多项式输出 - 洛谷

题目解读：这道题就是让我们输出一个表达式

题目有一些要求，

如果多项式 n 次项系数为正，则多项式开头不出 + 号，如果多项式 n 次项系数为负，则多项式以 - 号开头。

对于不是最高次的项，以 + 号或者 - 号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于 0 次的项，其系数的绝对值为 1，则无需输出 1）。如果 x 的指数大于 1，则接下来紧跟的指数部分的形式为“xb”，其中 b 为 x 的指数；如果 x 的指数为 1，则接下来紧跟的指数部分形式为 x；如果 x 的指数为 0，则仅需输出系数即可。

解题思路：

开始我看哪些要求那么多，心想好麻烦，但是最后细想几个if语句就可以解决问题，我们需要分情况进行讨论，将几种特殊的情况列举出来就可以！但这个的前提是系数不为0！！

这里的i是多项式的次数，n是多项式的最高次数，x是输入的数字

伪代码：看懂这个相信大家AC就是小问题！！

i!=n&&x>0 cout<<'+' 当多项式的次数不是最高项(最高项前不需要写+)并且输入的数字是整数，需要输出+号
i!=0&&x==-1 cout<<'-' 当多项式的次数不是0并且输入的值是-1，输出-号
abs(x)||i==0 cout<<x 当x的绝对值是正数或者多项式的次数为0，直接输出x即可
i==1 cout<<'x' 当多项式的次数为1，我们知道随便一个数的1次方都是那个原本的数，输出字符x
i>1 cout<<'x'<<'^'<<i 当多项式的次数大于1，按题目输出即可！
最后提醒：for循环次数从高到低遍历更好写呦

代码：

#include<bits/stdc++.h>
using namespace std;
int a[110];
int main()
{
	int n = 0,x = 0;
	cin >> n;
	for (int i = n; i >= 0; i--)
	{
		cin >> x;
		if (x != 0)
		{
			if (i != n && x > 0) cout << '+';
			if (x == -1 && i != 0) cout << '-';
			if (abs(x) > 1 || i == 0) cout << x;
			if (i == 1) cout << 'x';
			if (i > 1) cout << 'x' << '^' << i;
		}
	}
}

3.P1328生活大爆炸版石头剪刀布

跳转网址：https://www.luogu.com.cn/problem/P1328

题目解读：就是划拳，只不过我们一般是石头剪刀步子，它有增加了蜥蜴人和斯博克两个，题目让我们去计算a和b的得分，他们出拳是有周期性的，但是周期长度可能不相等，赢1分，输0分，平0分。

解题思路：开始我觉得在道题也比较麻烦，但是通过将大问题拆分成3个小问题就很简单了，这里如果我们能想到直接把表模拟出来就很简单了，可惜本蒟蒻当时没想出来

模拟一个游戏结束情况表，1表示a赢，-1表示b赢，0表示平局
进行输入

进行判断，比较结果，进行输出

当j>=na证明这一周期已完，进入下一周期。需要将j置0，k>=nb也是一样的道理，然后到打好的表寻找结果，然后胜的++，然后不要忘记j和k也要++，最后输入即可

代码：

#include<bits/stdc++.h>
using namespace std;
int a[210], b[210];
//0平局 1a胜 -1b胜
int game[5][5] =
{
	{0,-1,1,1,-1},
	{1,0,-1,1,-1},
	{-1,1,0,-1,1},
	{-1,-1,1,0,1},
	{1,1,-1,-1,0},
};
int sum_a, sum_b;
int main()
{
	int n, na, nb;
	cin >> n >> na >> nb;
	for (int i = 0; i < na; i++)
	{
		cin >> a[i];
	}
	for (int j = 0; j < nb; j++)
	{
		cin >> b[j];
	}
	int j = 0, k = 0;
	for (int i = 0; i < n; i++)
	{
		if (j >= na) j = 0;
		if (k >= nb) k = 0;
		int ret = game[a[j]][b[k]];
		if (ret == 1) sum_a++;
		if (ret == -1) sum_b++;
		j++;
		k++;
	}
	cout << sum_a << " " << sum_b;
	return 0;
}

4.P1563玩具谜题

跳转网址：https://www.luogu.com.cn/problem/P1563

题目解读：这道题的叙述叫长，大体意思就是一个圈里有n个人，有人是面朝圈内，有人面朝圈内，然后给我们i条指令，去找内个人

接下来 n 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中 0 表示朝向圈内，1 表示朝向圈外。保证不会出现其他的数。

接下来 m 行，其中第 i 行包含两个整数 ai,si，表示第 i 条指令。若 ai=0，表示向左数 si 个人；若 ai=1，表示向右数 si 个人。保证 ai 不会出现其他的数，1≤si<n。

这两句话很重要，0表示圈内，1表示圈外，ai=0左数，ai=1右数

解题思路：分类讨论即可，我们直接拿图来看，更加清晰明了

通过图我们就可以进行模拟

判断是顺时针还是逆时针

如果是顺时针序号就--
如果是逆时针序号就++

判断序号是否超过最大人数或减出负数

如果序号超过最大人数序号减去最大人数
如果序号被减出负数序号就加上最大人数

最后直接输出即可！

注意数组要开到1e5，不然不能AC，别问我是怎么知道的

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
string b[N];
int main()
{
	int n = 0, m = 0,ret = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < m; i++)
	{
		int x = 0, y = 0;
		cin >> x >> y;
		if ((a[ret] == 0 && x == 0) || (a[ret] == 1 && x == 1))
		{
			ret -= y;
		}
		else
		{
			ret += y;
		}

		if (ret >= n) ret -= n;
		else if (ret <= -1) ret += n;
	}
	cout << b[ret];
	return 0;
}

5.P1042 乒乓球

跳转网址：https://www.luogu.com.cn/problem/P1042

题目解读：大体意思就是给你一串字符串，W表示a赢，L表示b赢，计算11分制和21分制的比赛结果，注意分差大于等于2这一局才结束，最后输出11分制和21分制的比赛结果，题目读起来比较简单，是一道经典的模拟题，主播在最开始刷题就遇到了它，简直就是我的噩梦

解题思路：这道题其实就是模拟，我们可以分2部完成它

输入字符串
进行11分制和21分制的判断

读入字符串有多种办法

c语言的scanf遇到空格和换行就会自动结束，我们可以使用fget函数
c++语言的cin也是遇到空格和换行就结束，我们可以使用getline函数读
getchar()，这个函数也可以使用，getchar会读缓冲区的第一个字符并且返回，如果缓冲区没有字符就会一直等待
while(cin>>s) 这是cin的一个特性，如果没有读取到内容，就会返回0，循环结束

进行11分制21分制的判断

max(a,b) > x，这里的x就是11或者21分制
abs(a-b) >= 2 a-b的绝对值要大于2，题目要求的，abs是一个绝对值的函数
当输出结果以后不要忘记将a和b置0

本人遇到的一个小问题：我在遍历s字符串时，使用的是char，然后我去提交只能过30%，我还非常奇怪，感觉我的代码没有什么问题，后来找到问题是在char，char的有效范围是-127到128或者0到255，而洛谷给的数据比255的大多了，超出255就出现了溢出，所以就不能AC了，可恶啊

新代码：

#include<bits/stdc++.h>
using namespace std;
string s;
char c;
void game(int x)
{
	int a = 0, b = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'W') a++;
		if (s[i] == 'L') b++;
		if (max(a, b) >= x && abs(a - b) >= 2)
		{
			cout << a << ':' << b << endl;
			a = b = 0;
		}
	}
	cout << a << ':' << b << endl << endl;;
}
int main()
{
	while (cin >> c)
	{
		if (c == 'E') break;
		s += c;
	}
	game(11);
	game(21);
	return 0;
}

老代码，现在看看自己以前写的真是一坨...不过我还是贴上来了

#include<stdio.h>
int main()
{
    char arr[100000];
    int i = 0;
    char a;
    while ((a = getchar()) != 'E')
    {
        arr[i++] = a;

    }
    arr[i] = 'E';  //因为循环没有追加E所以后面加上
    //11分
    int n1 = 0, n2 = 0;
    int k = 0;
    for (k = 0; k <= i; k++)
    {
        if (arr[k] == 'W')
        {
            n1++;
        }
        if (arr[k] == 'L')
        {
            n2++;
        }
        if ((n1 >= 11 && (n1 - n2) >= 2) || (n2 >= 11 && (n2 - n1) >= 2))
        {
            printf("%d:%d\n", n1, n2);
            n1 = 0, n2 = 0;
        }
        else if (arr[k] == 'E')
        {
            printf("%d:%d\n", n1, n2);
            n1 = 0, n2 = 0;
            break;
        }
    }
    n1 = 0, n2 = 0;
    printf("\n");
    //21分
    //n1 = 0, n2 = 0;
    for (k = 0; k <= i; k++)
    {
        if (arr[k] == 'W')
        {
            n1++;
        }
        if (arr[k] == 'L')
        {
            n2++;
        }
        if ((n1 >= 21 && (n1 - n2) >= 2) || (n2 >= 21 && (n2 - n1) >= 2))
        {
            printf("%d:%d\n", n1, n2);
            n1 = 0, n2 = 0;
        }
        else if (arr[k] == 'E')
        {
            printf("%d:%d\n", n1, n2);
            n1 = 0, n2 = 0;
            break;
        }
    }
    return 0;
}

结语

当然了这只是基础的算法，可能都不叫什么算法，就是一些模拟编程题，后续我还会更新更多的算法，虽然我是个蒟蒻，我要变强，希望和大家一起变强！！！

信息学奥赛社区

集算法之大成！助力oier实现梦想！

更多推荐

cover

AT_abc398_e [ABC398E] Tree Game 题解

信息学奥赛社区

cover

2025-4-10-C++ 学习分支结构（中）

信息学奥赛社区

cover

2025第十六届蓝桥杯C++ B组题解

信息学奥赛社区

所有评论(0)

查看更多评论

unlockjy

已为社区贡献1条内容