日记

Thu Dec 12 2024

11 分钟

life 日记

1786 字

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，用一个栈记录经过的点，就可以得出答案。因为实现实在太美所以放一下代码。

CPP

#include<bits/extc++.h>
#pragma GCC optimize(2)
using namespace std;
const int maxn(3005);
const int maxq(4e5 + 5);
int n,m,q;
int ans[maxq];
bool vis[maxn];
int st[maxn];
void read(int &x)
{
    x = 0;
    int f = 1;
    char ch = getchar();
    while (!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
    while (isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    x *= f;
}
vector<int>g1[maxn],g2[maxn],g3[maxn];//g1是正图，g2是反图，g3是建出来的树
struct query{int u,v,k,id;};//离线存询问
vector<query>q1[maxn],q2[maxn];
void dfs1(int u)
{
    vis[u] = 1;
    for (auto v : g2[u])
        if (!vis[v])
            dfs1(v);
}
void dfs2(int u)//在树上跑dfs，记录答案
{
    st[++st[0]] = u;
    for (auto i : q2[u])
        if (st[0] >= i.k)
            ans[i.id] = st[st[0] - i.k + 1];
    for (auto v : g3[u])
        dfs2(v);
    st[0] --;
}
signed main()
{
    read(n),read(m),read(q);
    int u,v,k;
    for (int i(1); i <= m; i++)
    {
        read(u),read(v);//输入加建边
        g1[u].push_back(v);//建正图
        g2[v].push_back(u);//建反图
    }
    for (int i(1); i <= n; i++)
        sort(g1[i].begin(),g1[i].end());//给每一条出边连到的点排序，为下面找字典序最小做铺垫（死去的阅读理解忽然开始攻击我）
    for (int i(1); i <= q; i++)
    {
        read(u),read(v),read(k);
        q1[v].push_back((query){u,v,k,i});
    }
    memset(ans,0xff,sizeof ans);
    for (int ed(1); ed <= n; ed++)
    {
        for (int j(1); j <= n; j++)
            vis[j] = 0,q2[j].clear(),g3[j].clear();//对于每一个ed重新建图
        dfs1(ed);//先处理有哪些点可以到ed
        for (int i(1); i <= n; i++)
        {
            if (vis[i] && i != ed)
            {
                for (auto v : g1[i])
                {
                    if (vis[v])
                    {
                        g3[v].push_back(i);//建树
                        break;
                    }
                }
            }
        }
        for (auto i : q1[ed])//处理询问
            q2[i.u].push_back(i);
        dfs2(ed);
    }
    for (int i(1); i <= q; i++)
        printf("%d\n",ans[i]);
    return 0;
}

晚上#

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$ ，就可以了。
再贴一下代码：

CPP

//依旧又臭又长
#include<bits/extc++.h>
#define int long long
#define ls (rt << 1)
#define rs (rt << 1 | 1)
using namespace std;
const int maxn = 2e5 + 5;
int n,m;
int a[maxn];
struct edge
{
    int l,p;
    edge *nxt;
}*head[maxn];//链式前向星(?)记录右端点在i的赛事
struct Nahida//线段树（别管结构体名字）
{
    int l,r;
    int val,lazy;
}tree[maxn << 2];
void push_up(int rt){tree[rt].val = max(tree[ls].val,tree[rs].val);}//维护区间最大值
void push_down(int rt)//lazy_tag下放
{
    if (!tree[rt].lazy)
        return;
    tree[ls].val += tree[rt].lazy;
    tree[rs].val += tree[rt].lazy;
    tree[ls].lazy += tree[rt].lazy;
    tree[rs].lazy += tree[rt].lazy;
    tree[rt].lazy = 0;
}
void build(int l,int r,int rt)
{
    tree[rt].l = l;
    tree[rt].r = r;
    if (l == r)
    {
        tree[rt].val = tree[rt].lazy = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(l,mid,ls);
    build(mid + 1,r,rs);
}
void upd(int ql,int qr,int x,int rt = 1)
{
    int l = tree[rt].l;
    int r = tree[rt].r;
    if (ql <= l && r <= qr)
    {
        tree[rt].val += x;
        tree[rt].lazy += x;
        return;
    }
    push_down(rt);
    int mid = (l + r) >> 1;
    if (ql <= mid)
        upd(ql,qr,x,ls);
    if (qr > mid)
        upd(ql,qr,x,rs);
    push_up(rt);
}
void adde(int l,int r,int p)//链式前向星(?)增添赛事
{
    auto tmp = new edge;
    tmp->l = l;
    tmp->p = p;
    tmp->nxt = head[r];
    head[r] = tmp;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l,r,p;
    for (int i = 1; i <= m; i++)
    {
        cin >> l >> r >> p;
        adde(l,r,p);
    }
    build(1,n,1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        upd(i,i,ans);//j = i时的单点修改
        upd(1,i,-a[i]);//j < i和j = i的区间修改
        for (auto j = head[i]; j; j = j->nxt)
            upd(1,j->l,j->p);//增加赛事的收益
        ans = max(ans,tree[1].val);//记录最大答案
    }
    cout << ans;
    return 0;
}

日记

https://nahida.cfd/blog/2024-12-12日记/