2026-10-18 20:38:36
发布于：浙江
题解
；print('题目描述
定义： 第五分块
这是一个数据结构问题。
给定整数 n,m ，以及长度 n 的序列 x
1
,…,x
n
和 y
1
,…,y
n
，共 m 次操作。
需要维护序列 s
1
,…,s
n
，初值为0。
每次操作给出 a,b,c,v 表示对 ax
i
+by
i
+c<0 的每个 i ，将 s
i
修改为 s
i
+v ，然后查询被修改的 s
i
的和。
要求 1≤n≤3×10
4
,1≤m≤1×10
5
,1≤x
i
,y
i
,a,b,c,v≤10
9
，所有数值为整数。
输入格式为依次输入 n,m,x
1
,y
1
,…,x
n
,y
n
，然后依次输入每个操作的 a,b,c,v。
输出格式为对每个操作依次输出一个整数表示答案。
定义： 01矩阵乘法
a,b,c 分别是 n
1
×n
2
,n
2
×n
3
,n
1
×n
3
规模的由 [0,1] 范围内的整数构成的矩阵，满足：
c
i,k
j=1
∑
n
2
a
i,j
b
j,k
。
a,b 矩阵中的元素在范围内独立均匀随机选取。
输入格式为依次输入 n
1
,n
2
,n
3
，然后依次输入 a 和 b 矩阵。
输出格式为输出 c 矩阵。
输入（输出）一个 A×B 规模的矩阵 v 时，需要对 i=1,…,A 依次输入（输出）v
i,1
,…,v
i,B
。
你需要解决的问题
你需要编写一个程序，这个程序的输入为空，输出是一个由 指令 构成的程序，这个程序用于求解 01矩阵乘法 （需要按输入格式读若干个整数，最后按输出格式写若干个整数），且可以调用一次对 第五分块 的求解（对应的指令是特殊函数调用3，需要先按输入格式写若干个整数表示问题描述，调用后按输出格式读若干个整数得到答案）和若干次读写整数（对应的指令是特殊函数调用1,2）。
下发的库 （std.cpp）可以简化生成指令的过程，你可以基于下发的库编写程序。
下发的 模拟器 （chk.cpp）可以执行由指令构成的程序，并给出得分。
模拟器的编译运行方式可以参考下发的 makefile 。
说明/提示
输入文件名： mode.in 输出文件名 mode.out
T4相关文件下载
评分方式
如果你的程序不能正常结束，或输出的指令格式错误，或输出行数超过 1024，或输出的一行中超过 1024 个字符，则不能得到任何分数。
输出的指令构成的程序格式正确时，模拟器将对输出的程序进行评测。
输出的程序将被执行 4 次，依次对应 n
1
=n
2
=n
3
=50,100,150,200 。如果某次执行出现运行时错误（例如），则本题得 0 分；否则每次执行如果输出了正确的答案并正常结束，则可以得到 25(min(1,max(0,2−
M
0
M
))⋅min(1,max(0,2−
T
0
T
))) 的分数。设每次执行的分数之和为 S ，则总分为不超过 S 的最大的 20 的倍数（即下取整到 0,20,40,60,80,100 之一）。
其中 M 为内存访问次数，T 为指令执行条数，在 指令和模拟器 一节定义。
M
0
=160000
T
0
=3000000
指令和模拟器
以下简单介绍评测用的模拟器支持的指令，更详细的指令行为可以查看模拟器的源代码。
内存模型和计算代价统计：
可以读写的内存被表示为由 int64_t 整数组成的数组 M ，大小为 2
24
，初值为 0；
指针 S 初始值为 M ，可能被 call 和 ret 指令修改；
指令的操作数表示为 M[S[<Int32>]] 或 S[<Int32>] ，用于读写内存；
指令不保存在 M 中，不能读写。
模拟器统计的计算代价包括 指令执行条数 和 内存访问次数。
一条指令（不包括 <Label>: ）被执行时， 指令执行条数增加 1 ，指令中出现的每个 M[S[<Int>]] 导致 内存访问次数增加 1 。
模拟器从第一条指令开始执行，执行 exit 后结束执行。
指令默认顺序执行，但对于指令说明中要求跳转的情况，执行完当前指令后调整到相应位置继续执行。
指令中需要用到以下语法元素：
语法元素 说明
<A> 可以是 M[S[<Int>]] 或 S[<Int>] ，表示指令中需要读写的数据的来源
<UOP> 可以是 - !
<BOP> 可以是 `+ - * / % ^ &
<Label> 64位有符号整数常数，十进制，表示可以跳转到的标签
<Int> 64位有符号整数常数，十进制
<Int32> 32位有符号整数常数，十进制
支持的指令如下（需要严格满足描述的语法格式，不允许出现空格等）：
指令 说明
<A>=<A> 赋值，读取右边的 <A> 写到左边的 <A>
<A>=<UOP><A> 一元运算，语义和c对 int64_t 的相应运算相同，运算结果写到左边的 <A>
<A>=<A><BOP><A> 二元运算，语义和c对 int64_t 的相应运算相同，运算结果写到左边的 <A>
<A>=<Int> 赋值为常数
<A>=&S[<Int>] 取地址，相当于计算 S-M+<Int> 保存到 <A>
if <A> goto <Label> 条件跳转，如果 <A> 非零则跳转到 <Label>
goto <Label> 无条件跳转到 <Label>
ret 跳转到 S[0] 保存的指令地址，将 S 修改为 M+S[1]
call <Label> <Int> 保存下一条指令的地址到 S[<Int>] ，保存 S-M 到 S[<Int>+1] ，将 S 修改为 S+<Int> ，跳转到 <Label>
exit 结束执行
ncall <Int> <A> 特殊函数调用，<Int> 表示特殊函数的类型，可能读写 <A>
<Label>: 标签，同个标签只能出现一次，不计入指令执行条数，用于表示跳转到的指令地址
特殊函数调用的规定：
<Int> <A> 说明
1 读的整数的地址 读一个整数
2 写的整数 写一个整数
3 占位 只能调用一次，功能在题目描述中指定
输入输出模型：
输入输出被保存在一个初始为空的由整数组成的队列中。
特殊函数 1 从队列开头中取出一个整数，作为读取的结果；
特殊函数 2 将待写的整数放到队列末尾；
特殊函数 3 按指定输入输出格式调用特殊函数 1,2 读写整数。
使用下发的库生成指令
为了方便地生成指令，你可以使用下发的基于宏定义的库作为你提交的源代码的一部分，编译运行后可以输出生成的指令到标准输出。
<Type> 可以为 Int 表示 int64_t，或者 Ptr<T> 表示类型 T 的指针，或者 Array<T,n> 表示类型 T 的大小 n 的数组。要求 T 是 <Type> 。
在表达式中， Int 之间可以使用二元运算符 + - * / % ^ & | << >> < <= > >= == != += -= *= /= %= ^= &= |= <<= >>= 和一元运算符 + - ! ，计算结果的表达式类型为 Int。
Ptr<T> 或 Array<T,n> 和 Int 之间可以使用二元运算符 + - ，计算结果的类型为 Ptr<T>。
Ptr<T> 或 Array<T,n> 可以使用一元运算符 * ，计算结果的类型为 T 。
表达式中可以出现数组访问运算符 <Expr>[<Expr>] ，要求左边为 Array<T,n> 或 Ptr<T> ，右边为 Int ，计算结果的类型为 T。
表达式中可以出现整数常量，可以被隐式转化为 Int 处理。
表达式中可以使用 () 改变运算符优先级。
表达式中可以出现类型转化 <Type>(<Expr>) ，仅限于 Array<T,n> 转为 Ptr<T> 或同个类型内的转化，以及 T 转为 Ptr<T> 表示c++中的 &。
表达式中可以出现赋值 <Expr>=<Expr> ，赋值时需要满足右侧类型能转化为左侧类型。
<Expr> 是表达式，只能包含整数或类型为某种 <Type> 的变量，变量的作用域规则和c++相同。
If(<Expr>) ... End 类似于c++中的if语句。
If(<Expr>) ... Else ... End 对应于c++中的if-else语句。
While(<Expr>) ... End 对应于c++中的while语句。
For(A,B,C) ... End 对应于c++中的for语句，其中 A,B,C为 <Expr> 。
Break; Continue; Return; 对应c++中相应的关键字。
<Expr>; 用于计算表达式，并处理表达式中可能出现的赋值。
<Type> x; 或 <Type> x=<Expr>; 用于在栈上定义变量。特别地，如果 <Expr> 的形式为 <Expr>[<Expr>] 或 <Expr> ，则 x 是右侧表达式的引用，而不是一个新的变量。
Func(name,args) ... End 用于定义无返回值的函数，args 为参数（可以为空，或包含形如 <Type> x; 的若干个定义），从第一个被定义的函数开始执行。函数定义不能嵌套，参数类型必须是 Int 或 Ptr<T>，语句必须出现在函数定义内。
Read(<Expr>); ，Write(<Expr>); ，Solve(); 分别表示特殊函数调用1,2,3。
未说明的用法可能能通过编译，但不一定能正确翻译为指令。
框架没有进行过多的优化，因此生成的指令可能有较高的指令执行条数。内存访问次数对应于形如 <Expr>[<Expr>] 或 *<Expr> 且类型不是数组的表达式的执行次数。')
这里空空如也
有帮助，赞一个