P9218 「TAOI-1」Apollo题目背景Execution.这题原来叫std::cout std::fixed std::setprecision(1) 6.5 \n;。[被当事人删掉的图片.jpg]【Upd 2023/04/15 21:42】添加了一组 Hack 数据位于 Subtask 2#13。现在所有赛时的50 \bm{50}50分提交理论上均只能获得30 \bm{30}30分。题目描述给出n nn个十进制小数a 1 … a n a_1 \dots a_na1…an。对于一个数a aa定义其精度f ( a ) f(a)f(a)表示最小的非负整数k kk使得10 k × a 10^k\times a10k×a为整数对于整数a aa定义f ( a ) 0 f(a) 0f(a)0。对于两个十进制小数a , b a, ba,b定义g ( a , b ) g(a, b)g(a,b)为对于所有数c ∈ [ min ( a , b ) , max ( a , b ) ] c \in [\min(a,b), \max(a,b)]c∈[min(a,b),max(a,b)]的f ( c ) f(c)f(c)的最小值。对于所有1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n你需要求出∑ j 1 n g ( a i , a j ) \sum\limits_{j1}^ng(a_i, a_j)j1∑ng(ai,aj)的值并输出。定义十进制小数是一个含有整数部分和小数部分的数其小数部分不为0 00。之所以描述得这么愚蠢是因为保证输入的每个数都有小数点但是好像无论什么写法都会有人提出不满真是抱歉了。所以还是得看看被当事人删掉的图片。所以我在这里写闲话有人看得到吗。输入格式第一行一个整数n nn。接下来n nn行每行一个十进制小数a i a_iai。输出格式n nn行每行一个整数分别表示i 1 … n i 1 \dots ni1…n对应的答案。输入输出样例 #1输入 #15 11.4514 11.4778 11.1338 11.1236 11.4789输出 #110 11 9 9 11输入输出样例 #2输入 #28 1.1145 1.114 1.1145 1.514 1.19198 1.1154 1.114 1.1145输出 #224 21 24 10 18 22 21 24说明/提示数据范围本题采用捆绑测试。令∑ i 1 n f ( a i ) t \sum\limits_{i1}^n f(a_i) ti1∑nf(ai)t。Subtask 115 pointsa i ≤ 10 a_i \leq 10ai≤10n ≤ 5 n \leq 5n≤5t ≤ 10 t \leq 10t≤10。Subtask 215 pointsa i ≤ 10 a_i \leq 10ai≤10n ≤ 100 n \leq 100n≤100t ≤ 1000 t \leq 1000t≤1000。Subtask 320 pointsn ≤ 1722 n \leq 1722n≤1722。Subtask 415 pointsa i ≤ 1 a_i \leq 1ai≤1。Subtask 535 points无特殊限制。对于所有数据0 a i 10 9 0 \lt a_i \lt 10^90ai1091 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤1051 ≤ t ≤ 3 × 10 6 1 \leq t \leq 3 \times 10^61≤t≤3×106保证a i \bm{a_i}ai没有后导0 \color{black}\bm 00不保证a i \bm{a_i}ai互不相同。样例解释以i 1 i 1i1为例j 1 j 1j1取c 11.4514 c 11.4514c11.4514f ( c ) 4 f(c) 4f(c)4j 2 j 2j2取c 11.46 c 11.46c11.46f ( c ) 2 f(c) 2f(c)2j 3 j 3j3取c 11.2 c 11.2c11.2f ( c ) 1 f(c) 1f(c)1j 4 j 4j4取c 11.3 c 11.3c11.3f ( c ) 1 f(c) 1f(c)1j 5 j 5j5取c 11.47 c 11.47c11.47f ( c ) 2 f(c) 2f(c)2。故∑ j 1 n g ( a 1 , a j ) 4 2 1 1 2 10 \sum\limits_{j1}^n g(a_1, a_j) 4 2 1 1 2 10j1∑ng(a1,aj)4211210。对于同一个j jj上文给出的所有c cc都可能有其它的不同的c cc满足f ( c ) f(c)f(c)同样最小。C实现#includebits/stdc.husingnamespacestd;constintN3e610;inttrie[N][15],cnt[N],ed[N],tot0;string ss[N];intn;voidInsert(conststrings){intrt0;for(autoch:s){intx(ch.?10:ch-0);if(!trie[rt][x])trie[rt][x]tot;rttrie[rt][x];cnt[rt];}ed[rt];}intquery(conststrings){intrt0,tmp0,num0,sum0;boolflag0;for(autoch:s){intx(ch.?10:ch-0);rttrie[rt][x];if(flag){sumcnt[rt];tmped[rt];}flag|(x10);if(flag!num)numcnt[rt];}returnsumnum-tmp-(cnt[rt]-ed[rt]);}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){cinss[i];Insert(ss[i]);}for(inti1;in;i){coutquery(ss[i])\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
