Visits: 434

Hello 2020

New Year and Naming

模拟。

const int N = 23;
int n, m;
string s[N], t[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < m; i++) cin >> t[i];
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        --x;
        cout << s[x%n] << t[x%m] << endl;
    }
    return 0;
}

New Year and Ascent Sequence

组合计数，前缀和。

const int N = 1e5 + 7, M = 1e6 + 7;
int n, c[M], d[M], cnt;
vi e[N];
bool ok[N];

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) {
        int m;
        rd(m);
        while (m--) {
            int x;
            rd(x);
            e[i].pb(x);
        }
        for (ui j = 1; j < e[i].size(); j++)
            if (e[i][j-1] < e[i][j]) ok[i] = 1;
    }
    for (int i = 1; i <= n; i++)
        if (ok[i]) ++cnt;
        else {
            c[e[i][0]]++, d[e[i].back()]++;
        }
    for (int i = M - 2; ~i; i--) c[i] += c[i+1];
    ll ans = 1ll * n * n - 1ll * (n - cnt) * (n - cnt);
    for (int i = 0; i < M - 1; i++) {
        ans += 1ll * d[i] * c[i+1];
    }
    print(ans);
    return 0;
}

New Year and Permutation

组合计数。

const int N = 2.5e5 + 7;
int n;
modint p[N], ans;

int main() {
    rd(n), rd(P);
    p[0] = 1;
    for (int i = 1; i <= n; i++) p[i] = p[i-1] * i;
    for (int i = 1; i <= n; i++) ans += p[i] * p[n+1-i] * i;
    print(ans);
    return 0;
}

New Year and Conference

以某一维为时间轴，我们需要判定在这一维上有交的在另一维上是否有交。

那么扫过这一维的所有时间点，用 multiset 实时维护包含这个时间点的所有区间即可。

总时间复杂度 $\mathcal O(n \log n)$。

const int N = 1e5 + 7;
int n, m, sa[N], ea[N], sb[N], eb[N], a[N*4];
vi l[N*4], r[N*4];

inline bool solve() {
    for (int i = 1; i <= m; ++i) l[i].clear(), r[i].clear();
    for (int i = 1; i <= n; ++i) l[sa[i]].pb(i), r[ea[i]].pb(i);
    multiset <int, greater <int> > lmax;
    multiset <int> rmin;
    for (int i = 1; i <= m; ++i) {
        for (int id : l[i]) lmax.insert(sb[id]), rmin.insert(eb[id]);
        if (lmax.size() && *lmax.begin() > *rmin.begin()) return 1;
        for (int id : r[i]) lmax.erase(lmax.find(sb[id])), rmin.erase(rmin.find(eb[id]));
    }
    return 0;
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(sa[i]), rd(ea[i]), rd(sb[i]), rd(eb[i]);
    copy(sa + 1, sa + n + 1, a + 1);
    copy(ea + 1, ea + n + 1, a + n + 1);
    copy(sb + 1, sb + n + 1, a + n * 2 + 1);
    copy(eb + 1, eb + n + 1, a + n * 3 + 1);
    sort(a + 1, a + n * 4 + 1);
    m = unique(a + 1, a + n * 4 + 1) - a - 1;
    for (int i = 1; i <= n; ++i)
        sa[i] = lower_bound(a + 1, a + m + 1, sa[i]) - a,
        ea[i] = lower_bound(a + 1, a + m + 1, ea[i]) - a,
        sb[i] = lower_bound(a + 1, a + m + 1, sb[i]) - a,
        eb[i] = lower_bound(a + 1, a + m + 1, eb[i]) - a;
    bool ans = solve();
    swap(sa, sb), swap(ea, eb);
    puts((ans | solve()) ? "NO" : "YES");
    return 0;
}

New Year and Castle Construction

以每个点为原点做一次 P2992 [USACO10OPEN]三角形计数Triangle Counting，最后将答案 $\times \frac {n – 4}2$ 即可。

const int N = 2.5e3 + 7;
int n;
P a[N];

inline int f(P o) {
    int x = o.x, y = o.y;
    if (x <= 0 && y < 0) return 0;
    if (x > 0 && y <= 0) return 1;
    if (x >= 0 && y > 0) return 2;
    return 3;
}

inline bool cmpa(P x, P y) { return f(x) == f(y) ? x % y > 0 : f(x) < f(y); }

inline ll solve(int o) {
    if (n <= 3) return 0;
    ll ans = 1ll * (n - 1) * (n - 2) * (n - 3) / 6;
    vector <P> p;
    for (int i = 1; i <= n; i++)
        if (i != o) p.pb(a[i] - a[o]);
    sort(p.begin(), p.end(), cmpa);
    int w = p.size();
    for (int i = 0; i < w; i++) p.pb(p[i]);
    for (int i = 0, j = 1; i < w; i++) {
        if (j == i) j = i + 1;
        while (j < 2 * w && j != i + w && p[i] % p[j] > 0) ++j;
        int w = j - i - 1;
        ans -= 1ll * w * (w - 1) / 2;
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf %lf", &a[i].x, &a[i].y);
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans += solve(i);
    print(ans * (n - 4) / 2);
    return 0;
}

New Year and Social Network

题目太神仙了，先咕咕咕着。

Seollal

题目太神仙了，先咕咕咕着。