-
-
-
-
- 沒有傳送門
- 題目大意
- 思路
- 參考代碼
- 熟悉環境
-
-
-
沒有傳送門
題目大意
給你一個長度為 n n 的正整數序列 aiai，要求構造出 n n 個小數，使得它們的和為 11，且每個數小數點後恰好有 ai a i 位（當然要去除多餘的零啦！）。要求你構造出來，或者宣判無解。
思路
唉，我太弱了，看來涼了。到目前為止，我斷斷續續地做了大約 5 5 個小時，隻做了 T1。T2 猜了個結論打了個暴力，T3 暴力都打不來，唉，我太弱啦！
我也不知道這是不是正解，反正卡過咯（剛過就被登出，還以為見鬼了，原來是恰好命題組更新了 A 題（A + B Problem）QAQ），可能我隻會做 A 題吧。連 A + B 問題我都交了 44 次，唉，我太弱啦！
我的想法是考慮從小到大構造。一個很直接的想法是：先把數構造得盡量小，不夠再拿一些數來補嘛。先考慮特殊情況。顯然隻有一個數的時候是無解的。顯然，如果所有數都取理論最小值（ 0.00⋯1 0.00 ⋯ 1 ）時都超過了 1 1 也是無解的。我們立刻得到一個解決子任務 22 的算法：我們看 n n 的值。若 (n−1)∤10(n−1)∤10，顯然我們可以讓 (n−1) ( n − 1 ) 個數變成 0.00⋯1 0.00 ⋯ 1 ，讓最後一個數補足至 1 1 。這最後一個數的結尾肯定不是 00，符合題意。若 (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 變成 kk，用解決子任務 2 2 類似的方法，寫個高精度減法就好了。如果算到最後超出了 11，那麼問題無解。因為這種填充方法是貪心地使每個數填最小的，是以這麼判斷無解是對的。
需要注意的是判斷超出 1 1 的方法，不僅要記錄商，還要記錄餘數，原因顯然，但是像我這麼弱的人，寫都寫暈了（你把上面的思路看懂算我輸），哪裡還知道寫的什麼？于是又貢獻了兩發。總共送出了 1515 次，離限制的 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 = ; 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 * - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[]; int length = ;
if (x < ) putchar('-'); else x = -x;
do buffer[length++] = -(x % ) + '0'; while (x /= );
do putchar(buffer[--length]); while (length);
}
const char yes[] = "YES", no[] = "NO";
const int maxn = int() + ;
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();
putchar('.');
for (int i = ; i <= digit; i++)
printOut();
}
static void printPre(int digit)
{
for (int i = ; i <= digit; i++)
printOut();
}
std::vector<std::vector<int> > remain;
int idx[maxn];
bool need2[maxn];
work() : need2()
{
memset(buf, , sizeof(buf));
for (int i = ; i <= n; i++)
buf[a[i]]++;
for (int i = ; i < maxn; i++)
if (buf[i])
{
vec.push_back(std::make_pair(i, buf[i]));
idx[i] = vec.size() - ;
}
if (vec.back().second == )
{
puts(no);
return;
}
remain.resize(vec.size());
int contri = ;
for (int i = vec.size() - ; ~i; i--)
{
int temp = contri + vec[i].second;
bool mod = false;
for (int j = vec[i].first; temp && j > (i ? vec[i - ].first : ); j--)
{
mod |= (bool)(temp % );
temp /= ;
}
if (!i && temp && mod)
{
puts(no);
return;
}
remain[i].resize(vec[i].first - (i ? vec[i - ].first : ) + );
remain[i].back() = temp + mod;
while (remain[i].back() > )
{
remain[i].push_back(remain[i].back() / );
remain[i][remain[i].size() - ] %= ;
}
int t = contri;
int cnt = ;
while (t)
{
remain[i][cnt] -= t % ;
t /= ;
cnt++;
}
for (int j = ; j < remain[i].size() - ; j++)
if (remain[i][j] < )
{
remain[i][j] += ;
remain[i][j + ]--;
}
contri = temp + mod;
if (vec[i].second == && !remain[i][])
{
puts(no);
return;
}
int sub = vec[i].second - ;
if (sub % == remain[i][])
{
sub++;
need2[vec[i].first] = true;
}
t = sub;
cnt = ;
while (t)
{
remain[i][cnt] -= t % ;
t /= ;
cnt++;
}
for (int j = ; j < remain[i].size() - ; j++)
if (remain[i][j] < )
{
remain[i][j] += ;
remain[i][j + ]--;
}
while (!remain[i].back())
remain[i].pop_back();
}
puts(yes);
for (int i = ; i <= n; i++)
{
buf[a[i]]--;
if (need2[a[i]])
{
need2[a[i]] = false;
printPre2(a[i] - );
printOut();
putchar('\n');
}
else if (buf[a[i]])
{
printPre2(a[i] - );
printOut();
putchar('\n');
}
else
{
const std::vector<int>& v = remain[idx[a[i]]];
printPre2(a[i] - v.size());
for (int i = v.size() - ; ~i; i--)
printOut(v[i]);
putchar('\n');
}
}
}
};
void run()
{
n = readIn();
if (n == ) // 一個肯定不行
{
puts(no);
return;
}
for (int i = ; i <= n; i++)
{
sum += a[i] = readIn();
if (i > && a[i] != a[i - ]) t1 = false;
}
for (int i = ; i <= n; i++)
buf[a[i]]++;
for (int i = n; i; i--)
{
buf[i - ] += buf[i] / ;
buf[i] %= ;
}
bool bOk = false;
for (int i = ; i <= n; i++)
if (buf[i])
{
bOk = true;
break;
}
if ((buf[] && bOk) || buf[] > ) // 都選最小還比 1 大也不行
{
puts(no);
return;
}
RunInstance(work);
}
int main()
{
#ifdef LOCAL
freopen("C.in", "r", stdin);
#endif
run();
return ;
}
熟悉環境
感覺 Guide 還是挺不錯的，除了那個神奇的在 Linux 下的代碼補全，其它的地方都超過了記事本。我本來以為不能調字型，結果可以，在類似于調文法高亮的顔色那裡。我本來以為不能加編譯選項，結果可以，在檔案頁籤那裡點選右鍵就可以了（還是每個檔案一份配置，真是天地良心）。可惜的是沒有好看的字型，不等寬簡直閃瞎眼。
為什麼隻能按 Tab 統一縮進一格，不能按 Shift + Tab 統一取消縮進一格？可能是個 bug 吧……
![【BZOJ1179】【APIO2009】Atm（tarjan+spfa）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)