May
4
2008武汉大学软件文化节算法设计大赛D题
2008武汉大学软件文化节算法设计大赛D题Felix的代码. 超时,需要打表- -||
程序如下
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
程序如下
#include <iostream>
using namespace std;
char exp[1000], temp[10];
int n, count1;
int eval(char *exp){
char str[1000], t;
int i, j, sum, temp;
char op = 0;
for(i = 0, j = 0; exp[i] != 0; i++){
if(exp[i] == '.' || exp[i] == ' ')continue;
str[j++] = exp[i];
}
str[j] = 0;
sum = 0;
i = 0;
while(str[i] != 0){
if(str[i] == '+' || str[i] == '-'){
op = str[i];
i++;
}else{
temp = atoi(str + i);
if(op == 0){
sum = temp;
}else if(op == '-'){
sum -= temp;
}else if(op == '+'){
sum += temp;
}
while(true){
if(str[i] == 0 || str[i] == '+' || str[i] == '-')break;
i++;
}
}
}
return sum;
}
void go1(int i, int rear){
int bits = i < 10 ? 1 : 2;
if(i < n){
sprintf(exp + rear, "%d + ", i);
go1(i + 1, rear + bits + 3);
sprintf(exp + rear, "%d - ", i);
go1(i + 1, rear + bits + 3);
sprintf(exp + rear, "%d . ", i);
go1(i + 1, rear + bits + 3);
}else if(i == n){
sprintf(exp + rear, "%d", i);
go1(i + 1, rear + bits);
}else{
if(eval(exp) == 0){
count1 ++;
if(count1 <= 20)
cout << exp << endl;
}
}
}
int main(){
int t;
cin >> t;
while(t--){
count1 = 0;
cin >> n;
go1(1, 0);
cout << count1 << endl;
}
return 0;
}
using namespace std;
char exp[1000], temp[10];
int n, count1;
int eval(char *exp){
char str[1000], t;
int i, j, sum, temp;
char op = 0;
for(i = 0, j = 0; exp[i] != 0; i++){
if(exp[i] == '.' || exp[i] == ' ')continue;
str[j++] = exp[i];
}
str[j] = 0;
sum = 0;
i = 0;
while(str[i] != 0){
if(str[i] == '+' || str[i] == '-'){
op = str[i];
i++;
}else{
temp = atoi(str + i);
if(op == 0){
sum = temp;
}else if(op == '-'){
sum -= temp;
}else if(op == '+'){
sum += temp;
}
while(true){
if(str[i] == 0 || str[i] == '+' || str[i] == '-')break;
i++;
}
}
}
return sum;
}
void go1(int i, int rear){
int bits = i < 10 ? 1 : 2;
if(i < n){
sprintf(exp + rear, "%d + ", i);
go1(i + 1, rear + bits + 3);
sprintf(exp + rear, "%d - ", i);
go1(i + 1, rear + bits + 3);
sprintf(exp + rear, "%d . ", i);
go1(i + 1, rear + bits + 3);
}else if(i == n){
sprintf(exp + rear, "%d", i);
go1(i + 1, rear + bits);
}else{
if(eval(exp) == 0){
count1 ++;
if(count1 <= 20)
cout << exp << endl;
}
}
}
int main(){
int t;
cin >> t;
while(t--){
count1 = 0;
cin >> n;
go1(1, 0);
cout << count1 << endl;
}
return 0;
}
欢迎扫码关注:
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。