P10960 题解

Nasaepa · 2024-08-30 15:21:58 · 题解

Part 0 介绍

这道题是一道稍微有点烧脑的题目，考虑 dp + 模拟。

Part 1 题意转化

对于这样一个多项式：

我们可以往这个多项式上任意地套括号例如把它变成这样：

那它化开后就会变成这样：

我们通过多次尝试就会发现，在多次操作后，除了 a_1 和 a_2 ，所有数字前的符号都可以任意变换，而 a_1 的符号一定为正，a_2 的符号一定为负。

并且，这种不断套括号的操作也和题目中要求进行的操作等价。这样，问题就被我们转化成了这样：

给定一个长度为 n 的序列 a， a_1 的符号为正，a_2 的符号为负，a_3 \sim a_n 的符号可以自由变换，求使序列所有值和为 t 的方法。

Part 2 动态规划

非常简单的 dp。

我们定义 dp_{i,j} 表示在考虑第 i 个数字符号时，a_1 \sim a_i 所有值的总和等于 j 需要 a_i 的符号取正号还是负号，如果是正号，则 dp_{i,j} = 1，如果为负号，则 dp_{i,j} = -1，如果转移不了一点，则 dp_{i,j} = 0。

如果 dp_{(i-1),j} \ne 0，则 dp_{i,(j + a_i)} = 1，dp_{i,(j - a_i)} = -1。

而 i = 1 或者 i = 2 的情况需要特殊考虑，这是因为 a_1 的符号一定为正而 a_2 的符号一定为负。

而且我们也知道，在极限情况下，所有数字的和总是在 [-10000,10000] 区间内，但是数组如果下标取负数会 RE。我们可以通过映射把 [-10000,10000] 映射到 [0,20000]。

映射的代码实现如下：

inline int get(const int &x){// 将 -10000 ~ 10000 映射到 0 ~ 20000
    return x + 10000;
}

状态转移的代码实现如下：

dp[1][get(a[1])] = 1;
dp[2][get(a[1] - a[2])] = -1;
for(int i = 3;i <= n;++i){
    for(int j = -10000;j <= 10000;++j){
        // 只保证自己可以到达
        if(dp[i-1][get(j)] == 0)continue;
        dp[i][get(j + a[i])] = 1;
        dp[i][get(j - a[i])] = -1;
    }
}

Part 3 模拟溯源

如果 dp_{i,j} = 1，则可以确定其由 dp_{i-1,(j - a_i)} 转移而来。如果 dp_{i,j} = -1，则可以确定其由 dp_{i-1,(j + a_i)} 转移而来。我们可以提前定义 c 数组储存每个数字的符号。其代码实现如下：

// 往回溯源，得到操作
w = t;
for(int i = n;i >= 2;--i){
    c[i] = dp[i][get(w)];
    if(c[i] == -1)w += a[i];
    else w -= a[i];
}

Part 4 输出

最烧脑的部分来了。

假设对于这样一个式子：

我们可以让每一个符号为加号的数字 a_i 被 a_{i-1} 减去，然后 a_{i-1} 减完后再被 a_{i-2} 减去。

我们就可以这样转化我们的式子：

符号为正的数字可以直接被它的前一个数字减去，当所有符号为正的数字都消失了，我们就直接用 a_1 减去剩下的数字。我们要注意，在符号为正的数字被删除后，其后面的所有数字都会向前移一位。因此我们需要记录被删除的数字数量以计算出被减去的数字的实际下标。

代码实现如下：

int cnt = 0;// 有多少个数字被删除了
for(int i = 2;i <= n;++i){
    if(c[i] == 1){
        printf("%d\n",i - cnt - 1);
        ++cnt;
    }
}
// 最后输出被减的部分
for(int i = 2;i <= n;++i){
    if(c[i] == -1)printf("1\n");// 直接上 1
}

Part 5 完整的代码

// #pragma GCC optimize(2) // 开启O2优化
#include<bits/stdc++.h>
using namespace std;
#define N 110
#define INF 0x3f3f3f3f // 无穷大
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define func function<void()>
int n,t;
int dp[N][30010];// dp[i][j] 表示到达数字 j 需要加还是减少
inline int get(const int &x){// 将 -10000 ~ 10000 映射到 0 ~ 20000
    return x + 10000;
}
int a[N],w;
int c[N];// 每一步需要进行的操作

// 输入函数
void input(){
    scanf("%d%d",&n,&t);
    for(int i = 1;i <= n;++i)scanf("%d",a+i);
    // 前两个数字必然第一个加，第二个减
    dp[1][get(a[1])] = 1;
    dp[2][get(a[1] - a[2])] = -1;
}

// 处理函数
void solve(){
    // 处理每个数字
    for(int i = 3;i <= n;++i){
        for(int j = -10000;j <= 10000;++j){
            // 只保证自己可以到达
            if(dp[i-1][get(j)] == 0)continue;
            dp[i][get(j + a[i])] = 1;
            dp[i][get(j - a[i])] = -1;
        }
    }
    // 往回溯源，得到操作
    w = t;
    for(int i = n;i >= 2;--i){
        c[i] = dp[i][get(w)];
        if(c[i] == -1)w += a[i];
        else w -= a[i];
    }
}

// 输出函数
void output(){
    // 输出
    // 先输出被加的部分，如果被加了就是被减了 2 次负负得正
    int cnt = 0;// 有多少个数字被删除了
    for(int i = 2;i <= n;++i){
        if(c[i] == 1){
            printf("%d\n",i - cnt - 1);
            ++cnt;
        }
    }
    // 最后输出被减的部分
    for(int i = 2;i <= n;++i){
        if(c[i] == -1)printf("1\n");// 直接上 1
    }
}

// 主函数
int main(int argc,char* argv[]){
    input();
    solve();
    output();
    return 0;
}