上海計算機學會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;
}