上海市计算机学会2020年6月月赛（丙组）
第一道题：切蛋糕 AC
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int f[N];
int main() {
int n;
scanf("%d", &n);
f[1] = 2; f[2] = 3;
for (int i = 2; i <= n; i++)
f[i] = f[i-1] + i;
printf("%d", f[n]);
return 0;
}第二道题：单词替换 AC
#include <iostream>
#include <algorithm>
using namespace std;
string s;
int main() {
getline(cin, s);
for (int i = 0; i < s.size(); i++) {
if (s[i]=='a' && s[i-1]=='l' && s[i-2]=='b'
&& s[i+1]=='c' && s[i+2]=='k') s[i] = 'o';
printf("%c", s[i]);
}
return 0;
}第三道题：打印K型 AC
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int main() {
scanf("%d", &n);
for (int i = -n; i <= n; i++) {
cout << "**";
int x = abs(i);
if (x == 0) cout << "*";
for (int j = 1; j <= x; j++)
cout << " ";
for (int j = 1; j <= x; j++)
cout << "*";
puts("");
}
return 0;
}第四道题：牛奶供应（一） AC
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int p[N], c[N], n, m, sum = 0, l = 1, r = 1;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &p[i], &c[i]);
while (r <= n) {
if (r-l > m) l++;
while (l<=r && c[r]!=0) {
if (p[l] <= c[r]) {
sum += p[l];
c[r] -= p[l];
l++;
} else {
sum += c[r];
p[l] -= c[r];
c[r] = 0;
}
}
r++;
}
printf("%d", sum);
return 0;
}第五道题：影厅选座 AC
这道题有点难，先来说一下大概思路：题目传送门
我们可以按照先列后行的顺序来枚举。列有15种情况：
从第1列到第1列（只有一列），从第1列到第2列，从第1列到第3列，从第1列到第4列，从第1列到第5列；
从第2列到第2列，从第2列到第3列，从第2列到第4列，从第2列到第5列；
从第3列到第3列，从第3列到第4列，从第3列到第5列；
从第4列到第4列，从第4列到第5列；
从第5列到第5列。
对于这15种枚举列的情况，再分别枚举行。
以样例2中的数据为例，枚举过程如下：
（一）从第1列到第1列，L = 1, R = 1
（1）从第1行到第1行，up = 1, down = 1，只有一个空座，不够k 个。如图1-a所示。
（2）从第1行到第2行，up = 1, down = 2，只有一个空座，不够k 个。如图1-b所示。
（3）从第1行到第3行，up = 1, down = 3，只有一个空座，不够k 个。如图1-c所示。
（4）从第1行到第4行，up = 1, down = 4，只有一个空座，不够k 个。如图1-d所示。
所以L = 1, R = 1，无论取几行，都没有答案。
在这里插入图片描述
（二）从第1列到第2列，L = 1, R = 2
（1）从第1行到第1行，up = 1, down = 1，有两个空座，不够k个。如图2-a所示。
（2）从第1行到第2行，up = 1, down = 2，有三个空座，不够k个。如图2-b所示。
（3）从第1行到第3行，up = 1, down = 3，有三个空座，不够k个。如图2-c所示。
（4）从第1行到第4行，up = 1, down = 4，有三个空座，不够k个。如图2-d所示。
在这里插入图片描述
（三）从第1列到第3列，L = 1, R =3
（1）从第1行到第1行，up = 1, down = 1，有两个空座，不够k个。如图3-a所示。
（2）从第1行到第2行，up = 1, down = 2，有三个空座，不够k个。如图3-b所示。
（3）从第1行到第3行，up = 1, down = 3，有四个空座，不够k个。如图3-c所示。
（4）从第1行到第4行，up = 1, down = 4，有五个空座，够k个。此时的面积为3 * 4 =12。要尝试减少行数来确定有没有更小的面积。如图3-d所示。
（5）从第2行到第4行，up = 2, down = 4，有三个空座，不够k个。因此，从第3行到第4行和从第4行到第4行，都不用再枚举。因为肯定不够k个。如图3-e所示。
在这里插入图片描述
（四）从第1列到第4列，L = 1, R = 4
（1）从第1行到第1行，up = 1, down = 1，有两个空座，不够k个。如图4-a所示。
（2）从第1行到第2行，up = 1, down = 2，有三个空座，不够k个。如图4-b所示。
（3）从第1行到第3行，up = 1, down = 3，有四个空座，不够k个。如图4-c所示。
（4）从第1行到第4行，up = 1, down = 4，有六个空座，够k个。此时的面积为4 * 4 =16，与上面的12比较，最小的面积仍为12。要尝试减少行数来确定有没有更小的面积。如图4-d所示。
（5）从第2行到第4行，up = 2, down = 4，有四个空座，不够k个。因此，从第3行到第4行和从第4行到第4行，都不用再枚举。因为肯定不够k个。如图4-e所示。
在这里插入图片描述
（五）从第1列到第5列，L = 1, R = 5
（1）从第1行到第1行，up = 1, down = 1，有两个空座，不够k个。如图5-a所示。
（2）从第1行到第2行，up = 1, down = 2，有三个空座，不够k个。如图5-b所示。
（3）从第1行到第3行，up = 1, down = 3，有五个空座，够k个。面积为3 * 5 = 15，与最小面积12比较，最小值仍为12。不需要继续枚举从第1行到第4行，因为座位肯定够且面积会更大。如图5-c所示。
（4）从第2行到第3行，up = 2, down = 3，有三个空座，不够k个。如图5-d所示。
（5）从第2行到第4行，up = 2, down = 4, 有六个空座，够k个。当前面积为15，最小面积仍为12。如图5-e所示。
（6）从第3行到第4行，up = 3, down = 4，有五个座位，够k个，当前面积为10，最小面积更新为10。如图5-f所示。
（7）从第4行到第4行，up = 4, down = 4，有三个座位，不够k个。如图5-g所示。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1007, M = 1e9;
int n, m, k, tot, ans = M;
int a[N][N];
char seat;
void getsum(int L, int R) {
int em = 0, i = 1, j = 1;
for (; i <= n; i++) {
for (; j <= n && em<k; j++)
em += a[j][R] - a[j][L-1];
if (em < k) break;
ans = min(ans, (R-L+1) * (j-i));
em -= a[i][R] - a[i][L-1];
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> seat;
tot += (seat == '.');
a[i][j] = a[i][j-1] + (seat == '.');
}
}
if (tot < k) {
puts("No Solution");
return 0;
}
for (int L = 1; L <= m; L++)
for (int R = L; R <= m; R++)
getsum(L, R);
printf("%d\n", ans);
return 0;
}若有更好的解，欢迎评论或私信与我~