当前位置：首页 > news >正文

打卡信奥刷题（3324）用C++实现信奥题 P9218 「TAOI-1」Apollo

news 2026/6/2 7:47:00

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_{j=1}^ng(a_i, a_j)j=1∑ng(ai,aj)的值并输出。

定义十进制小数是一个含有整数部分和小数部分的数，其小数部分不为0 00。之所以描述得这么愚蠢是因为保证输入的每个数都有小数点，但是好像无论什么写法都会有人提出不满，真是抱歉了。~~所以还是得看看被当事人删掉的图片。所以我在这里写闲话有人看得到吗。~~

输入格式

第一行一个整数n nn。

接下来n nn行，每行一个十进制小数a i a_iai。

输出格式

n nn行，每行一个整数，分别表示i = 1 … n i = 1 \dots ni=1…n对应的答案。

输入输出样例 #1

输入 #1

5 11.4514 11.4778 11.1338 11.1236 11.4789

输出 #1

10 11 9 9 11

输入输出样例 #2

输入 #2

8 1.1145 1.114 1.1145 1.514 1.19198 1.1154 1.114 1.1145

输出 #2

24 21 24 10 18 22 21 24

说明/提示

数据范围

本题采用捆绑测试。

令∑ i = 1 n f ( a i ) = t \sum\limits_{i=1}^n f(a_i) = ti=1∑nf(ai)=t。

Subtask 1（15 points）：a i ≤ 10 a_i \leq 10ai≤10，n ≤ 5 n \leq 5n≤5，t ≤ 10 t \leq 10t≤10。
Subtask 2（15 points）：a i ≤ 10 a_i \leq 10ai≤10，n ≤ 100 n \leq 100n≤100，t ≤ 1000 t \leq 1000t≤1000。
Subtask 3（20 points）：n ≤ 1722 n \leq 1722n≤1722。
Subtask 4（15 points）：a i ≤ 1 a_i \leq 1ai≤1。
Subtask 5（35 points）：无特殊限制。

对于所有数据，0 < a i < 10 9 0 \lt a_i \lt 10^90<ai<109，1 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤105，1 ≤ 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 = 1i=1为例：

j = 1 j = 1j=1：取c = 11.4514 c = 11.4514c=11.4514，f ( c ) = 4 f(c) = 4f(c)=4；
j = 2 j = 2j=2：取c = 11.46 c = 11.46c=11.46，f ( c ) = 2 f(c) = 2f(c)=2；
j = 3 j = 3j=3：取c = 11.2 c = 11.2c=11.2，f ( c ) = 1 f(c) = 1f(c)=1；
j = 4 j = 4j=4：取c = 11.3 c = 11.3c=11.3，f ( c ) = 1 f(c) = 1f(c)=1；
j = 5 j = 5j=5：取c = 11.47 c = 11.47c=11.47，f ( c ) = 2 f(c) = 2f(c)=2。

故∑ j = 1 n g ( a 1 , a j ) = 4 + 2 + 1 + 1 + 2 = 10 \sum\limits_{j=1}^n g(a_1, a_j) = 4 + 2 + 1 + 1 + 2 = 10j=1∑ng(a1,aj)=4+2+1+1+2=10。对于同一个j jj，上文给出的所有c cc，都可能有其它的不同的c cc满足f ( c ) f(c)f(c)同样最小。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=3e6+10;inttrie[N][15],cnt[N],ed[N],tot=0;string ss[N];intn;voidInsert(conststring&s){intrt=0;for(auto&ch:s){intx=(ch=='.'?10:ch-'0');if(!trie[rt][x])trie[rt][x]=++tot;rt=trie[rt][x];cnt[rt]++;}ed[rt]++;}intquery(conststring&s){intrt=0,tmp=0,num=0,sum=0;boolflag=0;for(auto&ch:s){intx=(ch=='.'?10:ch-'0');rt=trie[rt][x];if(flag){sum+=cnt[rt];tmp+=ed[rt];}flag|=(x==10);if(flag&&!num)num=cnt[rt];}returnsum+num-tmp-(cnt[rt]-ed[rt]);}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(inti=1;i<=n;i++){cin>>ss[i];Insert(ss[i]);}for(inti=1;i<=n;i++){cout<<query(ss[i])<<"\n";}return0;}