Eous的小站
日记

日记

Wed Dec 04 2024
4 分钟
life 日记
845 字

嘻嘻

upd：被hack了，不嘻嘻

上午#

考试
先睡了1h
神奇模拟赛

T1：第一眼：没思路。第二眼：还是没思路。然后，我就在考试结束前 30min30min 把T1 O(n!)O(n!) 暴力打了出来，骗了 2020 分。

T2：一眼看出来做法。给每条边打一个时间戳，查询的时候也带上时间戳。如果在 xx 到 lca(x,y)lca(x,y) 的路上所有边的时间戳都小于查询时的时间戳，那么久统计并输出答案，否则就输出 −1-1 。

T3&T4：依然没看

最后T2挂了 1010 分，死因：没有判断最后 xx 到 lca(x,y)lca(x,y) 和 yy 到 lca(x,y)lca(x,y) 的两条边的时间戳。然后靠着这 120120 拿了一个rank3。

下午#

改题。

T1：source solution
题解写的十分清楚，我就不写了。现在我要去发泄我被hack的怨气。

T2：被hack了。donaldqian 的代码时间复杂度是 O(nlog2n)O(nlog^2n) ，我的代码时间复杂度是 O(nlogn+qlogn)O(nlogn + qlogn) 。其中，nlognnlogn 来自lca预处理，qlognqlogn 来自离线查询lca。凭什么 donaldqian 就能过我不行？？！我的时间复杂度还比 donaldqian 优。
如果时间复杂度算错了就joker了。

下午最后一节课，找了一个局域网打扑克的仓库，于是和 hrl 打了一节课的扑克。

晚上#

就在我和 hrl 打扑克的时候，祝老说明天讲状压dp，于是我赶紧去补dp。

P2704 [NOI2001] 炮兵阵地 solution#

先预处理出来，每一行哪里能填，哪里不能填，然后用一个 int 存起来。然后，对于每一行枚举它的所有状态，记录每一个合法状态，和它里面能装多少个阵地。然后就开始dp。
设 dpi,k,jdp_{i,k,j} 表示当前模拟到 ii 行，当前行的状态是 jj ，上一行的状态是 kk ，那么枚举当前行的状态和上一行的状态和上上一行的状态，如果当前行的状态和上一行的状态不矛盾，上一行的状态和上上一行的状态不矛盾，且当前行的状态和上上一行的状态不矛盾，那么就更新答案。
预处理+初始化：

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int cnt = 0;
for (int i = 0; i < (1 << m); i++)
{
    if ((i & (i << 1)) || (i & (i << 2)) || (i & (i >> 1)) || (i & (i >> 2)))//看是否矛盾
        continue;
    cnt ++;
    a[cnt].first = i;
    a[cnt].second = __builtin_popcount(i);//记录当前状态可以放置多少
    if ((mp[1] & i) == i)//当当前的状态成立
        dp[1][0][cnt] = a[cnt].second;
}
for (int i = 1; i <= cnt; i++)
    for (int j = 1; j <= cnt; j++)
        if (!(a[i].first & a[j].first) && (mp[2] & a[j].first) == a[j].first)//当前行的状态成立且不与上一行的状态矛盾
            dp[2][i][j] = dp[1][0][i] + a[j].second;

dp：

CPP
1
2
3
4
5
6
7
8
for (int i = 3; i <= n; i++)
    for (int j = 1; j <= cnt; j++)
        if ((mp[i] & a[j].first) == a[j].first)//当前状态成立
            for (int k = 1; k <= cnt; k++)
                if (!(a[k].first & a[j].first))//上一行的状态不与这一行的状态矛盾
                    for (int l = 1; l <= cnt; l++)
                        if (!(a[k].first & a[lfirst) && !(a[j].first & [l]first))//上一行的状态不与上上行的状态矛盾且上上行的状态不与当前行的状态矛盾
                            dp[i][k][j] = max(dp[i][k][j],dp[i - 1][l][k] + a[j].second);