c++ 数据结构 c语言 开发语言 青少年编程 2-1基础算法-枚举/模拟

文章目录

1.枚举2.模拟

1.枚举

[例1] 特别数的和 评测系统

#include

using namespace std;

bool pa(int x) {

while (x) {

if (x % 10 == 2 || x % 10 == 1 || x % 10 == 0 || x % 10 == 9) {

return true;

}

else {

x = x / 10;

}

}

return false;

}

int main()

{

int sum=0;

int m;

cin >> m;

for (int i = 1; i <= m; i++) {

if (pa(i)) {

sum += i;

}

}

cout << sum;

return 0;

}

[例2] 反序数 评测系统

#include

using namespace std;

int main()

{

int n;

cin >> n;

int a, b, c;

cin >> a >> b >> c;

int sum = 0;

for (int i = 1; i <= n; i++) {

if (i % a != 0 && i % b != 0 && i % c != 0) {

sum++;

}

}

cout << sum;

return 0;

}

[例3] 找到最多的数 评测系统

#include

#include

#include

using namespace std;

int main()

{

int n, m;

cin >> n >> m;

int num = n * m;

map mp;

vector a(num);//记录去重后的序列

while (num--) {

int x;

cin >> x;

if (!mp.count(x)) {

a.push_back(x);

}

mp[x]++;

}

for (const auto& x:a) { //也可以不使用vector，每次从map中取出[x.y]

if (mp[x] * 2 > n * m)

cout << x;

}

}

[例4] 评测系统

对于每种可能的颜色，我们尝试计算如果将走廊涂成这种颜色需要多少天。在遍历过程中要跳过已经是这种颜色的房子，每次移动k步。最后记录对于这种颜色所需的涂色天数，并与之前的最小天数进行比较，取较小值。 输入数据的最大值即为初始颜色种类数

#include

#include

using namespace std;

int main()

{

int t;

cin >> t;

while (t--) {

int n, k;

cin >> n >> k;

vector a(n);

int maxnum = 0;//记录初始颜色种类数

for (int i = 0; i < n; ++i) {

cin >> a[i];

maxnum=max(maxnum, a[i]);

}

int ans = n;

for (int c = 1; c <= maxnum; ++c) {

int cnt = 0;

int idx = 0;

while (idx < n) {

if (a[idx] == c) {

idx++;

continue;

}

idx += k;

cnt++;

}

ans = min(cnt, ans);

}

cout << ans << endl;

}

}

2.模拟

[例1] 扫雷 评测系统

#include

using namespace std;

const int N = 150;

int main()

{

int n, m;

cin >> n >> m;

int a[N][N], ans[N][N];

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

cin >> a[i][j];

}

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (a[i][j] == 1) {

ans[i][j] = 9;

continue;

}

int i2 = i, j2 = j;//遍历四周

for (i2 = max(0, i - 1); i2 <= min(n - 1, i + 1); i2++) {

for (j2 = max(0, j - 1); j2 <= min(m - 1, j + 1); j2++) {

if (a[i2][j2] == 1) ans[i][j]++;

}

}

}

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

cout << ans[i][j]<<" ";

}

cout << endl;

}

return 0;

}

[例2] 灌溉 评测系统

使用类似于BFS的过程，用bool类型的irrigated数组记录当前位置是否已被灌溉，最终统计已被灌溉的数量。

#include

#include

using namespace std;

const int N = 200;

int main()

{

int n, m, t;

cin >> n >> m >> t;

bool irrigated[N][N];

queue> q;

for (int i = 0; i < t; i++) {

int r, c;

cin >> r >> c;

r--;

c--;

irrigated[r][c] = true;

q.push({ r,c });

}

int k;

cin >> k;

for (int minute = 0; minute < k; ++minute) {

int size = q.size();

for (int i = 0; i < size; ++i) {

pair fr=q.front();//取到水管的位置坐标

int x = fr.first;

int y = fr.second;

q.pop();

for (int i2 = max(0,x - 1); i2 <= min(n,x + 1); i2++) { //四周灌溉

for (int j2 = max(0,y - 1); j2 <= min(m,y + 1); j2++) {

if (!irrigated[i2][j2]) {

irrigated[i2][j2] = true;

q.push({i2, j2});

}

}

}

}

}

int count = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (irrigated[i][j]) {

count++;

}

}

}

cout << count;

return 0;

}

也可使用map

#include

#include

using namespace std;

const int N = 200;

int main()

{

int n, m, t;

cin >> n >> m >> t;

bool irrigated[N][N];

map q;

for (int i = 0; i < t; i++) {

int r, c;

cin >> r >> c;

r--;

c--;

irrigated[r][c] = true;

q[r]=c;

}

int k;

cin >> k;

for (int minute = 0; minute < k; ++minute) {

int size = q.size();

for (const auto& i:q) {

int x = i.first;

int y = i.second;

for (int i2 = max(0,x - 1); i2 <= min(n,x + 1); i2++) {

for (int j2 = max(0,y - 1); j2 <= min(m,y + 1); j2++) {

if (!irrigated[i2][j2]) {

irrigated[i2][j2] = true;

q[i2]=j2;

}

}

}

}

}

int count = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (irrigated[i][j]) {

count++;

}

}

}

cout << count;

return 0;

}

[例3] 回文日期

评测系统

#include

#include

using namespace std;

bool huiwen(string s) {

if (s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4]) {

return true;

}

else

return false;

}

bool er(string s) {

if (s[0] == s[2] && s[2] == s[5] && s[5] == s[7] && s[1] == s[3] && s[3] == s[4] && s[4] == s[6]) {

return true;

}

else

return false;

}

int pdday(int year, int month) {

if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)

return 31;

else if (month == 2) {

if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) {

return 29;

}

else

return 28;

}

else

return 30;

}

string zifuchuan(int year, int month, int day) {

string s=to_string(year);

if (month / 10 == 0) {

s += '0' + to_string(month);

}

else {

s += to_string(month);

}

if (day / 10 == 0) {

s += '0' + to_string(day);

}

else {

s += to_string(day);

}

return s;

}

int main()

{

int day, month, year;

int chushi;

int day1,day2;

cin >> chushi;

day1 = chushi % 10;

chushi = chushi / 10;

day2= chushi % 10;

chushi = chushi / 10;

day=day2 * 10 + day1;

day1 = chushi % 10;

chushi = chushi / 10;

day2 = chushi % 10;

chushi = chushi / 10;

month = day2 * 10 + day1;

year = chushi;

bool flag = 0;

bool pdhuiwen = 0;

bool pder = 0;

int i, j, k;

for (i = year;; i++) {

for (j = 1; j <= 12; j++) {

if (flag == 0) {

j = month;

}

for (k = 1; k <= pdday(year,month); k++) {

if (flag == 0) {

k = day+1;

flag = 1;

}

string s=zifuchuan(i, j, k);

if (pdhuiwen!=1&&huiwen(s)) {

cout << s << endl;

pdhuiwen = 1;

}

if (pder!=1&&er(s)) {

cout << s;

pder = 1;

}

if (pdhuiwen == 1 && pder == 1) {

return 0;

}

}

}

}

}

[例4] 小蓝和小桥的挑战 评测系统

#include

#include

#include

using namespace std;

int main()

{

int n;

cin >> n;

while (n--) {

int m;

cin >> m;

vector a(m);

for(int i=0;i

cin >> a[i];

}

int cnt = count(a.begin(), a.end(), 0); // #include

int sum = 0;

for (const auto& x : a) {

sum += x;

}

if (sum == 0) {

cout << cnt + 1;

}

else

cout << cnt<

}

}

[例5] DNA序列修正

评测系统

#include

using namespace std;

bool pipei(char a, char b) {

return (a == 'A' && b == 'T') || (a == 'T' && b == 'A') || (a == 'C' && b == 'G') || (a == 'G' && b == 'C');

}

int main()

{

int n;

cin >> n;

string s1, s2;

cin >> s1 >> s2;

int cnt = 0;//计数

for (int i = 0; i < n; ++i) {

if (!pipei(s1[i], s2[i])) {

cnt++;

for (int j = i + 1; j < n; j++) {

if (!pipei(s1[j], s2[j])

&& pipei(s1[i], s2[j])

&& pipei(s1[j], s2[i])

) {

swap(s2[i], s2[j]);

break;

}

}

}

}

cout << cnt;

}

[例6] 无尽的石头 评测系统

#include

using namespace std;

int ssum(int x) {

int sum = 0;

while (x) {

sum += x % 10;

x /= 10;

}

return sum;

}

int main()

{

int t;

cin >> t;

while (t--) {

int x = 0;

cin >> x;

int step = 0;

bool end = 0;

for (int i = 1; i <= x; i += ssum(i)) {

if (i == x) {

cout << step << endl;

end = 1;

}

step++;

}

if (end == 0) {

cout << -1 << endl;

}

}

}

推荐阅读

 您阅读本篇文章共花了：