上海计算机学会11月月赛()

上海计算机学会11月月赛

奇偶数的判定

题目描述

给定一个整数 n,若 n 是一个偶数,输出 even,若 n 是一个奇数,输出 odd。

输入格式

单个整数:表示 n。

输出格式

单个字符串:表示 n 的奇偶性

数据范围

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

样例数据

输入:

0

输出:

even

输入:

-1

输出:

odd

解题思路

直接取模即可。注意最好模2,因为负数的余数是负数,正数的余数是正数,0既不是正数也不是负数。

搭积木

题目描述

小爱同学想要用积木搭起一个金字塔。为了结构稳定,金字塔的每一层要比上一层多一块积木。即搭建规则如下:

金字塔的第 1 层需要放 1 块积木

金字塔的第 2 层需要放 2 块积木

金字塔的第 3 层需要放 3 块积木

…

金字塔的第 i 层需要放 i 块积木

现在小爱拿到了 n 块积木,请问他最高可以搭出多少层的金字塔?

输入格式

输入一个正整数 n,表示小爱手中的积木数量

输出格式

输出一个正整数,表示小爱最高能搭的金字塔层数

数据范围

对于 \(50\%\) 的数据,\(1 \leq n \leq 1,000\)
对于 \(100\%\) 的数据,\(1 \leq n \leq 1,000,000,000\)

样例数据

输入:

12

输出:

4

说明:
4层金字塔需要1+2+3+4=10块积木,而5层金字塔需要1+2+3+4+5=15块积木,所以小爱在有12块积木的情况下,最多搭4层金字塔

解题

循环求解即可

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

积木染色

题目描述

有 n 块积木排成一排,小爱需要给每块积木染色,颜色有 m 种,请问有多少种方法,能使相邻两块积木的颜色均不相同?

输入格式

输入两个正整数n,m

输出格式

输出满足条件的方案数模\(10^9+7\)的结果

数据范围

对于 30% 的数据,\(1≤n,m≤10\)
对于 60% 的数据,\(1≤n,m≤10 ^4\)

对于 \(100\%\) 的数据,\(1 \leq n \leq 10^{15},1 \leq m \leq 10^9\)

样例数据

输入:

3 2

输出:

2

说明:

合法的染色方案有:{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;
}

解题思路

排列组合题。主要是套快速幂模板.

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

出栈序列

题目描述

给定一个长度为n的、仅由小写字母组成的字符串,将其按序依次放入栈中。

请问在所有可能的出栈序列中,字典序最小的出栈序列是多少?

输入格式

输入第一行, 一个正整数n
输入第二行,一个长度为n的字符串

输出格式

输出所有出栈序列中,字典序最小的出栈序列

数据范围

对于\(30\%\)的数据,\(1 \leq n \leq 10\)
对于\(60\%\)的数据,\(1 \leq n \leq 10^3\)

对于\(100\%\)的数据,\(1 \leq n \leq 10^5\)

样例数据

输入:

3
yes

输出:

esy

说明:

字符y、e、s依次进栈,所有出栈的可能性有:
{yes}、{yse}、{eys}、{esy}、{sey}
其中 {esy} 的字典序最小

解题思路

其实这道题是一道贪心题。
当栈顶的元素比还可以进栈序列中的最小值大时,那么这是出栈得到的序列一定不是最小的。
所以只要用栈来模拟一遍即可。

#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;
}
————————

上海计算机学会11月月赛

奇偶数的判定

题目描述

给定一个整数 n,若 n 是一个偶数,输出 even,若 n 是一个奇数,输出 odd。

输入格式

单个整数:表示 n。

输出格式

单个字符串:表示 n 的奇偶性

数据范围

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

样例数据

输入:

0

输出:

even

输入:

-1

输出:

odd

解题思路

直接取模即可。注意最好模2,因为负数的余数是负数,正数的余数是正数,0既不是正数也不是负数。

搭积木

题目描述

小爱同学想要用积木搭起一个金字塔。为了结构稳定,金字塔的每一层要比上一层多一块积木。即搭建规则如下:

金字塔的第 1 层需要放 1 块积木

金字塔的第 2 层需要放 2 块积木

金字塔的第 3 层需要放 3 块积木

…

金字塔的第 i 层需要放 i 块积木

现在小爱拿到了 n 块积木,请问他最高可以搭出多少层的金字塔?

输入格式

输入一个正整数 n,表示小爱手中的积木数量

输出格式

输出一个正整数,表示小爱最高能搭的金字塔层数

数据范围

对于 \(50\%\) 的数据,\(1 \leq n \leq 1,000\)
对于 \(100\%\) 的数据,\(1 \leq n \leq 1,000,000,000\)

样例数据

输入:

12

输出:

4

说明:
4层金字塔需要1+2+3+4=10块积木,而5层金字塔需要1+2+3+4+5=15块积木,所以小爱在有12块积木的情况下,最多搭4层金字塔

解题

循环求解即可

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

积木染色

题目描述

有 n 块积木排成一排,小爱需要给每块积木染色,颜色有 m 种,请问有多少种方法,能使相邻两块积木的颜色均不相同?

输入格式

输入两个正整数n,m

输出格式

输出满足条件的方案数模\(10^9+7\)的结果

数据范围

对于 30% 的数据,\(1≤n,m≤10\)
对于 60% 的数据,\(1≤n,m≤10 ^4\)

对于 \(100\%\) 的数据,\(1 \leq n \leq 10^{15},1 \leq m \leq 10^9\)

样例数据

输入:

3 2

输出:

2

说明:

合法的染色方案有:{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;
}

解题思路

排列组合题。主要是套快速幂模板.

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

出栈序列

题目描述

给定一个长度为n的、仅由小写字母组成的字符串,将其按序依次放入栈中。

请问在所有可能的出栈序列中,字典序最小的出栈序列是多少?

输入格式

输入第一行, 一个正整数n
输入第二行,一个长度为n的字符串

输出格式

输出所有出栈序列中,字典序最小的出栈序列

数据范围

对于\(30\%\)的数据,\(1 \leq n \leq 10\)
对于\(60\%\)的数据,\(1 \leq n \leq 10^3\)

对于\(100\%\)的数据,\(1 \leq n \leq 10^5\)

样例数据

输入:

3
yes

输出:

esy

说明:

字符y、e、s依次进栈,所有出栈的可能性有:
{yes}、{yse}、{eys}、{esy}、{sey}
其中 {esy} 的字典序最小

解题思路

其实这道题是一道贪心题。
当栈顶的元素比还可以进栈序列中的最小值大时,那么这是出栈得到的序列一定不是最小的。
所以只要用栈来模拟一遍即可。

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