POI 2013-526互联

P3560 [POI2013] LAN-Colorful Chain

长度固定，哈希。

对于所有满足条件的子串，它们的长度是固定的。

哈希加前缀和。

P3558 [POI2013] BAJ-Bytecomputer

首先，若仅考虑 \(a_{i-1}\) 与 \(a_i\)（\(a_{i-1} < a_i\)），发现操作次数仅与 \(a_i\) 有关而与 \(a_{i-1}\) 的值无关。因此，把一个数变得很大是不优的。
具体地，每个数不应超过最大值，也不应低于最小值，即更改后的序列 \(a'\) 仍满足 \(\forall a'_i,\ a'_i \in \{ -1,0,1 \}\)，而 \(a'\) 一定形如 \(-1,-1,-1...0,0,0...1,1,1\)。

于是考虑 DP，设 \(dp[i][j]\) 表示将前 \(i\) 个数改为合法，第 \(i\) 个数最终改为 \(j\) 的最少花费。
转移时依次枚举 \(i\) 和 \(j\)，设 \(d=j-a_i\)。\(d=0\) 直接从前一位小于等于 \(a_i\) 转移，而由于序列中只有 \(-1,0,1\)，所以 \(d>0\) 只能由前一位为 \(1\) 转移来，\(d<0\) 只能由前一位为 \(-1\) 转移来。简单分讨即可。

P3550 [POI2013] TAK-Taxis

一道贪心。

设当前位置为 \(j\)。
把过程分为两个部分：\(j < d\) 的和 \(j \ge d\) 的。

\(j \ge d\) 的，由一辆不小于 \(d\) 的车直接送走最优。
\(j < d\) 的，由于每次要先走 \(d-j\) 的路程，剩下的才是贡献，所以应该使 \(d-j\) “尽快地”减小，所以每次应该先选路程最大的车。

于是贪心策略整理如下：
预留一辆最小的不小于 \(m-d\) 的车处理 \(j \ge d\) 的情况，之后从大到小选择车辆，每次分讨一下。
需要注意，因为留了一辆车没有使用，所以需要每次判断是否可以用预留车直接结束。

具体地，按路程从大到小：

如果当前是预留的车就跳过、
如果预留的车能直接结束就结束。
如果当前车不能使人前进则无解。
使用当前车改变 \(j\)。
如果 \(j>=m\) 结束。

P3551 [POI2013] USU-Take-out

一定有解，可反证。
所以考虑倒序构造，用栈加前缀和维护。

LGP3556 [POI2013] MOR-Tales of seafaring

题意：

给 \(n\) 个点 \(m\) 条边无向图，边权为 \(1\)，每次询问两个点之间是否有长度为 \(d\) 的路径（不一定是简单路径）

分析：

首先想到，对于短于最短路径的一定不存在，其余的可能可以通过最短路加上 \(2\) 得到，即反复走刷步数。发现与奇偶有关。~~然后不会了。~~

考虑对于每个点维护奇数偶数的最短路，然后判断即可。离线处理（起点相同的一起查）。

实现：

SPFA 可以通过本题，复杂度应该是与 bfs 相同的吧。

LGP3557 [POI2013] GRA-Tower Defense Game

题意：

有一个 \(n\) 个点 \(m\) 条边的图，每条边距离是 \(1\) ，已知用 \(k\) 个攻击距离为 \(1\) 的塔可以打到整个地图，让构造一个方案使得用小于等于 \(k\) 个攻击距离为 \(2\) 的塔打到整个地图。

分析：

奇妙的思路。

发现由于不是求最小塔数，而是不多于 \(k\) 个，考虑性质。

若已经有 \((1,k)\) 的覆盖方式，则有：随意放置一个点，若不与 \((1,k)\) 的重合，则与至少一个相邻，可以覆盖到相邻位置的原先的塔所覆盖的全部位置。于是，无论怎么放，一定不会劣于 \(k\) 个，随意放置并记录即可。

实现：

似乎没什么细节。

LGP3554 [POI2013] LUK-Triumphal arch

题意：

给一颗 \(n\) 个节点的树（\(n \le 3 \times 10^5\)），初始时 \(1\) 号节点被染黑，其余是白的。两个人轮流操作，一开始 B 在 \(1\) 号节点。每一轮，A 选择 \(k\) 个点染黑，然后 B 走到一个相邻节点，如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。求能让 A 获胜的最小的 \(k\) 。

分析：

显然二分是可以的。

另外，B 一定不会走回头路。

考虑每次染色必须先将 B 所在点的所有子结点染黑，而多余的次数可以染子树里需要提前染色即子结点数大于 \(mid\) 的点。

树形 DP，\(aside_i\) 表示以 \(i\) 为根的子树内需要子树外“支援”多少染色次数。最后检查 \(aside_1\) 是否为零即可。

实现:

DP 时注意，时刻保证 \(aside_i\) 非负，似乎许多人没有注意到。感觉时刻保证非负是比较合理且不容易出错的写法。

LGP3563 [POI2013] POL-Polarization

题意：

给定一颗树，请给树边改成有向边，求连通的点对个数的最大最小值。点对连通，要么 \(a\) 能到达 \(b\)，要么 \(b\) 能到达 \(a\)。\((1\le n\le 250000)\)。

分析：

最小值
1. 因为树是一个二分图，所以显然可以将所有边从左部指向右部，于是联通对的数量为边数。
2. 也可以考虑每一层的边是相同指向，且与根结点相连的指向根结点，这会是除根结点外每个点能且仅能到达一个点。
3. 综上，最小值为 \(n-1\)。
最大值
1. 首先有引理如下（不会证）：
  对于一个使得联通点对最多的图，一定存在一个点，满足方案：以该点为根，每个子树内，要么所有边均指向根，要么均背向根。且根结点一定在重心上。
2. 答案的第一部分：
  不经越过根节点的，易知数量为 \(\sum (size_i-1)\)，意为新增了子树内其他点到根结点的贡献。
3. 第二部分：经过根节点的
  1. 设指向根的子树总大小为 \(x\) ，背向根的子树总大小为 \(y\)。则所有 ”\(x\)“ 可以到达根节点再到达所有“\(y\)”。所以数量为 \(x \times y\)。
  2. 若要使 \(x\times y\) 最大，一定是 \(x-y\) 最小时成立。实际为多重背包求（更接近 \(\dfrac{n}{2}\)）对应值是否可以得到。
  3. DP 式子：\(dp[j]|=dp[j-i]\)。\(dp[j]\) 表示当前值为 \(j\) 是否可取，\(i\) 表示大小为 \(i\) 的子树的值（其实就是 \(i\)）。复杂度 \(O(n^2)\)。
  4. 初步优化：二进制优化 01 背包。
  5. 复杂度分析
    发现树本身有性质：若子树少于 \(\sqrt{n}\) 个显然复杂度不劣于 \(O(n\sqrt{n})\)。若多于 \(\sqrt{n}\) 个，不妨想想怎么卡：如果有两个一样的显然会被合并，亏了，所以子树应两两不同，这样建树总点数为 \(\sum \limits_{i=1}^j\)，而\(j<\sqrt{n}\)。综上，总复杂度为 \(O(n \sqrt n)\)。
    6.进一步优化：bitset 优化连续二进制操作。具体地，操作改为 \(dp|=dp<<i\)。复杂度 \(O(\dfrac{n\sqrt n}{w})\)。

实现：

注意重新以重心为根节点维护子树；最终用于背包的子树是重心的直接子树； \(dp|=dp<<i\) 进行 \(cnt[i]\) 次。

参考：

Solution By Tsawke

LGP3553 [POI2013] INS-Inspector

摘要：

二分 \(k\)，每次沿时间轴检验前 \(mid\) 个是否冲突。
人的记录使他有一个必须存在的时间段。
逐时间点、尽可能使人数最少地满足记录要求，并检查是否使用超过 \(n\) 个人。

题意：

一天公司有 \(n\) 个员工和 \(m\) 个员工记录，每个员工只会在连续的一段时间内工作。现在给出 \(m\) 条记录分别是谁写的、什么时候写的以及写的时候除了他还有多少人。求最大的 \(k\) 使得前 \(k\) 条记录互不矛盾。

分析：

发现 \(k\) 似乎无法直接求得，考虑转化为检验前 \(k\) 条是否合法。
发现对于第 \(i+1\) 条记录，直接检验其与前 \(i\) 条是否冲突似乎不好实现，考虑每次检验 \(O(m)\) 地遍历全部时间点，因此需要二分 \(k\)。
如何检验
1. 由于每个员工工作时间连续，所以将记录整合可以得到每个人必须要工作的区间，后文简称“必要区间”，整合区间可以得到每个时间点至少有多少人，检验记录是否小于最小值。以及是否存在对于同一时刻有不同记录。
2. 通过了 i 检测的所有情况中，每个时间点的记录人数大于等于实际人数，因此若不限制人数一定合法（即每个人只工作于一个时间点）。问题转化为尝试使用不多于 \(n\) 个人构造一个合法解。
3. 沿时间轴检验并时刻判断即可，详见下文。个人认为本题难点是检测的思路和具体实现。
检验的实现
1. 思路：尝试用最优方式满足限制，并记录使用了多少人，看是否超过 \(n\)。
2. 预处理：每个时间点 \(i\) 的记录人数、有多少人的“必要区间”以当前时间开始或结束；即 \(cnt_i,bg_i,ed_i\)。
3. 实现方案不唯一，部分名称含义如下：
  \(now\)：当前至少要有多少人（由且仅由 \(st_i,ed_i\) 决定）。
  \(used\)：已经使用过多少人。
  \(exl\)：有多少人已经完成了必要区间，但是被迫延后下班。
  \(exr\)：有多少人还没到必要区间，但是被迫提前上班。
  \(fre\)：没有写记录的人，他们可以自由安排。
  \(left\)：已经完成了工作，离开公司的人，后续安排与他们无关。
  注意，初始时认为上述全部为零；另外，上述名称在表述时也视作集合。
4. 每一步的处理方法
  处理顺序：\(bg_i \rightarrow cnt_i \rightarrow ed_i\)。通过变量上的加减、逻辑上的人员调动（即从某一集合移动到另一集合），用 \(now,exl,exr\) 拼凑出 \(cnt_i\)
  1. 当前点至少有 \(bg_i\) 个人开始工作，逻辑上,要把 \(exr\) 或者 \(fre\) 拿出 \(bg_i\) 个转化为 \(now\)，优先使用 \(exr\)，不足则增加 \(used\)。
  2. \(now+exl+exr\) 是当前我们构造的方案的人数，若其小于 \(cnt_i\)，则需要从 \(fre\) 中抽调一些。因为\(now\) 是被 \(bg_i,ed_i\) 锁定的，所以把抽调的加在 \(exr\) 上，逻辑上为要求这些人提前工作。
  3. 若 \(now+exl+exr\) 大于 \(cnt_i\)，则先弹掉 \(exl\)，仍多则弹掉 \(exr\)。
  4. 在当前时间，有 \(ed_i\) 个人可以结束工作，让他们进入 \(exl\) 等待后续调度。
  5. 最后，判断 \(used\) 是否超限。把上述步骤循环 \(m\) 次即可。

实现：

采用了 \(now,used,exl,exr\) 实现，用 \(used \ge n\) 判断不合法，仅在每次结尾判断即可，中间不需要判哪些变量是不是负数，个人认为比较好写。


    for(int i=1;i<=m;i++)
    {
        if(!t[i].vis)continue;

        now += t[i].bgcnt;

        if(now>t[i].cnt)
            return false;

        while (t[i].bgcnt--)
        {
            if(exr>0)exr--;
            else  used++;
        }

        if(now+exl+exr<t[i].cnt)
        {
            int d = t[i].cnt-now-exl-exr;
            exr+= d;  used+= d;
        }
        if(now+exl+exr>t[i].cnt)
        {
            int d = now+exl+exr-t[i].cnt;
            while(d--)
            {
                if(exl>0)exl--;
                else exr--;
            }
        }

        now-=t[i].edcnt; exl+=t[i].edcnt;

        if(used>n)
        {
            return false;
        }
    }

LGP3552 [POI2013] SPA-Walk

题意：

有 \(2^n\) 个长度为 \(n\) 的 01 串，两个 01 串之间有边当且仅当这两个 01 串只有一位不同，现在从这 \(2^n\) 个串中拿掉 \(k\) 个，问指定两个串之间能否到达。

分析：

会不了一点（虽然别的也不会），看了题解发现是神奇的定理题。

由 n=1,n=2,n=3 一步步想，可以看出是一类很神奇的图形，学名是 n 维超立方体。

Lemma1：

将 n 维超立方体分成两部分，则连接两部分的边数不少于最少的那部分的点数。

\(|E_{middle}| \ge \min(|V_1|,|V_2|)\)

证明是有的，但是写完其他的再说，先咕掉。
Lemma2：

去掉 n 维超立方体中任意 \(k\) 个点，剩下的点最多形成一个点数大于 \(nk+1\) 的连通块。

\(\sum_{V_i \in V-V_k}\ [\ |V_i| > nk\ ] \le 1\)

可以用引理1证明：

假设把一个大于 \(nk\) 的这一部分拿出来，形成 \(|V_1|\ge nk+1,|V_2|\ge nk+1,|V'|\le 2^n-nk-1,|V_2|\in|V'|\)，则连接两部分的边至少有 \(nk+1\) 条。然而，每个点连接了 \(n\) 条边，删去 \(k\) 个只能删去 \(nk\) 个，所以任意两个 \(V_1\) 与 \(|V_2|\) 无法被分开，故不会有两个或更多。
由上述引理，可以有以下分析：
若 \(x,y\) 在同一个小于的连通块里，bfs 至多个点可以找到；若找完整个块没有找到说明不连通；若经过了超过 \(nk\) 个点未找到直接返回并记录，\(x,y\) 都属于这种状况可由引理 2 判断为连通。
用 stl 说是过不了，选择手写哈希，被 lhy 强烈谴责不如平板电视。

upd on 2023.09.25

引理 1 找到了两个证明：

比较复杂的一个，比较简洁的一个

简洁版是说，定义 \(x,y\) 的特殊路径为，顺次更改每一位，经过的路径，此处以从前往后为例。

经过某条边 \(u—v\) 的特殊路径有 \(2^{n-1}\) 条，证明如下。

【前半部分】【当前位置】【后半部分】

设路径 \(x,y\) 经过边 \(u—v\)，，当从 \(x\) 走到 \(u\) 时，仅更改了前半部分的点，即 \(x\) 在当前位置以及后半部分与 \(u\)，相同，是固定的；同理，\(y\) 的当前位置和前半部分也是固定的。即，只有 \(x\) 的前半部分与 \(y\) 的后半部分是任意的，相乘得到总共 \(2^{n-1}\) 对 \(x,y\)。

将 \(V\) 分成 \(S,T\) 两个无交集合,设 \(|S| \le |T|\)，则集合间的特殊路径有 \(|S|(2^n-|S|)\) 条，因此集合间的边数为 \(\dfrac{|S|(2^n-|S|)}{2^{n-1}} \ge \dfrac{|S|2^{n-1}}{2^{n-1}}=|S|\)。

复杂版留给读者。

实现：

注意哈希表要规范、正确。或者直接平板电视也可以。

LGP3547 [POI2013] CEN-Price List

题意：

给定一个 \(n\) 个点 \(m\) 条边的无向图，边权均为 \(a\)。

现在将原来图中满足最短路等于 \(2a\) 所有的点对 \((x,y)\) 之间加一条长度为 \(b\) 的无向边。

给定 \(k\)，求点 \(k\) 到所有点的最短路是多少。

分析：

感觉不难，没懂为啥评黑。

设 \(dis_a,dis_b\) 表示只走 \(a\) 路径或 \(b\) 路径的步数。

一共有三种走法：\(dis_a \times a ,\ \lfloor \dfrac{dis_a}{2}\rfloor \times b \ + dis_a \bmod 2 ,\ dis_b \times b\)

前两种直接 bfs 即可。

设 \(u\) 经 \(v\) 到 \(w\)，则由 bfs 的性质（类似 dijkstra，此处由于边权记 1 保证了 dij 的优先性质），不会存在 \(u'\) 经 \(v\) 到 \(w\) 而优于 \(u\)。因此每次若 \(w\) 不和 \(u\) 相连，即可更新 \(w\) 的 \(dis_b\)，并删去 \(v\) 到 \(w\) 的边（分两层，一层为基础，一层可删）。

对于所有的边：删去的只访问一遍，\(O(m)\)；不可删等价于三元环，每个三元环的每条边常数遍，而三元环是 \(m \sqrt m\) 级别，复杂度 \(O(m\sqrt m)\)，详见三元环计数。

另外，官方给出的复杂度证明为：

\(\sum_{v \in V}\min(deg(v)^2,m)\ \le \ \sum_{v \in V} \sqrt{deg(v)^2m} \ \le \ \sum_{v \in V}deg(v)\sqrt m = m \sqrt m\)

意思大概是，首先删去的边复杂度是 \(O(m)\) 级别。考虑三元环，对于枚举的中间点 \(v\)，分别有 \(vu,vw\) 数量相乘不超过 \(deg(v)^2\)，以及 \(uw\) 不超过 \(m\)，所以是两者取最小。

实现：

用 vector 存图会方便删除。

LGP3562 [POI2013] LAS-Laser

题意：

平面上有些线段，你最多从原点射出 \(k\) 条射线，穿过最多的线段，且使得每条线段最多被穿过 \(1\) 次。
求最多能穿过多少线段。

线段在第一象限。\(n \le 5\times 10^5,k\le 100\)。

分析：

有一个小性质，选端点一定不比选中间差。可以自己画一画。

所以想到，把二维中的线段处理到一维上，即按每个点到原点连线的斜率找出它的排名 \(pos\)，于是变成了一维选线段问题。记 \(cnt_i\) 表示第 \(i\) 个位置有几条线段，似乎可以 DP 了。

设 \(dp[i][j]\) 表示前 \(i\) 个端点里选了不超过 \(j\) 个端点的最大答案，发现若选择当前点，则前面的、被覆盖当前点的线段覆盖的点都不能选，因此对每个点，需要维护过该点的线段向左最多到哪，即 ”被经过当前点的线段覆盖的点“ 的最小坐标,记为 \(left_i\)。

于是 \(dp[i][j]=max(dp[i-1][j],dp[lft[i]-1][j-1]+cnt[i])\)。

发现空间开不下，于是把 \(j\) 的循环提到外层，\([0,1]\) 滚动即可。

实现：

for(int j=1;j<=k;j++)
{
    for(int i=1;i<=tot;i++)
    {
        if(lft[i]==inf)continue;
        dp[i][j&1]=max(dp[i-1][j&1],dp[lft[i]-1][(j-1)&1]+cnt[i]);
    }
}

update:

2023.09.23 初稿

2023.09.27 讲完，并更正了一些错误。