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
",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
",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
",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
",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;
}