大家好,我是 i64,我非常喜欢暴力算法,于是我用暴力通过了这道题。
1. 无优化
用基本 C++ 语法可以写出这段代码:
#include<iostream>
using namespace std;
#define int long long
const int maxn = 100010;
int a[maxn];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (m--) {
int opt;
cin >> opt;
if (opt == 1) {
int l, r, x;
cin >> l >> r >> x;
for (int i = l;i <= r;i++) {
if (a[i] % x == 0) {
a[i] /= x;
}
}
}
if (opt == 2) {
int l, r;
cin >> l >> r;
int ans = 0;
for (int i = l;i <= r;i++) {
ans += a[i];
}
cout << ans << endl;
}
}
return 0;
}
加上 O2,恭喜喜提 36pts。
关 cin&cout 同步流
#include<iostream>
using namespace std;
const int maxn = 100010;
int a[maxn];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (m--) {
int opt;
cin >> opt;
if (opt == 1) {
int l, r, x;
cin >> l >> r >> x;
for (int i = l;i <= r;i++) {
!(a[i]%x)?a[i]/=x:0;
}
}
if (opt == 2) {
int l, r;
cin >> l >> r;
long long ans = 0;
for (int i = l;i <= r;i++) {
ans += a[i];
}
cout << ans << endl;
}
}
return 0;
}
恭喜,你又喜提 88pts。我们离 AC 很近了。
加上快读快写和循环展开一下(10 位)
#include<iostream>
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(long long x) {
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
const int maxn = 100010;
int a[maxn];
int opt;
int n, m;
int l, r, x;
long long ans = 0;
int i;
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
n = read(), m = read();
for (i = 1; i <= n; i++) {
a[i] = read();
}
while (m--) {
opt = read();
if (opt == 1) {
l = read(), r = read(), x = read();
for (i = l;i <= r - 10;i += 11) {
!(a[i]%x)?a[i]/=x:1;
!(a[i+1]%x)?a[i+1]/=x:1;
!(a[i+2]%x)?a[i+2]/=x:1;
!(a[i+3]%x)?a[i+3]/=x:1;
!(a[i+4]%x)?a[i+4]/=x:1;
!(a[i+5]%x)?a[i+5]/=x:1;
!(a[i+6]%x)?a[i+6]/=x:1;
!(a[i+7]%x)?a[i+7]/=x:1;
!(a[i+8]%x)?a[i+8]/=x:1;
!(a[i+9]%x)?a[i+9]/=x:1;
!(a[i+10]%x)?a[i+10]/=x:1;
}
while(r-i+1) {
!(a[i]%x)?a[i]/=x:1;
i++;
}
}
if (opt == 2) {
ans = 0;
l = read(), r = read();
for (i = l;i <= r-10;i += 11) {
ans+=a[i]+a[i+1]+a[i+2]+a[i+3]+a[i+4]+a[i+5]+a[i+6]+a[i+7]+a[i+8]+a[i+9]+a[i+10];
}
while(r-i+1) {
ans+=a[i];
i++;
}
write(ans);
puts("");
}
}
return 0;
}
恭喜喜提 97pts,只差一个点就 AC 了,再优化一下。
改成 5 位一展开
#include <iostream>
using namespace std;
inline int read() {
register int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
void write(register long long x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
const int maxn = 100010;
int a[maxn];
signed main() {
register int opt;
register int n, m;
register int l, r, x;
register long long sum = 0;
register int i;
n = read(), m = read();
for (i = 1; i <= n; i++) {
a[i] = read();
}
while (m--) {
opt = read();
if (opt == 1) {
l = read(), r = read(), x = read();
if (x == 1) continue;
if (x == 2) {
for (i = l; i <= r - 5; i += 6) {
!(a[i] & 1) ? a[i] >>= 1 : 1;
!(a[i + 1] & 1) ? a[i + 1] >>= 1 : 1;
!(a[i + 2] & 1) ? a[i + 2] >>= 1 : 1;
!(a[i + 3] & 1) ? a[i + 3] >>= 1 : 1;
!(a[i + 4] & 1) ? a[i + 4] >>= 1 : 1;
!(a[i + 5] & 1) ? a[i + 5] >>= 1 : 1;
}
while (r - i + 1) {
!(a[i] & 1) ? a[i] >>= 1 : 1;
i++;
}
continue;
}
for (i = l; i <= r - 5; i += 6) {
!(a[i] % x) ? a[i] /= x : 1;
!(a[i + 1] % x) ? a[i + 1] /= x : 1;
!(a[i + 2] % x) ? a[i + 2] /= x : 1;
!(a[i + 3] % x) ? a[i + 3] /= x : 1;
!(a[i + 4] % x) ? a[i + 4] /= x : 1;
!(a[i + 5] % x) ? a[i + 5] /= x : 1;
}
while (r - i + 1) {
!(a[i] % x) ? a[i] /= x : 1;
i++;
}
}
if (opt == 2) {
sum = 0;
l = read(), r = read();
for (i = l; i <= r - 5; i += 6) {
sum +=
a[i] + a[i + 1] + a[i + 2] + a[i + 3] + a[i + 4] + a[i + 5];
}
while (r - i + 1) {
sum += a[i];
i++;
}
write(sum);
puts("");
}
}
return 0;
}
恭喜,你喜提 AC。