Nếu chạy thử từng trường hợp 1 và kiểm tra thì sẽ phải thử 910 lần. Như vậy thời gian duyệt sẽ khá lớn. Có cách nào để giảm số lần thử đi không nhỉ?
Bài toán: Tìm nghiệm sử dụng Quay lui
2 Likes
vì k <= 100 nên làm 1 cái mảng 100 phần tử chứa kết quả chạy sẵn rồi trả về answer[k-1] là xong 
4 Likes
NO 
3 Likes
Không lớn đến thế 
hãy suy nghĩ về bản chất đệ quy của bài toán
spoil
nhánh cận đó
3 Likes
Mình cũng nghĩ đến nhanh cận mà chưa làm được
2 Likes
hơi dài nhưng chắc chạy đúng 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main()
{
std::vector<std::vector<std::string>> answer{
{},
{},
{},
{},
{},
{},
{},
{},
{},
{},
{
"1111111111",
},
{},
{},
{
"1111111112",
},
{},
{},
{
"1111111122",
},
{},
{
"1111111113",
},
{
"1111111222",
},
{},
{
"1111111123",
},
{
"1111112222",
},
{},
{
"1111111223",
},
{
"1111111114",
"1111122222",
},
{
"1111111133",
},
{
"1111112223",
},
{
"1111111124",
"1111222222",
},
{
"1111111233",
},
{
"1111122223",
},
{
"1111111224",
"1112222222",
},
{
"1111112233",
},
{
"1111111134",
"1111222223",
},
{
"1111111115",
"1111111333",
"1111112224",
"1122222222",
},
{
"1111122233",
},
{
"1111111234",
"1112222223",
},
{
"1111111125",
"1111112333",
"1111122224",
"1222222222",
},
{
"1111222233",
},
{
"1111112234",
"1122222223",
},
{
"1111111144",
"1111111225",
"1111122333",
"1111222224",
"2222222222",
},
{
"1111111334",
"1112222233",
},
{
"1111111135",
"1111113333",
"1111122234",
"1222222223",
},
{
"1111111244",
"1111112225",
"1111222333",
"1112222224",
},
{
"1111112334",
"1122222233",
},
{
"1111111116",
"1111111235",
"1111123333",
"1111222234",
"2222222223",
},
{
"1111112244",
"1111122225",
"1112222333",
"1122222224",
},
{
"1111122334",
"1222222233",
},
{
"1111111126",
"1111111344",
"1111112235",
"1111223333",
"1112222234",
},
{
"1111111145",
"1111113334",
"1111122244",
"1111222225",
"1122222333",
"1222222224",
},
{
"1111111335",
"1111133333",
"1111222334",
"2222222233",
},
{
"1111111226",
"1111112344",
"1111122235",
"1112223333",
"1122222234",
},
{
"1111111245",
"1111123334",
"1111222244",
"1112222225",
"1222222333",
"2222222224",
},
{
"1111111136",
"1111112335",
"1111233333",
"1112222334",
},
{
"1111112226",
"1111122344",
"1111222235",
"1122223333",
"1222222234",
},
{
"1111111444",
"1111112245",
"1111223334",
"1112222244",
"1122222225",
"2222222333",
},
{
"1111111236",
"1111113344",
"1111122335",
"1112233333",
"1122222334",
},
{
"1111111345",
"1111122226",
"1111133334",
"1111222344",
"1112222235",
"1222223333",
"2222222234",
},
{
"1111111117",
"1111111155",
"1111112444",
"1111113335",
"1111122245",
"1111333333",
"1112223334",
"1122222244",
"1222222225",
},
{
"1111112236",
"1111123344",
"1111222335",
"1122233333",
"1222222334",
},
{
"1111111146",
"1111112345",
"1111222226",
"1111233334",
"1112222344",
"1122222235",
"2222223333",
},
{
"1111111127",
"1111111255",
"1111111336",
"1111122444",
"1111123335",
"1111222245",
"1112333333",
"1122223334",
"1222222244",
"2222222225",
},
{
"1111122236",
"1111223344",
"1112222335",
"1222233333",
"2222222334",
},
{
"1111111246",
"1111113444",
"1111122345",
"1112222226",
"1112233334",
"1122222344",
"1222222235",
},
{
"1111111227",
"1111111445",
"1111112255",
"1111112336",
"1111133344",
"1111222444",
"1111223335",
"1112222245",
"1122333333",
"1222223334",
"2222222244",
},
{
"1111113345",
"1111222236",
"1111333334",
"1112223344",
"1122222335",
"2222233333",
},
{
"1111111137",
"1111111355",
"1111112246",
"1111123444",
"1111133335",
"1111222345",
"1113333333",
"1122222226",
"1122233334",
"1222222344",
"2222222235",
},
{
"1111112227",
"1111112445",
"1111122255",
"1111122336",
"1111233344",
"1112222444",
"1112223335",
"1122222245",
"1222333333",
"2222223334",
},
{
"1111111346",
"1111123345",
"1112222236",
"1112333334",
"1122223344",
"1222222335",
},
{
"1111111156",
"1111111237",
"1111112355",
"1111113336",
"1111122246",
"1111223444",
"1111233335",
"1112222345",
"1123333333",
"1222222226",
"1222233334",
"2222222344",
},
{
"1111114444",
"1111122227",
"1111122445",
"1111222255",
"1111222336",
"1112233344",
"1122222444",
"1122223335",
"1222222245",
"2222333333",
},
{
"1111112346",
"1111133444",
"1111223345",
"1122222236",
"1122333334",
"1222223344",
"2222222335",
},
{
"1111111256",
"1111112237",
"1111113445",
"1111122355",
"1111123336",
"1111222246",
"1111333344",
"1112223444",
"1112233335",
"1122222345",
"1223333333",
"2222222226",
"2222233334",
},
{
"1111111118",
"1111111147",
"1111111455",
"1111124444",
"1111133345",
"1111222227",
"1111222445",
"1112222255",
"1112222336",
"1113333334",
"1122233344",
"1222222444",
"1222223335",
"2222222245",
},
{
"1111111337",
"1111113355",
"1111122346",
"1111233444",
"1111333335",
"1112223345",
"1133333333",
"1222222236",
"1222333334",
"2222223344",
},
{
"1111111446",
"1111112256",
"1111122237",
"1111123445",
"1111222355",
"1111223336",
"1112222246",
"1112333344",
"1122223444",
"1122233335",
"1222222345",
"2223333333",
},
{
"1111111128",
"1111111247",
"1111112455",
"1111113346",
"1111224444",
"1111233345",
"1112222227",
"1112222445",
"1122222255",
"1122222336",
"1123333334",
"1222233344",
"2222222444",
"2222223335",
},
{
"1111111356",
"1111112337",
"1111123355",
"1111133336",
"1111222346",
"1112233444",
"1112333335",
"1122223345",
"1233333333",
"2222222236",
"2222333334",
},
{
"1111112446",
"1111122256",
"1111134444",
"1111222237",
"1111223445",
"1112222355",
"1112223336",
"1122222246",
"1122333344",
"1222223444",
"1222233335",
"2222222345",
},
{
"1111111228",
"1111112247",
"1111114445",
"1111122455",
"1111123346",
"1111333444",
"1112224444",
"1112233345",
"1122222227",
"1122222445",
"1222222255",
"1222222336",
"1223333334",
"2222233344",
},
{
"1111111166",
"1111112356",
"1111122337",
"1111133445",
"1111223355",
"1111233336",
"1112222346",
"1113333344",
"1122233444",
"1122333335",
"1222223345",
"2233333333",
},
{
"1111111138",
"1111111347",
"1111113455",
"1111122446",
"1111222256",
"1111234444",
"1111333345",
"1112222237",
"1112223445",
"1122222355",
"1122223336",
"1133333334",
"1222222246",
"1222333344",
"2222223444",
"2222233335",
},
{
"1111111157", "1111111555", "1111112228", "1111113337",
"1111122247", "1111124445", "1111133355", "1111222455",
"1111223346", "1112333444", "1113333335", "1122224444",
"1122233345", "1222222227", "1222222445", "1333333333",
"2222222255", "2222222336", "2223333334",
},
{
"1111111266",
"1111113446",
"1111122356",
"1111222337",
"1111233445",
"1112223355",
"1112233336",
"1122222346",
"1123333344",
"1222233444",
"1222333335",
"2222223345",
},
{
"1111111238",
"1111111456",
"1111112347",
"1111123455",
"1111133346",
"1111222446",
"1112222256",
"1112234444",
"1112333345",
"1122222237",
"1122223445",
"1222222355",
"1222223336",
"1233333334",
"2222222246",
"2222333344",
},
{
"1111111257", "1111112555", "1111113356", "1111122228",
"1111123337", "1111144444", "1111222247", "1111224445",
"1111233355", "1111333336", "1112222455", "1112223346",
"1122333444", "1123333335", "1222224444", "1222233345",
"2222222227", "2222222445", "2333333333",
},
{
"1111112266",
"1111123446",
"1111222356",
"1111334444",
"1112222337",
"1112233445",
"1122223355",
"1122233336",
"1222222346",
"1223333344",
"2222233444",
"2222333335",
},
{
"1111112238",
"1111112456",
"1111122347",
"1111134445",
"1111223455",
"1111233346",
"1112222446",
"1113333444",
"1122222256",
"1122234444",
"1122333345",
"1222222237",
"1222223445",
"2222222355",
"2222223336",
"2233333334",
},
{
"1111111148", "1111111366", "1111111447", "1111112257",
"1111114455", "1111122555", "1111123356", "1111222228",
"1111223337", "1111244444", "1111333445", "1112222247",
"1112224445", "1112233355", "1112333336", "1122222455",
"1122223346", "1133333344", "1222333444", "1223333335",
"2222224444", "2222233345",
},
{
"1111111338",
"1111113347",
"1111122266",
"1111133455",
"1111223446",
"1112222356",
"1112334444",
"1113333345",
"1122222337",
"1122233445",
"1222223355",
"1222233336",
"1333333334",
"2222222346",
"2223333344",
},
{
"1111111119", "1111111357", "1111113555", "1111114446",
"1111122238", "1111122456", "1111133337", "1111222347",
"1111234445", "1111333355", "1112223455", "1112233346",
"1122222446", "1123333444", "1133333335", "1222222256",
"1222234444", "1222333345", "2222222237", "2222223445",
"3333333333",
},
{
"1111111248", "1111112366", "1111112447", "1111122257",
"1111124455", "1111133446", "1111222555", "1111223356",
"1112222228", "1112223337", "1112244444", "1112333445",
"1122222247", "1122224445", "1122233355", "1122333336",
"1222222455", "1222223346", "1233333344", "2222333444",
"2223333335",
},
{
"1111112338",
"1111113456",
"1111123347",
"1111222266",
"1111233455",
"1111333346",
"1112223446",
"1122222356",
"1122334444",
"1123333345",
"1222222337",
"1222233445",
"2222223355",
"2222233336",
"2333333334",
},
{
"1111111129", "1111111167", "1111111556", "1111112357",
"1111123555", "1111124446", "1111133356", "1111222238",
"1111222456", "1111233337", "1111344444", "1112222347",
"1112234445", "1112333355", "1113333336", "1122223455",
"1122233346", "1222222446", "1223333444", "1233333335",
"2222222256", "2222234444", "2222333345",
},
{
"1111112248", "1111122366", "1111122447", "1111144445",
"1111222257", "1111224455", "1111233446", "1112222555",
"1112223356", "1113334444", "1122222228", "1122223337",
"1122244444", "1122333445", "1222222247", "1222224445",
"1222233355", "1222333336", "2222222455", "2222223346",
"2233333344",
},
{
"1111111466",
"1111122338",
"1111123456",
"1111223347",
"1111334445",
"1112222266",
"1112233455",
"1112333346",
"1122223446",
"1133333444",
"1222222356",
"1222334444",
"1223333345",
"2222222337",
"2222233445",
},
{
"1111111229", "1111111267", "1111111348", "1111112556",
"1111113366", "1111113447", "1111122357", "1111134455",
"1111223555", "1111224446", "1111233356", "1112222238",
"1112222456", "1112233337", "1112344444", "1113333445",
"1122222347", "1122234445", "1122333355", "1123333336",
"1222223455", "1222233346", "1333333344", "2222222446",
"2223333444", "2233333335",
},
{
"1111111158", "1111111457", "1111113338", "1111114555",
"1111122248", "1111133347", "1111222366", "1111222447",
"1111244445", "1111333455", "1112222257", "1112224455",
"1112233446", "1122222555", "1122223356", "1123334444",
"1133333345", "1222222228", "1222223337", "1222244444",
"1222333445", "2222222247", "2222224445", "2222233355",
"2222333336", "3333333334",
},
{
"1111111139", "1111112466", "1111113357", "1111133555",
"1111134446", "1111222338", "1111223456", "1111333337",
"1112223347", "1112334445", "1113333355", "1122222266",
"1122233455", "1122333346", "1222223446", "1233333444",
"1333333335", "2222222356", "2222334444", "2223333345",
},
{
"1111112229", "1111112267", "1111112348", "1111114456",
"1111122556", "1111123366", "1111123447", "1111222357",
"1111234455", "1111333446", "1112223555", "1112224446",
"1112233356", "1122222238", "1122222456", "1122233337",
"1122344444", "1123333445", "1222222347", "1222234445",
"1222333355", "1223333336", "2222223455", "2222233346",
"2333333344",
},
{
"1111111258", "1111112457", "1111123338", "1111124555",
"1111133456", "1111222248", "1111233347", "1111444444",
"1112222366", "1112222447", "1112244445", "1112333455",
"1113333346", "1122222257", "1122224455", "1122233446",
"1222222555", "1222223356", "1223334444", "1233333345",
"2222222228", "2222223337", "2222244444", "2222333445",
},
};
int k;
std::cin >> k;
if (answer[k].empty())
std::cout << -1 << "\n";
else
for (auto& a : answer[k])
do
{
for (char c : a)
std::cout << c << " ";
std::cout << "\n";
} while (std::next_permutation(begin(a), end(a)));
}
5 Likes
Đề bài quy đổi thành
“Phân tích k thành tổng của 10 số chính phương từ 1 đến 100”
Chỉ có 10 số thành phần là 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
Với mỗi bộ kết quả thì tìm tất cả các hoán vị của nó.
2 cái này chắc trên mạng có sẵn code, có khi đọc lại hiểu 
5 Likes
Đề không nói là các số chính phương khác nhau mà anh.
4 Likes
3 Likes
Khá Ok nhưng nó không phải giải pháp mình muốn tìm
2 Likes
Để mình thử và báo cáo kết quả nhé 
3 Likes
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
void permutation(std::vector<int> x) {
static std::unordered_map<int, int> square_roots {
{1, 1}, {4, 2}, {9, 3}, {16, 4}, {25, 5},
{36, 6}, {49, 7}, {64, 8}, {81, 9} };
do {
for (auto &n : x) std::cout << square_roots[n] << ' ';
std::cout << '\n';
} while (std::next_permutation(x.begin(), x.end()));
}
bool backtrack(std::vector<int> &x, const std::vector<int> &squares, const int &k, int sum, int start, int step) {
bool has_solution = false;
for (auto i = start; i < squares.size(); i++) {
x[step] = squares[i];
sum += squares[i];
if (sum > k) break;
if (step == x.size() - 1) {
if (sum == k) {
permutation(x);
has_solution = true;
}
if (i < squares.size() - 1) {
sum -= squares[i];
continue;
}
} else {
has_solution = backtrack(x, squares, k, sum, i, step + 1) || has_solution;
sum -= squares[i];
}
}
return has_solution;
}
void solve_equation(int k) {
std::vector<int> x(10);
std::vector<int> squares { 1, 4, 9, 16, 25, 36, 49, 64, 81 };
if (!backtrack(x, squares, k, 0, 0, 0)) std::cout << -1;
}
int main() {
int k; std::cin >> k;
solve_equation(k);
}
8 Likes
ngắn quá ko biết đúng ko :V :V :V
#include <algorithm>
#include <iostream>
#include <numeric>
struct SortedNumber {
int a[10];
bool next() { return i(9); }
bool i(int d) {
return d < 0 ? 0 : a[d] < 9 ? ++a[d] : i(d - 1) ? a[d] = a[d - 1] : 0;
}
};
int main() {
int k;
std::cin >> k;
int cnt = 0;
for (SortedNumber p{1, 1, 1, 1, 1, 1, 1, 1, 1, 0}; p.next();)
if (k == std::transform_reduce(p.a, p.a + 10, 0,
[](int a, int b) { return a + b; },
[](int n) { return n * n; })) {
auto q = p;
do {
for (int c : q.a) std::cout << c << " ";
std::cout << "\n";
cnt++;
} while (std::next_permutation(q.a, q.a + 10));
}
if (!cnt) std::cout << "-1\n";
}
8 Likes
Code dp (làm màu đếm số nghiệm 
) nhưng có hàm trace (dùng backtrack )
Mình đang tìm cách tối ưu hàm show_all_permutations vì không phải lúc nào 1 dãy nghiệm cũng sinh ra 10! hoán vị, hoặc là đề bài thực chất không có nhiều bộ nghiệm phân biệt đến thế (sợ time limit ).
5 Likes
Cái này có phải quay lui đâu
7 Likes
Chơi xấu 
int cnt[10];
// cnt[i]: đếm số i trong dãy nghiệm
for (cnt[1] = 0; cnt[1] <= 10; cnt[1]++)
for (cnt[2] = 0; cnt[2] <= 10; cnt[2]++)
for (cnt[3] = 0; cnt[3] <= 10; cnt[3]++)
for (cnt[4] = 0; cnt[4] <= 6; cnt[4]++)
for (cnt[5] = 0; cnt[5] <= 4; cnt[5]++)
for (cnt[6] = 0; cnt[6] <= 2; cnt[6]++)
for (cnt[7] = 0; cnt[7] <= 1; cnt[7]++)
for (cnt[8] = 0; cnt[8] <= 1; cnt[8]++)
for (cnt[9] = 0; cnt[9] <= 1; cnt[9]++)
if (sum(cnt[i] * i for i in [1..9]) == n) {
backtrack_dựng_dãy_nghiệm_ahihi(cnt);
}
Độ phức tạp O(11^3 * 7 * 5 * 3 * 2^3 + 10!) ≈ 4.7M, time limit là tại đề
Cải tiến thêm 1 chút:
Trong các bộ nghiệm, không thể tồn tại khả năng 7^2 + 8^2, 8^2 + 9^2, 7^2 + 9^2 hay 7^2 + 8^2 + 9^2 (vì tổng của chúng đều vượt quá 100), do vậy chỉ có 4 khả năng xảy ra:
- Dãy nghiệm không có 7, 8, 9.
- Dãy nghiệm chỉ có 7.
- Dãy nghiệm chỉ có 8.
- Dãy nghiệm chỉ có 9.
Tạo 1 mảng flag789[4] = {0, 1, 2, 4} gồm các số có 3 bit, mỗi bit tượng trưng cho sự xuất hiện của các chữ số 7, 8, 9 (bit i <=> số i+7 xuất hiện). Hay đơn giản hơn, vẫn biểu diễn sự xuất hiện của 7, 8, 9 qua các số từ 0 -> 3 nhưng if else các khả năng
Độ phức tạp giảm còn O(11^3 * 7 * 5 * 3 * 4 + 10!) ≈ 4.1M :v
8 Likes
#include <bits/stdc++.h>
using namespace std;
ifstream fi ("GPT.INP");
ofstream fo ("GPT.OUT");
int sum = 0;
int dem = 0;
void InKQ (int x[], int k)
{
if(sum == k)
{
dem++;
for(int i=0; i<10; i++)
{
fo << x[i] << " ";
}
fo << endl;
}
}
void Tim (int i, int x[], int k)
{
for(int val=1; val<=9 ; val++)
{
x[i] = val;
sum += val * val;
if(i==9)
InKQ(x,k);
else if(sum < 100)
Tim(i+1,x,k);
sum -= val * val;
}
}
int main()
{
int k;
fi >> k;
if(k<10)
fo << "-1";
int x[10];
Tim(0,x,k);
if(dem == 0)
fo << "-1";
return 0;
}
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?