寒假学习计划
比赛地址
[E] 1-Trees and Queries
题意
给出一棵树以及q个询问,每个询问的形式是a,b,x,y,k.即判断在树上添加了一条x到y的边之后,是否存在一条从a到b的,长度为k的路径(可以重复走过任何一条边任意次)
题解
设Dis(a,b)=l,问题不难转化为判断l与k是否奇偶.假如同奇偶,就可以通过反复走某一条边使得路径的长度变成k.假如不同奇偶,添加了x到y的边后,会形成一个环,只需再判断这个环的长度是不是奇数,也就是能不能通过走一次这个环改变l的奇偶性.
如果l>k,只需判断一下能否走x->y这条近路减少路径长度即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,x,y,a,b,q,k,l,L,l2,L2,lsum=1;
int head[N],hson[N],top[N],size[N],msize[N],d[N],fa[N];
struct Edge{
int t,next;
}e[N*8];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
IL void Dfs(int x,int f){
int i=0;
size[x]++;
for (i=head[x];i;i=e[i].next){
if (e[i].t == f) continue;
d[e[i].t]=d[x]+1; Dfs(e[i].t,x);
fa[e[i].t]=x;
if (size[e[i].t]>size[hson[x]])
hson[x]=e[i].t;
size[x]+=size[e[i].t];
}
}
IL void Cut(int x){
int i=0;
top[hson[x]]=top[x];
if (hson[x]) Cut(hson[x]);
for (i=head[x];i;i=e[i].next){
if (e[i].t==hson[x] || e[i].t==fa[x]) continue;
top[e[i].t]=e[i].t; Cut(e[i].t);
}
}
IL int LCA(int x,int y){
while (top[x]^top[y])
(d[top[x]]>d[top[y]])?x=fa[top[x]]:y=fa[top[y]];
return (d[x]<d[y])?x:y;
}
IL int Dis(int x,int y){
reg int p=LCA(x,y);
return d[x]+d[y]-2*d[p];
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=1;i<n;i++){
x=read(); y=read();
Add(x,y); Add(y,x);
}
Dfs(1,0); top[1]=1; Cut(1);
q=read();
while (q--){
x=read(); y=read(); a=read(); b=read();
k=read();
l=Dis(a,b); L=Dis(x,y);
if (k<l){
l2=Min(Dis(a,x)+Dis(y,b)+1,Dis(a,y)+Dis(x,b)+1);
if (l2>k) {
puts("NO");
continue;
}
if (!((k-l2)%2)) {puts("YES"); continue;}
puts("NO");
continue;
}
if (!((k-l)%2)) {puts("YES"); continue;}
l2=Dis(a,x)+Dis(y,b)+1; L2=Dis(a,y)+Dis(x,b)+1;
if (l2<=k){
if (!((k-l2)%2)) {puts("YES"); continue;}
if (!(L%2) && l2+L+1<=k) {puts("YES"); continue;}
}
if (L2<=k){
if (!((k-L2)%2)) {puts("YES"); continue;}
if (!(L%2) && L2+L+1<=k) {puts("YES"); continue;}
}
puts("NO");
}
return 0;
}
[F] Animal Observation (hard version)
题意
太复杂了,见题目链接
题解
设f[i][j]表示第i天的相机拍摄[j,j+k-1]区域所能拍到动物的最大数量.
有如下转移方程:
f[i][j]=Max(f[i][j],f[i-1][g]+Cost([j,j+k-1]))
因为Cost([j,j+k-1])是会受g的选取影响的,所以在转移的时候要消除这个影响.
从左向右枚举,一开始的区间是[1,k],此时,上一天的区间左端点在[1,k]之间的会和这次有重叠,把重叠的部分减去,然后找f^{'}[i-1][g]的最大值即可.枚举的区间向右移动的时候,左端点处收到影响的区间再加上对应的值,包含即将成为右端点的区间要减去对应的值.最大值的查询和修改通过线段树维护.总的时间复杂度为O(nmlogm).具体细节见代码.
题解里还有一个用单调队列的O(nm)解法.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,k,i,j,g,h,l,r;
LL Ans,sum;
LL a[55][N],s[55][N],f[55][N];
struct Tree{
int l,r;
LL d,lz;
}t[N*4];
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
IL void Maketree(int x,int low,int high){
int mid=(low+high)>>1;
t[x].l=low; t[x].r=high;
if (low==high) return;
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
}
IL void Push(int x){
LL p=t[x].lz;
t[l(x)].d+=p; t[r(x)].d+=p;
t[l(x)].lz+=p; t[r(x)].lz+=p;
t[x].lz=0;
}
IL void Add(int x,int low,int high,LL val){
int mid=(t[x].l+t[x].r)>>1;
if (low>m || low>high) return;
if (t[x].l==low && t[x].r==high) {t[x].d+=val; t[x].lz+=val; return;}
if (t[x].lz) Push(x);
if (high<=mid) Add(l(x),low,high,val);
else if (low>mid) Add(r(x),low,high,val);
else Add(l(x),low,mid,val),Add(r(x),mid+1,high,val);
t[x].d=Max(t[l(x)].d,t[r(x)].d);
}
IL void Change(int x,int low,LL val){
int mid=(t[x].l+t[x].r)>>1;
if (t[x].l==t[x].r) {t[x].d=val; return;}
if (t[x].lz) Push(x);
(low<=mid)?Change(l(x),low,val):Change(r(x),low,val);
t[x].d=Max(t[l(x)].d,t[r(x)].d);
}
IL LL Query(int x,int low,int high){
int mid=(t[x].l+t[x].r)>>1;
if (low==t[x].l && high==t[x].r) return t[x].d;
if (t[x].lz) Push(x);
if (high<=mid) return Query(l(x),low,high);
else if (low>mid) return Query(r(x),mid+1,high);
else return Max(Query(l(x),low,mid),Query(r(x),mid+1,high));
}
IL void Ready(){
reg int i=0,j=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
a[i][j]=read();
memset(s,0,sizeof(s)); memset(f,0,sizeof(f));
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
s[i][j]=s[i][j-1]+a[i][j];
Maketree(1,1,m);
for (i=1;i<=m-k+1;i++){
f[1][i]=s[1][i+k-1]-s[1][i-1]+s[2][i+k-1]-s[2][i-1];
Add(1,i,i,f[1][i]);
}
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read(); k=read();
Ready();
for (i=2;i<=n;i++){
for (j=1;j<=k;j++)
Add(1,j,j,-(s[i][k]-s[i][j-1]));
for (j=1;j<=m-k+1;j++){
sum=t[1].d;
f[i][j]=sum+s[i][j+k-1]-s[i][j-1]+s[i+1][j+k-1]-s[i+1][j-1];
l=Max(1,j-k+1); Add(1,l,j,a[i][j]);
r=Min(m,j+k); Add(1,j+1,r,-a[i][j+k]);
}
for (j=1;j<=m;j++) Change(1,j,f[i][j]);
}
for (i=1;i<=m;i++) Ans=Max(Ans,f[n][i]);
cout<<Ans<<endl;
return 0;
}
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: CF Round #620 (Div. 2)部分题解
本文地址: CF Round #620 (Div. 2)部分题解
