上海计算机学会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;
}