2021 ICPC 网络赛第二场 Asia Regionals Online Contest (II)

线段树最后debug时间不够了orz 这场打得一般

把代码放上来

G

泰勒展开

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;
const double eps = 1e-8;
#define int ll
#define rep(i, l, r) for (int i = l; i <= r; ++i)
ll a[N], b[N], n, t;
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> t;
    int suma = 0, sumb = 1;
    rep(i, 1, n) cin >> a[i] >> b[i];
    if (t == 0)  return cout << 0, 0;
    for (int i = 1; i < t; ++i) {
        ll sum = 0;
        for (int j = 1; j <= n; ++j) {
            sum += a[j] * pow(b[j], i);
        }
        if (sum) return cout << "infinity", 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (t % 2 == 0) a[i] *= -1;
        for (int j = 1; j <= t; ++j) {
            a[i] *= b[i];
        }
        suma += a[i];
    }
    int gcd = __gcd(t, abs(suma));
    t /= gcd, suma /= gcd;

    if (t == 1)
        cout << suma;
    else
        cout << suma << '/' << t;
    return 0;
}

J

队友用桶写的

#include <bits/stdc++.h>
using namespace std;
const int N = 507;
typedef long long ll;
// #define int ll
#define rep(i, l, r) for (int i = l; i <= r; ++i)
double c[N][N];
int a[N][N], n;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool out(int x, int y) { return x >= 1 and x <= n and y >= 1 and y <= n; }
vector<pair<int, int>> mn[10000 + 1];
signed main() {
    double m;
    scanf("%d%lf", &n, &m);
    int maxht = 0, minht = 10000;
    rep(i, 1, n) rep(j, 1, n) scanf("%d", &a[i][j]),
        maxht = max(maxht, a[i][j]), minht = min(minht, a[i][j]);

    rep(i, 1, n) rep(j, 1, n) {
        c[i][j] = m;
        mn[a[i][j]].push_back({i, j});
    }

    for (int i = maxht; i > minht; --i) {
        for (auto k : mn[i]) {
            int x = k.first, y = k.second;
            int cnt = 0;
            bool u = 0, d = 0, l = 0, r = 0;
            if (a[x][y] > a[x][y - 1] and y - 1 >= 1) {
                cnt++;
                u = 1;
            }
            if (a[x][y] > a[x][y + 1] and y + 1 <= n) {
                cnt++;
                d = 1;
            }
            if (a[x][y] > a[x - 1][y] and x - 1 >= 1) {
                cnt++;
                l = 1;
            }
            if (a[x][y] > a[x + 1][y] and x + 1 <= n) {
                cnt++;
                r = 1;
            }
            if (u) c[x][y - 1] += c[x][y] / cnt;
            if (d) c[x][y + 1] += c[x][y] / cnt;
            if (l) c[x - 1][y] += c[x][y] / cnt;
            if (r) c[x + 1][y] += c[x][y] / cnt;
            c[x][y] = 0;
        }
    }

    rep(i, 1, n) {
        rep(j, 1, n) printf("%.10lf ", c[i][j]);
        putchar(10);
    }
    return 0;
}

赛后补了一个稍微好看点的

#include <bits/stdc++.h>
using namespace std;
const int N = 507;
typedef long long ll;
// #define int ll
#define rep(i, l, r) for (int i = l; i <= r; ++i)
double c[N][N];
int a[N][N], n;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool ins(int x, int y) { return x >= 1 and x <= n and y >= 1 and y <= n; }
vector<pair<int, int>> mn[10000 + 1];
signed main() {
    double m;
    scanf("%d%lf", &n, &m);
    int maxht = 0, minht = 10000;
    rep(i, 1, n) rep(j, 1, n) scanf("%d", &a[i][j]),
        maxht = max(maxht, a[i][j]), minht = min(minht, a[i][j]);

    rep(i, 1, n) rep(j, 1, n) {
        c[i][j] = m;
        mn[a[i][j]].emplace_back(i, j);
    }

    for (int i = maxht; i > minht; --i) {
        for (auto p : mn[i]) {
            int x = p.first, y = p.second, cnt = 0;
            rep(k, 0, 3) {
                int xx = x + dx[k], yy = y + dy[k];
                if (ins(xx, yy) && a[x][y] > a[xx][yy]) ++cnt;
            }
            rep(k, 0, 3) {
                int xx = x + dx[k], yy = y + dy[k];
                if (ins(xx, yy) && a[x][y] > a[xx][yy])
                    c[xx][yy] += c[x][y] / cnt;
            }
            c[x][y] = 0;
        }
    }

    rep(i, 1, n) {
        rep(j, 1, n) printf("%.10lf ", c[i][j]);
        putchar(10);
    }
    return 0;
}

M

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
typedef long long ll;
#define int ll
#define rep(i, l, r) for (int i = l; i <= r; ++i)
ll a[N], b[N], n, sg[N], c[N];
void opt(ll c[]) {
    for (int i = 0; i < n; ++i) {
        printf("%lld", 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;
}