1. Repeat Count

subject

In a limited sequence of positive integers, some numbers repeat several times. Please count the number of occurrences of each number, and then output the number and its number in the order where the number first appears in the sequence.
Output format:
A number of rows, two separated by a space in each row. The first is the number that appears in the column, and the second is the number of times that the number appears in the sequence.

Input sample:
Here is a set of inputs. For example:

Output sample:
The corresponding output is given here. For example:

Solving problems

Using the O (n^2) method, we passed on both platforms with full scores, so we only wrote the solution ideas of this method.

• Create two arrays of length n, one recording the read-in data and the other initializing all elements to 0. Does the record read-in data appear for the first time or, if not, change the corresponding 0 to 1.
• Initialize a variable count to 1, the number repeats, count++, print out count at the end of the loop, and reinitialize to 1 to prepare for the statistical frequency of the next data.

Code

#include<stdio.h>
#include<stdlib.h>
int main() {
	int N;
	int a[50001], b[50001] = { 0 };
	int count=1, i, j;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &a[i]);
	}
	for (i = 0; i < N; i++) {
		if (b[i]==0) {
			count = 1;//Initialization
			for (j = i + 1; j < N; j++) {
				if (a[i] == a[j]) {
					b[j] = 1;//Mark data that appears
					count++;//Statistical Frequency
				}
			}
			printf("%d %d\n", a[i], count);
		}
	}
}

2. Counting game

subject

n people form a circle, numbering one after another from the beginning, and playing counting games. It is now specified that when the number is reported from the first person to the mth person, the person goes out of the circle, and then starts again from the next person, it is still reported to the mth person to go out of the circle, so repeat until everyone goes out of the circle. The total number will be reported circularly when it is less than m. Please output the order in which everyone goes out of circle.
Input format:
One line, two integers n and m. N is the number of people in the game, m is the number of circles reported, 1 < n < 50000, 1 < m < 100.

Output format:
One line, n integers separated by spaces, indicating the order in which everyone goes out of the circle
Input sample:
Here is a set of inputs. For example:

Output sample:

Solving problems

• This is a simple Joseph Ring problem.
• Note that when the number reaches the nth person, reset i to 0.
• The teacher said it would be more efficient to use a chain structure, but I haven't tried yet.

 if (i == n) {
            i = 0;  //Number from scratch
        }

Code

#include <stdio.h>

void left(int* a,int n,int m) {
    int out = 0,count = 0,i = 0;    
    int *p = a;
    int num = 0;
    for(num = 0;num < n;num++) {
        *(a+num) = num+1;//Initialization
    } 
    while (out < n-1) {
        if (*(p+i) != 0) {
            count ++;  
        }
        if (count == m) {//The m th person was counted
            count = 0;//Initialize count, restart count
            printf("%d ",*(p+i));
            *(p+i) = 0;//Assign 0 to the number of people, not counting in the cycle
            out++;  
        }
        i++;
        if (i == n) {
            i = 0;  //Number from scratch
        }
    }
    for (num = 0; num < n; num++) {
        if (*(a+num) != 0) {
            printf("%d\n",*(a+num));//Last remaining person
        }
    }
}

int main()
{
    long n;
    int m;
    long a[50000] = {0};
    scanf("%d",&n);
    scanf("%d",&m);   
    left(a,n,m);
    return 0;
}

Three, arithmetic expression

subject

Task: Calculate the value of an arithmetic expression.

Arithmetic expressions are given as infixes and end with an = sign, including the +, -, /four operations and the (,) delimiter. The range of an operand is a non-negative integer, has no sign for positive and negative, and is less than or equal to 109.

During the calculation, if a divisor of 0 occurs, the result of the expression is "NaN"; If the intermediate result exceeds the range of 32-bit signed integers, it is still calculated as integers without special treatment. Enter to ensure the expression is correct.

Input format:
A line, including an arithmetic expression. The length of the arithmetic expression is less than or equal to 1000.

Output format:
Line, the value of the arithmetic expression.

Input sample:
Here is a set of inputs. For example:

Output sample:
The corresponding output is given here. For example:

Solving problems

• Priority comparison: Build a function where the corresponding x tag is 0 for'('or'), 1 for'+','-', and 2 for'*','/'.

int first(char ch) {
	int x = 0;
	switch (ch) {
	case '(':
		x = 0; break;
	case ')':
		x = 0; break;
	case '+':
		x = 1; break;
	case '-':
		x = 1; break;
	case '*':
		x = 2; break;
	case '/':
		x = 2; break;
	}
	return x;
}

• Build two stacks, one storage operator and one storage number. If the top element of the stack of an operator stack has a lower priority than the read operator, the read operator is stacked, otherwise, the top element of the stack is popped up, the operation function is called, the result of the operation is pushed onto the number stack.
• When data is stored in the digital stack, the operation of converting char-type data to int-type data is required. An array is opened up here, where numbers are stored separately if they are more than two digits. Finally, the data of type string is converted to type int using the atoll function.
• It is also important to note that the title requires that if the intermediate result exceeds the range of 32-bit signed integers, it is still calculated as integers without special treatment. But I didn't notice when I was writing in class, using the long long stack, which resulted in a 10-point test point that couldn't go through.
• Another problem with this code is that if I only enter a number it will output NaN. I haven't found out what's going on for a long time. Without affecting the score, I don't get tangled anymore. I hope the free guys can help me out.

Code

#include<stdio.h>
#include<iostream>
#include<stack>
#include<string>
#include<stdlib.h>
#define maxsize 1001
using namespace std;
stack<char> s1;
stack<int> s2;
int first(char ch);
int yunsuan(int a, int b, char ch);
void result(char str[]);
int first(char ch) {
	int x = 0;
	switch (ch) {
	case '(':
		x = 0; break;
	case ')':
		x = 0; break;
	case '+':
		x = 1; break;
	case '-':
		x = 1; break;
	case '*':
		x = 2; break;
	case '/':
		x = 2; break;
	}
	return x;
}
int yunsuan(int a, int b, char ch)
{
	int c = 0;
	switch (ch)
	{
	case '+':
		c = a + b;
		break;
	case '-':
		c = a - b;
		break;
	case '*':
		c = a * b;
		break;
	case '/':
		if (b == 0)
		{
			cout << "NaN" << endl;
			exit(0);
		}
		else
			c = a / b;
		break;
	}
	return c;
}
void result(char str[])
{
	char num[maxsize];
	char top1;
	int f, c, get1, get2;
	int j, i;
	for (i = 0; str[i] != '='; i++)
	{
		switch (str[i])
		{
		case '(':
			s1.push(str[i]);
			break;
		case '+':
		case '-':
		case '*':
		case '/':
			if ((s1.empty()))
				s1.push(str[i]);
			else if (first(str[i]) > first(s1.top()))
				s1.push(str[i]);
			else {
				while (!s1.empty() && first(str[i]) <= first(s1.top()) && s1.top() != '(')
				{
					get1 = s2.top();
					s2.pop();
					get2 = s2.top();
					s2.pop();
					top1 = s1.top();
					c = yunsuan(get2, get1, top1);
					s1.pop();
					s2.push(c);
				}
				s1.push(str[i]);
			}
			break;
		case ')':
			while (s1.top() != '(')
			{
				get1 = s2.top();
				s2.pop();
				get2 = s2.top();
				s2.pop();
				top1 = s1.top();
				s1.pop();
				c = yunsuan(get2, get1, top1);
				s2.push(c);
			}
			s1.pop();
			break;
		default:
			j = 0;
			do
			{
				num[j++] = str[i];
				i++;
			} while (str[i] >= '0' && str[i] <= '9');
			num[j] = '\0';
			f = atoll(num);
			i--;
			s2.push(f);
			break;
		}
	}
	while (!s1.empty())
	{
		get1 = s2.top();
		s2.pop();
		get2 = s2.top();
		s2.pop();
		top1 = s1.top();
		s1.pop();
		c = yunsuan(get2, get1, top1);
		s2.push(c);
	}
	printf("%d", s2.top());
}
int main() {
	char str[maxsize];
	scanf("%s", str);
	result(str);
	return 0;
}

Four, Favorite Sequences

subject

Xiao Tang spent this time in the research sequence. Take a sequence of N integers, and he assigns a favorite value to each integer in the sequence. Favorite values are also integers, with positive and negative values, and the larger the value, the more you like it. He wanted to know how to get the maximum number of m from the sequence in a row, and he got the most favorite values. 1 < N < 500000, 1 < m < N.
Input format:
The first line is two integers, N and m. Represents the number of numbers in the sequence and the maximum number that can be taken.

The second line is N integers separated by spaces, and the ith integer, Li, represents his favorite value for the ith number. Li < 1000

Output format:
A row with three numbers indicates the maximum favorite value and the first interval to get the maximum favorite value.

Input sample:
Here is a set of inputs. For example:

Output sample:
The corresponding output is given here. For example:

Solving problems

• Creates an array that records the sum of the first n terms while reading in the data for subsequent calculations.

for (int i = 1; i <= N; i++) {
		cin >> array[i];
		array[i] += array[i - 1];//The sum of the first n items recorded
	}

• Using the deque ue double-ended queue in STL, each element read is compared with the queue tail element. If the queue is not empty and the current element is smaller than the queue tail element, the queue tail element pops up and repeats the above operation until the queue empty or the queue tail element is smaller than the current element. If the number of the queue head element is not in the interval, the queue head element pops up and repeats the above operation.
• Initializes a variable to store the sum of the elements in the current interval, then compares them with the sum of the largest elements, and updates the sum of the largest elements if the sum of the elements in the current interval is greater than the sum of the largest elements.

Code

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<deque>
using namespace std;
deque<int> x;
int main() {
	int N, m, front, rear;
	cin >> N;
	cin >> m;
	int array[500001];
	array[0] = 0;
	for (int i = 1; i <= N; i++) {
		cin >> array[i];
		array[i] += array[i - 1];//The sum of the first n items recorded
	}
	int sum = 0;
	while (!x.empty())
		x.pop_back();
		x.push_front(0);
	for (int i = 1; i <= N; i++) {
		while (!x.empty() && array[x.front()] > array[i]) {//Determines if the queue is empty and the number of the node that pops up is greater than the current element
			x.pop_front();
		}
		x.push_front(i);//Number of current element enqueued
		while (!x.empty() && i - x.back() > m) {
			x.pop_back();
		}
		int tmp=array[i] - array[x.back()];
		if (sum < tmp) {//Determine whether to update maximum
			sum = tmp;
			front = x.back() + 1;
			rear = i;
		}
	}
	cout<<sum<<" "<<front<<" "<<rear;
	return 0;
}