Solved:3

Rank:105

治哥出题了 我感动哭了

 

F Planting Trees

题意:500x500的矩阵 求一个最大的子矩阵 使得区间最大减最小<=M

题解:枚举纵坐标的区间 对于每一个区间 从第一行开始 单调尺取搞一搞

#include 
      
       using namespace std;int a[505][505];int zd[505];int zx[505];int qd[505];int qx[505];int main() {    int T;    scanf("%d", &T);    while(T--) {        int n, m;        scanf("%d%d", &n, &m);        for(int i = 1; i <= n; i++) {            for(int j = 1; j <= n; j++)                scanf("%d", &a[i][j]);        }        int ans = 1;        for(int j = 1; j <= n; j++) {            for(int k = 1; k <= n; k++) {                zx[k] = 1e5 + 5;                zd[k] = 0;            }            for(int k = j; k <= n; k++) {                for(int i = 1; i <= n; i++) {                    zd[i] = max(zd[i], a[i][k]);                    zx[i] = min(zx[i], a[i][k]);                }                int lx = 1, rx = 0;                int ld = 1, rd = 0;                int nowl = 1;                for(int i = 1; i <= n; i++) {                    while(lx <= rx && zx[qx[rx]] >= zx[i]) rx--;                    qx[++rx] = i;                    while(ld <= rd && zd[qd[rd]] <= zd[i]) rd--;                    qd[++rd] = i;                    while(nowl <= i && zd[qd[ld]] - zx[qx[lx]] > m) {                        nowl++;                        while(lx <= rx && qx[lx] < nowl) lx++;                        while(ld <= rd && qd[ld] < nowl) ld++;                    }                    if(nowl <= i && zd[qd[ld]] - zx[qx[lx]] <= m) {                        ans = max(ans, (k - j + 1) * (i - nowl + 1));                    }                }            }        }        printf("%d\n", ans);    }    return 0;}
      

 

G Removing Stones

题意:n堆石子 每次可以选择两堆不同的各拿走一个 如果能拿完 就表示获胜

　　 如果石子的和为奇数 则将最少的一堆石子数-1

　　 问有多少对区间 能获胜

题解:显然 题目等于 计算 区间max * 2 <= 区间和的个数

　　 考虑反问题 计算max * 2 > 区间和

　　 然后直接暴力枚举每个点作为最大值 往前搞搞 往后搞搞

　　 巧妙的是这样的时间复杂度其实并不高 要让这样暴力枚举的时间复杂度退化到n方的数据 显然是ai >= ai+1  * 2

　　 举个例子长度为5的数组 16 8 4 2 1 能让暴力枚举的复杂度退化到n方 但是ai < 1e9

　　 均摊一下每个数的平均枚举到log

#include 
      
       using namespace std;typedef long long ll;ll a[300005];ll pre[300005];int main() {    int T;    scanf("%d", &T);    while(T--) {        ll n;        scanf("%lld", &n);        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);        ll ans = 0;        for(int i = 1; i <= n; i++) {            int cnt = 0;            pre[0] = 0;            for(int j = i + 1; j <= n; j++) {                pre[++cnt] = a[j];                pre[cnt] += pre[cnt - 1];                if(pre[cnt] >= a[i]) {                    cnt--;                    break;                }            }            ans += cnt;            ll sum = 0;            for(int j = i - 1; j >= 1; j--) {                sum += a[j];                if(sum >= a[i]) break;                ans++;                int l = 0, r = cnt;                int mid = l + r >> 1;                while(l + 1 < r) {                    mid = l + r >> 1;                    if(sum + pre[mid] < a[i]) l = mid;                    else r = mid;                }                if(sum + pre[r] < a[i]) ans += r;                else ans += l;            }        }        ans = n * (n - 1) / 2 - ans;        printf("%lld\n", ans);    }    return 0;}