今天是10月20号，1024合成游戏已经进行了四天。根据游戏规则，我们每人每天最多可以获得7张卡牌
1.每日做题可以获得三张数字牌
2.每日打开活动界面可以获得一张运算符牌
3.每日好友分享，可以获得三张好友已有的数字牌 或 运算符牌
相信又很多同学已经凑出了好几套1024了，不知道有没有人和我一样，已经凑出了至少一套1024，但并没有急于合成，而是留着分享给其他用户再分享给自己，使得自己目前已有1024组合再生。
但其实，在我不断分享的过程中，我发现如下几个规律
1.我们每次合成一套1024，都需要3个运算符和4个数字。但我们除了好友分享的卡牌以外，每天只能获得一张运算符，这样使得我们运算符相对来说较为短缺。
2.每天最好的情况是交换得到一张数字和两张运算符，刚好凑出1024，但是现实可能达不到这么好的效果
3.在我们保留之前1024之后，随着卡牌的增加，这些卡牌可能又凑出新的1024组合
基于上述的分析，我写了两个CPP程序：
1.我们目前已有的卡牌，最多可以凑出多少套1024.
2.增加多少运算符，可以凑出更多的1024（根据2的分析，其实应该考虑数字的，但由于我目前不知道数字可以是什么，加上时间原因，只考虑了运算符，后续会写一个考虑数字符的，现已更新）
代码整体思路：
1.统计当前卡牌可以凑出的所有1024的组合数
2.计算当前卡牌最多可以包含几个组合
首先介绍一下代码的使用方法：(AGA~BMH70%604_%7BRLS9N%7DH.png)
在初始化函数init()中，我们需要把自己有的数字写在nums[]中，把已有的符号数量写在对应的cnt中
例如，我现在又19,2,2,2,23,3,14,11,28,14,2,1,25,2这些数字
又1个*，1个**，1个//，3个|，1个&，3个<<,1个>>
最后表示方法就是我在图中填写的。
结果展示
4%7BY)(D0_9MI%6065.png)
个人建议先每天做完三道题，凑够足够的数字，再运算需要的符号牌
另，说一下我的思考。个人认为比较重要的运算符是 *， **， <<, >>, // 可以把数字放大缩小
代码错误订正：
1.之前没获得过0，所以没考虑/和%遇到0的问题
2.超出int范围那部分没处理好
现以改正
代码改进
昨天我获得了1024之后，发现组合数激增，导致运算需要很长很长的时间（一晚上还没跑完，可能是我的电脑不大行）
经过分析，代码主要是第二部分时间代价较大。第二部分类似一个多维完全背包问题。
因此，今天我对代码进行了改进，增加了一部分记忆化，今天30张卡牌的情况下，测试大概半小时内就能得到当前组数的结果。
代码：
计算目前最多可以组成的套数
#include<bits/stdc++.h>
using namespace std;
unordered_map<string, int> char_cnt;
unordered_map<int, int> num_cnt;
unordered_map<string, int> locs;
typedef long long ULL;
const ULL INF = 0x7fffffff;
const int card_size = 25;
void init(){
//目前团队中已有的数字，可以自行补充
int exist_nums[] = {0,1,2,3,5,7,11,14,16,19,23,25,28,1024};
//统计已有的数字
int nums[] = {0,1024,1024,0,19,2,2,2,23,3,14,11,28,14,2,1,25,2};
for(int num : nums){
num_cnt[num]++;
}
//统计已有的运算符号
string syms[] = {"+", "-", "*", "**", "%", "//", "|", "&", "^", "<<", ">>"};
int cnt[] = {0, 0, 1, 1, 0, 1, 3, 1, 1, 3, 1};
for(int i=0;i<11;i++){
char_cnt[syms[i]] = cnt[i];
}
int loc = 0;
for(int num : exist_nums){
locs[to_string(num)] = loc++;
}
for(auto str : char_cnt){
locs[str.first] = loc++;
}
}
ULL cal(ULL x, string str, ULL y){
if(str == "+") return x + y;
if(str == "-") return x - y;
if(str == "*") return x * y;
if(str == "**") return pow(x, y);
if(str == "%")
if(y) return x % y;
else return INF + 1;
if(str == "//")
if(y) return x / y;
else return INF + 1;
if(str == "|") return x | y;
if(str == "&") return x & y;
if(str == "^") return x ^ y;
if(str == "<<")
if(y <= 32 && y >= 0)
return x << y;
else return INF + 1;
if(str == ">>")
if(y >= 0) return x >> y;
else return INF + 1;
}
bool judge(ULL num){
return (num > INF) || (num < -INF - 1);
}
vector<string> ans;
vector<vector<string>> res;
set<vector<string>> resset;
void dfs(int i, ULL pre){
if(judge(pre))
return;
if(i == 7){
if(pre == 1024){
vector<string> temp(ans);
sort(temp.begin(), temp.end());
if(resset.find(temp) == resset.end()){
res.push_back(ans);
resset.insert(temp);
}
for(int j=0;j<ans.size();j++)
cout<<ans[j]<<" ";
cout<<pre<<endl;
}
return;
}
if(i == 0){
for(auto num : num_cnt)
if(num.second){
num_cnt[num.first]--;
ans.push_back(to_string(num.first));
dfs(i + 1, num.first);
ans.pop_back();
num_cnt[num.first]++;
}
}else if(i % 2 == 1){
for(auto str : char_cnt)
if(str.second){
char_cnt[str.first]--;
ans.push_back(str.first);
dfs(i + 1, pre);
ans.pop_back();
char_cnt[str.first]++;
}
}else{
for(auto num : num_cnt)
if(num.second){
num_cnt[num.first]--;
ans.push_back(to_string(num.first));
dfs(i + 1, cal(pre, ans[ans.size() - 2], num.first));
ans.pop_back();
num_cnt[num.first]++;
}
}
}
int max_size = 0;
vector<int> dp_cnt(card_size);
vector<vector<string>> temp_res;
map<vector<int>, bool> dp;
unordered_map< int, vector<vector<vector<string>>> > mp;
bool judge_res(vector<string> temp){
bool f = true;
for(int i=0;i<temp.size();i++){
if(i % 2 == 0){
if(!f || num_cnt[stoi(temp[i])] < 1)
f = false;
num_cnt[stoi(temp[i])]--;
}else{
if(!f || char_cnt[temp[i]] < 1)
f = false;
char_cnt[temp[i]]--;
}
}
for(int i=0;i<temp.size();i++){
if(i % 2 == 0){
num_cnt[stoi(temp[i])]++;
}else{
char_cnt[temp[i]]++;
}
}
return f;
}
void del(vector<string> temp){
for(int i=0;i<temp.size();i++){
if(i % 2 == 0){
num_cnt[stoi(temp[i])]--;
}else{
char_cnt[temp[i]]--;
}
dp_cnt[locs[temp[i]]]++;
}
}
void add(vector<string> temp){
for(int i=0;i<temp.size();i++){
if(i % 2 == 0){
num_cnt[stoi(temp[i])]++;
}else{
char_cnt[temp[i]]++;
}
dp_cnt[locs[temp[i]]]--;
}
}
void dfs_res(int i, int k, bool f){
if(k == res.size())
return;
if(dp.find(dp_cnt) != dp.end())
return;
if(i >= max_size && f){
if(i > max_size){
cout<<endl;
cout<<"max_size : "<<i<<endl;
for(int j=0;j<temp_res.size();j++){
for(int l=0;l<temp_res[j].size();l++){
cout<<temp_res[j][l]<<" ";
}
cout<<endl;
}
cout<<endl;
max_size = i;
}
mp[i].push_back(temp_res);
//max_res = temp_res;
}
int count = 0;
while(judge_res(res[k])){
count++;
del(res[k]);
temp_res.push_back(res[k]);
dfs_res(i + count, k + 1, true);
}
while(count--){
temp_res.pop_back();
add(res[k]);
}
dfs_res(i, k + 1, false);
dp[dp_cnt] = true;
}
void print(){
ofstream cout("out.txt");
cout<<"目前最多可以凑出"<<max_size<<"套1024，具体方案如下"<<endl<<endl;
for(int k=0;k<mp[max_size].size();k++){
vector<vector<string>> max_res = mp[max_size][k];
for(int i=0;i<max_res.size();i++){
vector<string> temp = max_res[i];
for(int j=0;j<temp.size();j++){
cout<<temp[j]<<" ";
}
cout<<endl;
}
cout<<endl<<"+++++++++++++++++"<<endl<<endl;
}
}
int main(){
init();
cout<<"当前可以凑出的1024组合："<<endl;
dfs(0, 0);
cout<<"---------------------"<<endl;
cout<<endl;
cout<<"res.size = "<<res.size()<<endl;
dfs_res(0, 0, true);
print();
cout<<"程序执行结束"<<endl;
} 再增加几个运算符和数字符，可以使得组成的套数最多（该代码很容易栈溢出，最好在牌少的时候使用）
#include<bits/stdc++.h>
using namespace std;
unordered_map<string, int> char_cnt;
unordered_map<int, int> num_cnt;
unordered_map<string, int> locs;
typedef long long ULL;
const ULL INF = 0x7fffffff;
const int card_size = 25;
int change = 3;
void init(){
//目前团队中已有的数字，可以自行补充
int exist_nums[] = {0,1,2,3,5,7,11,14,16,19,23,25,28,1024};
//统计已有的数字
int nums[] = {0,2,0,1024,1024,0,19,2,2,2,23,3,14,11,28,14,2,1,25,2};
for(int num : exist_nums){
num_cnt[num] = 0;
}
for(int num : nums){
num_cnt[num]++;
}
//统计已有的运算符号
string syms[] = {"+", "-", "*", "**", "%", "//", "|", "&", "^", "<<", ">>"};
int cnt[] = {0, 0, 1, 1, 0, 1, 3, 1, 1, 3, 1};
for(int i=0;i<11;i++){
char_cnt[syms[i]] = cnt[i];
}
int loc = 0;
for(int num : exist_nums){
locs[to_string(num)] = loc++;
}
for(auto str : char_cnt){
locs[str.first] = loc++;
}
}
ULL cal(ULL x, string str, ULL y){
if(str == "+") return x + y;
if(str == "-") return x - y;
if(str == "*") return x * y;
if(str == "**") return pow(x, y);
if(str == "%")
if(y) return x % y;
else return INF + 1;
if(str == "//")
if(y) return x / y;
else return INF + 1;
if(str == "|") return x | y;
if(str == "&") return x & y;
if(str == "^") return x ^ y;
if(str == "<<")
if(y <= 32 && y >= 0)
return x << y;
else return INF + 1;
if(str == ">>")
if(y >= 0) return x >> y;
else return INF + 1;
}
bool judge(ULL num){
return (num > INF) || (num < -INF - 1);
}
vector<string> ans;
vector<vector<string>> res;
set<vector<string>> resset;
void dfs(int i, ULL pre){
if(judge(pre))
return;
if(i == 7){
if(pre == 1024){
vector<string> temp(ans);
sort(temp.begin(), temp.end());
if(resset.find(temp) == resset.end()){
res.push_back(ans);
resset.insert(temp);
}
/*for(int j=0;j<ans.size();j++)
cout<<ans[j]<<" ";
cout<<pre<<endl;*/
}
return;
}
if(i == 0){
for(auto num : num_cnt){
if(num.second > 0 || change > 0){
if(num.second <= 0)
change--;
num_cnt[num.first]--;
ans.push_back(to_string(num.first));
dfs(i + 1, num.first);
ans.pop_back();
num_cnt[num.first]++;
if(num.second <= 0)
change++;
}
}
}else if(i % 2 == 1){
for(auto str : char_cnt)
if(str.second > 0 || change > 0){
if(str.second <= 0)
change--;
char_cnt[str.first]--;
ans.push_back(str.first);
dfs(i + 1, pre);
ans.pop_back();
char_cnt[str.first]++;
if(str.second <= 0)
change++;
}
}else{
for(auto num : num_cnt)
if(num.second > 0 || change > 0){
if(num.second <= 0)
change--;
num_cnt[num.first]--;
ans.push_back(to_string(num.first));
dfs(i + 1, cal(pre, ans[ans.size() - 2], num.first));
ans.pop_back();
num_cnt[num.first]++;
if(num.second <= 0)
change++;
}
}
}
int max_size = 0;
vector<int> dp_cnt(card_size);
vector<vector<string>> temp_res;
map<vector<int>, bool> dp;
unordered_map< int, vector<vector<vector<string>>> > mp;
bool judge_res(vector<string> temp){
bool f = true;
for(int i=0;i<temp.size();i++){
if(i % 2 == 0){
if(num_cnt[stoi(temp[i])] < 1){
change--;
}
num_cnt[stoi(temp[i])]--;
}else{
if(char_cnt[temp[i]] < 1){
change--;
}
char_cnt[temp[i]]--;
}
}
if(change < 0)
f = false;
for(int i=0;i<temp.size();i++){
if(i % 2 == 0){
if(num_cnt[stoi(temp[i])] < 0){
change++;
}
num_cnt[stoi(temp[i])]++;
}else{
if(char_cnt[temp[i]] < 0){
change++;
}
char_cnt[temp[i]]++;
}
}
return f;
}
void del(vector<string> temp){
for(int i=0;i<temp.size();i++){
if(i % 2 == 0){
num_cnt[stoi(temp[i])]--;
if(num_cnt[stoi(temp[i])] < 0)
change--;
}else{
char_cnt[temp[i]]--;
if(char_cnt[temp[i]] < 0)
change--;
}
dp_cnt[locs[temp[i]]]++;
}
}
void add(vector<string> temp){
for(int i=0;i<temp.size();i++){
if(i % 2 == 0){
num_cnt[stoi(temp[i])]++;
if(num_cnt[stoi(temp[i])] <= 0)
change++;
}else{
char_cnt[temp[i]]++;
if(char_cnt[temp[i]] <= 0)
change++;
}
dp_cnt[locs[temp[i]]]--;
}
}
void dfs_res(int i, int k, bool f){
if(k == res.size())
return;
if(dp.find(dp_cnt) != dp.end())
return;
if(i >= max_size && f){
if(i > max_size){
cout<<endl;
cout<<"max_size : "<<i<<endl;
for(int j=0;j<temp_res.size();j++){
for(int l=0;l<temp_res[j].size();l++){
cout<<temp_res[j][l]<<" ";
}
cout<<endl;
}
cout<<endl;
max_size = i;
}
mp[i].push_back(temp_res);
//max_res = temp_res;
}
int count = 0;
while(judge_res(res[k])){
count++;
del(res[k]);
temp_res.push_back(res[k]);
dfs_res(i + count, k + 1, true);
}
while(count--){
temp_res.pop_back();
add(res[k]);
}
dfs_res(i, k + 1, false);
dp[dp_cnt] = true;
}
int cal_add(vector<vector<string>> max_res){
unordered_map<string, int> m1;
unordered_map<int, int> m2;
for(int i=0;i<max_res.size();i++){
vector<string> temp = max_res[i];
for(int j=0;j<temp.size();j++){
if(j % 2 == 1)
m1[temp[j]]++;
else
m2[stoi(temp[j])]++;
}
}
int sum = 0;
for(auto i : m1){
string key = i.first;
int val = i.second;
sum += max(0, val - char_cnt[key]);
}
for(auto i : m2){
int key = i.first;
int val = i.second;
sum += max(0, val - num_cnt[key]);
}
return sum;
}
void print(){
ofstream cout("ccout.txt");
int min_size = 0x7fffffff;
for(int k=0;k<mp[max_size].size();k++){
vector<vector<string>> max_res = mp[max_size][k];
if(cal_add(max_res) < min_size){
min_size = min(min_size, cal_add(max_res));
cout<<"当前min_size : "<<min_size<<endl;
}
}
set<vector<string>> s;
for(int k=0;k<mp[max_size].size();k++){
vector<vector<string>> max_res = mp[max_size][k];
if(min_size == cal_add(max_res)){
map<string, int> m1;
map<int, int> m2;
for(int i=0;i<max_res.size();i++){
vector<string> temp = max_res[i];
for(int j=0;j<temp.size();j++){
if(j % 2 == 1)
m1[temp[j]]++;
else
m2[stoi(temp[j])]++;
}
}
vector<string> add;
for(auto i : m1){
string key = i.first;
int val = i.second;
int bu = max(0, val - char_cnt[key]);
if(bu){
for(int j=0;j<bu;j++)
add.push_back(key);
}
}
for(auto i : m2){
int key = i.first;
int val = i.second;
int bu = max(0, val - num_cnt[key]);
if(bu){
for(int j=0;j<bu;j++)
add.push_back(to_string(key));
}
}
s.insert(add);
}
}
cout<<"再增加"<<min_size<<"个运算符"<<endl;
cout<<"最多可以凑出"<<max_size<<"套1024，具体方案如下"<<endl<<endl;
for(auto si : s){
for(int i=0;i<si.size();i++){
if(i)
cout<<" , ";
cout<<si[i];
}
cout<<endl;
}
}
int main(){
init();
cout<<"当前可以凑出的1024组合："<<endl;
dfs(0, 0);
resset.clear();
cout<<"---------------------"<<endl;
cout<<endl;
cout<<"res.size = "<<res.size()<<endl;
dfs_res(0, 0, true);
print();
cout<<"程序执行结束"<<endl;
} 最后，我已经有的卡牌前面都说过了，有需要的可以私聊我哦，希望大家早日凑出足够数量的1024.
评论 (29)
