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

--------------cadifobp0802

创新互联成立于2013年，先为武都等服务建站，武都等地企业，进行企业商务咨询服务。为武都企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。T1奇偶数的判定 题目描述

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

输入格式

单个整数：表示 n。

输出格式

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

数据范围

−1,000,000≤n≤1,000,000

样例数据 输入:

0

输出:

even

输入:

-1

输出:

odd

我的想法

简单的奇偶数判断，过

#includeusing namespace std;

int n;

int main(){scanf("%d", &n);
	if (n % 2 == 0)
		printf("even\n");
	else
		printf("odd\n");
	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层金字塔

我的想法

用高斯公式循环求和（或者直接累加），大于所给积木就输出。
代码如下：

#includeusing namespace std;

int n;

int main(){scanf("%d", &n);
	for (int i = 1; i<= n; ++i) {if (i * (i + 1) / 2 >n) {	printf("%d\n", i - 1);
			break;
		}
	}
	return 0;
}

最长平台 题目描述

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

输入格式

第一行：单个整数 n
第二行：n 个整数 a₁,a₂,…,a_n

输出格式

两个整数：表示最长平台的长度与最长平台的数量

数据范围

对于 50% 的数据，n≤1000
对于 100% 的数据，n≤500,000
1≤a_i≤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

说明:
每个数字单独成一个平台

我的想法

从头开始找，每一段平台到头了就比较是否比之前的大平台大。如果大于的话，重新开始统计，如果等于的话，统计+1，否则不统计。
代码如下：

#includeusing namespace std;
#define MAXN 500010

int n, a[MAXN], s, ans = 0, cnt = 0;

int main(){scanf("%d", &n);
	for (int i = 1; i<= n; ++i)
		scanf("%d", &a[i]);
	int t = a[1];
	s = 1;
	a[n + 1] = a[n] - 1;//为了最后一次判断特地增加一个最少的
	for (int i = 2; i<= n + 1; ++i) {if (a[i] != t) {	if (s >ans) {		ans = s;
				cnt = 1;
			}
			else if (s == ans)
				cnt++;
			t = a[i];
			s = 1;
		}
		else
			s++;
	}
	printf("%d %d\n", ans, cnt);
	return 0;
}

积木染色 题目描述

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

输入格式

输入两个正整数n,m

输出格式

输出满足条件的方案数模10⁹+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种选择，之后每一种都是m-1次选择。
但是数据量非常大，n大能到10的15次方。我便采取一种硬核的遍历方式：
如果n<=10⁷,直接循环；
如果n>10⁷,先循环到10⁷，然后拿10⁷，开方，最后解决一些零头。
代码如下：

#includeusing namespace std;
#define ll long long
#define MODD 1000000007

ll n, m;

int main(){scanf("%lld%lld", &n, &m);
	ll k = m;
	m -= 1;
	n -= 1;
	ll mm = m;
	if (n< 1e7) {for (ll i = 2; i<= n; ++i) {	mm *= m;
			mm %= MODD;
		}
		k *= mm;
		k %= MODD;
	}
	else {for (ll i = 2; i<= 1e7; ++i) {	mm *= m;
			mm %= MODD;
		}
		ll z7 = n / 1e7, lt = n - z7 * 1e7, mmm = mm;
		for (ll i = 2; i<= z7; ++i) {	mmm *= mm;
			mmm %= MODD;
		}
		for (int i = 1; i<= lt; ++i) {	mmm *= m;
			mmm %= MODD;
		}
		k *= mmm;
		k %= MODD;
	}
	printf("%lld\n", k);
	return 0;
}

出栈序列 题目描述

给定一个长度为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} 的字典序最小

我的想法

这道题我用数组模拟链表来做。首先找到一个字典序最小的，排在前的优先。找到后再拿这个字母前一个和后面所有进行比较，优先输出靠前的。
代码如下：

#includeusing namespace std;
#define MAXN 100010

struct nod{int next, last;
	char c;
};

int n, id;
char op;
nod ca[MAXN];

void dfs(int w, int el) {cout<< ca[w].c;
	ca[ca[w].last].next = ca[w].next;
	ca[ca[w].next].last = ca[w].last;
	if (el == 0)
		return;
	int wl = ca[w].last;
	if (wl< 1)
		wl = ca[w].next;
	int p = ca[wl].next;
	while (p<= n) {if (ca[p].c< ca[wl].c) {	wl = p;
		}
		p = ca[p].next;
	}
	dfs(wl, el - 1);
}

int main(){cin >>n;
	for (int i = 1; i<= n; ++i) {cin >>ca[i].c;
		ca[i].last = i - 1;
		ca[i].next = i + 1;
		if (i == 1) {	op = ca[i].c;
			id = 1;
		}
		if (op >ca[i].c) {	op = ca[i].c;
			id = i;
		}
	}
	dfs(id, n - 1);
	cout<< endl;
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：上海月赛11月丙组解题报告-创新互联
网站地址：http://scgulin.cn/article/hidoe.html