AtCoder Beginner Contest 449 解析
A - π
通过样例可确定π取值为3.1415926535。
查看代码
#include
using namespace std;
int main() {
double diameter;
cin >> diameter;
diameter /= 2;
printf("%.8lf", diameter * diameter * 3.1415926535);
return 0;
}
B - 巧克力拆分
记录当前行数n和列数m。操作1减少x行（n-=x），操作2减少x列（m-=x），计算对应格子数。
查看代码
#include
using namespace std;
int main() {
int rows, cols, queries;
cin >> rows >> cols >> queries;
while (queries--) {
int op, amount;
cin >> op >> amount;
int result = 0;
if (op == 1) {
result = amount * cols;
rows -= amount;
} else {
result = amount * rows;
cols -= amount;
}
cout << result << '\n';
}
return 0;
}
C - 舒适距离
固定位置j，统计区间[j-r,j-l]内相同字符数量。维护滑动窗口计数器，动态更新左右边界。
查看代码
#include
using namespace std;
int main() {
int n, left, right;
char s[5000005];
int count[300];
cin >> n >> left >> right;
for (int i = 1; i <= n; ++i) cin >> s[i];
int total = 0;
for (int i = 1; i <= n; ++i) {
if (i - left >= 1) count[s[i-left]-'a']++;
if (i - right - 1 >= 1) count[s[i-right-1]-'a']--;
total += count[s[i]-'a'];
}
cout << total;
return 0;
}
D - 目标构建
通过坐标系对称性处理四个象限。计算第一象限符合条件的点数，再乘以对应象限数量。
查看代码
#include
using namespace std;
int getEven(int x, int y) { /* ... */ }
int getRange(int x, int y) { /* ... */ }
int calculate(int l, int r, int d, int u) { /* ... */ }
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
int signA = (a > 0) ? 1 : -1;
int signB = (b > 0) ? 1 : -1;
int signC = (c > 0) ? 1 : -1;
int signD = (d > 0) ? 1 : -1;
a = abs(a); b = abs(b); swap(a,b);
c = abs(c); d = abs(d); swap(c,d);
int result = 0;
if (signA == signB) {
if (signC == signD) {
result = calculate(a,b,c,d);
} else {
result = calculate(a,b,0,c) + calculate(a,b,1,d);
}
} else {
if (signC == signD) {
result = calculate(0,a,c,d) + calculate(1,b,c,d);
} else {
result = calculate(0,a,0,c) + calculate(0,a,1,d)
+ calculate(1,b,0,c) + calculate(1,b,1,d);
}
}
cout << result;
return 0;
}
E - 数组增量
采用桶排序思想，按高度和编号排序后使用树状数组维护空位编号。
查看代码
#include
using namespace std;
int main() {
int n, m;
int values[500005];
int frequency[500005];
int maxFrequency = 0;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> values[i];
frequency[values[i]]++;
maxFrequency = max(maxFrequency, frequency[values[i]]);
}
// 后续处理逻辑...
return 0;
}
F - 网格裁剪
使用扫描线算法求矩形面积并。将原问题转化为点覆盖问题进行处理。
查看代码
#include
using namespace std;
struct Event { /* ... */ };
int main() {
int maxX, maxY, n, m, _n_;
cin >> maxX >> maxY >> n >> m >> _n_;
// 处理输入并建立事件列表
vector<Event> events;
for (int i = 0; i < _n_; ++i) {
int r, c;
cin >> r >> c;
// 添加矩形事件
}
// 坐标离散化处理
vector<int> xCoords, yCoords;
// 构建线段树结构
// 扫描线处理
int total = (maxX-1)*(maxY-1);
for (int i = 1; i < xCoords.size()-1; ++i) {
int width = xCoords[i+1] - xCoords[i];
// 更新线段树状态
total -= tree.query() * width;
}
cout << total;
return 0;
}
