# 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

3 2

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

3
yes

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);
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;
}


Posted by skyagh on Thu, 24 Nov 2022 07:11:52 +0300