挑战群论(group)
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
这是一道交互题。
在本地编译时,你需要包含 group.h
,同时需要和 grader.cpp
同时编译。
我们在交互库中包含一个名为 Data
类型的变量,我们还支持 Data
的乘法运算。假设 Data
所有元素构成的集合为 。则 构成含幺半群。具体的,对任意 :
- 。
- 。
需要注意,含幺半群不满足交换律。也就是我们不保证 。
你有一个半平面,对上面的每个整点都包含一个 。初始时 。
你需要维护两种操作:
你需要实现以下函数:
void update(int x,int dim,Data d1,Data d2);
对每个 执行操作:
若 且 ,则将 修改为 ;
若 且 ,则将 修改为 ;
若 且 ,则将 修改为 ;
若 且 ,则将 修改为 ;
Data query(int x,int y);
查询 ,返回值为答案。
你可以调用关于 Data
元素 的操作包括:
x.clr()
把 ;x=y
把 ;x*=y
把 。
你可以调用不超过 次乘法操作,其中如果 或 为 ,不计入操作总数当中。
需要注意的是在提交至 HFOJ 时候,你需要把代码复制到下面模板的指定位置:
struct Data{
unsigned short a,b,c,d;
void operator*=(const Data &x);
void clr();
};
void update(int x,int dim,Data d1,Data d2);
Data query(int x,int y);
// copy your code
你需要注释 #include"group.h"
的语段。
你可以在赛时询问 @liangzexian 是否编译成功。
我们下发了三个样例 。表示本地编译时可能的调试数据。
本题中,前 个测试点的操作数分别为 $10,10^3,10^4,2\times 10^4,4\times 10^4,6\times 10^4,8\times 10^4,10^5$。每次操作随机生成,每个测试点 分。
对最后 分,你需要通过由若干个 次操作组成的数据组,你需要通过所有数据才能得到 分。
对所有操作传入变量,保证为正整数,且不超过 。
NOIP 2024 模拟赛(五)hard
- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2024-8-14 8:00
- End at
- 2024-8-14 12:00
- Duration
- 4 hour(s)
- Host
- Partic.
- 29