上海月赛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://cdkjz.cn/article/hidoe.html
