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

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

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

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

//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%,这个可以理解。。。

#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.树状数组求前缀和。

#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,我竟无言以对。暴力比树状数组快,这数据出的挺好的。。。