题解_牛客博客

实在是不好意思，关于这场的难度。

A

观察一下可以发现，答案就是 $2^{n-m+1}-x+1$

B,C

考虑 dp ，我们设 $dp_{i,j}$ 表示当前在 $(i,j)$ 位置时的最大价值和，因为纵向是可以走到底然后从上面走下来的，所以我们考虑转移的时候从左往右一列一列的转移

设 $sum_n=\sum_{i=1}^n val_{i,j}$

dp_{i,j}\leftarrow \max dp_{k,j-1}+\begin{cases} sum_i-sum_{k-1} & k<i\\sum_n-(sum_{k-1}-sum_i)&k>i \end{cases}

因为这里面只有 $sum_{k-1}$ 是不固定的，我们找到 $sum_{k-1}$ 最小的 $k$ 进行转移就行了，复杂度是 $O(n^2)$ 的， dp 数组可以滚动处理

#include<bits/stdc++.h>
#define Tn typename
#define Tp template
#define ll long long
#define int long long
#define pc(x) putchar(x)
using namespace std;
int begintime=clock();
bool __ST__;
void wr(int x){ if(x<0) x=-x,pc('-');if(!x) return ;wr(x/10);pc(x%10+'0');return ;}
inline void wrr(int x){ if(!x) pc('0');else wr(x);return ;}
inline void write(int x,char c='\n'){ wrr(x),pc(c);}
template<typename T>inline void read(T &res){
	res=0;char c=getchar();bool f=0;
	while(c<'0' || c>'9') c=='-'?f=1:f=f,c=getchar();
	while(c>='0' && c<='9') res=(res<<3)+(res<<1)+c-'0',c=getchar();
	return res=f?-res:res,void();
}
template<typename T,typename ...T2>inline void read(T &x,T2 &...y){ return read(x),read(y...),void();}
#ifdef segtree
#define mid ((l+r)>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#endif
#define fi first
#define se second
#define mt(x,y) ((1ll*(x)*(y))%mod)
#define pls(x,y) ((1ll*(x)+(y))%mod)
#define cmax(x,y) ((x)=(x)>(y)?(x):(y))
#define cmin(x,y) ((x)=(x)<(y)?(x):(y))
const int N=5e3+10,M=1e6+10,inf=1e18+10;
//const int mod=1e9+7;
//const int mod=998244353;

int Tt=1,n,m,s,t;
int dp[2][N],a[N][N],l[N],r[N],sum[N];

void solve(){

	read(n,m,s,t);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(a[i][j]);
	for(int i=1;i<=n;i++) dp[0][i]=-inf;
	dp[0][s]=0;
	for(int j=1;j<=m;j++){
		int now=j&1,pre=(j-1)&1;
		for(int i=0;i<=n+1;i++){
			l[i]=r[i]=-inf,sum[i]=0;
			dp[now][i]=dp[pre][i],dp[now][i]=0;
		}
		for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][j];
		for(int i=1;i<=n;i++) l[i]=max(l[i-1],dp[pre][i]-sum[i-1]);
		for(int i=n;i>=1;i--) r[i]=max(r[i+1],dp[pre][i]+sum[n]-sum[i-1]);
		for(int i=1;i<=n;i++) dp[now][i]=max(l[i],r[i+1])+sum[i];
	}                                                         
	printf("%lld\n",dp[m&1][t]);
	cerr<<dp[m&1][t]<<endl;
	return ;
}
void clr(){

	return ;
}

bool __ED__;
signed main(){
	double MEM=((&__ST__)-(&__ED__))/1024.0/1024.0;
	fprintf(stderr,"%.2lf MB %.2lf GB\n\n",MEM,MEM/1024.0);
#ifdef LOCAL
//	freopen("in.in","r",stdin);
//  	freopen("out.out","w",stdout);
#endif
//	ios_base::sync_with_stdio(false);
//  	cin.tie(0);
//	read(Tt);
	while(Tt--) solve(),clr();

	fprintf(stderr,"\n%d ms",clock()-begintime);
	return 0;
}

D

考虑对于树上的每条边，我们把链接的两个点的 $t$ 进行作差看一下

t_u-t_v=\sum_{i=1}^n val_{i}\times dis(u,i)-\sum_{i=1}^n val_{i}\times dis(v,i)\\=\sum_{i=1}^n val_i\times\left(dis(u,i)-dis(v,i)\right)\\=\sum_{i\in T(v)} val_i-\sum_{i\not\in T(v)}val_i

我们设 $s_v=\sum_{i\in T(v)} val_i$ ，则 $S-s_v=\sum_{i\not\in T(v)} val_i$

则有:

t_u-t_v=s_v-(S-s_v)\\=2s_v-S\\s_v=\frac{t_u-t_v+S}{2}

这个 $S$ 怎么求？我们不妨在回去观察一下 $t$ 数组的差值

这次反过来看 $t_v-t_u$ ，计算 $\sum_{(u\to v)\in E} t_v-t_u$

\sum_{(u\to v)\in E} t_v-t_u =\sum_{v\not=1}(S-2*s_v)\\ =S*(n-1)-2\sum_{v\not=1}s_v

接下来要考虑 $\sum_{v\not=1}s_v$ 该怎么计算？

如果我们硬把 $s_v=\sum_{i\in T(v)} val_i$ 往里带，不是很容易算出结果，但是如果考虑把这个式子重新改写，分开考虑每个 $val_i$ 对 $\sum_{v\not=1}s_v$ 的贡献次数，就可以得到另一个式子:

\sum_{v\not=1}s_v=\sum_{i\not=1} dis(1,i)*val_i

显然 $val_i$ 如果能计入答案，当且仅当 $v$ 是 $i$ 或者 $i$ 的祖先

算到这一步，我们仍然无法确定一个答案，观察到 $t_1=\sum_{i\not=1} dis(1,i)*val_i$ ，那么:

\sum_{(u\to v)\in E} t_v-t_u =S*(n-1)-2*t_1\\S=\frac{\sum_{(u\to v)\in E}(t_v-t_u)+2t_1}{n-1}

现在再把 $S$ 带回去，我们就能把 $s_v$ 解出来了

然后再作差就能求出 $val_v$

#include<bits/stdc++.h>
#define Tn typename
#define Tp template
#define ll long long
#define int long long
#define pc(x) putchar(x)
using namespace std;
int begintime=clock();
bool __ST__;
void wr(int x){ if(x<0) x=-x,pc('-');if(!x) return ;wr(x/10);pc(x%10+'0');return ;}
inline void wrr(int x){ if(!x) pc('0');else wr(x);return ;}
inline void write(int x,char c='\n'){ wrr(x),pc(c);}
template<typename T>inline void read(T &res){
	res=0;char c=getchar();bool f=0;
	while(c<'0' || c>'9') c=='-'?f=1:f=f,c=getchar();
	while(c>='0' && c<='9') res=(res<<3)+(res<<1)+c-'0',c=getchar();
	return res=f?-res:res,void();
}
template<typename T,typename ...T2>inline void read(T &x,T2 &...y){ return read(x),read(y...),void();}
#ifdef segtree
#define mid ((l+r)>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#endif
#define fi first
#define se second
#define mt(x,y) ((1ll*(x)*(y))%mod)
#define pls(x,y) ((1ll*(x)+(y))%mod)
#define cmax(x,y) ((x)=(x)>(y)?(x):(y))
#define cmin(x,y) ((x)=(x)<(y)?(x):(y))
const int N=2e6+10,M=1e6+10,inf=1e9+10;
//const int mod=1e9+7;
//const int mod=998244353;

int Tt=1,n,m,S;
int t[N],val[N],s[N];
vector<int> v[N];

void dfs1(int x,int p){
	for(auto u: v[x]){
		if(u==p) continue ;
		S+=t[u]-t[x],dfs1(u,x);
	}
	return ;
}
void dfs2(int x,int p){
	
	val[x]=s[x];
	for(auto u: v[x]){
		if(u==p) continue ;
		s[u]=(t[x]-t[u]+S)>>1;
		dfs2(u,x);
		val[x]-=s[u];
	}
	return ;
}
void solve(){

	read(n);
	for(int i=1;i<n;i++){
		int x,y;read(x,y);
		v[x].push_back(y),v[y].push_back(x);
	}
	for(int i=1;i<=n;i++) read(t[i]);
	dfs1(1,0);
	S+=2*t[1],S/=(n-1),s[1]=S;
//	printf("%lld\n",S);
	dfs2(1,0);
	for(int i=1;i<=n;i++) printf("%lld ",val[i]);
	return ;
}
void clr(){

	return ;
}

bool __ED__;
signed main(){
	double MEM=((&__ST__)-(&__ED__))/1024.0/1024.0;
	fprintf(stderr,"%.2lf MB %.2lf GB\n\n",MEM,MEM/1024.0);
#ifdef LOCAL
//	freopen("tree3.in","r",stdin);
//  	freopen("tree3.out","w",stdout);
#endif
//	ios_base::sync_with_stdio(false);
//  	cin.tie(0);
//	read(Tt);
	while(Tt--) solve(),clr();

	fprintf(stderr,"\n%d ms",clock()-begintime);
	return 0;
}

E

以 $k=3$ 为例，进行手模

-	1	2
1	$a$	$x$
2	$b$
3	$c$

考虑 $[2,2]$ 怎么填，因为随意取 $k$ 个数一定相等，所以考虑用已知的数字或者可以被抵消掉的数字求和， $x+b+[3,3]=[2,2]+a+[3,3]\rightarrow [2,2]=x+b-a$

-	1	2
1	$a$	$x$
2	$b$	$x+b-a$
3	$c$

用同样的方法，能求出其他的位置的值 :

-	1	2	3
1	$a$	$x$	$y$
2	$b$	$x+b-a$	$y+b-a$
3	$c$	$x+c-a$	$y+c-a$

仔细观察一下，可以发现格子 $[i,j]=[1][i]+[i][1]-[1][1]$

设 $A_i=[1][i]-[1][1],B_i=[i][1]$ ，则 $A=\{0,x-a,y-a\},B=\{a,b,c\} , [i][j]=A_i+B_j$

这样的一对数组就能唯一对应一个矩阵，因为 $A_{\min}=0$ 所以 $B_{\min}\ge m$

考虑把 $B$ 整体 $-m$ ，也就是说 $B'_{\min}\ge 0$ ，把至多 $n-k\times m$ 分到 $2k$ 的数列里，并且前 $k$ 个位置必须有至少一个 $0$ ，总个数是这样的 :

\dbinom{n-k\times m+2k}{2k}-\dbinom{n-k\times m+k}{2k}

这就是答案

#include<bits/stdc++.h>
#define int long long
using namespace std;
int begintime=clock();
bool __ST__;
int read(){
	int res=0;char c=getchar();bool f=0;
	while(c<'0' || c>'9') c=='-'?f=1:f=f,c=getchar();
	while(c>='0' && c<='9') res=(res<<3)+(res<<1)+c-'0',c=getchar();
	return f?-res:res;
}
const int N=2e6+10,mod=1e9+7;

int T=1,n,m;
int fac[N],ifac[N];

int C(int x,int y){ return x<y?0:fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
void solve(){

	n=read(),m=read();
	int res=0;
	for(int i=1;i<=n/m;i++) res=((res+C(n-i*m+2*i,i*2))%mod-C(n-i*m+i,2*i)+mod)%mod;
	printf("%lld\n",res);

	return ;
}
int qpow(int x,int y){
	if(y==1) return x%mod;
	if(y==0) return 1;
	int res=qpow(x,y/2)%mod;
	if(y&1) return res*res%mod*x%mod;
	else return res*res%mod;
}
void clr(){

}

bool __ED__;
signed main(){
	double MEM=((&__ED__)-(&__ST__))/1024.0/1024.0;
	fprintf(stderr,"%.2lf MB %.2lf GB\n\n",MEM,MEM/1024.0);
	
	T=read(),fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
	ifac[N-1]=qpow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
	while(T--) solve(),clr();

	fprintf(stderr,"\n%d ms",clock()-begintime);
	return 0;
}

F

我们可以先用 manacher 把所有的偶回文串在 $O(n)$ 时间内跑出来，因为显然除了长度为 $1$ 的廻文串，剩下的长度一定是偶数，然后考虑怎么计算廻文子串

举个栗子，当前的大回文串是 $abbaabba$ ，对于这个回文串，我们显然是希望在他的回文中心左右仍然存在回文中心，左边和右边是对称的，所以我们只考虑右侧，考虑右侧的回文中心应该在什么位置范围内，显然我们是不希望找到的廻文子串长于这个大回文串 $^1$ ，所以右侧的小回文串的回文中心应当在 $[i+1,i+\lfloor\frac{p_i}{2}\rfloor]$ 范围内并且小回文串的左边界一定要在 $[1,i]$ 范围内，否则可能出现右侧的小回文串无法将大回文串回文中心右侧的区域包含住的情况 $^2$

举两个例子:

$abbaeeabbae$

这种情况就是对于廻文子串长度限制的原因，右侧的 $eabbae$ 显然也是一个回文串，然而最右侧的 $e$ 不能够被 $abbaeeabba$ 管辖，所以一定要让右侧的小回文串的回文中心在 $[i+1,i+\lfloor\frac{p_i}{2}\rfloor]$ 中
$eeeabbazzabbaeee$

右侧的 $abba$ 因为没有包含到大回文串的回文中心，所以即使满足上一个条件，也不能选，这一点通过从右往左依次把左边界在当前回文串回文中心左侧的加入来解决

观察到这是一个单点修改区间查询的问题，我们可以通过树状数组或者线段树解决

考虑第二问，是一个经典的贪心问题，我们把所有的廻文子串算出来之后，按照子串左边界排序从小到大排序，依次选取同一个左端点但是右端点最靠右的即可，对于每个位置，可以通过线段树顺带求出来最右侧的端点

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+10;

int n,k;
int x[N],y[N],a[N],w[N],suf[N],pre[N];
priority_queue<int> q;
struct node{
	int x,y;
	bool friend operator < (node a,node b){
		return a.y<b.y;
	}
}b[N];

int read(){
    char c=getchar();int res=0,f=1;
    while(c>'9' || c<'0'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9') res=res*10+c-'0',c=getchar();
    return res*f;
}
int Abs(int x){ return x>0?x:-x;}

signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();
   if(k==n){
       sort(x+1,x+n+1),sort(y+1,y+n+1);
       int mid=(n+1)>>1;
       int X=x[mid],Y=y[mid];
       int ans=0;
       for(int i=1;i<=n;i++) ans+=Abs(X-x[i])+Abs(Y-y[i]);
       printf("%lld",ans);
       return 0;
   }else{
		int ans=1e18;
		for(int i=1;i<=n;i++) b[i]=((node){x[i],y[i]});
		sort(b+1,b+n+1);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) w[j]=Abs(b[i].x-b[j].x);
			for(int j=0;j<=n+1;j++) pre[j]=-1e18,suf[j]=-1e18;
			while(q.size()) q.pop();
			int res=0;
			for(int j=1;j<=n;j++){
				int v=w[j]-b[j].y;
				if(q.size()<k/2) q.push(v),res+=v;
				else{ if(q.top()>v) res=res-q.top()+v,q.pop(),q.push(v);}
				if(q.size()==k/2) pre[j]=res;
			}
			while(q.size()) q.pop();
			res=0;
			for(int j=n;j>=1;j--){
				int v=w[j]+b[j].y;
				if(q.size()<k/2) q.push(v),res+=v;
				else{ if(q.top()>v) res=res-q.top()+v,q.pop(),q.push(v);}
				if(q.size()==k/2) suf[j]=res;
			}
			for(int j=1;j<=n;j++){
				if(k%2){
					if(pre[j-1]==-1e18 || suf[j+1]==-1e18) continue ;
					ans=min(ans,pre[j-1]+suf[j+1]+w[j]);
				}else{
					if(pre[j-1]==-1e18 || suf[j+1]==-1e18) continue ;
					ans=min(ans,pre[j]+suf[j+1]);
				}
			}
		}
		printf("%lld",ans);
	}
    return 0;
}