日记 - 伊埃斯的博客站

OI的乐趣何在？

ctj
刷水题
卡常
和教练斗智斗勇

上午

考试。
私人考试链接
何谓 私人 ?
他™把 1600 的题放T3？他™把 2700 的题放T1？

T1

是道最短路？如是。
用 basic_string 把每一个路径存下来，知周所众，basic_string 就是 string++ ，所以它也有重载的 < 用来判断字典序。于是我就能搓一个 dijkstra 骗 $50$ 。
然而它RE了。

T2

似乎有点思路？
我们把这个平方展开，变成这个样子： $a + b + 2\times\sqrt{ab}$ 。然后它要是整数，那么 $ab$ 就得是完全平方数，也就是求有多少个 $a \in [1,n],b \in [1,m]$ 满足 $ab$ 是完全平方数。
也是只能想到这里了。

T3

一看：先把暴力打了再说。
再看：分块？
也是直接打出来了。时间复杂度是 $\mathcal{O}(q\sqrt{n})$ ，但是知周所众，我向来算不来时间复杂度，分块还那么难调，这样例还那么水。
然后就打出来过拍。
一看原题：1600 放T3？绿题放T3？

T4

一看： $1\times 10^{500}$
os:高精度滚啊

下午

改题

T1

source solution
这就是所谓的 T1 。
看题先看数据范围（因为我有过很多次没看数据范围导致以为想的是错解的经历）。它说 $n \le 5000$ ，但是 $q \le 4 \times 10^5$ ， $n$ 很小，所以我们应该在 $n$ 上做文章。
我们可以先把询问离线，然后枚举终点 $ed$ （为啥和题目里的变量名不一样，因为我写的代码里叫 $ed$ ，为了好理解代码），建反图，先不管字典序的问题，在反图上dfs，处理出能到 $ed$ 的点。
然后就是tj里很让人摸不着头脑的话：对于每一个能到 $ed$ 的点，它到 $ed$ 的字典序最小的路径里，它的后继一定是唯一的，也就是他出边连到的点里字典序最小或是编号最小的。
~~这不废话吗，你都最小了肯定唯一咯~~
然后知道了这个，我们就可以处理出它的后继，然后每一个点都建一条到他后继的边，那么就是一棵内向树。内向树可不好搞哦，所以我们要把他反过来，建成外向树。然后在这个树上再跑dfs，用一个栈记录经过的点，就可以得出答案。因为实现实在太美所以放一下代码。

1
#include<bits/extc++.h>
2
#pragma GCC optimize(2)
3
using namespace std;
4
const int maxn(3005);
5
const int maxq(4e5 + 5);
6
int n,m,q;
7
int ans[maxq];
8
bool vis[maxn];
9
int st[maxn];
10
void read(int &x)
11
{
12
    x = 0;
13
    int f = 1;
14
    char ch = getchar();
15
    while (!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
16
    while (isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
17
    x *= f;
18
}
19
vector<int>g1[maxn],g2[maxn],g3[maxn];//g1是正图，g2是反图，g3是建出来的树
20
struct query{int u,v,k,id;};//离线存询问
21
vector<query>q1[maxn],q2[maxn];
22
void dfs1(int u)
23
{
24
    vis[u] = 1;
25
    for (auto v : g2[u])
26
        if (!vis[v])
27
            dfs1(v);
28
}
29
void dfs2(int u)//在树上跑dfs，记录答案
30
{
31
    st[++st[0]] = u;
32
    for (auto i : q2[u])
33
        if (st[0] >= i.k)
34
            ans[i.id] = st[st[0] - i.k + 1];
35
    for (auto v : g3[u])
36
        dfs2(v);
37
    st[0] --;
38
}
39
signed main()
40
{
41
    read(n),read(m),read(q);
42
    int u,v,k;
43
    for (int i(1); i <= m; i++)
44
    {
45
        read(u),read(v);//输入加建边
46
        g1[u].push_back(v);//建正图
47
        g2[v].push_back(u);//建反图
48
    }
49
    for (int i(1); i <= n; i++)
50
        sort(g1[i].begin(),g1[i].end());//给每一条出边连到的点排序，为下面找字典序最小做铺垫（死去的阅读理解忽然开始攻击我）
51
    for (int i(1); i <= q; i++)
52
    {
53
        read(u),read(v),read(k);
54
        q1[v].push_back((query){u,v,k,i});
55
    }
56
    memset(ans,0xff,sizeof ans);
57
    for (int ed(1); ed <= n; ed++)
58
    {
59
        for (int j(1); j <= n; j++)
60
            vis[j] = 0,q2[j].clear(),g3[j].clear();//对于每一个ed重新建图
61
        dfs1(ed);//先处理有哪些点可以到ed
62
        for (int i(1); i <= n; i++)
63
        {
64
            if (vis[i] && i != ed)
65
            {
66
                for (auto v : g1[i])
67
                {
68
                    if (vis[v])
69
                    {
70
                        g3[v].push_back(i);//建树
71
                        break;
72
                    }
73
                }
74
            }
75
        }
76
        for (auto i : q1[ed])//处理询问
77
            q2[i.u].push_back(i);
78
        dfs2(ed);
79
    }
80
    for (int i(1); i <= q; i++)
81
        printf("%d\n",ans[i]);
82
    return 0;
83
}

晚上

CF115E Linear Kingdom Races solution
这道题，本来想的dp方程似乎是对的，但是一看tj，没有一道是我的那种dp，也是推得出来。
设 $dp_{i,j}$ 表示考虑到第 $i$ 条路， $[i,j]$ 全选的最大收益。那么对于 $j < i$ ，增加了修路的代价 $a_i$ ，获得了左端点在 $[i - j + 1,i]$ ，右端点在 $i$ 的比赛的收益。那么有转移： $dp_{i,j} = dp_{i - 1,j} - a_i + \sum\limits_{l_k \in [i - j + 1,i],r_k = i}p_k$ 。
但是我们只考虑了 $j < i$ 的情况。对于 $j = i$ ，有 $dp_{i,i} = \max\limits_{0 \le j \le k \le i - 1}dp_{k,j} - a_i + \sum\limits_{l_k = r_k = i}p_k = ans - a_i + \sum\limits_{l_k = r_k = i}p_k$ ，因为 $\max\limits_{0 \le j \le k \le i - 1}dp_{k,j}$ 就是 $i - 1$ 的答案。
这样子状态设计完了。但是，我们发现，这样子的空间复杂度是 $\mathcal{O}(n^2)$ 的，时间复杂度更是来到了 $\mathcal{O}(n^3)$ ，这对于 $n,m \le 2 \times 10^5$ 肯定不行啊。
我们先优化空间。发现对于 $j < i$ ，它只会从 $dp_{i - 1,?}$ 转移。而对于 $j = i$ ，我们可以通过记录 $ans$ 来转移，综上，它总是由 $dp_{i - 1,?}$ 转移而来，所以我们可以通过滚动数组来优化空间到 $\mathcal{O}(n)$ 。
然后现在该优化时间了。发现每多考虑一个 $i$ ，都是 $dp_{i,j} = dp_{i,?} - a_i$ ，结合上文的滚动数组可以发现是一个区间修改。而对于 $i = j$ ，相当于单点赋值。最后加上一个没考虑的 $\sum p_k$ ，就可以了。
再贴一下代码：

1
//依旧又臭又长
2
#include<bits/extc++.h>
3
#define int long long
4
#define ls (rt << 1)
5
#define rs (rt << 1 | 1)
6
using namespace std;
7
const int maxn = 2e5 + 5;
8
int n,m;
9
int a[maxn];
10
struct edge
11
{
12
    int l,p;
13
    edge *nxt;
14
}*head[maxn];//链式前向星(?)记录右端点在i的赛事
15
struct Nahida//线段树（别管结构体名字）
16
{
17
    int l,r;
18
    int val,lazy;
19
}tree[maxn << 2];
20
void push_up(int rt){tree[rt].val = max(tree[ls].val,tree[rs].val);}//维护区间最大值
21
void push_down(int rt)//lazy_tag下放
22
{
23
    if (!tree[rt].lazy)
24
        return;
25
    tree[ls].val += tree[rt].lazy;
26
    tree[rs].val += tree[rt].lazy;
27
    tree[ls].lazy += tree[rt].lazy;
28
    tree[rs].lazy += tree[rt].lazy;
29
    tree[rt].lazy = 0;
30
}
31
void build(int l,int r,int rt)
32
{
33
    tree[rt].l = l;
34
    tree[rt].r = r;
35
    if (l == r)
36
    {
37
        tree[rt].val = tree[rt].lazy = 0;
38
        return;
39
    }
40
    int mid = (l + r) >> 1;
41
    build(l,mid,ls);
42
    build(mid + 1,r,rs);
43
}
44
void upd(int ql,int qr,int x,int rt = 1)
45
{
46
    int l = tree[rt].l;
47
    int r = tree[rt].r;
48
    if (ql <= l && r <= qr)
49
    {
50
        tree[rt].val += x;
51
        tree[rt].lazy += x;
52
        return;
53
    }
54
    push_down(rt);
55
    int mid = (l + r) >> 1;
56
    if (ql <= mid)
57
        upd(ql,qr,x,ls);
58
    if (qr > mid)
59
        upd(ql,qr,x,rs);
60
    push_up(rt);
61
}
62
void adde(int l,int r,int p)//链式前向星(?)增添赛事
63
{
64
    auto tmp = new edge;
65
    tmp->l = l;
66
    tmp->p = p;
67
    tmp->nxt = head[r];
68
    head[r] = tmp;
69
}
70
signed main()
71
{
72
    ios::sync_with_stdio(0);
73
    cin.tie(0);
74
    cout.tie(0);
75
    cin >> n >> m;
76
    for (int i = 1; i <= n; i++)
77
        cin >> a[i];
78
    int l,r,p;
79
    for (int i = 1; i <= m; i++)
80
    {
81
        cin >> l >> r >> p;
82
        adde(l,r,p);
83
    }
84
    build(1,n,1);
85
    int ans = 0;
86
    for (int i = 1; i <= n; i++)
87
    {
88
        upd(i,i,ans);//j = i时的单点修改
89
        upd(1,i,-a[i]);//j < i和j = i的区间修改
90
        for (auto j = head[i]; j; j = j->nxt)
91
            upd(1,j->l,j->p);//增加赛事的收益
92
        ans = max(ans,tree[1].val);//记录最大答案
93
    }
94
    cout << ans;
95
    return 0;
96
}

Thanks for reading!

日记

周四 12月 12 2024

1754 字 · 11 分钟

life 日记