MX Day 15

T1：

思路：

首先，这道题其实用了一个很像滑动窗口的玩意来保存每个序列最小的数，其实最大也可以，只不过枚举方向要换。

我们首先发现这道题要用二分，因为要求最大值，且没什么特殊方式直接判断是否构成一个新序列，所以只能二分（毕竟T1）。

之后，我们二分答案，如果k*mid比n大，则直接跳出，毕竟根本不可能，否则就贪心，我们先用set存储末尾几个数（排过序），表示此时每个序列最小的数（但每个序列只有一个），之后我们再考虑前面的数，将这个数在之后备选序列找个最靠近的，这样保证最优，重复就可以了。

Code:

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, a[1000009], k, r;
bool vis[1000009];
bool check(int x)
{
    if (x * k > n)
    {
        return false;
    }
    if (k == 1)
    {
        return true;
    }
    multiset<int> s;
    for (int i = n - x + 1; i <= n; i++)
    {
        s.insert(a[i] - r);
    }
    int len = 0;
    for (int i = n - x; i >= 1; i--)
    {
        auto it = s.lower_bound(a[i]);
        if (it != s.end())
        {
            len++;
            s.erase(it);
            s.insert(a[i] - r);
            if (len >= x * (k - 1))
            {
                return true;
            }
        }
    }// I have a question: When I search it from n to 1, the ans is OK. But when I search ir from 1 to n, the ans id not OK. Why?
    return false;
}
signed main()
{
    freopen("pagoda.in", "r", stdin);
    freopen("pagoda.out", "w", stdout);
    n = read();
    k = read();
    r = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    sort(a + 1, a + n + 1);
    // int ans = 0;
    int l = 0, ans = 0, r = n / k;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

T2:

思路：

首先，我们要将这个变化方式转变为BA-->AA，AB--->BB，即现将每一个奇数位翻转，之后变化就成了减少连续段数，这样的话，我们就可以用线段树了，因为我们发现输出YES的情况只有任意一个前缀的连续段数量是上面的大于下面的，且最后一位字母相同，这样才能合理变化成下面的形式。

T3：

思路：

首先，我们注意到这道题其实式子是个等差数列，所以我们可以将其扔到一个数轴上（有序的数列都可以这么映射），所以，我们就将出现数的地方贡献乘上此时前面的数量，也就是前缀和大小，之后的话，我们就要考虑有多少个数落在这之间，用容斥就行了。

Code：

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> Pair;
const int N = 1e5 + 5;
const int T = 3e7;
#define F first
#define S second
Pair seq[N];
int a[N], b[N], p[N], cnt[30000005];
int n;
int ans, tot, A, B, D;
int cmp(Pair a, Pair b)
{
    return a.S - a.F > b.S - b.F;
}
signed main()
{
    //	freopen("a.in","r",stdin);
    //	freopen("a.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &seq[i].F, &seq[i].S);
        p[0] += seq[i].F;
        tot += seq[i].S;
    }
    sort(seq + 1, seq + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
    {
        a[i] = seq[i].F, b[i] = seq[i].S;
        p[i] = p[i - 1] - a[i] + b[i];
        A += a[i], B += b[i];
    }
    D = min(T, tot);
    for (int i = 1; i <= D; i++)
    {
        cnt[((A + i - 1) / i) * i - A]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (p[i - 1] > A + T)
        {
            break;
        }
        for (int j = p[i - 1] - A + 1; j <= p[i] - A && j <= T; j++)
        {
            ans += i * cnt[j];
        }
    }
    // D ---> menkan
    for (int l = D + 1, r; l <= tot; l = r + 1)
    {
        int L = l, R = tot;
        while (L <= R)
        {
            int mid = (L + R) >> 1;
            if ((A + l - 1) / l == (A + mid - 1) / mid)
            {
                r = mid, L = mid + 1;
            }
            else
            {
                R = mid - 1;
            }
        }
        int k = (A + l - 1) / l;
        int l0 = max(l, (A + k - 1) / k), r0 = min(r, B / k);
        if (l0 <= r0)
        {
            for (int i = 1; i <= n; i++)
            {
                if (p[i] / k >= l0)
                {
                    ans += 1ll * i * (min(p[i] / k, r0) - l0 + 1);
                }
                if (p[i - 1] / k >= l0)
                {
                    ans -= 1ll * i * (min(p[i - 1] / k, r0) - l0 + 1);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

文章操作

T1：

思路：

Code:

T2:

思路：

T3：

思路：

Code：

相关推荐

评论

MX Day 15