Question

c++超时了

1011. 说反话
时间限制

1000 ms

内存限制

65536 kB

代码长度限制

8192 B

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。要求创建一个Sentence类

输入格式：测试输入包含多个测试用例，每个用例占一行，在每一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用1个空格分开，输入保证句子末尾没有多余的空格。

输出格式：输出倒序后的句子。
输入样例：
Hello World Here I Come
Hello

输出样例：
Come I Here World Hello
Hello
下面是代码，不知道为什么超时？
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
class Sentence
{
public:
char c[100];int l,j,i,a,b,d;
Sentence(char b[])
{
l=strlen(b);j=0;
for(i=0;i<l;i++)
c[i]=b[i];
}
void display()
{
a=b=l;d=0;
for(i=l-1;i>0;i--)
{
if(c[i]==' ')
{
b=a;a=i;
for(j=a+1;j<b;j++)
cout<<c[j];
d=1;cout<<' ';
}
}
if(d==1)
{
for(i=0;i<a;i++){cout<<c[i];}
cout<<endl;
}
else
{
for(i=0;i<l;i++)
cout<<c[i];
cout<<endl;
}

}
};
int main()
{
char b[100];
while(1)
{
gets(b);
Sentence s(b);
s.display();
}
return 0;
}

Answer 1

数量过大，所以每次都在数组上进行操作 肯定会TLE的
三种操作中 3操作为纯输出 不用管
1 2 操作分别是取相反数和加上固定值A
也就是*-1和+A
这样1操作可以认为是*-1+0
2操作可以认为是*1+A
这样对于关于1 2的操作序列O1-On 设定每次的操作为S1-Sn(Sk=-1或1) 和A1-An(Ak为0或任意整数)
那么设定原始序列为a1 a2 .. an
计算后的序列为
(((ak*S1+A1)*S2+A2)*S3+A3)... *Sn+An
=ak*S1*S2*...*Sn + A1*S2*S3*...Sn+... +A(n-1)*Sn+An
也就是说 对于每一项的原始值 只需要计算最终的符号就可以，对于附加项，只需要不断累加并乘上每次操作的符号即可
这样单独开一个变量存A及累加A 一个变量存符号变化并随时与A相乘
每次输出计算一次就可以

而计算累加上 也可以采用更高效的算法
对于数列a1 a2 ... an
原始数组存S1 S2 S3 ... Sn 其中Sk=a1+a2+...ak
令S0=0
那么求操作3 s e(从as累加到ae就是)Se-S[s-1]
按照这个思路写程序 最终获得
#include <stdio.h>long long list[100001];int main(){ int n, m; long long add = 0; int sign = 1; int i,j; int s, e; scanf("%d%d", &n, &m); for(i = 1; i <= n; i ++) { scanf("%lld", &list[i]); if(i)list[i]+= list[i - 1]; } for(i = 0; i < m; i ++) { scanf("%d", &j); if(j == 1) { sign *= -1; add *= -1; } else if(j == 2) { scanf("%d", &s); add += s; } else if(j == 3) { scanf("%d%d",&s, &e); printf("%lld\n",(list[e]-list[s-1])*sign + add*(e-s+1)); } }}
这样可以么？

追问

你确定这个不是随便复制的？看不懂！