文章目录
正文
1. 【6.30】P1331 海战
题目链接：https://www.luogu.com.cn/problem/P1331
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1005; char chessboard[N][N]; int ans;
bool check(int i, int j)
{
int cnt = 0;
if (chessboard[i][j] == '#') cnt ++;
if (chessboard[i + 1][j] == '#') cnt ++;
if (chessboard[i][j + 1] == '#') cnt ++;
if (chessboard[i + 1][j + 1] == '#') cnt ++;
return cnt == 3;
}
void solve()
{
int r, c; cin >> r >> c;
for (int i = 0; i < r; i ++) for (int j = 0; j < c; j ++) cin >> chessboard[i][j];
for (int i = 0; i < r; i ++) for (int j = 0; j < c; j ++)
{
if (check(i, j)) { cout << "Bad placement.\n"; return ; }
if (chessboard[i][j] == '#' && chessboard[i - 1][j] != '#' && chessboard[i][j - 1] != '#') ans ++;
}
cout << "There are " << ans << " ships.\n";
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
2. 【7.1】P1087 [NOIP 2004 普及组] FBI 树
题目链接：https://www.luogu.com.cn/problem/P1087
【AC_Code】
#include <iostream>
#include <cmath>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
char ans[2050]; string s;
void build(int id, int l, int r)
{
int mid = l + r >> 1;
if (l == r) { ans[id] = s[l]; return; }
build(2 * id, l, mid); build(2 * id + 1, mid + 1, r);
if (ans[2 * id] == ans[2 * id + 1]) ans[id] = ans[2 * id];
else ans[id] = 'F';
}
void dfs(int id, int l, int r)
{
int mid = l + r >> 1;
if (l == r) { cout << ans[id]; return; }
dfs(2 * id, l, mid); dfs(2 * id + 1, mid + 1, r);
cout << ans[id];
}
void solve()
{
int n; cin >> n >> s; n = pow(2, n);
for (int i = 0; i < n; ++i) s[i] = (s[i] == '1' ? 'I' : 'B');
build(1, 0, n - 1); dfs(1, 0, n - 1); cout << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_--) solve();
return 0;
}
3. 【7.2】B Forgery
题目链接：https://codeforces.com/contest/1059
【AC_Code】
#include <iostream>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1005; int n, m, cmp[N][N]; char a[N][N];
void bfs(int x, int y)
{
if (x + 1 > n || x + 2 > n || y + 1 > m || y + 2 > m) return ;
if
(
a[x][y] == '.' ||
a[x + 1][y] == '.' ||
a[x + 2][y] == '.' ||
a[x][y + 1] == '.' ||
a[x][y + 2] == '.' ||
a[x + 1][y + 2] == '.' ||
a[x + 2][y + 1] == '.' ||
a[x + 2][y + 2] == '.'
) return ;
cmp[x][y] = cmp[x + 1][y] = cmp[x + 2][y] = cmp[x][y + 1] = cmp[x][y + 2]
= cmp[x + 1][y + 2] = cmp[x + 2][y + 1] = cmp[x + 2][y + 2]
= 1;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) cin >> a[i][j];
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) if (a[i][j] == '#') bfs(i, j);
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) if (a[i][j] == '#' && !cmp[i][j]) { cout << "NO\n"; return ; }
cout << "YES\n";
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_--) solve();
return 0;
}
4. 【7.3】SP15436 UCV2013H - Slick
题目链接：https://www.spoj.com/problems/UCV2013H/
【AC_Code】
#include <iostream>
#include <cstring>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 255;
int
mp[N][N], num[N * N],
dx[4] = { -1, 0, 1, 0 },
dy[4] = { 0, 1, 0, -1 },
n, m, pos, ans;
void dfs(int x, int y)
{
for (int i = 0; i < 4; i ++)
{
int nx = x + dx[i], ny = y + dy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < m && mp[nx][ny])
{ mp[nx][ny] = 0; pos ++; dfs(nx, ny); }
}
}
void solve()
{
while (cin >> n >> m && n && m)
{
ans = 0; memset(mp, 0, sizeof mp); memset(num, 0, sizeof num);
for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) cin >> mp[i][j];
for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) if (mp[i][j])
{ mp[i][j] = 0; pos = 1; dfs(i, j); num[pos] ++; ans ++; }
cout << ans << '\n';
for (int i = 0; i <= n * m; i ++) if (num[i]) cout << i << ' ' << num[i] << '\n';
}
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
5.【7.4】B - リモコン
题目链接：https://atcoder.jp/contests/arc001/tasks/arc001_2
【AC_Code】
#include <iostream>
#include <cmath>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
void solve()
{
int a, b; cin >> a >> b; int c = abs(b - a); int cnt = 0;
while (c >= 8) { c = abs(c - 10); cnt ++; }
cout << min(abs(5 - c) + 1, c) + cnt << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
6. 【7.5】P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins
题目链接：https://www.luogu.com.cn/problem/P1460
【AC_Code】
#include <iostream>
#include <cstring>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 30, M = 20; bool used[M];
int n, m, vmin[N], feed[M][N], sum[N], min_feed = M, current[M], ans[M];
bool check()
{
for (int i = 1; i <= n; i ++) if (sum[i] < vmin[i]) return false;
return true;
}
void dfs(int pos, int guse)
{
if (guse >= min_feed) return ;
if (check())
{
min_feed = guse;
for (int i = 1; i <= guse;i ++) ans[i] = current[i];
}
if (pos > m) return ;
for (int i = pos; i <= m; i ++)
{
if (used[i])
{
for (int j = 1; j <= n; j ++) sum[j] += feed[i][j];
current[guse + 1] = i; used[i] = false;
dfs(i + 1, guse + 1); used[i] = true;
for (int j = 1; j <= n; j ++) sum[j] -= feed[i][j];
}
}
}
void solve()
{
cin >> n; for (int i = 1; i <= n; i ++) cin >> vmin[i]; cin >> m;
for (int i = 1; i <= m; i ++)
{
for (int j = 1; j <= n; j ++) cin >> feed[i][j];
used[i] = true;
}
memset(sum, 0, sizeof sum); dfs(1, 0); cout << min_feed;
for (int i = 1; i <= min_feed; i ++) cout << ' ' << ans[i]; cout << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
7. 【7.6】P1706 全排列问题
题目链接：https://www.luogu.com.cn/problem/P1706
【AC_Code】
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
void solve()
{
int n; cin >> n; vector<int> nums(n);
for (int i = 0; i < n; i ++) nums[i] = i + 1;
do { for (int num : nums) cout << setw(5) << num; cout << '\n'; }
while (next_permutation(nums.begin(), nums.end()));
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
结语
感谢您的阅读！期待您的一键三连！欢迎指正！
