AHOI2024初中组个人题解（T3 80%）

· · 题解

T1 家庭作业

科普一个冷知识：int和char在cin里是分开输入的
所以，代码直接cin>>a>>b>>c>>d>>e;(int a,c,e;char b,d)就可以拿到三个数字
再者，用sscanf也可以实现格式输入，本处不再赘述
对于String模拟，可以通过叠加数位的方法实现字符串提取数字，本处提供一种写法： 

string s;
cin>>s;
long long a = 0,b = 0,c = 0;//不记得范围了，开一下避免误导
int flag = 0;
for(auto i:s){
        if(i=='+'||i=='=')flag++;
      else{
                if(flag == 0){
                        a = a*10+(i-'0');
                }else if(flag == 1){
                        b = b*10+(i-'0');
                }else c = c*10+(i-'0');
        }
}
cout<<((a+b == c)?"Right!":"Wrong!");//如果使用sync加速则需要添加endl

T2 求和

争对本题，我们可以想简单一点，已知我们要求的是：

\sum\limits_{i=1}^n \lfloor \sqrt[3]{i} \rfloor

因为有着 \lfloor \sqrt[3]{i} \rfloor 的存在，不难看出，在区间1~7内的值都是1 我们这里提供两种方法：

1. 直接打表

估算可得

\because \sqrt[2]{10^{12}} = 10^6 \lt 10^7 \therefore \sqrt[3]{10^{12}} \lt 10^7

因此可以直接打表，打表程序此处忽略，设表 init 记录了从 1 到 \sqrt[3]{10^{12}} 内所有正整数,输入数字记作a

\because ANS = \sum\limits_{i=1}^n \lfloor \sqrt[3]{i} \rfloor \therefore ANS = \sum\limits_{j=2}^{size(init)} \begin{cases} (init[j]-init[j-1])*{(j-1)}^3 & init[j] <= a \\ (a-init[j-1]+1)*{(j-1)}^3 & init[j]>a \end{cases}

2. 循环结束

略去打表过程，直接开方
因为公式基本一样，略去

结束了么？

通过数据范围不难发现，会超时。
题目明确指出：x_i是不会低于x_{i-1}的，即设数组x，则x数组是不下降数组
故此，可以将循环的起始点设为 \lfloor \sqrt[3]{x_{i-1}} \rfloor ,需要注意的是在减去x_{i-1}时因为数列不包含x_{i-1}，故要减去1

T3 操作

本题解仅提供80分题解作为参考

读题，首先提出递归思路，可以得到约20分
介于递归时间太慢，我们不妨绘制一下递归树，会发现一台机器往往会启动很多遍，而每次所产生的价值是恒定的常量，所以可以记忆化出每个机器的价值二维数组，规定一维表示a_i的操作值，二维表示操作a_i的机器编号，可以得到：

members[N][N]

设机器C_i的类型为op_i,另外两值统称为{C_i}.a，{C_i}.b
由题可得：
当op_i == 1时

members[{C_i}.a][i]+={C_i}.b

当op_i == 2时
设dis[i]表示机器C_i是否被标记为已查询
设

\operatorname{f}(x) = \begin{cases} members[][x.id] & dis[x] = true \\ \operatorname{f}({x.a \to x.b})(dis[x] = true) & dis[x] = false \end{cases} 且保证 op_x == 2

调用 \operatorname{f}(x) 即可

得到members数组后，按照K的顺序调用就行了

介于空间和时间约束，本思路只能实现80%的数据

T4

此处只是一个猜测，不能作为正解

我们不能直接通过分段来计算答案，因为会有重复的部分存在
设 dp[i][j] 表示j在以i为开头的分段存在几种可能
先计算1，方便后面去重 去重后 \sum\limits_{i=1}^n dp[i][n] 为正解