上海11月月赛丙组解题报告

1.奇偶数的判定

题目描述
给定一个整数 n，若 n 是一个偶数，输出 even，若 n 是一个奇数，输出 odd。

输入格式
单个整数：表示 n。

输出格式
单个字符串：表示 n 的奇偶性

数据范围
−1,000,000≤n≤1,000,000
样例数据
输入:
0
输出:
even
输入:
-1
输出:
odd

直接%2判断就行了

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

int n;

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

搭积木

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

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

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

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

…

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

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

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

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

数据范围
对于 50% 的数据，1≤n≤1,000
对于 100% 的数据，1≤n≤1,000,000,000
样例数据
输入:
12
输出:
4
说明:
4层金字塔需要1+2+3+4=10块积木，而5层金字塔需要1+2+3+4+5=15块积木，所以小爱在有12块积木的情况下，最多搭4层金字塔

两分答案

对于n层肯定要放n(n+1)/2个积木，然后两分答案即可。

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

long long n;

bool check(long long m){
	if(m*(1+m)<=2*n)
	  return true;
	else
	  return false;
}
int main(){
	cin >> n;
	long long l=0,r=n+1,mid;
	while(l+1<r){
		mid=(l+r)/2;
		if(check(mid)==true)
		  l=mid;
		else
		  r=mid;
	}
	cout << l << endl;
	return 0;
}

3.最长平台

题目描述
给定一个整数数列 a1,a2,……，an ，请找出最长平台，并输出最长平台的数量（数字相等但位置不同的平台算作不同的平台）。
所谓平台，就是指数列中一段连续的、完全相等的数字，单个数字可以成为一个平台。

输入格式
第一行：单个整数 n
第二行：n 个整数 a1,a2,……,an

输出格式
两个整数：表示最长平台的长度与最长平台的数量

数据范围
对于 50% 的数据，n≤1000
对于 100% 的数据，0≤n≤500,000，1≤ai≤1,000,000
样例数据
输入:
7
2 2 2 1 3 3 3
输出:
3 2
说明:
最长平台为2 2 2或3 3 3
输入:
5
3 1 4 1 5
输出:
1 5
说明:
每个数字单独成一个平台

模拟

用len表示当前的最长长度，l表示当前长度，sum表示当前最长块的个数，如果前后相等则l++。
若当前的一块结束了，则判断l和len哪个大，若len等于l，则sum++，若len<l则将len更新为l，sum更新为1.

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

int n,a[500010];

int main(){
    cin >> n;
    for(int i=1;i<=n;++i)
    	cin >> a[i];
    int len=1,l=1,sum=1;
    for(int i=1;i<=n;++i){
    	if(a[i+1]==a[i]){
    		l++;
    	}
    	else{
    		if(l==len)
    			sum++;
    		if(l>len){
    			len=l;
    			sum=1;
    		}
    		l=1;
    	}
    }
    if(len==1)
      sum-=1;
    cout << len << " " << sum << endl;
	return 0;
}

4.积木染色

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

输入格式
输入两个正整数n,m

输出格式
输出满足条件的方案数模10^9+7的结果

数据范围
对于 30% 的数据，1≤n,m≤10
对于 60% 的数据，1≤n,m≤10⁴
对于 100% 的数据，1≤n≤10¹⁵ ,1≤m≤10⁹

样例数据
输入:
3 2
输出:
2
说明:
合法的染色方案有：{1,2,1} {2,1,2}

快速幂

对于第一块积木有m种颜色可以涂，对于剩下的n-1块积木都有m-1种方法可以涂，所以结果为m*(m-1)^(n-1)。可用快速幂求解。

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

long long n,m;
long long ans=1;
const long long g=1000000007;

long long f(long long m,long long n,long long g){
	if(n==0)
	  return 1;
	if(n%2==1)
		return m*f(m,n-1,g)%g;
	else{
		long long tmp=f(m,n/2,g);
		return tmp*tmp%g;
	}
}

int main(){
    cin >> n >> m;
    long long ans=f(m-1,n-1,g);
    ans%=g;
    ans*=m;
    ans%=g;
    cout << ans << endl;
	return 0;
}

5. 出栈序列

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

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

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

输出格式
输出所有出栈序列中，字典序最小的出栈序列

数据范围
对于30%的数据，1≤n≤10
对于60%的数据，1≤n≤10³
对于100%的数据，1≤n≤10⁵

样例数据
输入:
3
yes
输出:
esy
说明:
字符y、e、s依次进栈，所有出栈的可能性有：
{yes}、{yse}、{eys}、{esy}、{sey}
其中 {esy} 的字典序最小

我的想法：

对于一个字符来说，位置在其后面的字符，一定可以通过出栈入栈操作得到，而在其前面的字符，只有前面第一个可以通过合法的出栈序列得到。因为要求字典序最小，所以首先要输出字符串中最小的字母，然后用其后面的字母与其前一个字母比较，输出最小的字母，直到输出n个字符。

我的代码：

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

int len;
string s;

int main(){
	cin >> len;
    cin >> s;
    char a=s[0];
    int pos=0,l=len;
    for(int i=1;i<len;++i){
    	if(s[i]<a){
    		pos=i;
    		a=s[i];
    	}
    }
    cout << a;
    s.erase(pos,1);
    l--;
    for(int i=1;i<len;++i){
    	if(pos>0){
    	  a=s[pos-1];
          pos-=1;
        }
        else{
        	a=s[pos];
        }
    	for(int j=pos+1;j<l;++j){
    		if(s[j]<a){
    			pos=j;
    			a=s[j];
    		}
    	}
    	cout << a;
    	s.erase(pos,1);
    	l--;
    }
    cout << endl;
	return 0;
}

最后

以上就是甜甜手套为你收集整理的上海11月月赛丙组解题报告上海11月月赛丙组解题报告的全部内容，希望文章能够帮你解决上海11月月赛丙组解题报告上海11月月赛丙组解题报告所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。