20251114

· · 个人记录

T1

第一遍读错题了，想了20min想出来了：数据结构优化矩阵快速幂。

写完发现读错题了，好消息是只需要修改转移矩阵。

然后我发现矩阵乘法不满足交换律！！

然后改成数据结构优化矩阵快速幂

然后就调过了。写+想总共用了2h+。（具体时间见md）

本来这题没什么问题的，但耗了我两个多小时，原因：

T2

转化为前缀和，差分约束秒了。

然后写了个漏洞百出的 spfa。

:::info[这是吐槽]{open}

这道题建出来的图点数为 5000 ，边数为 20000。时限 666ms。

所以spfa被卡常数了。应该得用bf。但是谁家正经人差分约束卡spfa啊。啊。啊。

题解区：

1.

if(这个点入队次数>3e3)有负环;

2.

if(总计出队次数>2e7)有负环;

3.

if(时间快超了)有负环;

4.

if(这个点松弛次数>n)有负环;
//应该为 2n+m

:::

T3

特殊性质 我的复杂度 最小的数据范围
链 O(n^3) n \le 10^3
t=0 O(n\times 2^{\frac{n(n-1)}{2}}) n \le 10^3
无特殊性质 O(n^2\times 2^{\frac{n(n-1)}{2}}) n \le 16

真的就是一个也做不了。

T4

亮点自寻。( n \le 20 )

int num[30];
for(...){
    for(...)
        if(...)...
        else{
            ...
            for(int j = b[i]+1;j<=2*n+1;j++)num[j]++;
        }
    ...
}

总结