Powered by:NEFU AB_IN
2021 ICPC网络赛第二场
J
-
题意
有一个 n × n n×n n×n的房顶,每个位置都相当于会有个高为 h i , j h_{i,j} hi,j的水杯,水往低处流。在高度为 0 0 0处为泄漏,问会泄露多少水 -
思路
写个排序,高处的水优先往低处流,有 0 0 0就有答案,没 0 0 0没有答案 -
代码
/* * @Author: NEFU AB-IN * @Date: 2021-09-25 14:08:39 * @FilePath: \Contest\J.cpp * @LastEditTime: 2021-09-25 14:27:06 */ #include <bits/stdc++.h> using namespace std; const int N = 505; struct sa { int height; int x; int y; }; bool cmp(const sa &a, const sa &b) { return a.height > b.height; } int n, m, cnt = 0, h[N][N]; double a[N][N]; sa b[N * N]; int f(int x, int y) { if (x >= 1 && x <= n && y >= 1 && y <= n) return 1; return 0; } void add(int x, int y) { int sum = 0; if (f(x - 1, y) && h[x - 1][y] < h[x][y]) sum++; if (f(x + 1, y) && h[x + 1][y] < h[x][y]) sum++; if (f(x, y - 1) && h[x][y - 1] < h[x][y]) sum++; if (f(x, y + 1) && h[x][y + 1] < h[x][y]) sum++; double hh = a[x][y]; if (f(x - 1, y) && h[x - 1][y] < h[x][y]) a[x - 1][y] += hh / sum; if (f(x + 1, y) && h[x + 1][y] < h[x][y]) a[x + 1][y] += hh / sum; if (f(x, y - 1) && h[x][y - 1] < h[x][y]) a[x][y - 1] += hh / sum; if (f(x, y + 1) && h[x][y + 1] < h[x][y]) a[x][y + 1] += hh / sum; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1, x; j <= n; j++) { cin >> h[i][j]; b[++cnt] = {h[i][j], i, j}; } } sort(b + 1, b + 1 + cnt, cmp); memset(a, 0, sizeof(a)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) a[i][j] += m; for (int i = 1; i <= cnt; i++) { if (b[i].height == 0) break; add(b[i].x, b[i].y); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (h[i][j] == 0) printf("%.6f ", a[i][j]); else printf("0 "); } printf("\n"); } return 0; }
G
-
题意
-
思路
一步步进行 t t t次洛必达即可,每次在循环里判断分子是否为 0 0 0,如果不为 0 0 0且不是最后一次洛必达,那么就是 i n f i n i t y infinity infinity -
代码
/* * @Author: NEFU AB-IN * @Date: 2021-09-25 12:11:45 * @FilePath: \Contest\g.cpp * @LastEditTime: 2021-09-27 19:23:03 */ #include <bits/stdc++.h> using namespace std; #define LL long long #define MP make_pair #define SZ(X) ((int)(X).size()) #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define DEBUG(X) cout << #X << ": " << X << endl; typedef pair<int, int> PII; int n, t; const int N = 105; int a[N], b[N]; signed main() { IOS; cin >> n >> t; for (int i = 1; i <= n; ++i) { cin >> a[i] >> b[i]; } int fm = 1, now = 0; for (int i = 1; i <= t; ++i) { now = 0; fm *= i; if (i == 1) { for (int j = 1; j <= n; j++) now = now + a[j] * b[j]; } else if (i == 2) { for (int j = 1; j <= n; j++) now = now + a[j] * b[j] * b[j] * (-1); } else if (i == 3) { for (int j = 1; j <= n; j++) now = now + a[j] * b[j] * b[j] * 2 * b[j]; } else if (i == 4) { for (int j = 1; j <= n; j++) now = now + a[j] * b[j] * b[j] * (-6) * b[j] * b[j]; } else { for (int j = 1; j <= n; j++) now = now + a[j] * b[j] * b[j] * 24 * b[j] * b[j] * b[j]; } if (now != 0 && i != t) { cout << "infinity" << endl; return 0; } } int gcd = __gcd(now, fm); fm /= gcd; now /= gcd; if (fm == 1) cout << now << '\n'; else cout << now << "/" << fm << '\n'; return 0; }
M
-
题意
-
思路
- 如果 a [ i ] + b [ i ] = 1 a [ i ] + b [ i ] = 1 a[i]+b[i]=1,则 c [ i ] = 1 c [ i ] = 1 c[i]=1;
- 如果 a [ i ] + b [ i ] = 2 a [ i ] + b [ i ] = 2 a[i]+b[i]=2,就要开始进位了,再来一层循环,从 j = i + 1 j = i + 1 j=i+1开始循环,
- 如果 s i g n [ j ] = s i g n [ i ] sign [ j ] = sign [ i ] sign[j]=sign[i],那么就像普通的二进制加法一样,该进位就进位,不该进位就不用进位,这里不再细谈。
- 如果 s i g n [ j ] ≠ s i g n [ i ] sign[ j ] \ne sign [ i ] sign[j]=sign[i]了,因为符号不同了,相当于出现了减法,不再是单纯的二进制加法,所以就要像十进制减法一样,我们考虑“借位”。
-
代码
/* * @Author: NEFU AB-IN * @Date: 2021-09-27 16:57:43 * @FilePath: \Contest\m1.cpp * @LastEditTime: 2021-09-27 17:07:39 */ #include <bits/stdc++.h> using namespace std; #define LL long long #define MP make_pair #define SZ(X) ((int)(X).size()) #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define DEBUG(X) cout << #X << ": " << X << endl; typedef pair<int, int> PII; const int N = 205; LL a[N], b[N], n, sg[N], c[N]; void opt(LL c[]) { for (int i = 0; i < n; ++i) { printf("%ld", c[i]); if (i != n - 1) putchar(' '); } } signed main() { cin >> n; for (int i = 0; i < n; ++i) cin >> sg[i]; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) cin >> b[i]; for (int i = 0; i < n; ++i) { c[i] += a[i] + b[i]; while (c[i] >= 2) { c[i] -= 2; for (int j = i + 1; j < n; ++j) { c[j] += 1; if (sg[j] == sg[i]) break; } } } opt(c); return 0; }