Lvat_s Blog

线段树大水题

#include<cstdio>
 
int n,m;
long long k[200005],b[200005];
const long long Mod=1000000007ll;
 
struct SegTree{
long long k,b;
int l,r;
}tree[1000005];
 
void Pushup(int rt){
tree[rt].k=tree[rt*2].k*tree[rt*2+1].k%Mod;
tree[rt].b=(tree[rt*2+1].b+tree[rt*2+1].k*tree[rt*2].b%Mod)%Mod;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].k=k[l]%Mod;tree[rt].b=b[l]%Mod;return;}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
Pushup(rt);
}
 
void Modify(int rt,int pos,long long k,long long b){
if(tree[rt].l==tree[rt].r){tree[rt].k=k%Mod;tree[rt].b=b%Mod;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Modify(rt*2,pos,k,b);
if(pos>mid)Modify(rt*2+1,pos,k,b);
Pushup(rt);
}
 
long long Query(int rt,int l,int r,long long x){
if(l<=tree[rt].l && tree[rt].r<=r){return (tree[rt].k*x%Mod+tree[rt].b)%Mod;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return Query(rt*2+1,l,r,x)%Mod;
else if(r<=mid)return Query(rt*2,l,r,x)%Mod;
return Query(rt*2+1,l,r,Query(rt*2,l,r,x)%Mod)%Mod;
}
 
int main(){
freopen("4499.in","r",stdin);
freopen("4499.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%lld %lld",&k[i],&b[i]);
}
Build(1,1,n);
for(int i=1;i<=m;i++){
    char s[5];
    long long l,r,v;
    scanf("%s %lld %lld %lld",s,&l,&r,&v);
    if(s[0]=='M')Modify(1,(int)l,r,v);
    else printf("%lld\n",Query(1,(int)l,(int)r,v));
}
return 0;
}

奇怪的二分+LCP

orz rky 考场上直接后缀平衡树秒掉

orz lyz 随手后缀数组秒掉

orz 两位2h AK SDOI2016 Day2的神犇

高二大爷们和wyx全AK了简直太可怕

因为我不敢写后缀数组（因为只写过2次），所以考场上GG咯

回来补一个二分LCP的做法

首先我们考虑两个后缀A,B对答案的贡献(已经按字典序排序)

贡献是$|A|+|B|-LCP(A,B)$

那么我们用一个set动态维护就可以了

每次插入一个字符一定会多一个后缀

然后我们在set里面找一找前驱后继算一下就好了

下面是rky的神·题解

-------------------------------------------------

-------------------------------------------------

orz 你萌都会后缀+平衡树。。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;

typedef long long LL;

const int N=100005;
const LL P=1e9+7;

int n,a[N];
LL Pow[N],Hash[N],ans;

LL GetHash(int l,int r){return (Hash[l]-Hash[r+1])*Pow[n-l];}

int LCP(int a,int b){
if(a>b)a^=b^=a^=b;
int l=0,r=n-b+2,ans=0;
while(l+1<r){
	int mid=l+r>>1;
	if(GetHash(a,a+mid-1)!=GetHash(b,b+mid-1)){r=mid;}
	else {l=mid;ans=mid;}
}
return ans;
}

struct Cmp{
bool operator()(int A,int B){
int Lcp=LCP(A,B);
if(B+Lcp>n)return 0;
if(A+Lcp>n)return 1;
return a[A+Lcp]<a[B+Lcp];
}
};

set<int,Cmp> St;

void Solve(){
for(int i=n;i;i--){
	set<int,Cmp>::iterator It,Pre,Nxt;
	Hash[i]=Hash[i+1]+a[i]*Pow[i];
	It=St.insert(i).first;
	Pre=It;Pre--;Nxt=It;Nxt++;
	ans+=n-i+1;
	if(It!=St.begin())ans-=LCP(*Pre,*It);
	if(Nxt!=St.end())ans-=LCP(*It,*Nxt);
	if(It!=St.begin() && Nxt!=St.end())ans+=LCP(*Pre,*Nxt);
	printf("%lld\n",ans);
}
}

template<typename T> void Read(T &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("4516.in","r",stdin);
freopen("4516.out","w",stdout);
Read(n);
for(int i=n;i;i--)Read(a[i]);
Pow[0]=1ll;
for(int i=1;i<=n;i++)Pow[i]=Pow[i-1]*P;
Solve();
return 0;
}

斜率优化DP，和玩具装箱很像。。。基本是裸的

注：那个Bf函数是暴力DP，可以参考一下和下面Upper函数(斜率优化DP)的共同点

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;

int first,last,Que[30005];
long long n,m,f[3005][3005],a[3005];

void Bf(){
for(int i=1;i<=n;i++){
	f[i][1]=a[i]*a[i];
	for(int j=2;j<=m;j++){
		f[i][j]=f[i][j-1];
		for(int k=1;k<i;k++){
			f[i][j]=min(f[i][j],f[k][j-1]+(a[i]-a[k])*(a[i]-a[k]));
		}
	}
}
printf("%lld\n",m*f[n][m]-a[n]*a[n]);
}

bool DelFirst(int q1,int q2,int i,int j){
return f[q1][j-1]+a[q1]*a[q1]-2ll*a[q1]*a[i]>f[q2][j-1]+a[q2]*a[q2]-2ll*a[q2]*a[i];
}

bool DelLast(int q1,int q2,int i,int j){
return (f[q1][j-1]+a[q1]*a[q1]-f[q2][j-1]-a[q2]*a[q2])*(a[i]-a[q2])<(f[q2][j-1]+a[q2]*a[q2]-f[i][j-1]-a[i]*a[i])*(a[q2]-a[q1]);
}

void Upper(){
for(int i=1;i<=n;i++)f[i][1]=a[i]*a[i];
for(int j=2;j<=m;j++){
	f[1][j]=a[1]*a[1];
	first=1;
	last=0;
	Que[++last]=1;
	for(int i=2;i<=n;i++){
		while(first<last && DelFirst(Que[first],Que[first+1],i,j))first++;
		f[i][j]=f[Que[first]][j-1]+(a[Que[first]]-a[i])*(a[Que[first]]-a[i]);
		while(first<last && DelLast(Que[last-1],Que[last],i,j))last--;
		Que[++last]=i;
	}
}
printf("%lld\n",m*f[n][m]-a[n]*a[n]);
}

int main(){
freopen("4518.in","r",stdin);
freopen("4518.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++){
	long long x;
	scanf("%lld",&x);
	a[i]=a[i-1]+x;
}
Upper();
return 0;
}

首先我们知道答案是$C(n,m)*Perm(n-m)$

$Perm(x)$表示为$x$的错排方案数

($n$个数里面选$m$个数作为稳定点，其余点均不在自己的位置上)

错排公式:$Perm(x)=(x-1)Perm(x-1)Perm(x-2)$

考场上这个想了很久。。。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;

const int N=1000005;
const long long Mod=1e9+7;
const long double eps=1e-10;

int T;
long long Pv[N+1],Px[N+1],Cu[N+1],m,n;

long long Qpow(long long A,long long B){
long long base=A,ans=1;
while(B){
	if(B&1)ans=ans*base%Mod;
	base=base*base%Mod;
	B>>=1;
}
return ans;
}

void Prepare(){
long long s=1;
Px[0]=1;
Pv[0]=1;
for(int i=1;i<=N;i++){
	s=s*i%Mod;
	Pv[i]=s;
	Px[i]=Qpow(s,Mod-2);
}
Cu[0]=1;
Cu[1]=0;
Cu[2]=1;
for(long long i=3;i<=N;i++)Cu[i]=(Cu[i-1]+Cu[i-2])%Mod*(i-1)%Mod;
}

long long C(long long a,long long b){
return Pv[a]*Px[b]%Mod*Px[a-b]%Mod;
}

int main(){
freopen("4517.in","r",stdin);
freopen("4517.out","w",stdout);
scanf("%d",&T);
Prepare();
while(T--){
	scanf("%lld %lld",&n,&m);
	printf("%lld\n",C(n,m)*Cu[n-m]%Mod);
}
return 0;
}

神转化。。。

首先我们考虑因为每一次只会知道奇偶性，所以我们对于一个区间[l,r]是否有球至少保证要知道[l...r]全部的奇偶性才可以判定每个杯子下面是否有球。（意味着如果每个杯子抽象成点，那么这些点之间必须全部连通才会知道每个杯子下面是否有球）

因为要费用最少，所以我们每次选择费用最小且有用的边加上去

然后就变成了最小生成树了。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,en,h[2005],cnt,f[2005];
long long ans=0;

struct Edge{
int a,b,v;
friend bool operator<(Edge a,Edge b){return a.v<b.v;}
}e[4000005];

void AddEdge(int sa,int sb,int sc){
e[++en].a=sa;
e[en].b=sb;
e[en].v=sc;
}

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){f[sb]=sa;}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("3714.in","r",stdin);
freopen("3714.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	for(int j=i;j<=n;j++){
		int x;
		scanf("%d",&x);
		AddEdge(i,j+1,x);
	}
}
sort(e+1,e+en+1);
for(int i=1;i<=n+1;i++)f[i]=i;
for(int i=1;i<=en && cnt<=n;i++){
	if(Find(e[i].a)!=Find(e[i].b)){Union(Find(e[i].a),Find(e[i].b));ans+=(long long)e[i].v;cnt++;}
}
printf("%lld\n",ans);
return 0;
}

今天考试考了一个斜率优化DP，一大群人A了。。

这让从没写过斜率优化的我情何以堪

所以我就把这题写了。。

感觉还是很好理解的：维护最优决策，再维护决策单调性

顺便Orz lyz rky今天AK了省选模拟

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
 
int n,first,last;
long long L,s[50005],dp[50005],q[500005],C;
 
bool DelFirst(int a,int b,int c){
return dp[a]+(s[c]-s[a]-C)*(s[c]-s[a]-C)>dp[b]+(s[c]-s[b]-C)*(s[c]-s[b]-C);
}
 
bool DelLast(int a,int b,int c){
return (dp[a]-dp[b]+s[a]*s[a]-s[b]*s[b])*(s[c]-s[b])<(dp[b]-dp[c]+s[b]*s[b]-s[c]*s[c])*(s[b]-s[a]);
}
 
int main(){
freopen("1010.in","r",stdin);
freopen("1010.out","w",stdout);
scanf("%d %d",&n,&L);
C=L+1;
for(int i=1;i<=n;i++){
    long long x;
    scanf("%lld",&x);
    s[i]=s[i-1]+x;
}
for(int i=1;i<=n;i++)s[i]+=i;
first=1;
last=0;
q[++last]=0;
for(int i=1;i<=n;i++){
    while(first<last && DelFirst(q[first],q[first+1],i))first++;
    dp[i]=dp[q[first]]+(s[i]-s[q[first]]-C)*(s[i]-s[q[first]]-C);
    while(first<last && DelLast(q[last-1],q[last],i))last--;
    q[++last]=i;
}
printf("%lld\n",dp[n]);
return 0;
}

首先，如果一个串可以被分割成两个串且这两个串均满足条件，那么这个串一定满足条件。

证明:$a=0(mod$ $m)$,$b=0(mod$ $m)$则$a*x+b*y=0(mod$ $m)$（显然）

那么我们只要统计有多少种满足情况的子串就可以了，设数目为$k$，然后方案数就是$2^k$

注意如果最后原串不满足条件就要输出0（显然原串不满足那么拆成的子串中至少有一个不满足该性质）

说了这么多，其实特别好写。。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,ans=0,len;
const int Mod=1e9+7;

int main(){
freopen("4421.in","r",stdin);
freopen("4421.out","w",stdout);
scanf("%d %d",&n,&m);
char ch;
while((ch=getchar())<'0' || ch>'9');
if((ch-'0')%m==0)ans=1;
len=ch-'0';
while((ch=getchar())>='0' && ch<='9'){
	len=(len*10+ch-'0')%m;
	if(len==0){
		if(ans==0)ans=1;
		else ans=ans*2%Mod;
	}
}
printf("%d\n",len==0?ans:0);
return 0;
}

Hash乱搞大法好

我先用一个伪随机序列然后每次排序随便判断

每次记录三个哈希值然后进行奇怪的运算就A掉了

怀疑很容易被卡掉。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int Smod=999973;
const long long Lmod1=666666666666667ll,Lmod2=233333333333333ll;

int cnt,en,m,h[1000005],H[55],n;
long long rnd[105],sum[105];

struct Hash{
long long lhash1,lhash2;
int next,v;
}ha[10000005];

void AddHash(int s,long long l1,long long l2,int x){
ha[++cnt].lhash1=l1;
ha[cnt].lhash2=l2;
ha[cnt].v=x;
ha[cnt].next=h[s];
h[s]=cnt;
}

int FindHash(int s,long long l1,long long l2){
for(int i=h[s];i;i=ha[i].next){
	if(ha[i].lhash1==l1 && ha[i].lhash2==l2)return i;
}
return 0;
}

struct Edge{
int b,next;
}e[1005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=H[sa];
H[sa]=en;
}

void Dfs(int u,int fa){
long long St[105];
int siz=0;
St[++siz]=233;
for(int i=H[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa)continue;
    Dfs(v,u);
    St[++siz]=sum[v];
}
sort(St+1,St+siz+1);
sum[u]=0;
for(int i=1;i<=siz;i++)sum[u]+=St[i]*rnd[i];
}

int main(){
freopen("4337.in","r",stdin);
freopen("4337.out","w",stdout);
scanf("%d",&m);
rnd[0]=233;
for(int i=1;i<=100;i++)rnd[i]=rnd[i-1]*99973ll+7;
for(int i=1;i<=m;i++){
	en=0;
	memset(H,0,sizeof(H));
	memset(sum,0,sizeof(sum));
	scanf("%d",&n);
	for(int j=1;j<=n;j++){
		int x;
		scanf("%d",&x);
		if(x){AddEdge(x,j);AddEdge(j,x);}
	}
	int ans1=0;
	long long ans2=0,ans3=77;
	for(int j=1;j<=n;j++){Dfs(j,0);ans1=ans1+sum[j];ans2=ans2^sum[j];ans3=ans3*sum[j];}
	ans1=max(ans1,-ans1);
	ans1=ans1%Smod+7;
	int dx=FindHash(ans1,ans2,ans3);
	if(!dx){AddHash(ans1,ans2,ans3,i);printf("%d\n",i);}
	else printf("%d\n",ha[dx].v);
}
return 0;
}

暴力的计算几何

暴力求出每一条线段，暴力比较是否能构成矩形

注意要long long不要double否则会炸精度

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
 
const int N=1505;
typedef long long LL;
 
int n,cnt;
LL ans; 
 
struct Point{
LL x,y;
Point(){}
Point(LL xs,LL ys){x=xs;y=ys;}
friend bool operator==(Point A,Point B){return A.x==B.x & A.y==B.y;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
friend LL operator*(Point A,Point B){return A.y*B.x-A.x*B.y;}
friend bool operator<(Point A,Point B){return A.x<B.x || (A.x==B.x && A.y<B.y);}
}poi[N];
 
LL Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
Point MidPoint(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
 
struct Line{
Point a,b,mid;
LL dis;
Line(){}
Line(Point A,Point B,Point MID,LL DIS){a=A;b=B;mid=MID;dis=DIS;}
friend bool operator<(Line A,Line B){
return A.dis<B.dis || (A.dis==B.dis && A.mid<B.mid) || (A.dis==B.dis && A.mid==B.mid && A.a<B.a);
}
}line[N*N];
 
LL Abs(LL x){return x>0?x:-x;}
 
int main(){
freopen("2338.in","r",stdin);
freopen("2338.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%lld %lld",&poi[i].x,&poi[i].y);
}
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        line[++cnt]=Line(poi[i],poi[j],MidPoint(poi[i],poi[j]),Dist(poi[i],poi[j]));
    }
}
sort(line+1,line+cnt+1);
for(int i=2;i<=cnt;i++){
    int j=i-1;
    while(line[j].mid==line[i].mid && line[j].dis==line[i].dis){
        ans=max(ans,Abs((line[i].a-line[j].a)*(line[i].a-line[j].b)));
        j--;
    }
}
printf("%lld\n",ans);
return 0;
}

用二分图建图再跑最大费用最大流就可以了

考场上建图写炸了。。。sad

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
 
const long long INF=1000000000000000ll;
 
int n,en,S,T,h[10005],flag[10005],Back[10005],Tag,tab[100005],cnt,X[10005],Y[10005],xs=0,ys=0;
long long A[2005],B[2005],C[2005],D[10005],Cost=0;
queue<int> Q;
 
struct Edge{
int b,back,next;
long long f,c;
}e[2000005];
 
void AddEdge(int sa,int sb,long long sc,long long sd){
e[++en].b=sb;
e[en].back=en+1;
e[en].f=sc;
e[en].c=sd;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].back=en-1;
e[en].f=0;
e[en].c=-sd;
e[en].next=h[sa];
h[sa]=en;
}
 
bool SPFA(){
memset(D,-80,sizeof(D));
memset(flag,0,sizeof(flag));
memset(Back,0,sizeof(Back));
D[S]=0;
Q.push(S);
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(D[u]+e[i].c>D[v] && e[i].f){
            D[v]=D[u]+e[i].c;
            Back[v]=i;
            if(!flag[v]){
                flag[v]=1;
                Q.push(v);
            }
        }
    }
}
return D[T]>-INF;
}
 
long long Flow(){
long long ans=INF,Co=0;
int Tx=Back[T];
while(Tx){
    ans=min(ans,e[Tx].f);
    Co+=e[Tx].c;
    Tx=Back[e[e[Tx].back].b];
}
while(Cost+ans*Co<0)ans--;if(ans<=0){Tag=1;return 0;}
Tx=Back[T];
while(Tx){
    e[Tx].f-=ans;
    e[e[Tx].back].f+=ans;
    Cost+=ans*e[Tx].c;
    Tx=Back[e[e[Tx].back].b];
}
return ans;
}
 
long long MaxCost(){
long long ans=0;
while(SPFA()){
    ans+=Flow();
    if(Tag)break;
}
return ans;
}
 
bool Test(int x){
if(x==1 || x==0)return 0;
for(int i=2;i*i<=x;i++){
    if(x%i==0)return 0;
}
return 1;
}
 
bool Testx(long long x){
if(x==1 || x==0)return 0;
for(int i=1;tab[i]*tab[i]<=x && i<=cnt;i++){
    if(x%tab[i]==0)return 0;
}
return 1;
}
 
void Prime(){
for(int i=2;i<=40000;i++){
    if(Test(i)){tab[++cnt]=i;}
}
}
 
int Count(long long x){
int px=0;
for(int i=1;tab[i]*tab[i]<=x && i<=cnt;i++){
    while(x%tab[i]==0){px++;x/=tab[i];}
}
if(x>1)px++;
return px;
}
 
int main(){
freopen("4514.in","r",stdin);
freopen("4514.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
for(int i=1;i<=n;i++)scanf("%lld",&B[i]);
for(int i=1;i<=n;i++)scanf("%lld",&C[i]);
Prime();
S=n+1;T=n+2;
for(int i=1;i<=n;i++){if(Count(A[i])&1)X[++xs]=i;else Y[++ys]=i;}
for(int i=1;i<=xs;i++)AddEdge(S,X[i],B[X[i]],0);
for(int i=1;i<=ys;i++)AddEdge(Y[i],T,B[Y[i]],0);
for(int i=1;i<=xs;i++){
    for(int j=1;j<=ys;j++){
        if(A[X[i]]%A[Y[j]]==0 && Testx(A[X[i]]/A[Y[j]])){AddEdge(X[i],Y[j],INF,C[X[i]]*C[Y[j]]);}
        if(A[Y[j]]%A[X[i]]==0 && Testx(A[Y[j]]/A[X[i]])){AddEdge(X[i],Y[j],INF,C[X[i]]*C[Y[j]]);}
    }
}
printf("%lld\n",MaxCost());
return 0;
}