没有传送门
题目大意
给你一个长度为
n
n
的正整数序列 ai，要求构造出
n
n
个小数，使得它们的和为 1，且每个数小数点后恰好有
ai
a
i
位（当然要去除多余的零啦！）。要求你构造出来，或者宣判无解。
思路
唉，我太弱了，看来凉了。到目前为止，我断断续续地做了大约
5
5
个小时，只做了 T1。T2 猜了个结论打了个暴力，T3 暴力都打不来，唉，我太弱啦！
我也不知道这是不是正解，反正卡过咯（刚过就被退出登录，还以为见鬼了，原来是恰好命题组更新了 A 题（A + B Problem）QAQ），可能我只会做 A 题吧。连 A + B 问题我都交了 4 次，唉，我太弱啦！
我的想法是考虑从小到大构造。一个很直接的想法是：先把数构造得尽量小，不够再拿一些数来补嘛。先考虑特殊情况。显然只有一个数的时候是无解的。显然，如果所有数都取理论最小值（
0.00⋯1
0.00
⋯
1
）时都超过了
1
1
也是无解的。我们立刻得到一个解决子任务 2 的算法：我们看
n
n
的值。若 (n−1)∤10，显然我们可以让
(n−1)
(
n
−
1
)
个数变成
0.00⋯1
0.00
⋯
1
，让最后一个数补足至
1
1
。这最后一个数的结尾肯定不是 0，符合题意。若
(n−1)∣10
(
n
−
1
)
∣
10
，如果还像这样做肯定就炸了，解决方法很简单：让前面的某一个数变成
0.00⋯2
0.00
⋯
2
，问题就解决了，顺利得到
21
21
分。
但是我太弱了，为了理解题意，我用类似的方法去构造样例数据，结果没过，用计算器一算发现加起来等于
0.9
0.9
，唉，这都算错了，我太弱啦！
根据经验，做题有两个突破口：一是用合理的方法解决小数据规模的问题，二是用合理的方法解决 Special Instance。现在我们解决了 Special Instance，我们看看能不能扩展到一般情况。拿样例来看，我们立刻得到一个思路：将数按长度分类，每类按长度排序。我们将长的那一类想办法凑齐至短的那一类的
0.00⋯1
0.00
⋯
1
的形式，则得到一个 Special Instance 的子问题，问题就解决了。但是显然不会这么简单，因为有可能短的那一类很多，导致超过了恰好比它长的那一位，怎么办呢？
当然是乱搞啊！我们将多的那个看成是对上一位的贡献，如果还有多的，贡献继续累加到再上一位就是了（不要问我在说什么，我太弱了，说不清楚）。另外，这会导致需要凑齐的数从
1
1
变成 k，用解决子任务
2
2
类似的方法，写个高精度减法就好了。如果算到最后超出了 1，那么问题无解。因为这种填充方法是贪心地使每个数填最小的，所以这么判断无解是对的。
需要注意的是判断超出
1
1
的方法，不仅要记录商，还要记录余数，原因显然，但是像我这么弱的人，写都写晕了（你把上面的思路看懂算我输），哪里还知道写的什么？于是又贡献了两发。总共提交了 15 次，离限制的
50
50
次还差很多，应该没什么问题吧。（毕竟我这么弱，根本没有恒心一道题交这么多次，卡常时除外）
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
const char yes[] = "YES", no[] = "NO";
const int maxn = int(1e5) + 5;
int n;
int a[maxn];
int sum, t1 = true;
int buf[maxn];
#define RunInstance(x) delete new x
struct work
{
std::vector<std::pair<int, int> > vec;
static void printPre2(int digit)
{
printOut(0);
putchar('.');
for (int i = 1; i <= digit; i++)
printOut(0);
}
static void printPre(int digit)
{
for (int i = 1; i <= digit; i++)
printOut(0);
}
std::vector<std::vector<int> > remain;
int idx[maxn];
bool need2[maxn];
work() : need2()
{
memset(buf, 0, sizeof(buf));
for (int i = 1; i <= n; i++)
buf[a[i]]++;
for (int i = 1; i < maxn; i++)
if (buf[i])
{
vec.push_back(std::make_pair(i, buf[i]));
idx[i] = vec.size() - 1;
}
if (vec.back().second == 1)
{
puts(no);
return;
}
remain.resize(vec.size());
int contri = 0;
for (int i = vec.size() - 1; ~i; i--)
{
int temp = contri + vec[i].second;
bool mod = false;
for (int j = vec[i].first; temp && j > (i ? vec[i - 1].first : 0); j--)
{
mod |= (bool)(temp % 10);
temp /= 10;
}
if (!i && temp && mod)
{
puts(no);
return;
}
remain[i].resize(vec[i].first - (i ? vec[i - 1].first : 0) + 1);
remain[i].back() = temp + mod;
while (remain[i].back() > 10)
{
remain[i].push_back(remain[i].back() / 10);
remain[i][remain[i].size() - 2] %= 10;
}
int t = contri;
int cnt = 0;
while (t)
{
remain[i][cnt] -= t % 10;
t /= 10;
cnt++;
}
for (int j = 0; j < remain[i].size() - 1; j++)
if (remain[i][j] < 0)
{
remain[i][j] += 10;
remain[i][j + 1]--;
}
contri = temp + mod;
if (vec[i].second == 1 && !remain[i][0])
{
puts(no);
return;
}
int sub = vec[i].second - 1;
if (sub % 10 == remain[i][0])
{
sub++;
need2[vec[i].first] = true;
}
t = sub;
cnt = 0;
while (t)
{
remain[i][cnt] -= t % 10;
t /= 10;
cnt++;
}
for (int j = 0; j < remain[i].size() - 1; j++)
if (remain[i][j] < 0)
{
remain[i][j] += 10;
remain[i][j + 1]--;
}
while (!remain[i].back())
remain[i].pop_back();
}
puts(yes);
for (int i = 1; i <= n; i++)
{
buf[a[i]]--;
if (need2[a[i]])
{
need2[a[i]] = false;
printPre2(a[i] - 1);
printOut(2);
putchar('\n');
}
else if (buf[a[i]])
{
printPre2(a[i] - 1);
printOut(1);
putchar('\n');
}
else
{
const std::vector<int>& v = remain[idx[a[i]]];
printPre2(a[i] - v.size());
for (int i = v.size() - 1; ~i; i--)
printOut(v[i]);
putchar('\n');
}
}
}
};
void run()
{
n = readIn();
if (n == 1)
{
puts(no);
return;
}
for (int i = 1; i <= n; i++)
{
sum += a[i] = readIn();
if (i > 1 && a[i] != a[i - 1]) t1 = false;
}
for (int i = 1; i <= n; i++)
buf[a[i]]++;
for (int i = n; i; i--)
{
buf[i - 1] += buf[i] / 10;
buf[i] %= 10;
}
bool bOk = false;
for (int i = 1; i <= n; i++)
if (buf[i])
{
bOk = true;
break;
}
if ((buf[0] && bOk) || buf[0] > 1)
{
puts(no);
return;
}
RunInstance(work);
}
int main()
{
#ifdef LOCAL
freopen("C.in", "r", stdin);
#endif
run();
return 0;
}
熟悉环境
感觉 Guide 还是挺不错的，除了那个神奇的在 Linux 下的代码补全，其它的地方都超过了记事本。我本来以为不能调字体，结果可以，在类似于调语法高亮的颜色那里。我本来以为不能加编译选项，结果可以，在文件选项卡那里点击右键就可以了（还是每个文件一份配置，真是天地良心）。可惜的是没有好看的字体，不等宽简直闪瞎眼。
为什么只能按 Tab 统一缩进一格，不能按 Shift + Tab 统一取消缩进一格？可能是个 bug 吧……
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
