2019洛谷csp冲刺模拟赛

难题做不动就去翻去年的洛谷csp题做，实在是水啊~

第一次

(A)

(dp_{i, j})表示使用(i)个色子得到点数为(j)的概率，这样求出(dp_x)和(dp_y)两个(dp)数组后就可以枚举(x)个色子得到的点数，(y)个色子得到的点数是一个前缀，枚举即可。

#include 
#include 
#include 
using namespace std;
int x, y;
double dp[1050][6050], sum[6050];
int main()
{
    scanf("%d%d", &x, &y);
    for (int i = 1; i <= 6; i++) dp[1][i] = 1.0 / 6.0;
    for (int i = 1; i <= (max(x, y)) - 1; i++)
        for (int j = 1; j <= 6 * i; j++)
            for (int k = 1; k <= 6; k++)
                dp[i + 1][j + k] = dp[i + 1][j + k] + dp[i][j] / 6.0;
    double ans = 0, sum = 0;
    for (int i = 0; i <= x * 6; i++)
        ans += sum * dp[x][i], sum += dp[y][i];
    printf("%.2lf", ans * 100.0); putchar('%');
    return 0;
}

(B)

显然最后每个人都会到某个人站的地方集合。

那么先按每个人站的地方排序，从左往右枚举集合的位置，发现这个位置之前的人距离会增加，之后的人的距离会减少，转移是(O(1))的。

所以瓶颈在于排序，时间复杂度(O(n))。

#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
const int N = 1000000;
const ll INF = 999999999999999999;
int a[N + 50], b[N + 50], n;
ll sumb[N + 50], sufb[N + 50];
struct Node
{
    int a, b;
} dl[N + 50];
void Read(int &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st  '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? -x : x;
    return;
}
ll Abs(ll x)
{
    return x < 0 ? -x : x;
}
int Cmp(Node a, Node b)
{
    return a.a < b.a;
}
int main()
{
    Read(n);
    for (int i = 1; i <= n; i++) Read(dl[i].a);
    for (int i = 1; i <= n; i++) Read(dl[i].b);
    ll ans = INF, tmp = 0;
    sort(dl + 1, dl + n + 1, Cmp);
    for (int i = 1; i <= n; i++) sumb[i] = sumb[i - 1] + dl[i].b;
    for (int i = n; i >= 1; i--) sufb[i] = sufb[i + 1] + dl[i].b;
    for (int i = 1; i <= n; i++) tmp = tmp + 1LL * Abs(dl[i].a - dl[1].a) * dl[i].b;
    ans = tmp; 
    for (int i = 2; i <= n; i++)
    {
        tmp = tmp + 1LL * sumb[i - 1] * Abs(dl[i].a - dl[i - 1].a) - 1LL * sufb[i] * Abs(dl[i].a - dl[i - 1].a);
        ans = min(ans, tmp);
    }
    printf("%lld", ans);
    return 0;
}

(C)

对于一段函数，最大值最小值已知的情况下将这段函数拟合到(min + (max - min) / 2)是最优的。

所以问题转化为将数列分成一些段使得每段的极差尽可能小。

二分最小极差判断可行性。

发现判断可行性可以用倍增实现，注意这里倍增时不能算出总共需要的段数，而是段数大于给定段数就要退出。

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1000000; 
int n, x[N + 50], y[N + 50], stmin[25][N + 50], stmax[25][N + 50], maxx;
void Read(int &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st  '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? -x : x;
    return;
}
void Prework()
{
    maxx = 21;
    for (int j = 1; j <= maxx; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            stmin[j][i] = min(stmin[j - 1][i], stmin[j - 1][i + (1 << (j - 1))]),
            stmax[j][i] = max(stmax[j - 1][i], stmax[j - 1][i + (1 << (j - 1))]);
    return;
}
bool Check(int d, int m)
{
//    cout << d << endl;
    int l = 1, i;
    for (int i = 0; i < m && l <= n; i++)
    {
        int tmpmax = -1, tmpmin = 1000000001, r = l;
        for (int j = maxx; j >= 0; j--)
            if (r + (1 << j) - 1 <= n)
                if (max(tmpmax, stmax[j][r]) - min(tmpmin, stmin[j][r]) <= d)
                    tmpmin = min(tmpmin, stmin[j][r]), tmpmax = max(tmpmax, stmax[j][r]), r += (1 << j);
    //    cout << l - 1 << " " ;
        l = r;
    }
//    cout << endl;
    return l == n + 1;
}
void Print(int x)
{
    if (x > 9) Print(x / 10);
    putchar(x % 10 + '0');
    return;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%*d%d", &stmin[0][i]), stmax[0][i] = stmin[0][i];
    Prework();
    int t, m;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &m);
        int l = 0, r = 1000000001;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (Check(mid, m)) r = mid;
            else l = mid + 1; 
        }
        if (l % 2) printf("%d.5\n", l/2);
        else printf("%d\n", l/2);
    }
    return 0;
}