HHKB Programming Contest 2020【ABCE】
2024-09-02 03:36:57
比赛链接：https://atcoder.jp/contests/hhkb2020/tasks
A - Keyboard
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
char s, t;
cin >> s >> t;
cout << (s == 'Y' ? char(toupper(t)) : t) << "\n";
return 0;
}
B - Futon
题解
每个点只考虑右方和下方的点即可。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h, w;
cin >> h >> w;
vector<string> MP(h);
for (auto &x : MP) cin >> x;
int ans = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (MP[i][j] == '.' and i + 1 < h and MP[i + 1][j] == '.') ++ans;
if (MP[i][j] == '.' and j + 1 < w and MP[i][j + 1] == '.') ++ans;
}
}
cout << ans << "\n";
return 0;
}
C - Neq Min
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
set<int> st;
for (int i = 0; i <= 200010; i++)
st.insert(i);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
st.erase(x);
cout << *st.begin() << "\n";
}
return 0;
}
E - Lamps
题解
假设每盏灯在所有情况中都亮着，则亮着的灯的总数为 \(k \cdot 2^k\) 。
考虑每盏灯不亮的情况有多少种：一盏灯不亮的充要条件是上下左右连通的灯都不亮，设这些灯加上自身总个数为 \(tot\)，那么其余的 \(k-tot\) 盏灯的亮灭情况是随意的，即 \(2^{(k - tot)}\) 。
答案即为 $k \cdot 2^k - \sum \limits _{i = 1}^k 2^{(k - tot_i)} $ 。
上下左右连通的灯数用前缀和计算一下即可。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 2020;
constexpr int MOD = 1e9 + 7;
char MP[N][N];
int up[N][N];
int dn[N][N];
int lf[N][N];
int rt[N][N];
int k;
int binpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1LL * res * a % MOD;
a = 1LL * a * a % MOD;
b >>= 1;
}
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h, w;
cin >> h >> w;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> MP[i][j];
if (MP[i][j] == '.') ++k;
}
}
for (int j = 1; j <= w; j++) {
for (int i = 1; i <= h; i++) {
if (MP[i][j] == '#') {
up[i][j] = 0;
} else {
up[i][j] = up[i - 1][j] + 1;
}
}
}
for (int j = 1; j <= w; j++) {
for (int i = h; i >= 1; i--) {
if (MP[i][j] == '#') {
dn[i][j] = 0;
} else {
dn[i][j] = dn[i + 1][j] + 1;
}
}
}
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (MP[i][j] == '#') {
lf[i][j] = 0;
} else {
lf[i][j] = lf[i][j - 1] + 1;
}
}
}
for (int i = 1; i <= h; i++) {
for (int j = w; j >= 1; j--) {
if (MP[i][j] == '#') {
rt[i][j] = 0;
} else {
rt[i][j] = rt[i][j + 1] + 1;
}
}
}
int ans = k * binpow(2, k);
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (MP[i][j] == '.') {
int tot = up[i][j] + dn[i][j] + lf[i][j] + rt[i][j] - 4 + 1;
ans -= binpow(2, k - tot);
(ans += MOD) %= MOD;
}
}
}
cout << ans << "\n";
return 0;
}
最新文章
- 烂泥：zabbix3.0安装与配置
- 常见的http响应状态码
- linux查看公网地址
- UVALive 3956 Key Task （bfs+状态压缩）
- CF_91B
- ubuntu下提示/boot空间不足，解决办法
- C#中的操作数据库的SQLHelper类
- win 7 设置防火墙例外的端口号, 让其域网中可以访问
- onsubmit事件
- shiro中 UnknownAccountException
- mysql 2pc理解
- Linux debug
- python--Numpy and Pandas 笔记01
- win7计划任务报该任务映像己损坏或己篡改
- 牛客小白月赛7 CSL的校园卡
- （树的直径）LightOJ -- 1094
- [javaEE] jsp的九大隐式对象
- django2自动发现项目中的url
- mysql 列转行,合并字段的方法
- redis的下载