Shanghai Computer Society November Competition

Judgment of odd and even numbers

topic description

Given an integer n, if n is an even number, output even, if n is an odd number, output odd.

input format

A single integer: represents n.

output format

A single string: representing the parity of n

data range

\(-1,000,000\leq n\leq 1,000,000\)

sample data

enter:

0

output:

even

enter:

-1

output:

odd

problem solving ideas

Just take the model directly. Note that it is best to modulo 2, because the remainder of a negative number is a negative number, the remainder of a positive number is a positive number, and 0 is neither positive nor negative.

building blocks

topic description

Xiao Ai wants to build a pyramid with building blocks. For structural stability, each layer of the pyramid has one more building block than the previous layer. That is, the construction rules are as follows:

Level 1 of the pyramid requires 1 block

The 2nd level of the pyramid requires 2 blocks

Pyramid level 3 requires 3 blocks

...

Pyramid's first i layer needs to be put i blocks

Now that Xiao Ai has got n blocks, how many layers of pyramids can he build up to?

input format

Enter a positive integer n, indicating the number of blocks in Xiaoai's hand

output format

Output a positive integer, indicating the highest number of pyramid layers that Xiaoai can build

data range

For \(50\%\) of data, \(1 \leq n \leq 1,000\)
For \(100\%\) of data, \(1 \leq n \leq 1,000,000,000\)

sample data

enter:

12

output:

4

illustrate:
A 4-story pyramid needs 1+2+3+4=10 blocks, while a 5-story pyramid needs 1+2+3+4+5=15 blocks, so Xiaoai can build up to 4 blocks with 12 blocks. layer pyramid

problem solving

Solve the loop

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int n;
    cin >> n;
    int sum = 0;
    int i = 0;
    while(sum < n)
    {
        i ++;
        sum += i;
    }
    cout << i - 1 << endl;
    return 0;
}

Brick dyeing

topic description

There are n blocks lined up in a row. Xiao Ai needs to dye each block. There are m colors. How many ways are there to make the colors of two adjacent blocks different?

input format

Enter two positive integers n,m

output format

Output the result of the scheme modulus \(10^9+7\) that meets the conditions

data range

For 30% of the data, \(1≤n,m≤10\)
For 60% of the data, \(1≤n,m≤10 ^4\)

For \(100\%\) data, \(1 \leq n \leq 10^{15},1 \leq m \leq 10^9\)

sample data

enter:

3 2

output:

2

illustrate:

Legal coloring schemes are: {1,2,1} {2,1,2}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    if(n == 0)
    {
        cout << "even"<< endl;
        return 0;
    }
    if(n % 2 == 0)
        cout << "even" << endl;
    else cout << "odd" << endl;
    return 0;
}

problem solving ideas

Arrange combination questions. It is mainly a set of quick power templates.

//liziyu

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 1e9 + 7;

int f(int a , int m , int mod)
{
	if(m == 0)
		return 1;
	int t = f(a , (m - 1) / 2 , mod) % mod;
	if(m % 2 == 0)
		return (t * t) % mod;
	else
		return (((t * t) % mod) * a) % mod;   
}

signed main()
{
	int n , m;
	cin >> n >> m;
	cout << (m % MOD * (f(m - 1, n - 1 , MOD) % MOD)) % MOD <<endl;
	return 0;
}

pop sequence

topic description

Given a string of length n consisting only of lowercase letters, put them on the stack in order.

Among all possible popping sequences, what is the smallest popping sequence in lexicographical order?

input format

Enter the first line, a positive integer n
Enter the second line, a string of length n

output format

Output the popping sequence with the smallest lexicographical order among all popping sequences

data range

For \(30\%\) data, \(1 \leq n \leq 10\)
For the data of \(60\%\), \(1 \leq n \leq 10^3\)

For \(100\%\) data, \(1 \leq n \leq 10^5\)

sample data

enter:

3
yes

output:

esy

illustrate:

The characters y, e, and s are pushed into the stack in turn, and all the possibilities of popping out of the stack are:
{yes},{yse},{eys},{esy},{sey}
where {esy} has the smallest lexicographical order

problem solving ideas

In fact, this question is a greedy question.
When the element at the top of the stack is larger than the minimum value in the sequence that can also be pushed into the stack, then the sequence obtained by popping the stack must not be the smallest.
So just use the stack to simulate it again.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1E5 + 10;

stack<char> stk;
char a[MAXN] ;
int n;
string s;

int main()
{
	cin >> n >> s;
	a[n - 1] = s[n - 1];
	for(int i = n - 2 ; i >= 1 ; i --)
		if(s[i] < a[i - 1]) a[i] = s[i];
		else a[i] = a[i - 1];
	int cnt = 1;
	stk.push(s[0]);
	while(!stk.empty() || cnt < n)
	{
		if(stk.empty() || (cnt < n && stk.top() > a[cnt]))
			stk.push(s[cnt]) , cnt ++;
		else
		{
			cout << stk.top();
			stk.pop();
		}
	}
	cout << endl;
	return 0;
}