当前位置: 首页 > news >正文

P10960 SUBSTRACT 个人题解

题目传送门

题目大意:

给定一个数组 \(a\) ,可以选择一个下标 \(i\) ,使 \(a[i]=a[i]-a[i+1]\) 并删去 \(a[i+1]\) ,使得数组最后剩下的数为 \(t\) ,输出每次操作的 \(i\)

解题方法:

我们把题目给出的这种操作命名为减操作,可以发现对于最终答案 \(t\) ,我们可以转化成这样 \(t=a[1]−a[2]±a[3]±······±a[n]\) 的形式。可以发现 \(a[1]\) 必须是 \(+\) 号, \(a[2]\) 必须是 \(-\) 号,首先我们来看 \(a[1]\) 必须是 \(+\) 号:因为减操作是前面一个数减去后面一个数,而 \(a[1]\) 前面没有数,所以他一定不会被减去,即一定是 \(+\) 号,因此最后一次减操作一定是对 \(i=1\) 进行的;而 \(a[2]\) 必须是 \(-\) 号是因为最后一次减操作一定是对 \(i=1\) 进行的,那 \(a[2]\) 一定是最后被减去的,所以一定是 \(-\) 号。

举一个 \(n=5\) 的例子(即样例):
原数组: \(a[1]~~a[2]~~a[3]~~a[4]~~a[5]\)
\(i=2\) 进行减操作: \(a[1]~~a[2]-a[3]~~a[4]~~a[5]\)
\(i=3\) 进行减操作:\(a[1]~~a[2]−a[3]~~a[4]−a[5]\)
\(i=2\) 进行减操作:\(a[1]~~a[2]−a[3]-(a[4]−a[5])\)
\(i=1\) 进行减操作:\(a[1]-(a[2]−a[3]-(a[4]−a[5]))\)
则处理完的数组为:\(a[1]−a[2]+a[3]+a[4]−a[5]\)

那么题目就被我们转换成给定一个数组,把数组中几个数变成其相反数,使最后加和成为 \(t\),那么就可以做了,我们用 \(f[i][j]\) 表示前 \(i\) 个数和为 \(j\) 时第 \(i\) 个数的符号( \(1\)\(-1\)),由于 C++ 的负号好像挂了,我们给每个数加上 \(10000\) ,保证下标为正数。

那么怎么反推出每一次的减操作呢?其实我也不会(),但是根据其他大佬的题解以及个人理解,我们可以发现除了 \(a[1]\)\(a[2]\) 以外
对于一个数,前面不是正号,就是负号,即\(\begin{cases}a[i]−a[i+1]\\a[i−1]−a[i]\end{cases}\)
说明只有当第 \(i-1\) 位进行减操作的时候,这个第 \(i\) 位才可以是负号,同理当第 \(i\) 位进行减操作的时候,这个第 \(i\) 位才可以是正号,那么我们可以每次找到正号的位置输出,不过记得要减去 \(cnt-1\)\(cnt\) 代表进行了几次减操作)。

注意到 \(1\le n \le100,1\le|T|\le10^4\),所以时间复杂度为 \(O(n|T|)\) ,在 \(10^6\) 级别内可以通过。

本题代码:

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=10005,MAXN=20086;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}//快读 
int low=10000;//给每个数加上low以保证下标为正数 
int n=read(),t=read(),f[N][MAXN],a[N],ans[N],s,cnt;
int main(){for(int i=1;i<=n;i++)a[i]=read();f[1][a[1]+low]=1;//a[1]只能为正 f[2][a[1]-a[2]+low]=-1;//a[2]只能为负 for(int i=3;i<=n;i++){for(int j=-10000+low;j<=10000+low;j++){if(f[i-1][j]){f[i][j-a[i]]=-1;f[i][j+a[i]]=1;}}}s=t+low;for(int i=n;i>=2;i--){//回溯减操作过程 ans[i]=f[i][s];if(ans[i]==1)s-=a[i];else if(ans[i]==-1)s+=a[i];}for(int i=2;i<=n;i++){//寻找正号位置输出 if(ans[i]==1){printf("%d\n",i-cnt-1);cnt++;	//减操作数+1 }}for(int i=2;i<=n;i++)//把负号输出 if(ans[i]==-1)puts("1");return 0;
}
http://www.hskmm.com/?act=detail&tid=28886

相关文章:

  • 牛客网刷题
  • 2025新型千斤顶厂家推荐:柳州市联桥科技,品质卓越服务到位
  • 2025深圳网站建设推荐:华企网络专业定制,助力企业线上腾飞
  • 2025石头纸设备批发厂家推荐鼎浩包装,环保高效生产首选!
  • 2025液压阀块供货厂家最新推荐榜:品质卓越与高效服务的行业
  • 2025年PP鱼池优质厂家推荐:超众渔业机械,环保耐用首选!
  • centos安装atop工具,检测服务器情况
  • 完整教程:MongoDB Ops Manager部署
  • 2025医疗器械微弧氧化优质厂家推荐,华源漆业技术领先服务到
  • 2025气柱袋优质厂家推荐:戈尔德包装,防护包装解决方案专家
  • 【网络协议】SSL与TLS的关系 - 教程
  • 2025深圳网站建设公司最新推荐榜:创意设计与专业服务引领者
  • 2025年安全光栅厂家最新推荐榜:精准防护与高效性能的工业首
  • 2025七水硫酸锌实力厂家推荐:安通环保科技,品质卓越信赖之
  • 20232306刘博2025-2026-1《网络与系统攻防技术》实验一实验报告
  • 软件工程学习日志2025.10.10
  • 2025智能照明系统直销厂家推荐:八渡科技,智慧生活首选!
  • 2025磁力泵厂家最新推荐榜:高效稳定与优质服务的首选指南
  • 最小乘积模型与快速凸包构造学习笔记
  • 记录---图文并茂讲解nginx中http升级https(部署SSL证书)知识点总结
  • 2025网络营销推广TOP5榜单:精准引流与高效转化的营销专
  • 控制自然语言生成中的模型幻觉技术
  • 基于 Scala 的英文数字验证码识别系统设计与实现
  • 2025智能防爆灯厂家最新推荐榜:安全高效与技术创新典范
  • CSP-S模拟29
  • 2025新型液压阀块定制厂家推荐,美泰克精密机械匠心打造!
  • commitlint Lint 提交消息格式控制
  • 2025氢氧化镁供应厂家推荐:辽宁润辉新材料科技优质厂家首选
  • 2025年离心曝气机源头工厂哪家强?离心曝气机知名厂家哪家好?
  • 2025整平机厂家最新推荐榜:高效精准与耐用品质的行业首选!