本来以为还是签完到就开始自闭,没想到今天的邀请赛还摸出一道C。这题看提交数其实不多,而且题目表达也挺复杂。简单来说,就是把一个数W拆成若干个Fib(Fib(x))之和,其中x各不相同。题目数据是,乍一看好像很夸张。其实去算就会发现,其实也就,再算,发现其实也就28个数。不过这28个数真的挺长的,打表还真打不下,好在Fib现算一遍也就O(logN)。
然后拆数我写的就很low了,由于字典序最小,我就用了的朴素方法。其实只有2和5需要处理,但是第一次交的时候好像我其它地方漏了个条件,于是WA了。后来保险就用了,总复杂度是。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
// 打表,前28项
final static int[] ind = {0,1,2,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811};
static boolean[] inS = new boolean[30];
static boolean[] used = new boolean[30];
static BigInteger[] ff = new BigInteger[30];
static int sCnt;
static boolean check(BigInteger W, int st) {
int curCheck = st;
sCnt = 0;
for (int i = 1; i < ind.length; i++) used[i] = false;
while (W.compareTo(BigInteger.ZERO) > 0 && curCheck > 0) {
if (!inS[curCheck] && W.compareTo(ff[curCheck]) >= 0) {
W = W.subtract(ff[curCheck]);
used[curCheck] = true;
sCnt++;
}
curCheck--;
}
if (sCnt > 0 && W.equals(BigInteger.ZERO)) {
for (int i = 1; i < ind.length; i++) inS[i] = inS[i] || used[i];
return true;
}
return false;
}
public static void main(String[] args) {
int curInd, cnt;
BigInteger fn_2, fn_1, fn;
fn_2 = BigInteger.ONE;
fn_1 = BigInteger.ONE;
ff[1] = BigInteger.ONE; ff[2] = BigInteger.ONE; ff[3] = BigInteger.ONE;
cnt = 2; curInd = 4;
while (curInd < ind.length) {
fn = fn_2.add(fn_1);
fn_2 = fn_1;
fn_1 = fn;
cnt++;
if (cnt == ind[curInd]) {
ff[curInd] = fn;
curInd++;
}
}
// 读入
Scanner sc = new Scanner(System.in);
int T, curCheck;
BigInteger W;
T = sc.nextInt();
while (T-- > 0) {
W = sc.nextBigInteger();
sCnt = 0; // 集合S大小
// 初始化inS
for (int i = 1; i < ind.length; i++) inS[i] = false;
// 检查
if (!check(W, ind.length - 1)) {
// 失败
System.out.println("-1");
continue;
}
// 对每个数,向前分割
BigInteger num;
curCheck = ind.length - 1;
while (curCheck > 0) {
while (curCheck > 0 && !inS[curCheck]) curCheck--;
if (!inS[curCheck]) break;
// inS[curCheck] = true
if (check(ff[curCheck], curCheck - 1)) {
inS[curCheck] = false;
}
curCheck--;
}
// 重新计算sCnt
sCnt = 0;
for (int i = 1; i < ind.length; i++) if (inS[i]) sCnt += 1;
// 打印
for (int i = 1; i < ind.length; i++) {
if (inS[i]) {
System.out.print(i);
sCnt--;
if (sCnt > 0) System.out.print(' ');
}
}
System.out.println();
}
}
}
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
// 打表,前28项
final static int[] ind = {0,1,2,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811};
static boolean[] inS = new boolean[30];
static boolean[] used = new boolean[30];
static BigInteger[] ff = new BigInteger[30];
static int sCnt;
static boolean check(BigInteger W, int st) {
int curCheck = st;
sCnt = 0;
for (int i = 1; i < ind.length; i++) used[i] = false;
while (W.compareTo(BigInteger.ZERO) > 0 && curCheck > 0) {
if (!inS[curCheck] && W.compareTo(ff[curCheck]) >= 0) {
W = W.subtract(ff[curCheck]);
used[curCheck] = true;
sCnt++;
}
curCheck--;
}
if (sCnt > 0 && W.equals(BigInteger.ZERO)) {
for (int i = 1; i < ind.length; i++) inS[i] = inS[i] || used[i];
return true;
}
return false;
}
public static void main(String[] args) {
int curInd, cnt;
BigInteger fn_2, fn_1, fn;
fn_2 = BigInteger.ONE;
fn_1 = BigInteger.ONE;
ff[1] = BigInteger.ONE; ff[2] = BigInteger.ONE; ff[3] = BigInteger.ONE;
cnt = 2; curInd = 4;
while (curInd < ind.length) {
fn = fn_2.add(fn_1);
fn_2 = fn_1;
fn_1 = fn;
cnt++;
if (cnt == ind[curInd]) {
ff[curInd] = fn;
curInd++;
}
}
// 读入
Scanner sc = new Scanner(System.in);
int T, curCheck;
BigInteger W;
T = sc.nextInt();
while (T-- > 0) {
W = sc.nextBigInteger();
sCnt = 0; // 集合S大小
// 初始化inS
for (int i = 1; i < ind.length; i++) inS[i] = false;
// 检查
if (!check(W, ind.length - 1)) {
// 失败
System.out.println("-1");
continue;
}
// 对每个数,向前分割
BigInteger num;
curCheck = ind.length - 1;
while (curCheck > 0) {
while (curCheck > 0 && !inS[curCheck]) curCheck--;
if (!inS[curCheck]) break;
// inS[curCheck] = true
if (check(ff[curCheck], curCheck - 1)) {
inS[curCheck] = false;
}
curCheck--;
}
// 重新计算sCnt
sCnt = 0;
for (int i = 1; i < ind.length; i++) if (inS[i]) sCnt += 1;
// 打印
for (int i = 1; i < ind.length; i++) {
if (inS[i]) {
System.out.print(i);
sCnt--;
if (sCnt > 0) System.out.print(' ');
}
}
System.out.println();
}
}
}
import java.math.BigInteger; import java.util.Scanner; public class Main { // 打表,前28项 final static int[] ind = {0,1,2,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811}; static boolean[] inS = new boolean[30]; static boolean[] used = new boolean[30]; static BigInteger[] ff = new BigInteger[30]; static int sCnt; static boolean check(BigInteger W, int st) { int curCheck = st; sCnt = 0; for (int i = 1; i < ind.length; i++) used[i] = false; while (W.compareTo(BigInteger.ZERO) > 0 && curCheck > 0) { if (!inS[curCheck] && W.compareTo(ff[curCheck]) >= 0) { W = W.subtract(ff[curCheck]); used[curCheck] = true; sCnt++; } curCheck--; } if (sCnt > 0 && W.equals(BigInteger.ZERO)) { for (int i = 1; i < ind.length; i++) inS[i] = inS[i] || used[i]; return true; } return false; } public static void main(String[] args) { int curInd, cnt; BigInteger fn_2, fn_1, fn; fn_2 = BigInteger.ONE; fn_1 = BigInteger.ONE; ff[1] = BigInteger.ONE; ff[2] = BigInteger.ONE; ff[3] = BigInteger.ONE; cnt = 2; curInd = 4; while (curInd < ind.length) { fn = fn_2.add(fn_1); fn_2 = fn_1; fn_1 = fn; cnt++; if (cnt == ind[curInd]) { ff[curInd] = fn; curInd++; } } // 读入 Scanner sc = new Scanner(System.in); int T, curCheck; BigInteger W; T = sc.nextInt(); while (T-- > 0) { W = sc.nextBigInteger(); sCnt = 0; // 集合S大小 // 初始化inS for (int i = 1; i < ind.length; i++) inS[i] = false; // 检查 if (!check(W, ind.length - 1)) { // 失败 System.out.println("-1"); continue; } // 对每个数,向前分割 BigInteger num; curCheck = ind.length - 1; while (curCheck > 0) { while (curCheck > 0 && !inS[curCheck]) curCheck--; if (!inS[curCheck]) break; // inS[curCheck] = true if (check(ff[curCheck], curCheck - 1)) { inS[curCheck] = false; } curCheck--; } // 重新计算sCnt sCnt = 0; for (int i = 1; i < ind.length; i++) if (inS[i]) sCnt += 1; // 打印 for (int i = 1; i < ind.length; i++) { if (inS[i]) { System.out.print(i); sCnt--; if (sCnt > 0) System.out.print(' '); } } System.out.println(); } } }