题解 | 2024河北工业大学ICPC集训队夏季选拔赛

比赛链接-2024河北工业大学ICPC集训队夏季选拔赛

本场难度相对较高，赛时 K 题重测一次。

A 题签到题

名副其实签到题。

C/C++ 代码：

#include<stdio.h>
int main()
{
    int n;scanf("%d",&n);
    if(n<0)printf("negative");
    else printf("non-negative");
}

Python 代码：

print("negative"if int(input())<0 else"non-negative")

B 题瓷砖艺术

flood fill 遍历连通块的题目，dfs、bfs、并查集均可，不过要求遍历的同时记录数量。

一半及以上的颜色一定是颜色里的“众数”，反之不成立，一半及以上这个性质更强一些。所以也可以根据某个颜色出现次数最多，来判断它是主题颜色。

OI wiki dfs、OI wiki bfs、OI wiki 并查集。

此处给出 dfs 的实现。

C/C++ 代码：

#include<stdio.h>
#include<string.h>
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};//方向分量数组
int n,m;
char vis[500][500],mp[500][501];
//vis 记录数组是否被访问，mp 记录地图情况
//mp 第二维开 501 是因为使用字符串读入，末尾要保留一块 \0 的位置
int ans[128],rec[128];
void dfs(int x,int y)
{
    vis[x][y]=1;//记录是否被访问过，以免该格被重复访问
    rec[mp[x][y]]++;//记录情况
    for(int f=0;f<4;f++)
    {
        int xx=x+dx[f],yy=y+dy[f];
        if(0<=xx&&xx<n&&0<=yy&&yy<m&&!vis[xx][yy]&&mp[xx][yy]!='#')
            dfs(xx,yy);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%s",mp[i]);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)
        if(!vis[i][j]&&mp[i][j]!='#')//dfs 起点不能被访问过，也不能是 '#'
        {
            memset(rec+'a',0,sizeof(rec[0])*26);//'a'-'z'重置为 0
            dfs(i,j);cnt=0;
            for(char c='a';c<='z';c++)cnt+=rec[c];//连通块的总大小
            for(char c='a';c<='z';c++)
                if(rec[c]*2>=cnt)ans[c]++;
                //占用一半以上，注意该条件等价于 rec[c]>=cnt/2.0（浮点运算）
        }
    for(char c='a';c<='z';c++)
        if(ans[c])printf("%c %d\n",c,ans[c]);
    //从 'a' 到 'z' 输出结果
}

Python 代码：

import sys
sys.setrecursionlimit(10000000)
#设置递归上限，不设置的话默认 1000，dfs 会出异常，设置足够大的数即可
n,m=map(int,input().split())
mp=[input()for i in range(n)]#读入地图
vis=[[0]*m for i in range(n)]#记录是否访问过
#d=[0]*26
dx=[-1,0,1,0]#方向分量数组
dy=[0,1,0,-1]
def dfs(x,y):
    vis[x][y]=1#记录访问情况，避免再次被访问
    d[ord(mp[x][y])-97]+=1
    for f in range(4):
        xx=x+dx[f]
        yy=y+dy[f]
        if 0<=xx<n and 0<=yy<m and not vis[xx][yy] and mp[xx][yy]!='#':
            dfs(xx,yy)
rec=[0]*26
for i in range(n):
    for j in range(m):
        if not vis[i][j] and mp[i][j]!='#':
            #dfs 起点不能被访问过，也不能是 '#'
            d=[0]*26#重置记录数组
            dfs(i,j)
            cnt=sum(d)#连通块总数
            for k in range(26):
                if d[k]*2>=cnt:
                    rec[k]+=1
for i in range(26):
    if rec[i]:
        print(chr(i+97),rec[i])
#从 'a' 到 'z' 输出结果

C 题抓兔子（简单版）

状压+搜索，将每个兔子洞视为一个结点，地下通路视为边，将兔子可能存在的结点集视为一个状态，初始状态为全体结点。每次让 Ethan 行动，去掉状态中的一个结点，然后让兔子行动，兔子们能通过边访问到的结点集取并集（或运算），得到一个新状态，并搜索这个新状态，如果能够访问空集状态 $\varnothing$ ，也就是可以确信兔子都被 Ethan 抓到了。

状态集合可以用 01 串表示，一个 01 串表示全集中某个序号的元素包含在该集合，如果某位置上是 '1' 意味着对应结点存在于对应集合中，否则是 '0' 则不存在于对应集合中，该 01 串可以转化为一个数字，直观地理解为数字的二进制表示。

二进制数表示集合详见 OI wiki 二进制集合操作。

在常见假设下，下面的代码时间复杂度是 $\mathcal{O}(n^22^n)$ 的。

C/C++ 代码：

#include<stdio.h>
int n,edges[14][2];
int rabbit_round(int state)
{
    int newstate=0;
    for(int i=0;i<n-1;i++)
    {
        int u=edges[i][0],v=edges[i][1];
        //u v 直接相连
        if(state&1<<u)newstate|=1<<v;//u 的兔子跑到 v
        if(state&1<<v)newstate|=1<<u;//v 的兔子跑到 u
    }
    return newstate;
}
char vis[1<<15];
//state 被看成是一个二进制数，任意状态对应数字小于 2 的 15 次方
void dfs(int state)
{
    if(vis[state])return;vis[state]=1;
    for(int i=0;i<n;i++)if(state&1<<i)
    {
        //Ethan 处理掉了 i 号洞口的兔子，此时状态为 state^1<<i;
        //然后是兔子的回合，调用上面的函数 rabbit_round
        dfs(rabbit_round(state^1<<i));
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",edges[i]+0,edges[i]+1);
        edges[i][0]--,edges[i][1]--;
        //将结点编号减一，编号就落在 0~n-1 了
        //方便我们可以少开一半状态空间（当然也可以不这么处理）
    }
    dfs((1<<n)-1);//数 (1<<n)-1 前 n 位都是 1，代表全集状态
    if(vis[0])puts("Yes");//能访问到空集（对应为 0）意味着所有兔子都被处理了
    else puts("No");
}

Python 代码：

import sys
sys.setrecursionlimit(1000000)#开大递归上限，不开默认1000，很可能会寄
def rabbit_round(state):#兔子回合
    newstate=0
    for u,v in e:#u v 直接相连
        if state&1<<u:newstate|=1<<v#u 的兔子跑到 v
        if state&1<<v:newstate|=1<<u#v 的兔子跑到 u
    return newstate
def dfs(state):
    if vis[state]:return
    vis[state]=True
    for i in range(n):
        if state&1<<i:
            dfs(rabbit_round(state^1<<i))
            #Ethan 处理掉了 i 号洞口的兔子，此时状态为 state^1<<i;
            #然后是兔子的回合，调用上面的函数 rabbit_round
n=int(input())
e=[tuple(map(lambda x:int(x)-1,input().split()))for i in range(n-1)]
#读入边存成[(u1,v1),(u2,v2),...] 的形式，将结点编号减一，编号就落在 0~n-1 了，
#方便我们可以少开一半状态空间（当然也可以不这么处理）
vis=[False]*(1<<n)
#state 被看成是一个二进制数，任意状态对应数字小于 2 的 n 次方
dfs((1<<n)-1)#数 (1<<n)-1 前 n 位都是 1，代表全集状态
print('Yes' if vis[0] else "No")
#能访问到空集（对应为 0）意味着所有兔子都被处理了

D 题抓兔子（困难版）

结论题，C 题代码是对拍工具，要求你总结出来一个结论，思维量巨大、枚举数据时间花费很长。

Ethan 抓不到所有兔子当且仅当树形图中存在三阶三叉子（树）图，如图：

三阶三叉子（树）图

给树上结点依次染成黑色和白色，黑白相间，回合数为 $0$ 时，称在黑色结点上的兔子为“黑兔子”，白色结点上的兔子为“白兔子”，显然在偶数回合，“黑兔子”只在黑结点上，在奇数回合“黑兔子”只在白结点上；“白兔子”的情况恰好相反。可能地，黑兔子存在的结点如下图所示：

分奇偶处理

Ethan 采用最优策略能够确保抓到所有兔子当且仅当 Ethan 采用最优策略能够确保抓到所有“黑兔子”。因为能确保抓到全体“黑兔子”，就意味着能以同样的方式确保抓到全体“白兔子”，也就是说可以只考虑抓到“黑兔子”。

通过 C 题程序可以发现：如果存在三阶三叉子（树）图，这个图铁定不行。如果不存在三阶三叉子（树）图，意味着可以将整棵树的直径单独抽出来，在直径上的每个结点的边，要么连接直径上的点，要么连接一个深度至多为 $2$ 的非直径结点子树。如果一个直径结点连接一个深度为 $3$ 的非直径结点子树，意味着该点到直径两端的距离都大于等于 $3$ ，这样的话就可以找到一个三阶三叉子图了。所以“一个图包含三阶三叉子（树）图”与“一个图的直径结点上的边要么连接到一个直径结点，要么连接到一个深度至多为 $2$ 的非直径结点子树”是对立事件。

下证不含三阶三叉子（树）图具有可行的策略确保抓到“黑兔子”：

不妨设 $1,2,\cdots,m$ 依次是直径上的结点编号，编号相差为 $1$ 的直径结点是相连的，剩下的 $m+1,m+2,\cdots,n$ 是非直径上的结点编号，下面简称“非直径结点组成的子树”为“子树”。

初始时设置 $u=1$ ，循环执行以下过程直到结束：

①如果 $u>m$ ，结束（你过关！♪正在播放过关の小曲♪）；

②如果当前结点 $u$ 上可能有“黑兔子”，查看 $u$ ，“黑兔子”们走一步，由于“黑兔子”之间必然隔着至少一个空结点，所以下一步该结点不可能出现“黑兔子”，下次一定不会执行②操作；

③如果当前结点一定没有“黑兔子”，但是存在一个与 $u$ 相连的非直径结点 $v_0>m$ 上可能有“黑兔子”，那么查看 $v_0$ ，“黑兔子”们走一步， $v_0$ 是子树上深度为 $1$ 的结点，由于“黑兔子”之间必然隔着至少一个空结点，所以 $v_0$ 代表的子树深度为 $2$ 的结点也同样一定没有“黑兔子”，下次一定不会执行③操作，此时该子树一定不存在“黑兔子”了，同样由于其他“黑兔子”跳到该子树需要两步，必然经由直径结点 $u$ ，所以它一定会在结点 $u$ 上被查到，从而之后的操作中该子树上也不会出现“黑兔子”；

④如果当前结点 $u$ 上不可能有“黑兔子”，全体与 $u$ 直接相连的非直径结点 $v$ 上也不存在“黑兔子”，但是存在以 $v_0$ 为根的子树上可能有“黑兔子”，那么跳一步（查看 $u$ ），“黑兔子”们走一步，由于“黑兔子”之间必然隔着至少一个空结点，那只有可能是“黑兔子”们到了与 $u$ 相连的非直径结点上，此时 $u$ 上一定没有“黑兔子”，并执行③；

⑤如果当前结点 $u$ 上和全体与 $u$ 相连的子树都不可能存在“黑兔子”， $u$ 自增 $1$ ，即 $u\leftarrow u+1$ 。

操作②、④执行后只能跳到③、⑤，而③、⑤的执行次数必然是有限的：执行③的次数至多是与直径结点相连的全体子树个数，执行⑤的次数是 $m$ 次。从而有限步内可以结束该过程。

上面这种策略步数不是最少的，仅用作证明参考。

具体情况请见以下动态图：

兔子动图

关于判别的方法：

①抽出来全体直径结点，对每个直径结点，判断是否有一个深度为 $3$ （根结点深度为 $0$ ）的非直径结点组成的子树，如果存在一个深度为 $3$ 的子树，同样这个结点到直径两端的距离必然大于等于 $3$ ，这样图中就存在三阶三叉子（树）图，否则不存在。这一过程中可以保证所有结点被访问个位数次。

②找到直径一个端点，从这个端点为根结点开始处理记录树上结点信息，需要处理当前结点 $u$ 到根结点距离 root_dis 和以当前结点 $u$ 为根的子树深度 depth，对于全体结点 $u$ 的全体子结点 $v$ ，记 $\mathrm{cnt}[u]=[\mathrm{root\_dis}[u]\geqslant 3]+\sum\limits_{v}[\mathrm{depth}[v]\geqslant 3]$ ，如果存在 $u_0$ 使得 $\mathrm{cnt}[u_0]\geqslant 3$ ，这样图中就存在三阶三叉子（树）图，否则不存在。这一过程中可以保证所有结点被访问个位数次。

C/C++ 代码：

#include<stdio.h>
int head[400000],to[400000],next[400000],gt;//graph top
void add(int u,int v)
{
    ++gt;next[gt]=head[u],head[u]=gt,to[gt]=v;
    ++gt;next[gt]=head[v],head[v]=gt,to[gt]=u;
}
int maxdepth,deepest_node;
int depth[200001],father[200001];
void dfs(int u,int fa)
{
    father[u]=fa;
    depth[u]=depth[fa]+1;
    if(depth[u]>maxdepth)maxdepth=depth[u],deepest_node=u;
    for(int i=head[u];i;i=next[i])if(to[i]!=fa)dfs(to[i],u);
}
void rooted_tree(int root,int fa)
{
    maxdepth=0,depth[fa]=0;
    dfs(root,fa);
}
char on_diameter[200001];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
    }
    rooted_tree(1,0);
    rooted_tree(deepest_node,0);
    for(int u=deepest_node;u;u=father[u])
    {
        on_diameter[u]=on_diameter[father[u]]=1;
        for(int i=head[u];i;i=next[i])
        {
            int v=to[i];
            if(on_diameter[to[i]])continue;
            rooted_tree(v,u);
            if(maxdepth>=3)return puts("No"),0;
        }
    }
    puts("Yes");
}

Python 代码（pypy3 段错误。这似乎是牛客的设置问题？牛客的 Cpython3 版本也有点落后了）：

import sys
sys.setrecursionlimit(1000000)
n=int(input())
e=[[]for i in range(n+1)]
for i in range(n-1):
    u,v=map(int,input().split())
    e[u].append(v)
    e[v].append(u)
maxdepth=0;deepest_node=0
depth=[0]*(n+1);father=[0]*(n+1)
def dfs(u,fa):
    global maxdepth,deepest_node
    father[u]=fa
    depth[u]=depth[fa]+1
    if depth[u]>maxdepth:maxdepth=depth[u];deepest_node=u
    for v in e[u]:
        if v!=fa:
            dfs(v,u)
def rooted_tree(root,fa):
    global maxdepth
    maxdepth=0;depth[fa]=0
    dfs(root,fa)
rooted_tree(1,0)
rooted_tree(deepest_node,0)
on_diameter=[False]*(n+1)
u=deepest_node
while u:
    on_diameter[u]=on_diameter[father[u]]=True
    for v in e[u]:
        if not on_diameter[v]:
            rooted_tree(v,u)
            if maxdepth>=3:
                print("No")
                exit(0)
    u=father[u]
print("Yes")

E 题太阳能路灯

模拟题，不做过多解释。

C/C++ 代码：

#include<stdio.h>
int main()
{
    int n,t,r,x=0,ans=0;scanf("%d%d%d",&n,&t,&r);
    for(int i=1;i<=n;i++)
    {
        int c;scanf("%d",&c);
        x+=c;
        if(x>t)x=t;
        x-=r;
        if(x<0)x=0,ans++;
    }
    printf("%d",ans);
}

Python 代码：

n,t,r=map(int,input().split())
now=0;ans=0
for c in map(int,input().split()):
    now=min(now+c,t)
    if now<r:ans+=1;now=0
    else:now-=r
print(ans)

F 题循环移位

本题的设想是一道数据结构模板题。std 代码写的是 01 trie 树，不需要找太多规律，而且这个规律也不太好搞，导致本题数据不好造，数据其实偏弱。

你都来写这道题了，想必 $L(x)$ 和 $R(x)$ 的实现难不倒你吧，不懂的话看下面的实现即可。

记 $\bigoplus\limits_{k=1}^nx_k=X$ ，那么根据异或的性质，可知解就是 $\max\limits_{i\neq j}\{X\oplus x_i\oplus L(x_i)\oplus x_j\oplus R(x_j)\}$ 。

记 $l_k=x_k \oplus L(x_k),r_k=x_k \oplus R(x_k)$ ，解就简化为了 $\max\limits_{i\neq j}\{X\oplus l_i\oplus r_j\}$ ，一个方案就是枚举 $X\oplus l_i$ 的值找使得答案最大的 $r_j$ 。

std 的方法为：

01 trie 树需要的实现：add(x) 添加一个数 $x$ ，minus(x) 删去一个数 $x$ ，max_xor(x) 从一堆数中找到一个 $y$ 使得 $x\oplus y$ 最大。

初始时 01 trie 中有全体 $r_k$ ，枚举 $i=1,2,\cdots,n$ ，

删掉 $r_i$ ；
求 01 trie 中的一个 $r_j$ ，让它与 $X\oplus x_i$ 异或的答案最大化；
加入 $r_i$ 。

这些过程中求出的全体答案取最大即可。

也可以转化为 $\max\{\max\limits_{i<j}\{X\oplus l_i\oplus r_j\},\max\limits_{i>j}\{X\oplus l_i\oplus r_j\}\}$ ，跑两遍 01 trie 或者干脆建两个 01 trie，这样还省去了删除操作。

C/C++ 代码（__builtin_clz 函数可见于OI wiki 内建函数）：

#include<stdio.h>
#define lg(xx) (31-__builtin_clz(xx))
//在 C++ algorithm 中有一个非标准函数 std::__lg 就是这条宏定义内容，
//虽然是非标准函数，但往往都可以用
int L(int x){return(x^1<<lg(x))<<1|1;}
int R(int x){return x>>1|(x&1)<<lg(x);}
int son[32*200000][2],size[32*200000],_n;
void insert(int u,const int v)//加入、删除操作二合一
{
    int now=0;
    for(int i=29;i>=0;i--)
    {
        char f=!!(u&1<<i);
        if(!son[now][f])son[now][f]=++_n;
        now=son[now][f];
        size[now]+=v;
    }
}
int max_xor(int x)
{
    int now=0,res=0;
    for(int i=29;i>=0;i--)
    {
        char f=x>>i&1;//f 是当前 bit
        if(size[son[now][!f]])now=son[now][!f],res+=1<<i;
        //尽量往 bit 相反的方向走，往反方向走才有贡献
        //由于 bit 是从大到小枚举的，所以可以优先保证位次更高的 bit 产生贡献
        //而某个位次上的 bit 比它所有低位次加起来都大，
        //例如：8=(1000)>(0111)=7，所以这样操作是最优的
        else now=son[now][f];//反方向没有值，所以只能往同方向上走
    }
    return res;
}
int main()
{
    int x=0,n,ans=0;scanf("%d",&n);
    int l[200000],r[200000];
    for(int i=0,a;i<n;i++)
    {
        scanf("%d",&a);
        x^=a;l[i]=a^L(a);r[i]=a^R(a);
        insert(r[i],1);
    }
    for(int i=0;i<n;i++)
    {
        insert(r[i],-1);
        int res=max_xor(x^l[i]);
        ans=ans>res?ans:res;
        insert(r[i],1);
    }
    printf("%d",ans);
}

Python 代码（然而赛后提交 PyPy3 并没有跑过去，2024年10月30日测试发现可以过了）：

def lg(x):return x.bit_length()-1
# Python 没有__builtin_clz，但可以使用 bit_length()
def L(x):return (x^(1<<lg(x)))<<1|1
def R(x):return x>>1|(x&1)<<lg(x)
son=[[0,0]]
size=[0]
def insert(x,v):
    now=0
    for i in range(29,-1,-1):
        f=(x>>i)&1#f 是当前 bit
        if not son[now][f]:
            son[now][f]=len(size)
            size.append(0)
            son.append([0,0])
        now=son[now][f]
        size[now]+=v

def max_xor(x):
    now=0;res=0
    for i in range(29,-1,-1):
        f=(x>>i)&1
        if size[son[now][1-f]]:#尽量往 bit 相反的方向走
            now=son[now][1-f]
            res+=1<<i
            #尽量往 bit 相反的方向走，往反方向走才有贡献
            #由于 bit 是从大到小枚举的，所以可以优先保证位次更高的 bit 产生贡献
            #而某个位次上的 bit 比它所有低位次加起来都大，
            #例如：8=(1000)>(0111)=7，所以这样操作是最优的
        else:
            now=son[now][f]
            #反方向没有值，所以只能往同方向上走
    return res

n=int(input())
l=[0]*n;r=[0]*n
X=0;ans=0
x=list(map(int,input().split()))
for i in range(n):
    X^=x[i]
    l[i]=x[i]^L(x[i])
    r[i]=x[i]^R(x[i])
    insert(r[i],1)
for i in range(n):
    insert(r[i],-1)
    ans=max(ans,max_xor(X^l[i]))
    insert(r[i],1)
print(ans)

G 题转动齿轮

题目中没有暗示转不起来的情况，实际上也不存在这样的情况，若 $i+j$ 是奇数，那么让 $i$ 行 $j$ 列的齿轮逆时针转（如果存在的话）；若 $i+j$ 为偶数，那么让 $i$ 行 $j$ 列齿轮顺时针转（如果存在的话），这样不管怎么放齿轮都不会有转不起来的情况。（仔细观察题目中的动态图，你会感觉到这个图其实略带卡顿。）

总结方案数就是 $2^{n\times m}=(2^n)^m$ ，（小心爆 long long）记得写成 bpow(bpow(2,n,998244353),m,998244353)，其中 bpow(a,b,m) 可以是二进制取幂方法，表示 $a^b\bmod m$ 的结果。

话题：洛谷云剪切板谈“快速幂”这一名称

当然你也可以使用费马小定理/欧拉定理/扩展欧拉定理来处理 $2^{n\times m}\bmod 998244353$ ，记 $p=998244353$ （ $p$ 是质数），有 $2^{n\times m}\bmod p=2^{n\times m\bmod(p-1)}\bmod p=2^{[n\bmod(p-1)]\times[m\bmod(p-1)]\bmod(p-1)}\bmod p.$

C/C++ 代码：

#include<stdio.h>
#define ll long long
ll mod=998244353;
ll bpow(ll a,ll b)
{
    ll ans=1;a%=mod;
    for(;b;a=a*a%mod,b>>=1)
        if(b&1)ans=ans*a%mod;
    return ans;
}
int main()
{
    ll n,m;scanf("%lld%lld",&n,&m);
    printf("%lld",bpow(bpow(2,n),m));
}

Python 代码：

mod=998244353
n,m=map(int,input().split())
print(pow(pow(2,n,mod),m,mod))

H 题飘雪

字符处理+二维数组题，旋转地图 $180^\circ$ 的方法是倒序枚举每一行的字符串，对每一行倒序枚举每一列的字符。

C/C++ 代码：

#include<stdio.h>
char mp[101][102];
int main()
{
    int n,m;char c;scanf("%d%d %c",&n,&m,&c);
    for(int i=1;i<=n;i++)scanf("%s",&mp[i][1]);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
        mp[i][j]=9-(mp[i][j]-'0')+'0';
    if(c=='N')
    {
        for(int i=1;i<=n;i++,putchar(10))
            for(int j=1;j<=m;j++)putchar(mp[i][j]);
    }
    else if(c=='S')
    {
        for(int i=n;i>=1;i--,putchar(10))
            for(int j=m;j>=1;j--)putchar(mp[i][j]);
    }
}

Python 代码：

n,m,f=input().split()
n=int(n);m=int(m)
l=[list(input()) for i in range(n)]
for i in range(n):
    for j in range(m):
        l[i][j]=str(9-int(l[i][j]))
if f=='S':
    for i in range(n):
        l[i].reverse()
    l.reverse()
print(*list(map(lambda x:''.join(x),l)),sep='\n')

I 题等分半圆

题目绘图的 Desmos 记录链接

如果你是高中生，应该能够求出来分割的图形的面积，但如果你是大学生并且忘掉了一切，并且你不会使用格林公式熟练算面积的话，不好意思，你可能寄了。不过方法有很多，各显神通吧。

让我忘掉一切吧

std 的写法是搞出来一个面积和某个角度的函数，易知累积部分面积和是 $\dfrac{k}{n}\dfrac{\mathrm{\pi}}{2},k=1,2,\cdots,n$ ，根据累积部分面积和二分这个函数找到对应的角度，求出来对应点即可。

该图的 Desmos 记录链接

设左下角有一个 $\theta$ ， ${\color{orange}{橙色}}+{\color{orangered}{橙红色}}$ 就是分割出的面积，该面积由一个三角形面积和一个扇形面积组成。根据圆心角是圆周角两倍可得圆心角是 $2\theta$ ，再根据正余弦函数定义可知三角形半侧底边长 $\cos\theta$ ，高 $\sin\theta$ 。

三角形面积可以用 $\dfrac{\text{底}\times\text{高}}{2}$ 得出，底是 $2\times 1\times\cos\theta$ ，高是 $1\times\sin\theta$ ，面积为 $\sin\theta\cos\theta=\dfrac{\sin 2\theta}{2}$ 。

扇形面积可以用 $\dfrac{半径²\times 弧度}{2}$ 得出，即面积为 $2\theta/2=\theta$ 。

因此得到了等分线以下面积 $S$ 关于 $\theta$ 的函数式 $S=\dfrac{\sin 2\theta}{2}+\theta$ ，对应等分点坐标为 $(\cos 2\theta,\sin 2\theta)$ 。

（也可以设圆心角为 $\theta$ ，然后得出 $S=\dfrac{\sin\theta+\theta}{2}$ ，对应等分点坐标为 $(\cos\theta,\sin \theta)$ ）

我们知道所需求出的单个等分面积为 $\dfrac{1}{n}\times\dfrac{\mathrm{\pi}}{2}$ ，将这些面积按逆时针累加起来得到 $\dfrac{k}{n}\times\dfrac{\mathrm{\pi}}{2}(k=1,2,\cdots,n)$ ，这就是对应等分线下方的面积，据此只需要找出满足 $S=\dfrac{k}{n}\times\dfrac{\mathrm{\pi}}{2}$ 的 $\theta$ 即可，由于 $S$ 是 $\theta$ 的单调函数，所以可以用二分。实际上精度要求只有 $10^{-6}$ ，直接逐差 $\mathrm{\Delta}\theta=10^{-7}$ 枚举 $\theta$ 在时间上也是过得去的。

注意：两个函数 $S$ 在常用迭代法看来都是有些 病态的，所以尽量不要用牛顿法等等常用高阶迭代法来近似这两个函数的逆。

下面取 $S=\dfrac{\sin 2\theta}{2}+\theta$ 给出二分代码：

C/C++ 代码：

#include<stdio.h>
#include<math.h>
double S(double theta){return sin(2*theta)/2+theta;}//(sin 2θ)/2+θ
const double pi=3.1415926535897932384626;
double invS(double area)
{
    double l=0,r=pi/2;
    while(r-l>1e-10)
    {
        double mid=(l+r)/2;
        if(S(mid)<area)l=mid;
        else r=mid;
    }
    return (l+r)/2;
}
int main()
{
    int n;scanf("%d",&n);
    for(int k=1;k<n;k++)
    {
        double theta=invS(pi/2*k/n);
        printf("%7lf %7lf\n",cos(2*theta),sin(2*theta));
    }
}

Python 代码：

import math
n=int(input())
def S(theta):
    return math.sin(2*theta)/2+theta#(sin 2θ)/2+θ
def invS(area):
    l=0;r=math.pi/2
    while r-l>1e-10:
        mid=(l+r)/2
        if S(mid)<area:l=mid
        else:r=mid
    return (l+r)/2
for k in range(1,n):
    theta=invS(k/n*math.pi/2)
    print(math.cos(2*theta),math.sin(2*theta))

J 题大炮运输

很典型的 dp 形式，观察到大炮每次射程不会很大，姑且枚举转移点的时候只枚举前面 $500$ 个，你发现你过了，这个正确性是可以证明的。

设 $\mathrm{dp}[i]$ 表示从 $0$ 号大炮到 $i$ 号大炮的总最小成本，那么有 $\mathrm{dp}[i]=\min\limits_{0\leqslant j<i}\{\mathrm{dp}[j]+a[j](i-j)^3+b[j]\}.$

我们考虑从 $j$ 转移到 $i$ ，如果每次都跳一步的话需要的成本为 $\sum\limits_{k=j}^{i-1}a[k]+b[k]$ ，我们知道 $\sum\limits_{k=j}^{i-1}a[k]+b[k]\leqslant(i-j)(10^5+10^5)$ 而大炮一次从 $j$ 射到 $i$ 需要的成本为 $a[j](i-j)^3+b[j],$ 于是得到 $\sum\limits_{k=j}^{i-1}a[k]+b[k]\leqslant 200000(i-j){\color{blue}\leqslant}(i-j)^3\leqslant a[j](i-j)^3+b[j],$

由 ${\color{blue}\leqslant}$ 两边不等式解得 $i-j\geqslant\sqrt{200000}\approx 447.2136$ ，那么任何 $i-j\geqslant 448$ 的单次转移肯定不如每次都跳一步成本更低，所以只需要枚举前 $448$ 就足够了。

事实上这个 $448$ 还不是最极限的固定转移决策点差的上界。

我们考虑再设一个中间点 $m$ ，让 $j$ 先转移到 $m$ 再单步跳到 $i$ ，也就是 $j\to m\to m+1\to\cdots\to i$ ，这样成本就有 $a[j](m-j)^3+b[j]+\sum\limits_{k=m}^{i-1}a[k]+b[k]\leqslant a[j](m-j)^3+b[j]+200000(i-m)$ 让这种策略比从 $i$ 直接跳到 $j$ 成本更低一些，即取最小的 $i-j$ 使得下面不等式成立 $a[j](m-j)^3+b[j]+200000(i-m)\leqslant a[j](i-j)^3+b[j]$ 记 $t=a[j],y=i-j,x=m-j$ 转化为一个最优化问题：最小化 $y$ ，满足存在 $0\leqslant x\leqslant y$ 使得 $tx^3-200000x\leqslant ty^3-200000y$ 对 $\forall 1\leqslant t\leqslant 100000$ 成立。

该问题的严谨求解非常复杂，就直接上计算器求得其最优解为 $y=\sqrt{\frac{200000}{3}}\approx 258.199$ ，在数值上等于 $\dfrac{\mathrm{d}}{\mathrm{d}x}(x^3-200000x)=0$ 的正数解 $x$ 。

这意味着对于任意单次跳 $259$ 格以上的转移，都存在另一个转移比它更优，所以不需要枚举到 $259$ 及以上跨度的转移点，而取 $257$ 在题目数据中都有反例，所以 $258$ 是固定上确界，减一会出错，加一会多余。

C/C++ 代码：

#include<stdio.h>
#include<string.h>
long long dp[100003];
int a[100003],b[100003];
int main()
{
    int n;scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d%d",a+i,b+i);
    memset(dp,0x3f,sizeof dp);dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i-500;j<=i;j++)if(j>=0)
        {
            long long d=i-j,res=d*d*d;
            res=dp[j]+a[j]*res+b[j];
            dp[i]=dp[i]<res?dp[i]:res;
        }
    }
    printf("%lld",dp[n]);
    return 0;
}

Python 代码：

n=int(input())
a=[0]*n;b=[0]*n
for i in range(n):a[i],b[i]=map(int,input().split())
dp=[int(1e18)]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(1,min(i+1,500)):
        dp[i]=min(dp[i],dp[i-j]+a[i-j]*j**3+b[i-j])
print(dp[n])

K 题相遇

观察到函数 $f(n)$ 单调不减，而且存在一个上界和 $n$ 成线性关系，所以可以大胆二分，不用整一些奇葩的性质，赛时卡掉了一些这种代码。

$f(n)=\begin{cases}0,\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad n=0,1,2\\f\bigl((n-1)-2^{\left\lfloor\log_2(n-1)\right\rfloor}\bigr)+2^{\left\lfloor\log_2(n-1)\right\rfloor-1},\quad n\geqslant 3\end{cases}$

如何理解 $f(n)$ ？

一种三消合成类游戏规则如下：

$3$ 个物品可以合成一个更高级的物品；
合成时有一些限制，或者其他更优策略，促使玩家进行思考。

对于 $f(n)$ 而言规则是这样的：

你有 $n$ 个次级物品，你每次可以选 $2^k+1(k=1,2,\cdots)$ 个次级物品，合成 $2^{k-1}$ 个高级物品，也就是每次合成需要凭空消耗一个次级物品，剩下的需要合成的次级物品二合一，转化为高级物品，例如： $3$ 合 $1$ ， $5$ 合 $2$ ， $9$ 合 $4$ ， $17$ 合 $8$ ……；
你需要最大化合成的高级物品。

$f(n)$ 就是最优解，显然就是每次让 $k$ 最大，用 $2^k+1$ 个次级物品，合成 $2^{k-1}$ 个物品，然后用剩下的次级物品递归这样的过程。

依次来理解 $f(n)$ 的性质：

（非严格）单调性，增加次级物品数量，最多能生成的高级物品数量肯定不会减少；
线性下界，每次都选择 $3$ 合 $1$ 得到的结果肯定不会超过最优解，即 $\left\lfloor\dfrac{n}{3}\right\rfloor\leqslant f(n)$ ， $\dfrac{f(n)}{n}$ 最小值为 $\dfrac{1}{4}$ （ $f(4)=1$ ）。

这意味着，使得 $f(m)=x$ 的 $x$ 最大不会超过 $4m$ ，于是整数二分即可，如果再细致地考量一下，可以得出取上界 $3m$ 也是完全正确的。

洛谷专栏文章整数二分的两个关键点

C/C++ 代码：

#include<stdio.h>
long long g(long long n)
{//It needs n>=3.
    n--;
    int res=0;
    while(n!=1)res++,n/=2;
    return 1ll<<res;
}
long long f(long long n)
{
    if(n<=2)return 0;
    return f(n-g(n)-1)+g(n)/2;
}
int main()
{
    long long x;scanf("%lld",&x);
    long long l=1,r=4*x;
    while(l<r)
    {
        long long mid=(l+r)/2;
        if(x<=f(mid))r=mid;
        else l=mid+1;
    }//找到第一个 x<=f(m) 的值 m，然后判断这个 f(m) 是否等于 x
    puts(f(l)==x?"Yes":"No");
    return 0;
}

Python 代码：

def g(n:int):
    #It needs n>=3.
    n-=1
    res=0
    while n!=1:res+=1;n>>=1
    return 1<<res
def f(n:int):
    if n<=2:return 0
    return f(n-g(n)-1)+g(n)//2
x=int(input())
l=1;r=int(1e15)
while l<r:
    mid=(l+r)//2
    if f(mid)>=x:r=mid
    else:l=mid+1
#找到第一个 x<=f(m) 的值 m，然后判断这个 f(m) 是否等于 x
print("Yes" if f(l)==x else "No")

L 题第三方账号登录

综合图论题，把网站当成结点，第三方登录方式当成边，先把账号对应网站能访问到的边和结点处理出来，不能访问的可以扔掉不管，然后判断处理出来的边和结点是否构成环，有环输出 infinity，没有环就是 DAG 上 dp（严格地讲只是递推，不是 dp，不涉及优化的计数问题叫递推比较合适），还要区分边的种类，实际上对于有依赖的边，不需要考虑其终点，只需要考虑其起点。计数求和取余即可。

注意：必须根据手头账号把可能涉及到的边挑出来，如果环上就不会有账号，即便存在环也不能输出 infinity。

C/C++ 代码：

#include<stdio.h>
#include<string.h>
#define N 200003
#define mod 998244353;
int head[N],to[N],next[N],on[N];//链式前向星，on表示边是否会被启用
void add(int u,int v)
{
    static int gt=0;
    ++gt;next[gt]=head[u],head[u]=gt,to[gt]=v;
}
int f[N],ind[N],t_ind[N];
//ind 和 t_ind都是入度，t_ind 会在遍历过程中被修改，ind 则不会
char vis[N];
void dfs1(int u)
{
    if(vis[u])return;vis[u]=1;
    for(int i=head[u];i;i=next[i])
    {
        int v=to[i];on[i]=1;
        dfs1(v);
    }
}
void dfs2(int u)
{
    for(int i=head[u];i;i=next[i])if(on[i])
    {
        int v=to[i];
        f[v]=(f[u]+f[v])%mod;
        if(!--t_ind[v])dfs2(v);
    }
}
int expoint[N],_e=-1;//有依赖边的起点，即需要额外统计计数结果的点
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    while(m--)
    {
        int u,v,t;scanf("%d%d%d",&u,&v,&t);
        if(t==0)add(u,v);
        else expoint[++_e]=u;
    }
    int k;scanf("%d",&k);
    while(k--)
    {
        int a;scanf("%d",&a);
        f[a]+=1;dfs1(a);
    }
    for(int u=1;u<=n;u++)
        for(int i=head[u];i;i=next[i])if(on[i])
        {
            int v=to[i];
            ind[v]++;//入度只记录启用的边
        }
    memcpy(t_ind,ind,sizeof(ind[0])*(n+1));//复制一下
    for(int u=1;u<=n;u++)if(!ind[u])dfs2(u);//跑 DAG 上 dp
    for(int u=1;u<=n;u++)if(t_ind[u])return puts("infinity"),0;
    //发现跑完一遍还有没有处理到的，那说明存在环
    int ans=0;
    for(int u=1;u<=n;u++)ans=(ans+f[u])%mod;
    for(int i=0;i<=_e;i++)ans=(ans+f[expoint[i]])%mod;
    printf("%d",ans);
}

Python 代码（提交 pypy3 不过，时间似乎给少了）：

import sys
sys.setrecursionlimit(10000000)
mod=998244353
n,m=map(int,input().split())
e=[[]for i in range(n+1)]
# e[u]=[[v,is_on],[v,is_on],...] is_on 表示边 <u,v> 是否会被使用到
expoint=[]# 有依赖边的起点，即需要额外统计计数结果的点
for i in range(m):
    u,v,t=map(int,input().split())
    if t==0:e[u].append([v,False])
    else:expoint.append(u)
f=[0]*(n+1)# 递推状态
k=int(input())
vis=[False]*(n+1)
def dfs1(u):
    if vis[u]:return
    vis[u]=True
    for i in range(len(e[u])):
        e[u][i][1]=True
        dfs1(e[u][i][0])
for i in map(int,input().split()):
    f[i]+=1
    dfs1(i)
ind=[0]*(n+1)
for u in range(1,n+1):
    for v,is_on in e[u]:
        if is_on:ind[v]+=1
t_ind=ind[:]#深拷贝
#ind 和 t_ind 都是入度，t_ind 会在遍历过程中被修改，ind 则不会
def dfs2(u):
    for v,is_on in e[u]:
        if is_on:
            f[v]=(f[u]+f[v])%mod
            t_ind[v]-=1
            if t_ind[v]==0:dfs2(v)
for u in range(1,n+1):
    if ind[u]==0:dfs2(u)
for u in range(1,n+1):
    if t_ind[u]!=0:
        print("infinity")
        exit(0)
ans=0
for u in range(1,n+1):ans=(ans+f[u])%mod
for u in expoint:ans=(ans+f[u])%mod
print(ans)

M 题精炼琥珀

背景很有意思，是一道比较真实的题目。推荐大家去尝试一下 Minecraft 2024 年毒马铃薯更新整活包！

std 写的是状压 dp，这个题很像网络流题，不知道有没有网络流解法。方法比较抽象，如果感觉不错的话能想出来。

将每种清晰度抽象为一层，将清晰度对应的杂质类型抽象为该层的结点，那么就得到了 $10$ 层图，图每层 $16$ 个结点，再外加一层，该层只有一个结点代表琥珀。将制箭台看成两层之间的有向边，就能得到下面这样的图。两个字母的是毒树脂，前一个字母是清晰度，后一个则是杂质类型，G 是琥珀宝石（Amber Gem）。 $\color{grey}{闲话：树脂和琥珀本质是一种东西，两者区别于价值，即是否成为了宝石 Gem，所以琥珀宝石记为 G。}$

样例示意图

设状态 $\mathrm{dp}[i][S_i]$ ，其中 $S_i$ 表示结点集，表示第 $i$ 层启用了结点状态集合为 $S_i$ ，回到题目中的意思，就是清晰度为 $i$ 的毒树脂只会是 $S_i$ 中的一种（杂质类型）。

容易想到让每层毒树脂的杂质类型逐层减少——至少让它不增加是最优的，而且对应的制箭台数量就等于该层出现的毒树脂的杂质类型数量。也就是让每层状态集合 $S_i$ 的大小逐渐减小，而且答案就是这些状态集合 $S_i$ 的大小 $|S_i|$ 之和（除去琥珀那层的状态集合大小）的最小值，整出来转移方程优化即可。

图的最左侧是初始结点，要求从左侧所有红色结点（所有 糟糕（Abysmal） 清晰度的毒树脂），从左到右经过中间的黑色层（中间清晰度的毒树脂）逐层通过中间边到达橙色结点（琥珀），求启用边的数量（制箭台的数量）。

符号说明：

$N_i$ 表示第 $i$ 层的全体结点的集合， $S_i$ 表示第 $i$ 层启用的结点集合，表示 $0$ 层中所有结点都存在路径到达 $S_i$ 中的一个结点；
$E_i$ 表示数据中从 $N_i$ 到 $N_{i+1}$ 的全体边组成的边集；
$S_1\overset{E}{\mapsto}S_2$ 表示 $\forall u\in S_1,\exists v_0\in S_2$ 使得 $\langle u,v\rangle\in E$ ，即 $S_1$ 中的结点通过边集 $E$ 都能到达一个 $S_2$ 中的结点；
$|\cdot|$ 表示边集中边的个数（ $|E|$ ），或者一层结点集中包含的结点数（ $|S|$ ）；
$f_{i+1}(S_{i+1})$ 表示全体 $S_{i+1}$ 中结点通过 $E_i$ 能够反向到达的全体 $N_i$ 中的结点集合，即 $f_{i+1}(S_{i+1})=\{u\mid u\in N_i,\exists v_0\in S_{i+1},\langle u,v_0\rangle\in E_i\}=\{u\mid\forall v\in S_{i+1},\langle u,v\rangle\in E_i\}$ ，可以发现 $S\subset f_{i+1}(S_{i+1})$ 当且仅当 $S\overset{E_i}{\mapsto}S_{i+1}$ ；
对于 $\min\{x\}$ 运算，如果没有满足 $\min$ 条件的 $x$ ，默认 $\min=+\infty$ 。

设 $\mathrm{dp}_0[i][S_i]$ 表示到第 $i$ 层启用结点集合为 $S_i$ 所需要的启用边的数量，初始状态有

$\mathrm{dp}_0[0][S_0]=\begin{cases} 0,&S_0=N_0\\ +\infty,&S_0\neq N_0 \end{cases}$

即要求初始状态包含所有 $0$ 层结点， $+\infty$ 表示不合要求，不合要求的状态值均为 $+\infty$ ，转移方程为

$\begin{aligned} &i=1,2,\cdots,10,\forall S_i\subset N_i,S_{i-1}\subset N_{i-1}\\ &\mathrm{dp}_0[i][S_i]=\min\limits_{S_{i-1}\overset{E}{\mapsto}S_i}\{\mathrm{dp}_0[i-1][S_{i-1}]+|E|\} \end{aligned}$

最终结果显然是 $\mathrm{dp}_0[10][N_{10}]$ ，表示所有初始结点到达最终结点需要启用的边最小数量。

这样一个转移方程求解颇费时间，我们考虑优化它。

①观察到：最优解转移的两层之间启用结点数不会随着层数增加而增加；

反证：对一个最优解启用的边集 $E=\bigcup\limits_{i=0}^{10}E_{0i}$ ，最优解启用的结点依次为 $S_0,S_1,\cdots,S_{10}$ ，且有 $S_i\overset{E_{0i}}\mapsto S_{i+1}$ 。假设存在 $j$ 使得 $|S_j|<|S_{j+1}|$ ，则可以对每个 $u\in S_j$ ，挑出 $E_{0j}$ 中唯一一条边 $\langle u,v\rangle$ 使得 $v\in S_{j+1},\langle u,v\rangle\in E_{0j}$ ，将挑出的全体边组成的集合记为 $E_{0j}'$ ，显然 $E_{0j}'\subset E_{0j}$ ，且 $|E_{0j}'|=|S_j|<|S_{j+1}|\leqslant|E_{0j}|$ ，那么在该层将 $E_{0j}$ 替换 $E_{0j}'$ 更优，即取 $E'=\left(\bigcup\limits_{i=0,i\neq j}^{10}E_{0i}\right)\cup E_{0j}'$ ，就有 $|E'|<|E|$ ，与 $E$ 是最优解的假设矛盾。

即证最优解逐层启用的结点集满足 $|S_i|\geqslant|S_{i+1}|(i=0,1,\cdots,9)$ 。

②如果逐层转移时结点数不增，即 $|S_{i-1}|\geqslant |S_i|$ ，且 $\exists E,S_{i-1}\overset{E}{\mapsto}S_i$ ，那类似 ① 中证明的那样，我们可以从 $E$ 中挑出一个子集 $E'$ 使得 $|E'|=|S_{i-1}|$ 和 $S_{i-1}\overset{E'}{\mapsto}S_i$ 成立。

③设 $\mathrm{dp}_1[i][S_i]$ 表示第 $i$ 层启用结点集合为 $S_i$ 且逐层启用结点数不增，所需要的启用边的数量，初始状态依然有

$\mathrm{dp}_1[0][S_0]=\begin{cases} 0,&S_0=N_0\\ +\infty,&S_0\neq N_0 \end{cases}$

转移方程为

$\begin{aligned} &i=1,2,\cdots,10,\forall S_i\subset N_i,S_{i-1}\subset N_{i-1}\\ &\mathrm{dp}_1[i][S_i]=\min\limits_{\begin{smallmatrix} S_{i-1}\overset{E}{\mapsto}S_i\\ |S_{i-1}|\geqslant|S_i| \end{smallmatrix}}\{\mathrm{dp}_1[i-1][S_{i-1}]+|E|\}\\ &\qquad\qquad=\min\limits_{\begin{smallmatrix} S_{i-1}\subset f_{i}(S_i)\\ |S_{i-1}|\geqslant|S_i| \end{smallmatrix}}\{\mathrm{dp}_1[i-1][S_{i-1}]+|S_{i-1}|\} \end{aligned}$

最终结果 $\mathrm{dp}_1[10][N_{10}]$ 表示所有初始结点到达最终结点，并保证每层启用的结点数逐层不增，启用边的最小数量，显然 $\mathrm{dp}_1[10][N_{10}]=\mathrm{dp}_0[10][N_{10}]$ 。

$\mathrm{dp}_1[i][S_i](i=1,2,\cdots,10)$ 还可以理解为第 $i$ 层启用结点集合为 $S_i$ 且逐层启用结点数不增，左侧 $j=0,1,\cdots,i-1$ 层启用的结点总数的最小值。

考虑继续优化它。

①注意到 $|S_{i-1}|\geqslant|S_i|$ 这个限制比较难以达成，而且似乎有些鸡肋，因为既然最优解一定是逐层递减的，那么即便不设这一限制，也不会有非逐层递减的解比逐层递减的解更优。不过不能想当然，我们证明一下。

设 $\mathrm{dp}_2[i][S_i]$ 表示第 $i$ 层启用结点集合为 $S_i$ ，左侧 $j=0,1,\cdots,i-1$ 层启用的结点总数的最小值，初始状态依然有

$\mathrm{dp}_2[0][S_0]=\begin{cases} 0,&S_0=N_0\\ +\infty,&S_0\neq N_0 \end{cases}$

转移方程为

$\begin{aligned} &i=1,2,\cdots,10,\forall S_i\subset N_i,S_{i-1}\subset N_{i-1}\\ &\mathrm{dp}_2[i][S_i]=\min\limits_{S_{i-1}\subset f_i(S_i)}\{\mathrm{dp}_2[i-1][S_{i-1}]+|S_{i-1}|\} \end{aligned}$

最终结果为 $\mathrm{dp}_2[10][N_{10}]$ 。下证： $\mathrm{dp}_1[10][N_{10}]=\mathrm{dp}_2[10][N_{10}]$ 。

证明：

设非逐层不增解启用的结点集为 $S_i\subset N_i,i=0,1,\cdots,10$ ，对应结点集为 $S_0,S_1,\cdots,S_{10}$ ，存在 $j$ 使得 $|S_{j-1}|<|S_{j}|$ 。同之前的证明那样，这意味着 $\exists E$ 使得 $S_{j-1}\overset{E}{\mapsto}S_j$ ，也就 $\exists E'$ 满足 $|E'|<|E|$ 和 $S_{j-1}\overset{E'}{\mapsto}S_j$ ，也存在 $S_{j}'$ 使得 $|S_{j-1}|\geqslant |S_{j}'|$ ，此时 $S_0,\cdots,S_{j}',\cdots,S_{10}$ ，也是一组可行解，此时 $\sum\limits_{i=0}^9|S_i|>\left(\sum\limits_{i=0,i\neq j}^9|S_i|\right)+|S_{j}'|$ ，从而如此转移计算的最优解必然不是非逐层不增解，从而 $\mathrm{dp}_1[10][N_{10}]=\mathrm{dp}_2[10][N_{10}]$ ，即 $\mathrm{dp}_2$ 的转移方式是正确的。

虽然 $\mathrm{dp}_2$ 转移方程已经足够简单，但是如果我们记层数（毒树脂清晰度等级数+1）为 $m$ ，每层结点数（杂质类型数）为 $n$ ，那么枚举子集去更新状态的操作数最差为 $\mathcal O(mn^23^n)$ 级别的，这显然也不行。

有限集合 $N$ 的幂集 $2^N$ （幂集是全体 $N$ 的子集组成的集合，设 $N$ 有 $n$ 个元素，因为其元素数为 $2^n$ ，故而此处 $N$ 的幂集被记为 $2^N$ ），包含关系 $\subset$ 是幂集 $2^N$ 的元素的一个偏序关系， $2^N$ 关于 $\subset$ 构成偏序集。

设 $g:2^N\mapsto\overline{\mathbb R}$ 已经给定， $h:2^N\mapsto\overline{\mathbb R}$ 为目标函数， $\overline{\mathbb R}=[-\infty,+\infty]$ 是广义实数集，考虑整体性优化 $h(T)=\min\limits_{S\subset T}\{g(S)+|S|\}$ 的计算效率。

将偏序集 $2^N$ 元素看做结点，把包含关系 $\subset$ 看成有向边，那么我们就得到了一个有向图 $G_0$ （ $G_0$ 不含自环以外的环），去掉 $G_0$ 中的自环得到有向无环图 $G$ ，给结点 $T$ 上附上初始点权 $v(T)=g(T)+|T|$ ，在 $G$ 中进行拓扑排序转移求解，转移方程为 $\forall S\subsetneqq T,v(T)=\min\{v(T),v(S)\}$ ，那转移最终结果是 $v(T)=h(T)$ 。

考虑进一步优化。将 $h(T)$ 写为 $h(T)=\min\limits_{S\subset T}\{g(S)+|S|-|T|\}+|T|$ ，并记 $u(T)=h(T)-|T|=\min\limits_{S\subset T}\{g(S)+|S|-|T|\}$ 。

若 $2^N$ 中有三个集合 $S_1\subsetneqq S_2\subsetneqq S_3$ ，则有

$\begin{aligned} u(S_3)&=\min\limits_{S\subset S_3}\{g(S)+|S|-|S_3|\}\\ &=\min\left\{\min\limits_{\begin{smallmatrix} S\subset S_3\\ S\not\subset S_2 \end{smallmatrix}}\{g(S)+|S|-|S_3|\},\min\limits_{S\subset S_2}\{g(S)+|S|-|S_3|\}\right\}\\ &=\min\left\{\min\limits_{\begin{smallmatrix} S\subset S_3\\ S\not\subset S_2 \end{smallmatrix}}\{g(S)+|S|-|S_3|\},\min\limits_{S\subset S_2}\{g(S)+|S|-|S_2|\}+|S_2|-|S_3|\right\}\\ &=\min\left\{\min\limits_{\begin{smallmatrix} S\subset S_3\\ S\not\subset S_2 \end{smallmatrix}}\{g(S)+|S|-|S_3|\},u(S_2)+|S_2|-|S_3|\right\} \end{aligned}$

可见 $u(S_3)$ 不需要直接由 $u(S_1)$ 转移而来。 $u(T)$ 只需要由满足 $\not\exists S_0$ 使得 $S\subsetneqq S_0\subsetneqq T$ 的 $S$ 上的点权 $u(S)$ 转移得来。

对于偏序集 $2^N$ ，只需要构造其 Hasse 图 $G_H$ ， $G_H$ 中结点依然代表偏序集 $2^N$ 中的元素，结点 $T$ 上附上初始点权 $v(T)=g(T)$ ，若 $\not\exists S_0$ 使得 $S\subsetneqq S_0\subsetneqq T$ ，则图 $G_H$ 中存在有向边 $\langle S,T\rangle$ 。可以证明，在图 $G_H$ 中，有向边 $\langle S,T\rangle$ 相连的两个结点对应的集合只差一个元素，并且 $|T|-|S|=1$ ，对应的转移方程为 $\forall S=T\backslash\{u\}(u\in T),v(T)=\min\{v(T),v(S)-1\}$ ，然后拓扑排序求解就能求出 $v(T)=u(T),\forall T\subset 2^N$ 。

注： $A\backslash B$ 表示差集 $\{x\mid x\in A,x\notin B\}$ 。

求出 $u(T)$ 后对应就能得到 $h(T)=u(T)+|T|$ 。这点可以应用到 $\mathrm{dp}_2$ 的求解中。

总结转移方程为：

初始状态

$\mathrm{dp}_2[0][S_0]=\begin{cases} 0,&S_0=N_0\\ +\infty,&S_0\neq N_0 \end{cases}$

转移方程为

$\begin{aligned} &i=1,2,\cdots,10,\forall S_i\subset N_i,S_{i-1}\subset N_{i-1},\\ &\mathrm{dp}_2[i][S_i]=\mathrm{dp}_3[i-1][f_i(S_i)]+|f_i(S_i)|\\ &\mathrm{dp}_3[i][S_i]=\min\limits_{\begin{smallmatrix} S\subset S_i\\ \not\exists S^*,S\subsetneqq S^*\subsetneqq S_i \end{smallmatrix}}\{\mathrm{dp}_2[i][S]-|S_i|+|S|\}\\ &\qquad\qquad=\min\left\{\mathrm{dp}_2[i][S_i],\min\limits_{u\in S_i}\bigl\{\mathrm{dp}_2[i][S_i\backslash\{u\}]-1\bigr\}\right\} \end{aligned}$

其中， $\{u\}$ 是只含元素 $u$ 的集合。进行交叉转移即可，这样更新状态的操作数可以优化到 $\mathcal O(mn2^n)$ 级别，足以通过本题。

C/C++ 代码：

#include<stdio.h>
#include<string.h>
int dp[10][1<<16],from[10][1<<16],final_from;
int popcount[1<<16],lg2[1<<16],f[1<<16];
int min(int a,int b){return a<b?a:b;}
int main()
{
    for(int s=1;s<1<<16;s++)popcount[s]=popcount[s^s&-s]+1;
    for(int i=0;i<16;i++)lg2[1<<i]=i;
    memset(dp,0x3f,sizeof dp);dp[0][(1<<16)-1]=0;
    //dp[0] 既是 dp2 的状态值也是 dp3 的状态值
    int n;scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        char s[4];scanf("%s",s);
        int ic=s[0]-'A',ii=s[1]-'A',oc=ic+1,oi=s[2]-'A';
        //i 是 input，o 是 output；c 是 clarity，i是 impurities
        //ic：输入清晰度 ii：输入杂质类型 oc：输出清晰度 oi：输出杂质类型
        if(ic!=9)from[oc][oi]|=1<<ii;
        else final_from|=1<<ii;
    }
    for(int i=1;i<10;i++)
    {
        for(int s=1;s<1<<16;s++)f[s]=f[s^s&-s]|from[i][lg2[s&-s]];
        for(int s=1;s<1<<16;s++)dp[i][s]=dp[i-1][f[s]]+popcount[f[s]];
        for(int s=1;s<1<<16;s++)for(int j=0;j<16;j++)if(s&1<<j)
            dp[i][s]=min(dp[i][s],dp[i][s^1<<j]-1);//处理出本层的 dp3
    }
    int ans=dp[9][final_from]+popcount[final_from];
    if(ans>0x33333333)puts("No");
    else printf("%d",ans);
    //运算过程中可能出现 +∞-1，而我们实现的+∞仅为足够大的有限值0x3f3f3f3f，
    //所以需要找一个略小于它的值 0x33333333 来测定结果是不是+∞
}

Python 代码（提交 pypy3）：

popcount=[0]*(1<<16)
for s in range(1,1<<16):popcount[s]=popcount[s^s&-s]+1;
lg2=[0]*(1<<16)
for i in range(1,16):lg2[1<<i]=i
dp=[[0x3f3f3f3f]*(1<<16)for _ in range(10)]
dp[0][(1 << 16)-1]=0
#dp[0] 既是 dp2 的状态值也是 dp3 的状态值
from_matrix=[[0]*16 for _ in range(10)]
final_from = 0

n = int(input())
for i in range(n):
    s=input()
    ic,ii,oc,oi=ord(s[0])-ord('A'),ord(s[1])-ord('A'),ord(s[0])-ord('A')+1,ord(s[2])-ord('A')
    #i 是 input，o 是 output；c 是 clarity，i是 impurities
    #ic：输入清晰度 ii：输入杂质类型 oc：输出清晰度 oi：输出杂质类型
    if ic!=9:from_matrix[oc][oi]|=1<<ii
    else:final_from|=1<<ii

for i in range(1,10):
    f =[0]*(1<<16)
    for s in range(1,1<<16):
        f[s]=f[s^s&-s]|from_matrix[i][lg2[s&-s]]
    for s in range(1,1<<16):
        dp[i][s]=dp[i-1][f[s]]+popcount[f[s]]
        for j in range(16):
            if s&(1<<j):
                dp[i][s]=min(dp[i][s],dp[i][s^(1<<j)]-1)

ans = dp[9][final_from]+popcount[final_from]
if ans>0x33333333:print("No")
else:print(ans)
#运算过程中可能出现 +∞-1，而我们实现的+∞仅为足够大的有限值0x3f3f3f3f，
#所以需要找一个略小于它的值 0x33333333 来测定结果是不是+∞

题解 | 2024河北工业大学ICPC集训队夏季选拔赛

A 题 签到题

B 题 瓷砖艺术

C 题 抓兔子（简单版）

D 题 抓兔子（困难版）

E 题 太阳能路灯

F 题 循环移位

G 题 转动齿轮

H 题 飘雪

I 题 等分半圆

J 题 大炮运输

K 题 相遇

L 题 第三方账号登录

M 题 精炼琥珀

A 题签到题

B 题瓷砖艺术

C 题抓兔子（简单版）

D 题抓兔子（困难版）

E 题太阳能路灯

F 题循环移位

G 题转动齿轮

H 题飘雪

I 题等分半圆

J 题大炮运输

K 题相遇

L 题第三方账号登录

M 题精炼琥珀