论改题只用两分钟的速度QAQ
其实就是换了个数组名字，加上加了一句话
第一题：
首先考虑k=1的情况，考虑构造转移矩阵A
ans*(A^0+A^1+……+A^(n-1))
然后括号里的式子等比数列求和一下
是(A^0-A^n)/(A^0-A^1)
涉及到除法，手动矩阵求逆就可以了
然后这个式子就变成了一个矩阵
我们考虑k>1的情况，发现扩维不过就是又乘了一次这个矩阵
然后把这个矩阵自乘k次即可
(考试的时候犯傻，没有想到k>1的时候直接自乘k次就可以了，下午加了一句话就A了）
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int T,n,k;
LL f[1000010];
LL sum;
struct Matrix{
LL a[2][2];
void clear(){memset(a,0,sizeof(a));}
}A,B,C,ans;
void DFS(int num,int pos){
if(pos>k){
num=num-k+1;
sum+=f[num];
if(sum>=mod)sum-=mod;
return;
}
for(int i=1;i<=n;++i)DFS(num+i,pos+1);
}
Matrix operator *(const Matrix &A,const Matrix &B){
Matrix C;C.clear();
for(int i=0;i<2;++i){
for(int j=0;j<2;++j){
for(int k=0;k<2;++k){
C.a[i][j]=C.a[i][j]+A.a[i][k]*B.a[k][j]%mod;
if(C.a[i][j]>=mod)C.a[i][j]-=mod;
if(C.a[i][j]<0)C.a[i][j]+=mod;
}
}
}return C;
}
Matrix pow_mod(Matrix v,int p){
Matrix tmp;tmp.clear();
for(int i=0;i<2;++i)tmp.a[i][i]=1;
while(p){
if(p&1)tmp=tmp*v;
v=v*v;p>>=1;
}return tmp;
}
int main(){
scanf("%d",&T);
f[0]=0;f[1]=1;
for(int i=2;i<=1000000;++i){
f[i]=f[i-1]+f[i-2];
if(f[i]>=mod)f[i]-=mod;
}
while(T--){
scanf("%d%d",&n,&k);
A.clear();A.a[0][1]=1;A.a[1][0]=1;A.a[1][1]=1;
C=pow_mod(A,n);
for(int i=0;i<2;++i){
for(int j=0;j<2;++j){
C.a[i][j]=(i==j)-C.a[i][j];
if(C.a[i][j]<0)C.a[i][j]+=mod;
}
}
B.clear();B.a[0][1]=-1;B.a[1][0]=-1;B.a[1][1]=-1;
C=C*B;C=pow_mod(C,k);
ans.clear();ans.a[0][1]=1;ans=ans*C;
printf("%lld
",(ans.a[0][1]%mod+mod)%mod);
}return 0;
}
第二题显然是要树分治的
HEOI的思路，我们二分答案，把小于答案的设为-1，大于等于答案的设为1
我们很容易发现答案具有单调性，判断的话只需要判断树上是否有一条经过边数在[L,R]的长度>=0的边即可
然后就是树分治啦，注意这里如果每次用线段树查最大值
是O(nlog^3n)，30s是肯定能过的
不过可以优化，我们发现每次查最大值都是查定长区间的最大值，我们可以通过BFS使得dep有序化，之后做单调队列就可以优化到O(nlog^2n)
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100010;
const int oo=0x7fffffff/3;
int n,L,R;
int A,B;
int h[maxn],cnt=0;
struct edge{
int to,next,w;
}G[maxn<<1];
struct Edge{
int u,v,w;
}c[maxn];
bool vis[maxn];
int f[maxn],g,sum;
int w[maxn],top=0;
struct OP{
int dep,dis;
}st[maxn];
int tim=0;
struct Seg_Tree{
int mx,t;
}t[maxn<<2];
void add(int x,int y,int z){
++cnt;G[cnt].to=y;G[cnt].next=h[x];G[cnt].w=z;h[x]=cnt;
}
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void UPD(int o,int L,int R,int p,int v){
if(L==R){
if(t[o].t!=tim){
t[o].t=tim;
t[o].mx=v;
}else t[o].mx=max(t[o].mx,v);
return;
}
int mid=(L+R)>>1;
int A=(o<<1),B=(A|1);
if(p<=mid)UPD(A,L,mid,p,v);
else UPD(B,mid+1,R,p,v);
t[o].t=tim;
A=(t[A].t==tim?t[A].mx:-oo);
B=(t[B].t==tim?t[B].mx:-oo);
t[o].mx=max(A,B);
}
int ask(int o,int L,int R,int x,int y){
if(L>=x&&R<=y){
if(t[o].t!=tim)return -oo;
return t[o].mx;
}
int mid=(L+R)>>1;
if(y<=mid)return ask(o<<1,L,mid,x,y);
else if(x>mid)return ask(o<<1|1,mid+1,R,x,y);
else return max(ask(o<<1,L,mid,x,y),ask(o<<1|1,mid+1,R,x,y));
}
void cmax(int &a,int b){if(b>a)a=b;}
void Get_G(int u,int fa){
f[u]=0;w[u]=1;
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(v==fa||vis[v])continue;
Get_G(v,u);
w[u]+=w[v];
cmax(f[u],w[v]);
}cmax(f[u],sum-w[u]);
if(f[g]>f[u])g=u;
}
void Get_dis(int u,int f,int d,int D){
++top;st[top].dep=d;st[top].dis=D;
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v]||v==f)continue;
Get_dis(v,u,d+1,D+G[i].w);
}return;
}
bool Get_div(int u){
vis[u]=true;tim++;
UPD(1,0,n,0,0);
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v])continue;
top=0;Get_dis(v,-1,1,G[i].w);
for(int j=1;j<=top;++j){
int dep=st[j].dep,dis=st[j].dis;
int A=L-dep,B=R-dep;
if(B<0)continue;
if(A<0)A=0;
int now=ask(1,0,n,A,B);
if(now+dis>=0)return true;
}
for(int j=1;j<=top;++j)UPD(1,0,n,st[j].dep,st[j].dis);
}
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v])continue;
g=0;sum=w[v];
Get_G(v,-1);
if(Get_div(g))return true;
}return false;
}
bool check(){
memset(vis,false,sizeof(vis));
f[0]=oo;g=0;sum=n;
Get_G(1,-1);
if(Get_div(g))return true;
return false;
}
int main(){
read(n);read(L);read(R);
A=oo;B=-oo;
for(int i=1;i<n;++i){
read(c[i].u);read(c[i].v);read(c[i].w);
A=min(A,c[i].w);B=max(B,c[i].w);
}
while(A<B){
int mid=A+((B-A+1)>>1);
memset(h,0,sizeof(h));cnt=0;
for(int i=1;i<n;++i){
if(c[i].w>=mid)add(c[i].u,c[i].v,1),add(c[i].v,c[i].u,1);
else add(c[i].u,c[i].v,-1),add(c[i].v,c[i].u,-1);
}
if(check())A=mid;
else B=mid-1;
}
printf("%d
",A);
return 0;
}
第三题这么丝薄的题目我因为end是系统关键字挂掉了！
没有人跟我说啊喂！以后再也不用英文单词了！
还是HEOI的题目的变形
我们差分之后倍长，多出来的那一半是原来差分的序列的取反情况
之后我们建出反串的SAM
对于每次询问，在后一半找到取反的序列，在前一半查询有多少的位置和他的LCP>=len
可以直接搞出parent树之后用树状数组维护DFS序+倍增找位置就可以了
注意到区间不能重叠，也就是对前一半的区间有限制，我们把树状数组换成可持久化线段树就可以啦
时间复杂度O(nlogn)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<map>
using namespace std;
const int maxn=400010;
const int oo=0x7fffffff;
int n,cnt,la,m,L,R;
int a[maxn],b[maxn];
int P[maxn];
int h[maxn],c=0;
int pos[maxn],ed[maxn],tot=0;
int dep[maxn];
int anc[maxn][20];
struct edge{
int to,next;
}G[maxn];
struct Node{
map<int,int>nxt;
int len,link;
}st[maxn];
int rt[maxn],sum;
struct Seg_Tree{
int L,R,v;
}t[11000010];
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void add_edge(int x,int y){
c++;G[c].next=h[x];G[c].to=y;h[x]=c;
}
int add(int c){
int cur=++cnt;
st[cur].len=st[la].len+1;
int p;
for(p=la;p!=-1&&!st[p].nxt.count(c);p=st[p].link)st[p].nxt[c]=cur;
if(p==-1)st[cur].link=0;
else{
int q=st[p].nxt[c];
if(st[q].len==st[p].len+1)st[cur].link=q;
else{
int clone=++cnt;
st[clone]=st[q];st[clone].len=st[p].len+1;
for(;p!=-1&&st[p].nxt[c]==q;p=st[p].link)st[p].nxt[c]=clone;
st[q].link=st[cur].link=clone;
}
}la=cur;return la;
}
void build_Graph(){
for(int i=1;i<=cnt;++i)add_edge(st[i].link,i);
}
void Get_DFS(int u,int f){
pos[u]=++tot;
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(v==f)continue;
dep[v]=dep[u]+1;
Get_DFS(v,u);
}ed[u]=tot;
}
void pre_LCA(){
for(int i=0;i<=cnt;++i){
anc[i][0]=st[i].link;
for(int j=1;(1<<j)<=cnt;++j)anc[i][j]=-1;
}
for(int j=1;(1<<j)<=cnt;++j){
for(int i=0;i<=cnt;++i){
if(anc[i][j-1]!=-1){
int a=anc[i][j-1];
anc[i][j]=anc[a][j-1];
}
}
}return;
}
void build(int &o,int L,int R){
o=++sum;
if(L==R)return;
int mid=(L+R)>>1;
build(t[o].L,L,mid);
build(t[o].R,mid+1,R);
}
void UPD(int &o,int L,int R,int p){
t[++sum]=t[o];o=sum;
if(L==R){t[o].v++;return;}
int mid=(L+R)>>1;
if(p<=mid)UPD(t[o].L,L,mid,p);
else UPD(t[o].R,mid+1,R,p);
t[o].v=t[t[o].L].v+t[t[o].R].v;
}
int ask(int o,int L,int R,int x,int y){
if(L>=x&&R<=y)return t[o].v;
int mid=(L+R)>>1;
if(y<=mid)return ask(t[o].L,L,mid,x,y);
else if(x>mid)return ask(t[o].R,mid+1,R,x,y);
else return ask(t[o].L,L,mid,x,y)+ask(t[o].R,mid+1,R,x,y);
}
int Get_pos(int u,int len){
int log;
for(log=0;(1<<log)<=dep[u];++log);--log;
for(int i=log;i>=0;--i){
if(anc[u][i]!=-1&&st[anc[u][i]].len>=len)u=anc[u][i];
}return u;
}
/*void print(){
for(int i=0;i<=cnt;++i){
for(map<int,int>::iterator it=st[i].nxt.begin();it!=st[i].nxt.end();++it){
printf("%d %d %d
",i,(it->first),(it->second));
}printf("
");
}return;
}*/
int main(){
read(n);cnt=la=0;st[0].link=-1;
for(int i=1;i<=n;++i)read(a[i]);
n--;
for(int i=1;i<=n;++i)b[i]=a[i+1]-a[i];
b[n+1]=oo;
for(int i=n+2;i<=(n<<1)+1;++i)b[i]=-b[i-n-1];
n=(n<<1|1);
for(int i=n;i>=1;--i)P[i]=add(b[i]);
//print();
build_Graph();Get_DFS(0,-1);pre_LCA();
build(rt[0],1,tot);
for(int i=1;i<=n;++i){
rt[i]=rt[i-1];
UPD(rt[i],1,tot,pos[P[i]]);
}
read(m);
for(int i=1;i<=m;++i){
read(L);read(R);
if(L==R){printf("%d
",(n>>1));continue;}
int v=Get_pos(P[L+(n>>1)+1],R-L);
int A,B,C;L=L-(R-L+1);
A=ask(rt[(n>>1)],1,tot,pos[v],ed[v]);
B=ask(rt[R],1,tot,pos[v],ed[v]);
if(L<0)C=0;
else C=ask(rt[L],1,tot,pos[v],ed[v]);
B=B-C;A=A-B;
printf("%d
",A);
}return 0;
}
今天考试非常的不开心
lemon和网站上同时卡了我end的关键字，第三题爆零了
lemon还是在win下测得，第二题还挂了两个点的栈空间
第一题上午也是丝薄了，忘记自乘k次了QAQ
UPD:感觉考试暴露了自己一些弱点
1、矩阵求逆不太会写
2、树分治用单调队列优化不熟练
3、对于矩阵的概念和应用不了解
今天需要做的题目：
1、51NOD 约数之和(完成)
2、BZOJ 矩阵求逆的裸题
3、WC 重建计划(完成)
4、ZJOI 细胞(完成)
一些要做但是可以暂时坑掉的题目：
1、生日聚会
2、棋盘制作(完成)
3、各种面积并，面积交以及求周长
4、基站选址
5、最小割