题解

南京邮电大学ACM集训-南京多校联合训练赛1

本场比赛的lineseparate两题来自于我。

Line

不难想到,如果令f(n,m)表示n \times m的网格中的线段长度比,则f(n,m)=f (\frac{n}{gcd(n,m)},\frac{m}{gcd(n,m)}).

那么当n和m不互质时,就先将n和m化为互质的组合。

当n和m互质时,如果n或m为偶数,那么由对称性可知答案是1:1

而若n和m均为奇数,答案就为 (n*m+1)/2:(n*m)/2

本质上是一道找规律题(误

Separate

题意大致为:将一个n个元素的集合分为两个集合AB,集合A中任意两元素差值不小于X,集合B中任意两元素差值不小于Y,输出分法(\bmod 1000000007)。

不难想到有O(n^2)的简单DP做法:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 2010
int fx[N][N], fy[N][N], n;
ll a[N], A, B;
int main() {
    a[0] = -4223372036854775807ll;
    fx[1][0] = fy[1][0] = 1;
    scanf("%d%lld%lld", &n, &A, &B);
    for (int i = 1; i <= n; i++) scanf("%lld", a + i);
    sort(a + 1, a + n + 1);
    for (int i = 1; i < n; i++) {
        if (a[i + 1] - a[i] >= A)
            for (int j = 0; j < i; j++) fx[i + 1][j] = fx[i][j];
        if (a[i + 1] - a[i] >= B)
            for (int j = 0; j < i; j++) fy[i + 1][j] = fy[i][j];
        for (int j = 0; j < i; j++) {
            if (a[i + 1] - a[j] >= B)
                fy[i + 1][i] = (fy[i + 1][i] + fx[i][j]) % mod;
            if (a[i + 1] - a[j] >= A)
                fx[i + 1][i] = (fx[i + 1][i] + fy[i][j]) % mod;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) ans = (ans + (fx[n][i] + fy[n][i]) % mod) % mod;
    printf("%d\n", ans);
    return 0;
}

因为不能开二维数组存储,考虑当前DP到S_{i},观察当i变为i+1对答案的影响
因为S是递增的,所以满足S_{i+1}-S_{j}\geq B S_{j}一定是一段前缀,所以我们可以用二分找到右端点并用线段树求区间和
其他转移就相当于线段树的单点更新,再用lazy tag实现清零即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
#define mod 1000000007
ll a[N], A, B;
int tree[N * 4], f[N];
int t, n, m, ans;
void change(int p, int l, int r, int a, int b) {
    if (l == r) {
        (tree[p] += b) %= mod;
        return;
    }
    int mid = (l + r) / 2;
    if (a <= mid)
        change(p * 2, l, mid, a, b);
    else
        change(p * 2 + 1, mid + 1, r, a, b);
    tree[p] = (tree[p * 2] + tree[p * 2 + 1]) % mod;
}
int query(int p, int l, int r, int a, int b) {
    if (a > b) return 0;
    if (l == a && r == b) return tree[p];
    int mid = (l + r) / 2;
    if (b <= mid)
        return query(p * 2, l, mid, a, b);
    if (a > mid)
        return query(p * 2 + 1, mid + 1, r, a, b);
    return (query(p * 2, l, mid, a, mid) + query(p * 2 + 1, mid + 1, r, mid + 1, b)) % mod;
}
int main() {
    scanf("%d%lld%lld", &n, &A, &B);
    if (A < B) swap(A, B);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    a[0] = -A, a[n + 1] = a[n] + A, f[0] = 1;
    change(1, 0, n, 0, f[0]);
    int l = 0, r = 0;
    for (int i = 1; i <= n + 1; i++) {
        while (a[i] - a[r + 1] >= A) r++;
        if (i >= 2 && a[i - 1] - a[i - 2] < B) l = i - 2;
        if (a[i] - a[i - 1] >= A) f[i] = f[i - 1];
        (f[i] += query(1, 0, n, l, min(i - 2, r))) %= mod;
        if (i <= n && a[i + 1] - a[i - 1] >= B) change(1, 0, n, i, f[i]);
    }
    ll ans = (f[n + 1] + mod) % mod;
    printf("%lld\n", ans);
}

同时我们也注意到可转移的范围是一个随i右移的区间,用前缀和优化即可,时间复杂度O(n),然而本题也放了线段树的版本过了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define N 100010
#define mod 1000000007
int n, f[N], g[N];
ll a[N], A, B, ans;
int main() {
    scanf("%d%lld%lld", &n, &A, &B);
    if (A > B) swap(A, B);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 3; i <= n; i++)
        if (a[i] - a[i - 2] < A) {
            puts("0");
            return 0;
        }
    f[0] = g[0] = 1;
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        while (r < i - 1 && a[i] - a[r + 1] >= B) ++r;
        if (l <= r) f[i] = (g[r] + mod - (l ? g[l - 1] : 0)) % mod;
        g[i] = (g[i - 1] + f[i]) % mod;
        if (i > 1 && a[i] - a[i - 1] < A) l = i - 1;
    }
    for (int i = n; i >= 0; i--) {
        ans = (ans + f[i]) % mod;
        if (i < n && a[i + 1] - a[i] < A) break;
    }
    printf("%lld\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注