Task.1 Global warming (JZOJ 6310)
题目大意：给定整数 (n) 和 (x)，以及一个大小为 (n) 的序列 (a)。你可以选择一个区间 ([l,r])，然后令 (a[i]+=d(l<=i<=r))，其中 (d) 满足 (|d|<=x)。要求最大化 (a) 的最长上升子序列的长度，并输出该值。
数据范围：(Nleq200000,x,a_ileq10^9)
考虑把某段区间增加或减少了一个值之后答案会变成什么样：一定把前面的一部分上升子序列和后面的一部分上升子序列接起来，并且发现对某段区间 ([l,r]) 增减，扩展到对 ([1,l]) 或 ([r,n]) 一定不会让答案变差；而且前缀加减和后缀加减几种情况，都可以归纳为前缀加或者后缀加。加多少呢？对于一段前缀或者后缀肯定往多了加不会让答案变差，加多了可以选择的范围就变大了。
那么就只需要一个数据结构维护一下转移时用的最值，前后各做一遍然后枚举在哪个位置加就可以了。复杂度 (O(Nlog N))。
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
template<class T>void read(T &x){
x=0; bool f=0; char c=getchar();
while(c<'0'||'9'<c){f|=(c=='-'); c=getchar();}
while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
x=f?-x:x;
}
const int N=200005;
int n,d,ans;
int a[N],b[N<<2],m,t[N],c[N];
int f[N],g[N];
void cmax(int &x,int y){if(x<y)x=y;}
struct segt{
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
int s[N<<3];
void clear(){memset(s,0,sizeof(s));}
void pushup(int p){s[p]=max(s[p<<1],s[p<<1|1]);}
void upd(int x,int c,int l,int r,int p){
if(l==r){cmax(s[p],c); return ;}
int mid=(l+r)>>1;
if(x<=mid)upd(x,c,lson);
else upd(x,c,rson);
pushup(p);
}
int query(int L,int R,int l,int r,int p){
if(R<L)return 0;
if(L<=l&&r<=R) return s[p];
int mid=(l+r)>>1,res=0;
if(L<=mid)res=max(res,query(L,R,lson));
if(R>mid)res=max(res,query(L,R,rson));
return res;
}
}T;
void solve(){
sort(b+1,b+m+1); m=unique(b+1,b+m+1)-b-1;
for(int i=1;i<=n;i++){
t[i]=lower_bound(b+1,b+m+1,a[i])-b;
c[i]=lower_bound(b+1,b+m+1,a[i]+d)-b;
}
for(int i=1;i<=n;i++){
f[i]=T.query(1,t[i]-1,1,m,1)+1;
T.upd(t[i],f[i],1,m,1);
}
T.clear();
for(int i=n;i;i--){
g[i]=T.query(t[i]+1,m,1,m,1)+1;
T.upd(t[i],g[i],1,m,1);
}
T.clear();
for(int i=1;i<=n;i++){
T.upd(t[i],f[i],1,m,1);
cmax(ans,g[i+1]+T.query(1,c[i+1]-1,1,m,1));
}
printf("%d
",ans);
}
int main(){
freopen("glo.in","r",stdin);
freopen("glo.out","w",stdout);
read(n); read(d);
for(int i=1;i<=n;i++){
read(a[i]);
b[++m]=a[i];
b[++m]=a[i]+d;
}
solve();
return 0;
}
Task.2 Mobitel (JZOJ 6311)
题目大意：给定一个 (r) 行 (s) 列的矩阵，每个格子里都有一个正整数。问如果从左上角走到右下角，且每次只能向右或向下走到相邻格子，那么使得路径上所有数的乘积不小于 (n) 的路径有多少条？答案对 (10^9+7) 取模的结果。
数据范围：(1leq r,sleq300,1leq nleq10^6)，矩阵中的数不超过 (10^6)。
比较容易设计出状态 (F_{i,j,k}) 表示走到格子 ((i,j)) 时乘积为 (k) 的方案数，求问题的补集乘积小于等于 (n) 的方案数。但是这样状态数是 (O(NRS)) 的，时间和空间都不能接受，我们需要一种优化方法：根据除法分块，(lfloor frac{n}{i} floor) 的取值只有 (sqrt{n}) 种，试着用某个乘积 (k) 所在块来代替它本身。
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
template<class T>void read(T &x){
x=0; char c=getchar();
while(c<'0'||'9'<c)c=getchar();
while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
}
const int N=305;
const int NN=1000005;
const int M=1000000007;
int r,s,n;
int a[N][N];
int rk[2005],id[NN],cnt;
int f[2][N][2005];
int inv(int x){
int res=1,t=M-2;
while(t){
if(t&1)res=1ll*res*x%M;
x=1ll*x*x%M; t>>=1;
}return res;
}
int C(int x,int y){
int up=1,down=1;
if(y<x-y)y=x-y;
for(int i=y+1;i<=x;i++)
up=1ll*up*i%M;
if(y>x-y)y=x-y;
for(int i=1;i<=y;i++)
down=1ll*down*i%M;
return 1ll*up*inv(down)%M;
}
int main(){
freopen("mobitel.in","r",stdin);
freopen("mobitel.out","w",stdout);
read(r); read(s); read(n);
n--;
for(int i=1;i<=n;i++)if(rk[cnt]!=n/i){
rk[++cnt]=n/i;
id[n/i]=cnt;
}
for(int i=1;i<=r;i++)for(int j=1;j<=s;j++)read(a[i][j]);
int t;
bool now=0,pre=1;
f[0][1][1]=1;
for(int i=1;i<=r;i++){
swap(now,pre);
memset(f[now],0,sizeof(f[now]));
for(int j=1;j<=s;j++){
t=a[i][j];
for(int k=1;k<=cnt;k++){
f[now][j][id[rk[k]/t]]=(1ll*f[now][j][id[rk[k]/t]]+1ll*f[pre][j][k]+f[now][j-1][k])%M;
}
}
}
int sum=0;
for(int i=1;i<=cnt;i++)sum=(sum+f[now][s][i])%M;
printf("%d
",(C(r+s-2,s-1)-sum+M)%M);
return 0;
}
Task.3 Lottery (JZOJ 6312)
题目大意：定义两个序列对应位置上不同的值的个数不超过 (k)，则可称为 (k) 相似。
现在有一个长度为 (n) 的序列 (a)，将它划分为 (n−l+1) 个长度为 (l) 的子串（第 (i) 个子串为 (a[i]~a[i+l-1])）
(q) 组询问，第 (j) 组询问给出一个 (k_j)，求每个子串与多少个其它的子串可称为 (k_j) 相似。
数据范围：(k_jleq Lleq Nleq 10000,qleq 100,a_ileq10^9)
首先我们要知道，(O(N^2)) 是可以过 (10000) 的。
我们可以用两个滑动窗口在序列上滑的方法去 (O(1)) 从([l_1,r_1],[l_2,r_2]) 得到 ([l_1+1,r_1+1],[l_2+1,r_2+1]) 子串的相似度。每次从头滑到尾复杂度是 (O(N))，选择不同的([l_1,r_1],[l_2,r_2])，就可以 (O(N^2)) 得到所有子串两两的相似度。因为询问只有 (q) 次，所以空间上就开到 (O(Nq)) 存储排序后询问的答案即可。复杂度 (O(N^2))。
代码：what