题解 P2089 【烤鸡】

2016-11-30 19:14:24


P2089题解

如果这道题是输出所有方案,再输出方案数,那么这道题将变得很容易。

但是,这要先输出方案数,再输出答案,因此需要考虑怎样将其存起来。

做法

方法很简单,就是深搜、枚举,甚至连剪枝都可以不用。这道题的奥妙在于输出。

怎样将方案存起来

我们的方法是,将这个东西输出到字符串中。

sprintf函数

sprintf函数的作用是将数据输出到字符串中,用法大概如下:

#include <cstdio>
int main(){
    char buf[100];
    int a, b;
    scanf("%d%d", &a, &b);
    sprintf(buf, "%d", a + b);
    puts(buf);
    return 0;
}

直接交上去可以通过P1001 A+B Problem

如果对同一字符串多次使用sprintf,会怎样呢?

#include <cstdio>
int main(){
    char buf[100];
    int a, b;
    scanf("%d%d", &a, &b);
    sprintf(buf, "%d", a + b);
    sprintf(buf, "%d", a + b);
    puts(buf);
    return 0;
}

交上去也能过A+B。这说明,sprintf会覆盖原字符串。

如何往字符串末尾输出字符串?我们有另外的方法。

假如说一个字符串s存储了"Hello, world",其结构将会如下:

s[0] = 'H';
s[1] = 'e';
s[2] = 'l';
s[3] = 'l';
s[4] = 'o';
s[5] = ',';
s[6] = ' ';
s[7] = 'w';
s[8] = 'o';
s[9] = 'r';
s[10]= 'l';
s[11]= 'd';
s[12]= '!';
s[13]= '\0';
s[14]= '"未定义"'
s[15]= '"未定义"'
s[16]= '"未定义"'
// 省略一堆……

我们只要找到字符串的末尾(也就是'\0'),将字符串末尾看成一个字符串的开头,然后sprintf进去,就可以往字符串末尾添加字符串了。

因此,我们的方法是,找到'\0'的位置,将它视为字符串的开头,然后用sprintf输出到旧的'\0'开始的位置,取代'\0'及之后的位置。

比如:

int main(){
    char c[100] = "abc";
    sprintf(c + 3, "defgh%s%s", "ijklmnopqrst", "uvwxyz");
    puts(c);
}

在上面的例子中,c + 3是'\0'的位置(因为strlen("abc") == 3,而strlen恰好是'\0'的下标),这样可以实现在末尾添加字符串的功能。

方案1:strlen函数

strlen可以直接找到'\0'的下标。由此,我们有第一代的程序:

#include<cctype>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 13;

char ans[1000000 + 5];
char *anscur = ans;
int nums[maxn];                    // 当前调料 
int cnt = 0;                    // 方案数 

void printans(){
    for(int i = 0; i < 10; i++){
        sprintf(ans + strlen(ans), "%d ", nums[i]);
    }
    sprintf(ans + strlen(ans), "\n");
}

void dfs(int cur, int left){    // 深搜过程 
    if(cur == 10 && !left){        // 已经搜到第10层,这个时候调料恰好加完 
        cnt++;                    // 方案数+1 
        printans();                // 将方案输出到字符串里面 
        return;
    } 
    int &i = nums[cur];            // 声明别名(引用) 
    for(i = 1; i <= 3; i++){
        if((10 - cur - 1) * 3 + i < left) continue;    // 剪枝。如果剩下的调料都加3克都不够,说明不可能 
        if((10 - cur - 1) + i > left) break;        // 剪枝。如果剩下的调料都加一克也超量,说明不可能 
        dfs(cur + 1, left - i); 
    }
}

int main(){
    int n;
    scanf("%d", &n);

    if(10 <= n && n <= 30) dfs(0, n);// 如果n不在[10, 30]范围内,说明不可能有解,跳过搜索 
    printf("%d\n%s", cnt, ans);        //输出答案 
}

交上去提示AC,最高时间263ms。

方案2:使用stringstream

stringstream在高手眼里看来,是没什么用的。它非常灵活,但效率低下。我们来看看它的效率如何。

#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<sstream>
using namespace std;

const int maxn = 13;

ostringstream ans;
int nums[maxn];                    // 当前调料 
int cnt = 0;                    // 方案数 

void printans(){
    for(int i = 0; i < 10; i++){
        ans << nums[i] << " ";
    }
    ans << endl;
}

void dfs(int cur, int left){    // 深搜过程 
    if(cur == 10 && !left){        // 已经搜到第10层,这个时候调料恰好加完 
        cnt++;                    // 方案数+1 
        printans();                // 将方案输出到字符串里面 
        return;
    } 
    int &i = nums[cur];            // 声明别名(引用) 
    for(i = 1; i <= 3; i++){
        if((10 - cur - 1) * 3 + i < left) continue;    // 剪枝。如果剩下的调料都加3克都不够,说明不可能 
        if((10 - cur - 1) + i > left) break;        // 剪枝。如果剩下的调料都加一克也超量,说明不可能 
        dfs(cur + 1, left - i); 
    }
}

#include<iostream>

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;

    if(10 <= n && n <= 30) dfs(0, n);// 如果n不在[10, 30]范围内,说明不可能有解,跳过搜索          
    cout << cnt << endl << ans.str();// 输出答案
}

遗憾的是,结果是RE,我也不知道为什么。

方案3:直接计算新的'\0'位置

strlen虽然已经过了这道题,但是还是有优化的余地。如果能直接计算'\0'的位置,那么就可以节省时间。

我们考虑使用指针,该指针指向ans字符串的'\0'位置。

int版


#include<cctype>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 13;

char ans[1000000 + 5];
int anscur = 0;
int nums[maxn];                    // 当前调料 
int cnt = 0;                    // 方案数 

void printans(){
    for(int i = 0; i < 10; i++){
        sprintf(ans + strlen(ans), "%d ", nums[i]);
        anscur += strlen(ans + anscur);
    }
    sprintf(ans + strlen(ans), "\n");
    anscur += strlen(ans + anscur);
}

// 省略了

char* 版

#include<cctype>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 13;

char ans[1000000 + 5];
char *anscur = ans;
int nums[maxn];                    // 当前调料 
int cnt = 0;                    // 方案数 

void printans(){
    for(int i = 0; i < 10; i++){
        sprintf(ans + strlen(ans), "%d ", nums[i]);
        anscur += strlen(anscur);
    }
    sprintf(ans + strlen(ans), "\n");
    anscur += strlen(anscur);
}

这样就可以更快了。

方案4:printf中的%n控制符

上述的方法还是要再进行一次计算才能知道当前的指针。能否在sprintf的同时计算出新的指针呢?这是可能的。

printf家族中,有一个控制符%n——这个东西非常有用,意思是我到底输出了多少个字符。怎么用呢?

char s[100];
int cnt;
sprintf(s, "abcdefg%n", &cnt);

一共输出了7个字符,此时cnt存储了7。

最终版的程序如下:

#include<cctype>
#include<cstdio>

using namespace std;

const int maxn = 13;

char ans[1000000 + 5];
char *anscur = ans;
int nums[maxn];                    // 当前调料 
int cnt = 0;                    // 方案数 

void printans(){
    int offset;
    for(int i = 0; i < 10; i++){
        sprintf(anscur, "%d %n", nums[i], &offset);
        anscur += offset;
    }
    sprintf(anscur, "\n%n", &offset);
    anscur += offset;
}

void dfs(int cur, int left){    // 深搜过程 
    if(cur == 10 && !left){        // 已经搜到第10层,这个时候调料恰好加完 
        cnt++;                    // 方案数+1 
        printans();                // 将方案输出到字符串里面 
        return;
    } 
    int &i = nums[cur];            // 声明别名(引用) 
    for(i = 1; i <= 3; i++){
        if((10 - cur - 1) * 3 + i < left) continue;    // 剪枝。如果剩下的调料都加3克都不够,说明不可能 
        if((10 - cur - 1) + i > left) break;        // 剪枝。如果剩下的调料都加一克也超量,说明不可能 
        dfs(cur + 1, left - i); 
    }
}

int main(){
    int n;
    scanf("%d", &n);

    if(10 <= n && n <= 30) dfs(0, n);// 如果n不在[10, 30]范围内,说明不可能有解,跳过搜索 
    printf("%d\n%s", cnt, ans);        //输出答案 
}

最终用时34ms,最长一个点10ms,快了差不多几十倍。