上海月赛11月丙组解题报告-创新互联

上海月赛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;
}
最长平台 题目描述

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

输入格式

第一行:单个整数 n
第二行:n 个整数 a1,a2,…,an

输出格式

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

数据范围

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

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

我的想法

从头开始找,每一段平台到头了就比较是否比之前的大平台大。如果大于的话,重新开始统计,如果等于的话,统计+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

输出格式

输出满足条件的方案数模109+7的结果

数据范围

对于 30% 的数据,1≤n,m≤10
对于 60% 的数据,1≤n,m≤104
对于 100% 的数据,1≤n≤1015,1≤m≤109

样例数据 输入:
3 2
输出:
2

说明:
合法的染色方案有:{1,2,1} {2,1,2}

我的想法

这道题看上去难度不大,第一个积木有m种选择,之后每一种都是m-1次选择。
但是数据量非常大,n大能到10的15次方。我便采取一种硬核的遍历方式:
如果n<=107,直接循环;
如果n>107,先循环到107,然后拿107,开方,最后解决一些零头。
代码如下:

#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≤103
对于100%的数据,1≤n≤105

样例数据 输入:
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://pwwzsj.com/article/hidoe.html