P8574 「DTOI-2」星之影
题目背景
闻是白极影，见时方立竿。
题目描述
白极影化为立竿之人莅临人间，带来了星之函数f(x)f(x)f(x)，它的值为最接近于x4\sqrt[4]x4x的整数$\$（即f(x)=⌊x4+12⌋f(x)=\left\lfloor\sqrt[4]x+\dfrac12\right\rfloorf(x)=⌊4x+21⌋；⌊u⌋\lfloor u\rfloor⌊u⌋为对uuu向下取整后的值）。
现有ttt个数字nnn，对于每个nnn，立竿人想知道∑i=1n1f(i)\sum\limits_{i=1}^n\dfrac1{f(i)}i=1∑nf(i)1的值是多少，请你告诉它吧。
因为立竿人很急，所以本题的ttt组询问强制在线，后一个询问需通过前一个询问的答案生成。
可用以下C++代码生成（其他语言同理；需包含<stdio.h>）：
typedeflonglongll;charbuf_ans[114];llnext_n(doublelast_ans=0,ll get_n=0){//last_ans<n<=1e18sprintf(buf_ans,"%.6f",last_ans);for(ll i=0,x=0;;i++){if(buf_ans[i]=='.')returnget_n^x;if(i&1)x*=10;elsex=x*10+(buf_ans[i]^48);}}该函数第一个参数为上一次询问的答案（第一次询问时该值为000，也就是说第一个数未经加密），第二个参数为这一次读入的被加密的数，函数返回解密后的nnn。
输入格式
第一行一个整数ttt，表示数据组数（询问次数）。
对于每组数据，仅一行一个整数表示加密后的nnn（第一个nnn未被加密）。
输出格式
每行输出一个六位小数，表示答案。
输入输出样例 #1
输入 #1
7 1 5 12 95 2040 1145141920209 1070909051输出 #1
1.000000 4.000000 6.500000 38.666667 403.857143 1475989956.412959 1.000000说明/提示
样例解释
样例#1 解密后各组询问分别是：
t1234567n14889202211451419198101 \def\r{\cr\hline} \def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{t}&1&2&3&4&5&6&7\r \textbf{n}&1&4&8&89&2022&1145141919810&1\r \end{array}tn112438489520226114514191981071
数据范围
本题采用捆绑测试。
Subtaskt=n≤Score110106221000106133100109154100010184055×105101830 \def\arraystretch{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & t= & n\le&\bm{\textbf{Score}} \cr\hline 1 & 10&10^6 & 2 \cr\hline 2&1000&10^6&13\cr\hline 3&100&10^9&15\cr\hline 4 &1000&10^{18}&40\cr\hline 5 &%\text{No Special Constraints} 5\times10^5&10^{18}& 30 \cr\hline \end{array}Subtask12345t=10100010010005×105n≤10610610910181018Score213154030
对于100%100\%100%的数据，10≤t≤5×10510 \le t \le 5\times10^510≤t≤5×105，1≤n≤10181 \le n \le 10^{18}1≤n≤1018。
计分规则
本题采用Special Judge\textbf{Special Judge}Special Judge，令你输出的答案为pans\text{pans}pans，标答答案为jans\text{jans}jans，如果∣pans−jans∣<jans×10−5\vert \text{pans}-\text{jans}\vert<\text{jans}\times10^{-5}∣pans−jans∣<jans×10−5那么该组数据通过，在一个测试点内只有所有ttt组数据通过该测试点才算通过。
注意后一个Subtask\text{Subtask}Subtask对前一个Subtask\text{Subtask}Subtask有依赖关系，即如果你没有在前一个Subtask\text{Subtask}Subtask拿到分，那么你即使通过后一个Subtask\text{Subtask}Subtask的所有测试点，你也无法拿到后面的分数。
C++实现
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongintt,n;signedmain(){cin>>t;while(t--){cin>>n;longdoubleans=0.0;intsum=0,cnt=0;while(true){cnt++;if(sum+4*cnt*cnt*cnt+cnt>n)break;ans+=4*cnt*cnt+1;sum+=4*cnt*cnt*cnt+cnt;}ans+=1.0*(n-sum)/cnt;cout<<fixed<<setprecision(6)<<ans<<endl;}return0;}在这里插入图片描述
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容