7.17

F

认真读题吧

A

算法一:

\(c = ab,x = a + b + c\)

所以

\(x = a + b + ab\)

\(=(b + 1)a + b\)

所以我们枚举\(b\)

\(O(1)\)check了

但是这样是\(O(x)\)

之后我们由

\(x = a + b + ab\)可得

\(ab<=x\)

由于\(a,b\)本质相同

所以\(min(a,b)<=\sqrt{x}\)

所以我们枚举到\(\sqrt{x}\)就好了

算法二:

我们由\(x = a + b + ab\)可得

\(x + 1 = (a + 1) (b + 1)\)

C

我们发现我们直接括号匹配,求左括号在左,右括号在右的答案就好了.

D

我们设

\(40\)分:

\(f_{l,r}\)表示\(l,r\)表示\(l-r\)之间的答案

如果\(l, r\)能够匹配

则有\(f_{l,r} = f_{l+1,r-1}+2\)

否则

\(f_{l,r} = max(f_{l+1,r},f_{l,r - 1})\)

这样就有40分了

\(k = 2\):

我们发现,其实每一对数就是一个区间

我们要寻找的是嵌套的最大的不相交的区间

左端点排序之后,实质上是求右端点的最长递减子序列

所以求一下右端点的LIS就可以了

之后我么推广到k<=4,发现将所有可能的区间进行上述操作即可,因为要求单调递减所以不可能存在同一个数被选择两次

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype> 
#include<vector> 
using namespace std;
const int N = 5e5 + 3;
struct node{
    int li,ri,v;    
}q[N << 1];
vector <int> G[N];
int tot,maxx;
int a[N],f[N];
int sum[N];
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar(); 
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;   
        ch = getchar();
    }
    return v * c;
}
int n,m,k;
struct BIT{
    int c[N];
    inline void clear(){memset(c,0,sizeof(c));}
    inline void updata(int x,int v){
        for(;x <= n;x += x & -x) c[x] = max(c[x],v);
    }
    inline int query(int x){
        int res = 0;
        for(;x;x -= x & -x) res = max(res,c[x]);
        return res; 
    }
}T;
inline bool cmp(node x,node y){
    if(x.li != y.li) return x.li < y.li;
    return x.ri < y.ri; 
}
int main(){
    int tt = read();
    while(tt--){
        memset(sum,0,sizeof(sum));
        int ans = 0;
        n = read(),k = read();tot = 0;  
        T.clear();memset(f,0,sizeof(f));
        for(int i = 1;i <= 100000;++i) G[i].clear();
        for(int i = 1;i <= n;++i) {
            a[i] = read();
            q[++tot] = (node){i,i,1};
            for(int j = 0;j < (int)G[a[i]].size();++j)
            q[++tot] = (node){G[a[i]][j],i,2};
            G[a[i]].push_back(i);
        }
        sort(q + 1,q + tot + 1,cmp);
        for(int i = 1;i <= tot;++i){
            f[i] = max(f[i],T.query(n - q[i].ri + 1 - 1) + q[i].v);
            T.updata(n - q[i].ri + 1,f[i]);
            ans = max(ans,f[i]);
        }
        printf("%d\n",ans);
    }
    return 0;   
}

E

此类题目一般要旋转坐标系!!!

首先,我们考虑一下\(n^2\)做法

我们旋转坐标系之后,求出每一条直线有矩形的交点,然后把交点进行旋转.

之后我们发现每一条线与矩形的交点旋转之后是可以求出的

这样的话,线段就变成了只有\(x,y,d\)三个参数的

如果是竖着的,就\(d\)行,从\(x\)\(y\)

横着同理

之后我们发现

我们在枚举竖着的之后,可以将符合条件的加入BIT查询即可,由于查询的是横着的线段在这个区间内的数量

而任意两条线段,所以要\(ans + C^2_{x}\)

\(nlogn\)

我们发现,要求的其实就是\(\sum_{l + 1}^rC_x^2\)

所以考虑线段树扫描线,在加入横着线段的同时维护区间的\(\sum_{l + 1} ^rC_x^2\)的答案

\(C_{x + k}^2 = C_{x}^2+x*k+C^2_k\)

所以我们要维护区间\(x\)的和,区间长度,以及区间\(C_{x}^2\)的和

但是注意一点:

在下方标记的时候,要先更新区间\(C_x^2\)的值,因为它的值是受之前的\(\sum x\)影响的

同时此题离散化的是由,由于使用了upper_bound缩小的范围

所以只能先排序,然后边用便利离散化

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cctype>
#include<vector>
#include<algorithm>
#include<queue>
#define LL long long
#define mk make_pair
#define pii pair<LL,LL>
using namespace std; 
const int N = 2e5 + 3;
const LL INF = 1e15;
const LL mod = 1e9 + 7;
vector <pii> G1;
LL A[N],B[N];
inline LL mo(LL x){
    if(x >= mod) x -= mod;
    if(x < 0) x += mod;
    return x;
}
inline LL read(){
    LL v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar(); 
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;   
        ch = getchar();
    }
    return v * c;
}
inline LL get(LL x,LL k,LL len,LL s1){
    return (k * (k - 1) / 2 * len % mod + x + s1 * k % mod) % mod;  
}
struct tree{
    int t;
    struct node{
        int lc,rc;
        LL s1,s2;
        LL tag;
    }a[N << 1];
    inline void pushup(int u){
        a[u].s1 = (a[a[u].lc].s1 + a[a[u].rc].s1) % mod;
        a[u].s2 = (a[a[u].lc].s2 + a[a[u].rc].s2) % mod;    
    }
    inline void build(int u,int l,int r){
        if(l == r) return ;
        int mid = (l + r) >> 1;
        a[u].lc = ++t;
        build(a[u].lc,l,mid);
        a[u].rc = ++t;
        build(a[u].rc,mid + 1,r);   
        pushup(u);
    }
    inline void pushdown(int u,int l,int r){
        if(!a[u].tag) return ;
        int mid = (l + r) >> 1; 
        a[a[u].lc].s2 = get(a[a[u].lc].s2,a[u].tag,mid - l + 1,a[a[u].lc].s1);
        a[a[u].rc].s2 = get(a[a[u].rc].s2,a[u].tag,r - mid,a[a[u].rc].s1);
        a[a[u].lc].s1 = (a[a[u].lc].s1 + a[u].tag * (mid - l + 1)) % mod;
        a[a[u].rc].s1 = (a[a[u].rc].s1 + a[u].tag * (r - mid)) % mod;
        a[a[u].lc].tag = mo(a[a[u].lc].tag + a[u].tag);
        a[a[u].rc].tag = mo(a[a[u].rc].tag + a[u].tag);
        a[u].tag = 0;
    }
    inline void updata(int u,int l,int r,int ll,int rr,int w){
    //  printf("%d %d %d %lld %lld\n",u,l,r,a[u].s1,a[u].s2);
        if(l == ll && r == rr){
            a[u].s2 = get(a[u].s2,w,r - l + 1,a[u].s1);
            a[u].s1 = (a[u].s1 + r - l + 1) % mod;
            a[u].tag = mo(a[u].tag + w);
            return ;    
        }
        pushdown(u,l,r);
        int mid = (l + r) >> 1;
        if(rr <= mid) updata(a[u].lc,l,mid,ll,rr,w);
        else if(ll > mid) updata(a[u].rc,mid + 1,r,ll,rr,w);
        else {
            updata(a[u].lc,l,mid,ll,mid,w);
            updata(a[u].rc,mid + 1,r,mid + 1,rr,w); 
        }
        pushup(u);
    }
    inline int query(int u,int l,int r,int ll,int rr){
        if(ll > rr) return 0;
        if(l == ll && r == rr) return a[u].s2;
        pushdown(u,l,r);
        int mid = (l + r) >> 1;
        if(rr <= mid) return query(a[u].lc,l,mid,ll,rr);
        else if(ll > mid) return query(a[u].rc,mid + 1,r,ll,rr);
        else return (query(a[u].lc,l,mid,ll,mid) + query(a[u].rc,mid + 1,r,mid + 1,rr)) % mod; 
    }
}T;
LL w,h;
int n,m;
LL a[N],b[N];
struct line{
    LL li,ri;
        LL di;  
};
line x[N],y[N];
int main(){
    int tot = 0;
    w = read(),h = read(),n = read(),m = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i <= m;++i) b[i] = read();
    for(int i = 1;i <= n;++i){
        x[i].di = a[i];
        B[i] = a[i];    
    }
    for(int i = 1;i <= m;++i){
        LL p1=min(w+h,min(2*w-b[i],2*h+b[i]));
        LL p2=max(0ll,max(-b[i],b[i]));
    //  .push_back(mp(p2,p1));
        y[i].ri = p1;
        y[i].li = p2;
    }
//  for(int i = 1;i <= n;++i) printf("%d ",x[i].di);puts("");
//  for(int i = 1;i <= m;++i) printf("%d %d\n",y[i].li,y[i].ri);
    sort(B + 1,B + n + 1);
    B[0] = unique(B + 1,B + n + 1) - B - 1;
    for(int i = 1;i <= n;++i) //x[i].di = lower_bound(B + 1,B + B[0] + 1,x[i].di) - B,
    G1.push_back(mk(x[i].di,INF));
    for(int i = 1;i <= m;++i){
    //  y[i].li = upper_bound(B + 1,B + B[0] + 1,y[i].li) - B - 1;
    //  y[i].ri = upper_bound(B + 1,B + B[0] + 1,y[i].ri) - B - 1;
        G1.push_back(mk(y[i].li,y[i].ri));
    //  G1[y[i].li].push_back(y[i].ri);
    //  G2[y[i].ri].push_back(y[i].li);
    }
    sort(G1.begin(),G1.end());
//  for(int i = 0;i < (int)G1.size();++i) printf("%lld %lld\n",G1[i].first,G1[i].second);
    T.t = 1;
    T.build(1,1,n);
    LL ans = 0;
    for(int i = 0;i < (int)G1.size();++i){
        if(G1[i].first > G1[i].second) continue;
        
        if(G1[i].second == INF){
            G1[i].first = lower_bound(B + 1,B + B[0] + 1,G1[i].first) - B;
            if(G1[i].first < n) ans = (ans + T.query(1,1,n,G1[i].first + 1,n)) % mod;
        }
        else{
            G1[i].second = upper_bound(B + 1,B + B[0] + 1,G1[i].second) - B - 1; 
            if(G1[i].second >= 1) T.updata(1,1,n,1,G1[i].second,1);
        }
    //  cout << ans << endl;
    }
    cout << ans << endl;
    return 0;   
}