上海市计算机学会竞赛平台2020年6月月赛丙组
切蛋糕
内存限制: 256 Mb时间限制: 1000 ms
题目描述
一个圆型的蛋糕，切 𝑛n 刀后，最多能将蛋糕分成多少块？例如 𝑛=3n=3 时，最多可以分成 77 块，如下图：
输入格式
- 单个整数：表示切割的次数 𝑛n。
输出格式
- 单个整数：表示最多能将蛋糕切成多少份。
数据范围
- 1≤𝑛≤50001≤n≤5000。
样例数据
输入:
1
输出:
2
输入:
3
输出:
7
#include<iostream>
int main()
{
int n;
std::cin >> n;
std::cout << 1 + (n + 1) * n / 2 << “\n”;
}单词替换
内存限制: 256 Mb时间限制: 1000 ms
题目背景
最近，谷歌公司做出了一项决定，由于 black list（黑名单）这个词语涉及对有色人种的歧视，所以需要将它们修改成 block list（屏蔽名单）。
题目描述
给定一个仅仅由小写字母组成的字符串 𝑠s，请将其中所有的 black 全部替换成 block 。
输入格式
单个字符串：表示需要替换的字符串 𝑠s。
输出格式
单个字符串：表示将 black 替换成 block 后的字符串。
数据范围
设字符串的长度为 ∣𝑠∣∣s∣，则
- 对于 50%50% 的数据，1≤∣𝑠∣≤2001≤∣s∣≤200；
- 对于 100%100% 的数据，1≤∣𝑠∣≤2000001≤∣s∣≤200000。
样例数据
输入:
ablacklistblackmatter
输出:
ablocklistblockmatter
#include <bits/stdc++.h>
using namespace std;
int main(){
string a;
cin >> a;
for(int i=0;i<a.size()-4;i++){
if(a[i]=='b' and a[i+1]=='l' and a[i+2]=='a' and a[i+3]=='c' and a[i+4]=='k'){
a[i+2]='o';
}
}
cout << a;
}打印K型
内存限制: 256 Mb时间限制: 1000 ms
题目描述
小爱想用 * 打出一个大写的 K。例如 𝑛=3n=3 时，输出
** *** ** ** ** * *** ** * ** ** ** ***给定一个整数 𝑛n 表示字形的大小。请输出一个由星号组成的，对应大小的 K 字形图案。该字形由 2𝑛+12n+1 行组成，第一笔竖线固定占两列，第二笔折线会根据参数 𝑛n 适当调整粗细，具体请参考样例。
输入格式
单个整数表示 𝑛n。
输出格式
共 2𝑛+12n+1 行，表示一个 K 字形图案。
数据范围
1≤𝑛≤501≤n≤50
样例数据
输入:
5
输出:
** ***** ** **** ** *** ** ** ** * *** ** * ** ** ** *** ** **** ** *****输入:
7
输出:
** ******* ** ****** ** ***** ** **** ** *** ** ** ** * *** ** * ** ** ** *** ** **** ** ***** ** ****** ** ******* #include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
for(int i=n;i>=1;i--){
cout << "**";
for(int j=0;j<i;j++){
cout << " ";
}
for(int j=0;j<i;j++){
cout << "*";
}
cout << endl;
}
cout << "***";
cout << endl;
for(int i=1;i<=n;i++){
cout << "**";
for(int j=0;j<i;j++){
cout << " ";
}
for(int j=0;j<i;j++){
cout << "*";
}
cout << endl;
}
}牛奶供应
内存限制: 256 Mb时间限制: 1000 ms
题目描述
有一家牧场每天都会产出牛奶，在第 𝑖i 天，牛奶的产量为 𝑝𝑖pi。生产的牛奶可以卖到市场上，在第 𝑖i 天，市场需求为 𝑐𝑖ci。如果市场需求不大，卖不掉牛奶，则多余的牛奶就会放进冷库保存。牛奶有一个保鲜期，如果超过了 𝑚m 天 （𝑚m 为一个给定的整数），就必须倒掉了。卖牛奶时，应先卖冷藏时间长的。
给定天数 𝑛n 以及每天的产量和收购量，请求出牧场一共可以卖出多少牛奶。
输入格式
第一行：两个整数 𝑛n 和 𝑚m；
第二行到第 𝑛+1n+1 行：第 𝑖+1i+1 行每行两个整数表示 𝑝𝑖pi 和 𝑐𝑖ci。
输出格式
单个整数表示答案。
数据范围
- 对于 30%30% 的数据，1≤𝑛,𝑚≤10001≤n,m≤1000；
- 对于 60%60% 的数据，1≤𝑛,𝑚≤100001≤n,m≤10000；
- 对于 100%100% 的数据，1≤𝑛,𝑚≤1000001≤n,m≤100000；
- 0≤𝑝𝑖,𝑐𝑖≤100000≤pi,ci≤10000。
样例数据
输入:
5 2
50 0
100 0
250 0
300 0
1000 5000
输出:
1550
说明:
最后一天的收购量很大，但第一天和第二天的牛奶由于过期不能出售了
输入:
5 5
0 2
2 3
5 0
3 0
2 0
输出:
2
#include <bits/stdc++.h>
using namespace std;
int p[100000],c[100000];
int a=0,b=0;
int main (){
int n,m;
cin >>n >>m;
for(int i=1;i<=n;i++){
cin >>p[i] >>c[i];
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
a++;
if(a>m+1){
break;
}
if(c[j]!=0){
if(c[j]>=p[i]){
b=b+p[i];
c[j]=c[j]-p[i];
break;
}else{
b=b+c[j];
p[i]=p[i]-c[j];
c[j]=0;
}
}
}
a=0;
}
cout <<b;
}影厅选座
内存限制: 256 Mb时间限制: 1000 ms
题目描述
小爱和朋友们去看电影，一共需要购买 𝑘k 张电影票。电影院共有 𝑛n 排 𝑚m 列，合计 𝑛×𝑚n×m 个座位。有些位置已经占了，小爱希望和朋友能够做得近一点。请你找在电影院里找一个矩形区域，该区域能够包含 𝑘k 个空座，且面积达到最小。
输入格式
第一行：三个整数 𝑛n，𝑚m 及 𝑘k；
接下来 𝑛n 行，每行 𝑚m 个字符，X 表示座位已被预定，. 表示可选。
输出格式
若电影院空座不足 𝑘k 个，输出 No Solution，否则输出一个整数，表示包含 𝑘k 个空座的最小矩形面积。
数据范围
- 对于30%30%的数据，1≤𝑛,𝑚≤501≤n,m≤50；
- 对于60%60%的数据，1≤𝑛,𝑚≤2001≤n,m≤200；
- 对于100%100%的数据，1≤𝑛,𝑚≤8001≤n,m≤800；
- 1≤𝑘≤𝑛×𝑚1≤k≤n×m。
样例数据
输入:
3 3 4
XXX
XX.
XX.
输出:
No Solution
说明:
影厅不足4个空位
输入:
4 5 5
..XXX
X.XXX
XX.X.
XX...
输出:
6
说明:
右下角2*3的矩型中包含5个空位
#include <bits/stdc++.h>
using namespace std;
int n, m, k, a[810][810], b[810], l, r, ans = 1e8;
char c[810][810];
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
cin >> c[i][j];
if(c[i][j] == '.') a[i][j] = 1;
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
if(a[n][m] < k) {
cout << "No Solution";
return 0;
}
for(int i1 = 1; i1 <= n; i1++)
for(int i2 = 0; i2 < i1; i2++) {
l = 1;
for(int j = 1; j <= m; j++) {
b[j] = a[i1][j] - a[i2][j];
while(b[j] - b[l - 1] >= k) {
ans = min(ans, (i1 - i2) * (j - l + 1));
l++;
}
}
}
cout << ans;
}