刷题日志

刷题日志

[P1457 USACO2.1]城堡 The Castle 思维难度不高，难度居然是蓝，被某谷赋虚高了，主要是考码力，地图需要在每个点上统计东南西北四处是否有墙，好在没有冲突的情况，无需分类讨论（实际上我也不会/qwq）。剩下的就是DFS洪水填充，统计一下就可以了，反正范围只到50。

#include <iostream>
#include <cstring>
#include <cstdio>
// #include <windows.h>using namespace std;const int MAXN = 55;
const int dir[5][2] = {{0, 0}, {0, -1}, {-1, 0}, {0, 1}, {1, 0}
};
int n, m, cnt, maxn, total;
bool a[MAXN][MAXN][4], vis[MAXN][MAXN];void Judge(int x, int y, int t) {
//	1: 在西面有墙(1)
//	2: 在北面有墙(2)
//	4: 在东面有墙(3) 
//	8: 在南面有墙(4)// 这段写累死了switch(t) {case 1:a[x][y][1] = true;break;case 2:a[x][y][2] = true;break;case 3:a[x][y][1] = a[x][y][2] = true;break;case 4: a[x][y][3] = true;break;case 5: a[x][y][1] = a[x][y][3] = true;break;case 6: a[x][y][2] = a[x][y][3] = true;break;case 7: a[x][y][1] = a[x][y][2] = a[x][y][3] = true;break;case 8: a[x][y][4] = true;break;case 9: a[x][y][1] = a[x][y][4] = true;break;case 10: a[x][y][2] = a[x][y][4] = true;break;case 11: a[x][y][1] = a[x][y][2] = a[x][y][4] = true;break;case 12: a[x][y][3] = a[x][y][4] = true;break;case 13: a[x][y][1] = a[x][y][3] = a[x][y][4] = true;break;case 14: a[x][y][2] = a[x][y][3] = a[x][y][4] = true;break;case 15: a[x][y][1] = a[x][y][2] = a[x][y][3] = a[x][y][4] = true;break;default:break;}// cout << t << " " << a[x][y][1] << " " << a[x][y][2] << " " << a[x][y][3] << " " << a[x][y][4] << endl; 
}bool valid(int x, int y) {return x >= 1 && y >= 1 && x <= n && y <= m;
}
void dfs(int x, int y) {// cout << x << " " << y << endl;vis[x][y] = true;cnt ++;for(int i=1; i<=4; i++) {int nx = x + dir[i][0], ny = y + dir[i][1];if(valid(nx, ny) && !a[x][y][i] && !vis[nx][ny]) {dfs(nx, ny);}}// vis[x][y] = false; 洪水填充 
}
int maxt, posx, posy;
char c;int main() {cin >> m >> n;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {int t;cin >> t;Judge(i, j, t);}}memset(vis, false, sizeof(vis));/*for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cout << i << " " << j << " " << a[i][j][1] << " " << a[i][j][2] << " " << a[i][j][3] << " " << a[i][j][4] << endl; }} */for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(!vis[i][j]) {// cout << i << " " << j << endl;cnt = 0;dfs(i, j);total ++;maxn = max(maxn, cnt);// cout << endl;}}}cout << total << endl << maxn << endl;// system("pause");for(int j=1; j<=m; j++) {for(int i=n; i>=1; i--) {if(a[i][j][2]) {memset(vis, false, sizeof(vis));a[i][j][2] = false;cnt = 0;dfs(i, j);a[i][j][2] = true;if(cnt > maxt) {maxt = cnt;posx = i, posy = j;c = 'N';}}if(a[i][j][3]) {memset(vis, false, sizeof(vis));a[i][j][3] = false;cnt = 0;dfs(i, j);a[i][j][3] = true;if(cnt > maxt) {maxt = cnt;posx = i, posy = j;c = 'E';}}}}cout << maxt << endl << posx << " " << posy << " " << c;return 0;
}

[P1458 USACO2.1]顺序的分数 Ordered Fractions 按部就班模拟即可，唯一的坑点就是0和某个数的最大公约数需要特判

#include <iostream>
#include <algorithm>using namespace std;int n, m;
struct node {int p, q;double c;
} a[165*165];int gcd(int x, int y) {return x%y==0?y:gcd(y,x%y);
}bool cmp(node x, node y) {return x.c < y.c;
}int main() {cin >> n;for(int i=1; i<=n; i++) {for(int j=0; j<=i; j++) {int k;if(j == 0) k = i;else k = gcd(i, j);if(k == 1) {m ++;a