为什么暴力可以拿60?

P8818 [CSP-S 2022] 策略游戏

@[slyzzsb](/user/488669) 我的也是60. ```cpp #include <bits/stdc++.h> #define maxn 100010 using namespace std; typedef long long ll; /* 先打暴力 选择一行即使是最小值也比其他行的最大值大的行数,这样能够达到要求 a数组负责提供行的字母,b数组.. */ int n; int m; int q; ll a[maxn]; ll b[maxn]; int l1,r1,l2,r2; ll get_val(int l_n,int r_n){ return a[l_n] * b[r_n]; } ll line_min(int l,int r,int line_number){ ll mi = get_val(line_number,l); //int mi_num; for(int i = l + 1; i <= r; i++){ if(mi > get_val(line_number,i)){ mi = get_val(line_number,i); //mi_num = i; } } return mi; } int main(){ //freopen("game.in","r",stdin); //freopen("game.out","w",stdout); //freopen("game3.in","r",stdin); //("game.out","w",stdout); cin >> n >> m >> q; for(int i = 1; i <= n; i++){ scanf("%lld",&a[i]); } for(int i = 1;i <= m; i++){ scanf("%lld",&b[i]); } for(int i = 0; i < q; i++){ scanf("%d %d %d %d",&l1,&r1,&l2,&r2); ll ma = -999999999999999999; int mi_line; for(int j = l1; j <= r1; j++){ //每行列举l2-r2的最小数 ll mi; mi = line_min(l2,r2,j); if(mi > ma){ mi_line = j; ma = mi; } } printf("%lld\n",ma); } fclose(stdin); fclose(stdout); return 0; } ```
by Stevehim @ 2022-10-29 20:34:48


@[slyzzsb](/user/488669) 小常数估计是可以过~~可你要面对超级慢的CCF评测机~~
by bamboo1030 @ 2022-10-29 20:35:06


几乎是q(r1-l1)(r2-l2)的复杂度啊
by IAKNOIP @ 2022-10-29 20:35:48


@[bamboo123](/user/369181) 人在SD不用面对()
by IAKNOIP @ 2022-10-29 20:36:26


@[slyzzsb](/user/488669) 看数据强度吧(虽然说CCF的数据一般都很水)
by bamboo1030 @ 2022-10-29 20:38:00


常数炒鸡小的树状数组能拿60吗(手动滑稽
by Hollow_knight_ @ 2022-10-29 20:53:07


@[Hollow_knight_](/user/546939) $qn\log n$ 的线段树暴力都有85 ![](//啧.tk/xyx)
by BFSDFS123 @ 2022-10-29 21:04:33


@[BFSDFS123](/user/358739) 我滴树状数组区间最值比较玄学,单词查询 $≤2log len $
by Hollow_knight_ @ 2022-10-29 21:11:02


但通常开销比递归少太多了(尤其是结构体线段树)
by Hollow_knight_ @ 2022-10-29 21:11:45


@[slyzzsb](/user/488669) 至少 40 会有,特殊性质 B 时间复杂度少个 n
by Nicrobot @ 2022-10-29 21:19:12


| 下一页