没错我们又考了一次普及组的题
被普及组的题折磨了两天我也是没救了…

这里写图片描述

懵逼的 题目

哈哈哈老娘又能上Luogu辣

扯淡的 题解

记得D1晚上听他们说题目来着, 听中初中部的人说题目好难啊, 然后就去找学弟萌玩♂耍…学弟一脸懵逼 “不难啊”威武我大实验!, 要被学弟碾了…

T1T2没啥好说的…只要T2别脑子抽了写trie就没啥问题…似乎当成字符串暴力匹配都能过? 还是普及组良心!

T3是一个最短路…吧

听到题目就想到酱的一个事实

如果从一个有颜色的格子走到一个没有颜色的格子, 最优方案应该把没有颜色的格子的颜色变成当前在的格子的颜色

然后就是把白格子分成两部分: 一部分将(江)要变成红色, 一部分将(江)要变成黄色, 然后连边跑dijk就行…数据范围小的一批…0ms稳如poi~我才不会告诉你我读错题目改了2h+
最后注意一个细节…题目只说了起点是有颜色的…终点可能是白色…所以最终答案其实是min(d[终点变成红色], d[终点变成黄色])…不过数据非常良心没有给我卡成0分…

T4是一个二分答案×单调队列优化DP

woc单调队列优化DP都是普及组考点了嘛…????
我用实际行动告诉泥萌数据点里每一个-1的点…所以我也就没有判断…

首先二分答案很好想到…但是当时和学弟坐在床上聊♂天也没有听的太懂题目…
回来以后做题…读错题目…以为一步必须走一格的意思是必须走一个单位距离…然后发现这题没法做了…发现woc这个判断怎么写啊….???然后写了个puts(-1)一分没有…伤人感情…好歹咱也是花了1h+看了这道题是吧…

首先明确一下题目: 每次必须走一格的意思就是每一次都要到达下一个 [有分数的点] (两点间的距离 >= 最小步长 || <= 最大步长),

然后应该比较容易想到一个n ^ 2DP…f[i] = max{f[j] + a[i]} , j = 0 ~ (i - 1) (i, j间可到达)

然后你就有了50’…
发现f[i]的取值其实就是max{f[j]} + a[i]…而a[i]是固定的…所以其实转移就是要求一个能到达的最大的f[j]!
而一个点能到的范围很容易发现是一个连续的区间, 而且这个区间是一个滑动窗口!(两点(i, j)距离 < 当前最短步长, 那么i之前的点和j的距离肯定也小于最短步长, 两点距离 > 当前最长步长, 那么i之后的点和j的距离肯定也大于最长步长)
于是就可以写一个优雅的单调队列来优化转移惹…

注意单调队列为空的处理…(push(make_pair(0, 0))和当单调队列为空, 你又往里面加了一个(0, 0)的时候, 是不能转移的…

沙茶的 代码

T1(用double好像会WA)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib> 
#include <algorithm>
#define LL long long
#define DD double
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

using namespace std;
typedef pair<int, int> pii;

const int homework = 2;
const int normaltest = 3;
const int finalexam = 5;

int main()
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    printf("%lld", ((LL)(a * homework) + (b * normaltest) + (c * finalexam)) / 10);
    fclose(stdout);
    fclose(stdin);
    return 0;
}

T2(一开始以为要输出编号就蛋疼的加了个pair)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib> 
#include <cmath>
#include <algorithm>
#define MAXN (1000 + 5)
#define MAXQ (1000 + 5)
#define LL long long
#define DD double
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

using namespace std;
typedef pair<int, int> pii;

int n;
int q;
pii a[MAXN];

bool cmp(const pii&, const pii&);
int cx(pii&);
int mpow(int,  int);
int main()
{

    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    sort(a + 1, a + n + 1, cmp);
    pii srx;
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &srx.second, &srx.first);
        srx.second = mpow(10, srx.second);
        printf("%d\n", cx(srx));
    }
    fclose(stdout);
    fclose(stdin);
    return 0;
}
bool cmp(const pii& x, const pii& y)
{
    return x.first < y.first;
}
int cx(pii& x)
{
    for (int i = 1; i <= n; i++)
    {
        if ((a[i].first % x.second) == x.first)
        {
            return a[i].first;
        }
    }
    return -1;
}
int mpow(int di, int zhi)
{
    int re = 1;
    for (int i = 1; i <= zhi; i++)
    {
        re *= di;
    }
    return re;
}

/*
5 5
2123
1123
23
24
24
2 23
3 123
3 124
2 12
2
12
*/

T3(蜜汁码长)


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (10000 + 5)
#define MAXM (40000 + 5)
#define MAXL (100 + 5)
#define INF (0x7ffffff)
#define TW (2)
#define TD (1)
#define TS (0)
#define LL long long
#define DD double
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define bh(a, b) ((a - 1) * srn + b)

using namespace std;
typedef pair<int, int> pii;

struct cmp
{
    bool operator () (const pii x, const pii y)
    {
        return x.second > y.second;
    }
};

struct edg
{
    int from;
    int to;
    int next;
    int cost;
} b[MAXM << 1];
int g[MAXN << 1];
int cntb;

int n;
int m;

int srn, srh;

int dis[MAXN << 1];

pii a[MAXN << 1];

void ade(int*, edg*, int&, int, int, int);
void init();
void dijk();
inline int calcost(const int, const int);
int main()
{


    scanf("%d%d", &srn, &srh);
    n = srn * srn;
    int srx, sry, srz;
    for (int i = 1; i <= srh; i++)
    {
        scanf("%d%d%d", &srx, &sry, &srz);
        a[bh(srx, sry)].second = srz + 1;
    }
    init();
    dijk();
    if (dis[n] < INF || dis[n << 1] < INF)
        printf("%d", min(dis[n], dis[n << 1]));
    else
        puts("-1");
    fclose(stdout);
    fclose(stdin);
    return 0;
}
void ade(int* gx, edg* bx, int& cntx, int from, int to, int cost)
{
    bx[++cntx].next = gx[from];
    bx[cntx].from = from;
    bx[cntx].to = to;
    bx[cntx].cost = cost;
    gx[from] = cntx;
}
void init()
{
    for (int i = 1; i <= srn; i++)
    {
        for (int j = 1; j <= srn; j++)
        {
            int t = bh(i, j);
            a[t + n].first = a[t].first = t;
        }
    }
    for (int i = 1; i <= srn; i++)
    {
        for (int j = 1; j <= srn; j++)
        {
            int srf = bh(i, j);
            if (a[srf].second)
            {
                if (i != 1)
                {
                    int srt = bh(i - 1, j);
                    if (!a[srt].second)
                    {
                        if (a[srf].second == 2)
                            srt += n;
                        ade(g, b, cntb, srf, srt, TW);
                    }
                    else 
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                if (i != srn)
                {
                    int srt = bh(i + 1, j);
                    if (!a[srt].second)
                    {
                        if (a[srf].second == 2)
                            srt += n;
                        ade(g, b, cntb, srf, srt, TW);
                    }
                    else 
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }

                }
                if (j != 1)
                {
                    int srt = bh(i, j - 1);
                    if (!a[srt].second)
                    {
                        if (a[srf].second == 2)
                            srt += n;
                        ade(g, b, cntb, srf, srt, TW);
                    }
                    else 
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                if (j != srn)
                {
                    int srt = bh(i, j + 1);
                    if (!a[srt].second)
                    {
                        if (a[srf].second == 2)
                            srt += n;
                        ade(g, b, cntb, srf, srt, TW);
                    }
                    else 
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
            }
            else
            {
                a[srf].second = 1;
                if (i != 1)
                {
                    int srt = bh(i - 1, j);
                    if (a[srt].second)
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                if (i != srn)
                {
                    int srt = bh(i + 1, j);
                    if (a[srt].second)
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                if (j != 1)
                {
                    int srt = bh(i, j - 1);
                    if (a[srt].second)
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                if (j != srn)
                {
                    int srt = bh(i, j + 1);
                    if (a[srt].second)
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                srf += n;
                a[srf].second = 2;
                if (i != 1)
                {
                    int srt = bh(i - 1, j);
                    if (a[srt].second)
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                if (i != srn)
                {
                    int srt = bh(i + 1, j);
                    if (a[srt].second)
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                if (j != 1)
                {
                    int srt = bh(i, j - 1);
                    if (a[srt].second)
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                if (j != srn)
                {
                    int srt = bh(i, j + 1);
                    if (a[srt].second)
                    {
                        ade(g, b, cntb, srf, srt, calcost(srf, srt));
                    }
                }
                a[srf].second  = a[srf - n].second = 0;
            }
        }
    }
}
inline int calcost(int from, int to)
{
    if (!a[to].second)
    {
        return TW;
    }
    else
    {
        return ((a[from].second ==  a[to].second) ? (TS) : (TD));
    }
}
void dijk()
{
    int startDash = 1;
    priority_queue<pii, vector<pii>, cmp> q;
    q.push(make_pair(startDash, 0));
    bool vis[MAXN << 1];
    memset(vis, false, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    dis[startDash] = 0;
    while (!q.empty())
    {
        pii dq = q.top();
        q.pop();
        if (vis[dq.first])
        {
            continue;
        }
        vis[dq.first] = true;
        for (int i = g[dq.first]; i; i = b[i].next)
        {
            if (dis[dq.first] < INF && dis[b[i].to] > dis[dq.first] + b[i].cost)
            {
                dis[b[i].to] = dis[dq.first] + b[i].cost;
                q.push(make_pair(b[i].to, dis[b[i].to]));
            }
        }
    }
}

/*
10 28
1 1 1
2 2 1
3 2 1
4 7 0
4 8 1
4 4 1
4 3 1
5 3 1
6 6 0
6 5 1
6 3 0
6 4 0
6 7 1
7 2 1
7 4 0
7 3 1
8 5 1
8 2 0
8 4 1
9 4 0
9 3 0
9 10 1
9 7 1
9 6 1
10 9 1
10 6 0
10 7 1
10 5 0

*/

T4(注释里面的是没有优化的50’判断…结构体单调队列真他娘难调…)


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000 + 5)
#define INF (0x7ffffff)
#define LL long long
#define DD double
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
//#define GG

using namespace std;
typedef pair<int, int> pii;

struct moqueue// max
{
    pii a[MAXN];
    int cnt;
    int CNT;
    int p[MAXN];
    int he, ta;
    void init()
    {
        memset(a, 0, sizeof(a));
        memset(p, 0, sizeof(p));
        cnt = CNT = 0;
        he = 1;
        ta = 1;
    }
    pii ask()
    {
        return a[he + 1];
    }
    void ins(pii x)
    {
        while (he < ta && a[ta].second <= x.second)
        {
            --ta;
        }
        a[++ta] = x;
        p[ta] = ++cnt;
    }
    void del()
    {
        if (he < ta && p[he + 1] == ++CNT)
        {
            ++he;
        }
    }
    bool empty()
    {
        return he >= ta;
    }
}maxf;

int n;
int goal;
int fdis;
int ans;
int maxl;

pii a[MAXN];

void ef();
bool pd(int, int);
void solve();
int main()
{
#ifdef GG
    freopen("jump.in", "r", stdin);
    freopen("jump.out", "w", stdout);
#endif
    scanf("%d%d%d", &n, &fdis, &goal);
    LL sum = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].first, &a[i].second);
        sum += (a[i].second > 0 ? a[i].second : 0);
    }
    maxl = a[n].first;
    if (sum < goal)
    {
        puts("-1");
        return 0;
    }
    solve();
    printf("%d", ans);
    fclose(stdout);
    fclose(stdin);
    return 0;
}
void solve()
{
    ef();
}
void ef()
{
    int le = 1;
    int ri = maxl + 1;
    while (le < ri)
    {
        int mi = (le + ri) >> 1;
        if (pd(max(1, fdis - mi), fdis + mi))
        {
            ans = mi;
            ri = mi;
        }
        else
        {
            le = mi + 1;
        }
    }
}

/*
bool pd(int sm, int ga)
{
    int re = 0;
    int f[MAXN];
    memset(f, -1, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[j].first + ga >= a[i].first && a[j].first + sm <= a[i].first && f[j] != -1)
            {
                f[i] = max(f[j] + a[i].second, f[i]);
                re = max(f[i], re);
            }
        }
    }
    return re >= goal;
}
*/

// first 璺濈, second 鍒嗘暟
bool pd(int sm, int ga)
{
    int re = 0;
    int f[MAXN];
    memset(f, -1, sizeof(f));
    f[0] = 0;
    maxf.init();
    int lastorder = 0;
    for (int i = 1; i <= n; i++)
    {
        int ok = 1;
        for (; lastorder < i; lastorder++)
        {
            if (a[lastorder].first + sm <= a[i].first)
            {
                if (f[lastorder] != -1)
                    maxf.ins(make_pair(a[lastorder].first, f[lastorder]));// 有问题...
            }
            else
            {
                ok = 0;
                break;
            }
        }
        pii fr = maxf.ask();
        while (!maxf.empty() && fr.first + ga < a[i].first)
        {
            maxf.del();
            fr = maxf.ask();
        }
        if (maxf.empty())
        {
            maxf.ins(make_pair(0, 0));
            continue;
        }
//        lastorder += ok;
        fr = maxf.ask();
        if (fr.first + sm > a[i].first || fr.first + ga < a[i].first)
        continue;
        f[i] = fr.second + a[i].second;
        re = max(re, f[i]);
    }
    return re >= goal;
}

/*
10 72 112
16 18
18 -5
45 32
95 43
126 46
168 42
214 14
256 4
302 6
347 0
*/

/*
7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2
*/

By 写树状数组都能崩的 Cansult