Algorithm-simulation

Preface:

The so-called "simulation algorithm" used in the so-called simulation problems does not have a completely accurate definition. The analog algorithm, as the old saying goes, "Paint the ladle according to the gourd"; The official interpretation is that key elements are filtered and extracted according to the title description, and actual problems are solved by writing code on demand.

It is not difficult to simulate this algorithm, mainly because of the logical troubles, but we can do it directly without clearing up the logical thinking of simulation when we brush a question normally. It is very easy to make a mistake if there is not too much water in this problem.

Core Action: You should record the relevant conditions one by one while reading, check them repeatedly after reading, first simulate the process on the draft paper and then write the code manually!! Don't be greedy!!

P1042 [NOIP2003 Popularity Group] Table Tennis-Details

Input and Output Samples

Input

WWWWWWWWWWWWWWWWWWWW
WWLWE

Output

11:0
11:0
1:1

21:0
2:1

Instructions/Tips

Each line has up to 25 letters and up to 2500 lines.

(Note: One test point actually has 2501 rows of data.)

 

Points of detail:

  1. Most people who have played table tennis know that in regular table tennis competitions, not only do they score more than 11 (or 21), but they also score more than 2. If the score reaches 11-10, the game will continue. Until one person is two points more than the other. (e.g. 13-11)
  2. There is no last round to output, that is, 0:0 case to output;
  3. Character array size (worst case 25*2501), at least char s[62525];

AC code: (fast, easy to write)

#include<bits/stdc++.h>
using namespace std;
int a,b;
char ch;
char s[100100];
int count=0;
int main()
{
	for(int i=0;;i++)
	{
		cin>>s[i];
		if(s[i]=='E') break;    //Enter with'E'
	}
	for(int i=0;s[i]!='\0';i++)
	{
		if(s[i]=='W') a++;
		if(s[i]=='L') b++;
		if((a>=11||b>=11)&&abs(a-b)>=2||s[i]=='E')   //Full simulation of rules
		{
			cout<<a<<":"<<b<<endl;
			a=b=0;
		}
	}
	cout<<endl;
	for(int i=0;s[i]!='\0';i++)
	{
		if(s[i]=='W') a++;
		if(s[i]=='L') b++;
		if((a>=21||b>=21)&&abs(a-b)>=2||s[i]=='E')    //Step by step, not easy to make mistakes
		{
			cout<<a<<":"<<b<<endl;
			a=b=0;
		}
	}
	return 0;
}

Summary: It is really fast to write down the details of the topic on the draft paper.

(Suddenly a slogan comes to mind: running fast does not necessarily win, not falling behind is success.) (

 

P2670 [NOIP2015 Popularity Group] Minesweeper Game-Rules

 

 

The details are as follows: starting from line 1, line 0 leaves a position for the corners to "add clockwise", otherwise it crosses the boundary;

#include<bits/stdc++.h>
using namespace std;
char a[110][110];
int n,m;
char ch;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>ch;
			if(ch=='*') a[i][j]=1;
		}
		
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==1) cout<<"*";
			else cout<<a[i-1][j]+a[i-1][j+1]+
					   a[i][j+1]+a[i+1][j+1]+
					   a[i+1][j]+a[i+1][j-1]+
					   a[i][j-1]+a[i-1][j-1];    //Add a circle clockwise next to this number of Mines
			
		}
		cout<<endl;
	}
		
	return 0;
}

 

 

P1563 [NOIP2016 Improvement Group] Toy Puzzle-Record

Title Description

Xiao Nan has a set of cute toys and they all have different professions.

One day, these little toys hid Xiao Nan's glasses. Xiao Nan found that the toy children were surrounded by a circle, some of them were facing inside the circle and some of them were facing outside the circle. As follows:

Input and Output Samples

Input

7 3
0 singer
0 reader
0 mengbier 
1 thinker
1 archer
0 writer
1 mogician 
0 3
1 1
0 2

Output

writer

Input

10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4

Output

y

Instructions/Tips

[Sample 1 explanation]

This set of data is an example mentioned in the Title Description.

[Subtasks]

The subtasks give some characteristics of the test data. If you have difficulty solving a problem, you can try to solve only a part of the test data.

The data size and characteristics of each test point are as follows:

Some of the abbreviated columns have the following meaning:

* All inward: if'', this means that the test point guarantees that all toy toys are facing inward;

Full Left Number: If'', this means that the test point guarantees that all instructions are left, i.e. for any

1 ≤ z ≤ m, a_i=0;

s= 1s=1:If'', this test point guarantees that only one instruction is available for any

1 ≤ z ≤ m , s_i=1;

Professional Length 1: If'', this means that the test point guarantees that all toy puppies must have one profession

A string of length 1.

 

 

Ideas:

The title can be said to be quite long, as it is a difficult problem to control; But if you read the title and record it, and find it is a water topic, you will be drawing a ladle exactly like a gourd.

Outward (1), Left (0): Counterclockwise, +

Outward (1), Right (1): Clockwise, -

Inward (0), Left (0): Clockwise, -

Inward (0), Right (1): Counterclockwise, +

Pure simulation:

#include<bits/stdc++.h>
using namespace std;
int n,m,k=1;
char s[100010][11];
int a[100010];
int x,y;

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i]>>s[i];
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		if(a[k]==0)
		{
			if(x==0) k-=y;
			else k+=y;
			
		}
		else
		{
			if(x==0) k+=y;
			else k-=y;
		}
		if(k>n) k-=n;
		if(k<=0) k+=n;
	}
	cout<<s[k];
	
	return 0;
}

 

 

Keywords: C++ Algorithm p2p

Added by The Silent on Thu, 03 Mar 2022 19:06:03 +0200