CCF傻逼题，201709-5-除法---暴力可以过？？？？？

发表于 | 更新于 | 阅读次数：
本文字数： 4.5k | 阅读时长 ≈ 4 分钟

这题特么无语，史上最无语没有之一，C++纯暴力过 90？？？？，JAVA纯暴力过了？？？？？？？？？？？？，tell me ，发生了什么，这题为什么能暴力。

CCF如果JAVA熟练，建议大家用JAVA。

http://118.190.20.162/view.page?gpid=T59

JAVA纯暴力AC代码。。。。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 //import java.lang.reflect.Array;
import java.math.*;
import java.util.Arrays;
import java.util.Scanner;

//import om.sun.swing.internal.plaf.basic.resources.basic;



public class Main {
	static int[] a= new int[100005];
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt(),m = input.nextInt();
		for(int i= 1 ; i <= n ; i ++) {
			a[i] = input.nextInt();
		}
		int op,l,r,v;
		for(int j=0;j<m;j++) {
//			
			op = input.nextInt();
			l = input.nextInt();
			r = input.nextInt();
			if(op==1) {
				
				v = input.nextInt();
				if(v == 1)continue;
				for(int i = l ; i <= r; i ++) {
					if(a[i] >= v && a[i] % v == 0) {
						a[i] /= v;
					}
				}
				
			}
			else {
//				l=input.nextInt();
//				r=input.nextInt();
				long ans=0;
				for(int i=l;i<=r;i++) {
					ans += a[i];
				}
				System.out.println(ans);
			}
		}
//		System.out.println(ans);
	}
}

C++纯暴力，过 90%，这个可以理解。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>

using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> P;

const long long mod=1e9+7;
const int maxn=1e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int A[maxn];
int n,m;
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%d",&A[i]);
    }
    while(m--) {
        int op,l,r,v;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1) {
            scanf("%d",&v);
            if(v==1)continue;
            while(l<=r) {
                if(A[l]>=v&&A[l]%v==0) {
                    A[l]/=v;
                }
                l++;
            }
        } else {
            long long ans=0;
            while(l<=r) {
                ans+=A[l++];
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

C++，AC代码。也是半个暴力。因为每个数去除最多只能除 32次，（因为数的最大值只有1e6,每次就算只除2，也不能除多少次，所以这个更新可以暴力，并不会超时。复杂度最高也只有 32 N logN,重点在于处理前缀和），不会再多，所以只需要用一个树状数组维护前缀和即可，每次更新值，直接暴力能不能除，然后再更新值即可。

考察两点：1.暴力更新值（注意特判除1），2.树状数组求前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>

using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> P;

const long long mod=1e9+7;
const int maxn=1e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int A[maxn];
long long  bit[maxn];
int n,m;
long long  sum(int i) {
    long long  ans=0;
    while(i>0) {
        ans+=bit[i];
        i-=i&-i;
    }
    return ans;
}

void add( int i, int x) {
    while(i<=n) {
        bit[i]+=x;
        i += i&-i;
    }
}


int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%d",&A[i]);
        add(i,A[i]);
    }
    while(m--) {
        int op,l,r,v;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1) {
            scanf("%d",&v);
            if(v==1)continue;
            while(l<=r) {
                if(A[l]>=v&&A[l]%v==0) {
                    add(l,0-A[l]+A[l]/v);
                    A[l]/=v;
                }
                l++;
            }
        } else {
            printf("%lld\n",sum(r)-sum(l-1));
        }
    }
    return 0;
}

细心的孩子，肯定一定发现了。。。。。。。。。，JAVA暴力，6s 。C++树状数组7s，我竟无言以对。暴力比树状数组快，这数据出的挺好的。。。