专栏文章

20251114

1123456ph
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min870ef
此快照首次捕获于
2025/12/01 22:09
3 个月前
此快照最后确认于
2025/12/01 22:09
3 个月前
查看原文

T1

第一遍读错题了，想了20min想出来了：数据结构优化矩阵快速幂。
写完发现读错题了，好消息是只需要修改转移矩阵。
然后我发现矩阵乘法不满足交换律！！
然后改成数据结构优化矩阵快速幂
然后就调过了。写+想总共用了2h+。（具体时间见md）
本来这题没什么问题的，但耗了我两个多小时，原因：
  • 我的转移矩阵是3个人中最复杂的。10×(4∗4)10 \times (4*4) 个数，每个数都得现推。
  • 我读错题了，需要修改转移矩阵，重新推 10×(4∗4)10 \times (4*4) 个数。工作量超大的。

T2

转化为前缀和，差分约束秒了。
然后写了个漏洞百出的 spfa。
  • cnt 在点出队的时候才统计，常数很大
  • cnt*=-1 与 cnt++ 的先后顺序错误。
这是吐槽
这道题建出来的图点数为 50005000 ，边数为 2000020000。时限 666ms。
所以spfa被卡常数了。应该得用bf。但是谁家正经人差分约束卡spfa啊。啊。啊。
题解区：
CPP
if(这个点入队次数>3e3)有负环;
CPP
if(总计出队次数>2e7)有负环;
CPP
if(时间快超了)有负环;
CPP
if(这个点松弛次数>n)有负环;
//应该为 2n+m

T3

特殊性质我的复杂度最小的数据范围
链O(n3)O(n^3)n≤103n \le 10^3
t=0O(n×2n(n−1)2)O(n\times 2^{\frac{n(n-1)}{2}})n≤103n \le 10^3
无特殊性质O(n2×2n(n−1)2)O(n^2\times 2^{\frac{n(n-1)}{2}})n≤16n \le 16
真的就是一个也做不了。

T4

亮点自寻。( n≤20n \le 20 )
CPP
int num[30];
for(...){
	for(...)
		if(...)...
		else{
			...
			for(int j = b[i]+1;j<=2*n+1;j++)num[j]++;
		}
	...
}

总结

  • 不要读错题，否则花费的时间将翻倍
  • 矩阵乘法不满足交换律
  • 去复习spfa
  • 数组要开够

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...