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; }