我們剛剛知道那些題的解法-6
ZR 2390
比較妙的構造題。
首先考慮那些大于 \(\frac{n}{2}\) 的質數一定是沒可能了，那些小于等于 \(\frac{n}{2}\)，大于 \(\frac{n}{3}\) 的質數只能放在兩邊，如果能構造一種方案，滿足剩下的質數都能放進去，以及所有的包含這些質數的合數，那么就一定是最優解，那么可以考慮小于 \(12\) 的進行爆搜，大于這個數的，我們把那兩個特殊的質數放在兩邊，其余的質數之間用 \(2,3\) 公因數來鏈接，最后想辦法把最后一個鏈接弄成 \(2\) 就行，一個方法是插入 \(12\)，也可以讓最后一個質數是 \(2\)。不過注意處理 \(2\times 3=6\) 這種比較尷尬的情況，\(3\) 和 \(2\) 這兩個質數特判一下鏈接地方即可。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 1000100
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
vi ans,tmp;
int n,s[N],top,pr[N],ta;
bool ban[N],no[N];
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
inline void dfs(int lst){
if(ans.size()<tmp.size()) ans=tmp;
rep(i,2,n){
if(!ban[i]&&(lst==0||gcd(i,lst)>1)){
ban[i]=1;tmp.pb(i);dfs(i);tmp.pop_back();ban[i]=0;
}
}
}
inline void add(int x){
if(!ban[x]) ans.pb(x),ban[x]=1;
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);
if(n<=12){
dfs(0);
}
else{
no[1]=1;
rep(i,2,n/2){
if(!no[i]){
pr[++ta]=i;
if(i>n/3) s[++top]=ta;
}
for(int j=1;j<=ta&&1ll*pr[j]*i<=n/2;j++){
no[pr[j]*i]=1;
if(i%pr[j]==0) break;
}
}
if(s[1]) add(pr[s[1]]),add(pr[s[1]]*2),ta=s[1]-1;
int o=2;
dec(i,1,ta){
int now=o^1,lst=o;
if(i==2) lst=2,now=4;
if(i==1&&s[2]) now=pr[s[2]];
add(lst*pr[i]);
rep(j,1,n/pr[i]){
if(j==now) continue;
add(j*pr[i]);
}
add(now*pr[i]);o^=1;
}
if(s[2]) add(2*pr[s[2]]),add(pr[s[2]]);
}
printf("%d\n",(int)ans.size());
for(int x:ans) printf("%d ",x);
return 0;
}
ZR 2426
考慮一個 naive 的 DP \(f_{l,r,k}\) 表示 \(l\) 到 \(r\) 之間的數，只考慮小于等于 \(k\) 的最優解是多少。之所以有 \(k\) 的限制是因為我們每次都是從當前考慮區間中枚舉最大值的位置和最大值的值是多少，不過不難發現，如果直接把這個限制去掉，當一個最大值超過限制的時候不難發現這個時候我們的答案是算小了的，也就是說這個限制形同虛設，因為不滿足這個限制的一定不是最優解。因此可以直接做區間 DP。
注意我們要求形如 \(kx-b\) 的最大值，用動態開點李超樹維護即可。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 310
#define M 10000010
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=1e18;
const dd eps=1e-9;
const int m=9e7;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int Q[N][N],n,len[N],g[N][N][N],qs[N][N],maxx[N];
int f[N][N];
struct Node2{
int v,c;
inline bool operator < (const Node2 &b)const{
return v<b.v;
}
};
vc<Node2> v[N];
struct Node{
int K,B,ls,rs;
inline Node(){K=B=-1;ls=rs=0;}
inline Node(int k_,int b_){K=k_;B=b_;}
inline int calc(int x){return K*x+B;}
}p[M];
int tot,rt[N];
struct LCT{
inline LCT(){tot=0;}
#define ls(k) p[k].ls
#define rs(k) p[k].rs
inline void Change(int &k,int l,int r,int K,int B){
// printf("l=%lld r=%lld\n",l,r);
if(!k){
k=++tot;
assert(tot<=M);
}
if(l==r){
if(p[k].K==-1||p[k].calc(l)<Node(K,B).calc(l)) p[k]=Node(K,B);
return;
}
int mid=(l+r)>>1;
if(p[k].K==-1) p[k].K=K,p[k].B=B;
if(p[k].calc(mid)<Node(K,B).calc(mid)){
swap(K,p[k].K);swap(B,p[k].B);
}
if(p[k].calc(l)<Node(K,B).calc(l)) Change(ls(k),l,mid,K,B);
else Change(rs(k),mid+1,r,K,B);
}
inline int Ask(int k,int l,int r,int x){
// printf("l=%lld r=%lld\n",l,r);
if(!k) return -INF;
if(l==r) return p[k].calc(x);
int mid=(l+r)>>1;
int ans=p[k].calc(x);
// printf("k=%d K=%d B=%d\n",k,p[k].K,p[k].B);
if(x<=mid) ans=max(ans,Ask(ls(k),l,mid,x));
else ans=max(ans,Ask(rs(k),mid+1,r,x));
return ans;
}
}st[N];
inline int dfs(int l,int r){
if(r<l){
return 0;
}
if(f[l][r]!=-INF){
return f[l][r];
}
int &ans=f[l][r];
ans=-INF;
rep(i,l,r){
int sum=0;
sum=g[l][r][i];
int maxx=-INF;
rep(o,1,len[i]){
// ans=max(ans,dfs(l,i-1)+dfs(i+1,r)+sum*v[i][o].v-v[i][o].c);
}
ans=max(ans,dfs(l,i-1)+dfs(i+1,r)+st[i].Ask(rt[i],1,m,sum));
}
if(ans==-INF) ans=-INF-1;
return ans;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);
rep(i,1,n)rep(j,i,n) read(Q[i][j]),qs[i][j]=qs[i][j-1]+Q[i][j];
rep(i,1,n)rep(r,i,n){
int sum=0;
dec(l,1,i){
sum+=qs[l][r]-qs[l][i-1];
g[l][r][i]=sum;
}
}
rep(i,1,n){
read(len[i]);
v[i].resize(len[i]+1);
rep(j,1,len[i]){
read(v[i][j].v);read(v[i][j].c);
}
sort(v[i].begin(),v[i].end());
}
// exit(0);
rep(i,1,n){
// printf("i=%d\n",i);
rep(j,1,len[i]){
// printf("j=%d\n",j);
// printf("v[i][j].v=%d v[i][j].c=%d\n",v[i][j].v,v[i][j].c);
st[i].Change(rt[i],1,m,v[i][j].v,-v[i][j].c);
}
}
// exit(0);
rep(i,1,n)rep(j,1,n) f[i][j]=-INF;
int ans=-INF;
rep(i,1,n){
// printf("i=%d\n",i);
int sum=0;
sum=g[1][n][i];
rep(k,1,len[i]){
// int nowans=dfs(1,i-1)+dfs(i+1,n)+sum*v[i][k].v-v[i][k].c;
// ans=max(ans,nowans);
}
// printf("sum=%lld\n",sum);
// printf("maxx=%lld\n",st[i].Ask(rt[i],1,m,sum));
int nowans=dfs(1,i-1)+dfs(i+1,n)+st[i].Ask(rt[i],1,m,sum);
ans=max(ans,nowans);
}
printf("%lld\n",ans);
return 0;
}
ZR 2428
考慮第二個 subtask 我們可以逐層把樹給剖開，然后我們知道每一層都有哪些點，現在只需要考慮相鄰兩層點之間的父子關系如何確定。
考慮我們可以通過二分來確定一個點的一個兒子，那么在總詢問次數 \(n\log n\) 的情況下，我們是可以通過 subtask2 的。
考慮這個做法的瓶頸在于剖葉子節點，從下往上做不行，我們考慮從上往下做，設 \(f(k)\) 函數表示把以 \(k\) 為根的子樹弄好，整棵樹我們認為 \(1\) 為根。
通過詢問指定集合加 \(1\) 所在的最小聯通塊是否包含 \(k\)，我們可以知道指定集合中是否有 \(k\) 子樹中的一個點，我們可以用一下算法來構造我們這棵樹：
調用 \(f(k)\)，然后隨便求出 \(k\) 子樹內的一個沒有訪問到的點，如果能得到這樣一個點，設為 \(x\)，調用 \(f(x)\)。否則，說明 \(k\) 的所有兒子都已經訪問過，我們維護一個集合表示所有訪問過但是父親沒有確定的點，我們在里面二分找出 \(k\) 的所有兒子，如果找不出來，要么找完了，要么 \(k\) 是葉子，然后把 \(k\) 加入所有訪問過但是父親沒有確定的點集。
總詢問次數是 \(n\log n\) 的。
#include<bits/stdc++.h>
#include"D.h"
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N number
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
vi s,t;
vc<P> ans;
inline vi ge_ve(vi v,int l,int r){
vi now;now.clear();
rep(i,l,r) now.pb(v[i]);
return now;
}
inline bool in_subtree(vi v,int x){
v.pb(1);
return ask(v,x);
}
inline void add(int a,int b){
ans.pb(mp(a,b));
}
inline void F(int k){
// printf("k=%d\n",k);
// printf("s.size()=%d\n",(int)s.size());
while(s.size()&&in_subtree(s,k)){
int l=0,r=(int)s.size()-1;
while(l<r){
int mid=(l+r)>>1;
vi now=ge_ve(s,l,mid);
if(in_subtree(now,k)) r=mid;
else l=mid+1;
}
int x=s[l];
s.erase(s.begin()+l);
F(x);
}
// printf("Enter! k=%d\n",k);
if(!t.size()||!in_subtree(t,k)){
t.pb(k);
return;
}
// printf("t.size()=%d\n",(int)t.size());
while(t.size()&&in_subtree(t,k)){
int l=0,r=(int)t.size()-1;
while(l<r){
int mid=(l+r)>>1;
vi now=ge_ve(t,l,mid);
if(in_subtree(now,k)) r=mid;
else l=mid+1;
}
int x=t[l];
t.erase(t.begin()+l);
add(k,x);
}
t.pb(k);
// puts("End");
}
std::vector<std::pair<int,int> > work(int n){
s.clear();t.clear();
rep(i,2,n) s.pb(i);
// exit(0);
F(1);
// for(P now:ans){
// printf("%d %d\n",now.fi,now.se);
// }
return ans;
}
ZR 2427
考慮如果我們能計算 \(E(dep_x)\)，以及 \(P(l=lca(x,y))\) 的話，我們就可以得出答案了，答案相當于：
\[dep_x+dep_y-2\sum\limits_{i=1}^{x-1}P(i=lca(x,y))E(dep_i)-2E(dep_x)P(x\le y)
\]
其中 \(x\le y\) 表示 \(x\) 是 \(y\) 的祖先。減去后面的原因是可能 \(x,y\) 的 \(lca\) 是 \(x\)，這種情況發生的概率是 \(x\) 是 \(y\) 祖先的概率，這樣兩倍的 \(E(dep_x)\) 會被算重。
考慮 \(P(x\le y)\) 是多少，設 \(S\) 為 \(x,y\) 之間（不包括 \(x,y\)）的點所組成的點集。所以我們有：
\[P(x\le y)=\frac{a_x}{b_{y-1}}\sum\limits_{S\subseteq(x,y)}\prod\limits_{i\in S}\frac{a_i}{b_{i-1}}=\frac{a_x}{b_{y-1}}\prod\limits_{x<i<y}(1+\frac{a_i}{b_{i-1}})=\frac{a_x}{b_x}
\]
而 \(E(dep_x)\) 相當于枚舉所有點為 \(x\) 祖先的概率，以及乘上對應的貢獻，有：
\[E(dep_x)=c_1+c_x+2\sum\limits_{1<i<x}\frac{c_ia_i}{b_i}
\]
現在考慮如何計算 \(P(l=lca(x,y))\)，這里我們假設 \(l<x<y\)，我們把所有 \(l\) 到 \(x,y\) 上的點裝入一個集合中，設為 \(S\)，不難發現對于 \(S\) 中的那些滿足 \(i<x\) 的元素，既可以放在 \(l\) 到 \(x\) 路徑上，也可以放在 \(l\) 到 \(y\) 路徑上，所以這里要乘上一個 \(2\)，也就是說，我們需要考慮 \(S\) 對應了多少種不同的放點方法，對于每個 \(i<x\)，都有一個 \(2\) 的貢獻。其余的貢獻都是 \(1\)，所以我們有：
\[\begin{aligned}
P(l=lca(x,y))&=\frac{a_l^2}{b_{x-1}b_{y-1}}\sum\limits_{S_1\subset(l,x)}\sum\limits_{S_2\subset(x,y)}\prod\limits_{i\in S_1}\frac{2a_i}{b_{i-1}}\prod\limits_{i\in S_2} \frac{a_i}{b_{i-1}}\\
&=\frac{a_l^2}{b_{x-1}b_x}\prod\limits_{l<i<x}\frac{b_{i-1}+2a_i}{b_{i-1}}
\end{aligned}
\]
經過進一步的化簡與預處理，我們可以在 \(O(1)\) 的復雜度內回答一個詢問。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 1000100
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=1e9+7;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n,Q,a[N],c[N],b[N],sum[N],tim[N],su[N];
inline int ksm(int a,int b,int mod){
int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int x){return ksm(x,mod-2,mod);}
inline int calc_dep(int x){
if(x==1) return 0;
return (c[1]+c[x]+sum[x-1]*2%mod)%mod;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(Q);
rep(i,1,n-1) read(a[i]);
rep(i,1,n) read(c[i]);
rep(i,1,n-1) b[i]=b[i-1]+a[i];
rep(i,2,n-1){
sum[i]=(sum[i-1]+c[i]*a[i]%mod*inv(b[i])%mod)%mod;
}
// rep(i,1,n){
// printf("%lld\n",calc_dep(i));
// }
tim[1]=1;
rep(i,2,n){
tim[i]=tim[i-1]*((b[i-1]+2*a[i]%mod)%mod)%mod*inv(b[i-1])%mod;
}
// rep(i,1,n) printf("%lld\n",tim[i]);
rep(i,1,n) su[i]=(su[i-1]+calc_dep(i)*a[i]%mod*a[i]%mod*inv(tim[i])%mod)%mod;
// rep(i,1,n) printf("%lld\n",su[i]);
rep(i,1,Q){
int u,v;
read(u);read(v);
if(u==v){
puts("0");continue;
}
if(u>v) swap(u,v);
int ans=0;
// int ans=a[u]*inv(b[u])%mod*((calc_dep(v)-calc_dep(u))%mod)%mod;
// // printf("ans=%d\n",ans);
// if(u!=1) ans=(ans+calc_dep(u)+calc_dep(v)-2*tim[u-1]%mod*inv(b[u-1]*b[u]%mod)%mod*su[u-1]%mod)%mod;
ans=(ans+calc_dep(u)+calc_dep(v)-2*tim[u-1]%mod*inv(b[u-1]*b[u]%mod)%mod*su[u-1]%mod-2*calc_dep(u)*a[u]%mod*inv(b[u])%mod)%mod;
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
ZR 2391
考慮操作 \(2\) 怎么做，考慮一個 \(1\) 操作等價于把之前的所有坐標進行一個統一變換，那么我們給每個 \(1\) 操作維護一個 \(tagtimes,tagadd\)，然后維護全局的 \(tagtimes,tagadd\)，每次兩個標記已合并就知道某個 \(1\) 操作的坐標進行了什么樣的變換。
接下來考慮操作 \(3\)，注意到末尾的一些 \(k>0\) 的 \(1\) 操作，如果在這個范圍內，我們可以直接二分，只需要維護前面的第一個 \(k=0\) 的 \(1\) 操作即可，每次遇到一個 \(k=0\) 的 \(1\) 操作，如果當前操作房間號是奇數，那么就是這個 \(k=0\) 操作，否則除以 \(2\)，我們最多除 \(30\) 次 \(2\)，因為 \(x\le 10^9\)，注意如果 \(x\) 變成 \(0\)，那我們就需要知道前面第一個 \(k>0\) 的 \(1\) 操作，同樣預處理一下即可。
總復雜度 \(O(n\log V)\)。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 300010
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=1e9+7;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n,sum[N],tot,tag_time,tag_add,ans[N],beg[N],pre[N],pre2[N];
P tag[N];
struct Ques{
int op,g,k;
}q[N];
inline int ksm(int a,int b,int mod){
int res=1;
while(b){if(b&1)res=1ll*a*res%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int x){return ksm(x,mod-2,mod);}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);
rep(i,1,n){
read(q[i].op);read(q[i].g);
if(q[i].op==2) read(q[i].k);
}
tag_time=1;
int lst=0,lst2=0;
rep(i,1,n){
if(q[i].op==1){
++tot;
if(q[i].g==0){
tag_time=tag_time*2%mod;
tag_add=tag_add*2%mod;
beg[tot]=1;
lst=tot;
}
else{
tag_add=(tag_add+q[i].g)%mod;
beg[tot]=0;
lst2=tot;
}
tag[tot].fi=inv(tag_time);
tag[tot].se=-tag_add*inv(tag_time)%mod;
pre[tot]=lst;
sum[tot]=sum[tot-1]+q[i].g;
pre2[tot]=lst2;
}
else if(q[i].op==2){
int x;
if(beg[q[i].g]==1){
x=(1+(q[i].k-1)*2)%mod;
}
else x=q[i].k-1;
int k=tag[q[i].g].fi,b=tag[q[i].g].se;
k=k*tag_time%mod;
b=b*tag_time%mod;
b=(b+tag_add)%mod;
x=(x*k+b)%mod;
printf("%lld\n",(x+mod)%mod);
}
else{
int now=tot;
bool op=0;
int ans=-1;
while(now>0){
int all_sum=sum[now]-sum[pre[now]];
int r=now,l=pre[now]+1;
if(all_sum>q[i].g){
while(l<r){
int mid=(l+r+1)>>1;
if(sum[now]-sum[mid-1]>q[i].g) l=mid;
else r=mid-1;
}
op=1;
ans=l;
break;
}
else{
q[i].g-=all_sum;
if(!q[i].g){
if(pre2[now]==0){
op=1;ans=0;break;
}
op=1;
ans=pre2[now];
break;
}
if(q[i].g&1){
if(pre[now]==0) break;
op=1;
ans=pre[now];
break;
}
now=pre[now]-1;
q[i].g=q[i].g/2;
}
}
if(!op) puts("0");
else printf("%lld\n",ans);
}
}
}
ZR 2392
建出點分樹，考慮 \(dist(T,i,j)=dist(T,i,l)+dist(T,l,j)\)，其中 \(l\) 是 \(i,j\) 的 \(lca\)。這是因為 \(l\) 一定刪掉后讓 \(i,j\) 分屬于不同的連通塊，我們把兩顆樹的點分樹都建出來，對于所有的 \(i\)，枚舉 \(l_1,l_2\)，由于點分樹的樹高是 \(\log\) 的，所以目前復雜度是 \(n\log^2n\) 的，考慮我們要選出一個 \(j\)，滿足 \(j\) 和 \(i\) 的 \(lca\) 分別是 \(l_1,l_2\)，且要求 \(j\) 到 \(l_1,l_2\) 的距離之和最小。
后面這個限制是難做的，不妨考慮讓 \(j\) 為 \(l_1,l_2\) 子樹中共有的點，那么如果不滿足上述條件，一定還存在一種選擇 \(lca\) 的方法使得答案變優，所以這個限制的寬松是正確的。
需要注意，一定要求是共有的點，因為如果 \(j\) 不在 \(l_1\) 或 \(l_2\) 的子樹中，可能會導致答案變小。即我們不能讓 \(i,j\) 的 \(lca\) 成為我們枚舉的 \(l_1,l_2\) 的祖先。
那么寬松之后其實也不是很好做，我們可以對于第一棵樹，維護點分樹上每個點到其子樹中的點的路徑長度，然后先枚舉 \(l_1\)，再枚舉 \(l_1\) 子樹中的點 \(i\)。對于第二棵樹，維護點分樹上每個點到其祖先的路徑長度，枚舉 \(i\) 之后再枚舉 \(l_2\)，我們可以用 \(mn_{l_2}\) 中的值來進行更新，最后用 \(i\) 到 \(l_1,l_2\) 的距離之和來更新 \(mn_{l_2}\)，這樣就做完了。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 100010
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=1e18;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
struct Tree{
int dep[N],siz[N],rt,op,max_siz[N];
vc<P> e[N],v[N];
bool vis[N];
inline void get_rt(int k,int fa,int n){
siz[k]=1;max_siz[k]=0;
for(P to:e[k])if(to.fi!=fa&&!vis[to.fi]){
get_rt(to.fi,k,n);siz[k]+=siz[to.fi];cmax(max_siz[k],siz[to.fi]);
}
cmax(max_siz[k],n-siz[k]);
if(max_siz[rt]>max_siz[k]) rt=k;
}
inline void get_dep(int k,int fa,int rt){
// printf("k=%d rt=%d\n",k,rt);
if(op) v[rt].pb({k,dep[k]});
else v[k].pb({rt,dep[k]});
for(P to:e[k])if(to.fi!=fa&&!vis[to.fi]){
dep[to.fi]=dep[k]+to.se;
get_dep(to.fi,k,rt);
}
}
inline void div(int k){
// printf("nowdiv k=%d\n",k);
vis[k]=1;dep[k]=0;get_dep(k,0,k);
// printf("div k=%d\n",k);
for(P to:e[k])if(!vis[to.fi]){
rt=0;
get_rt(to.fi,0,siz[to.fi]);
div(rt);
}
}
inline void build(int n){
// printf("build(n)=%d\n",n);
rep(i,1,n-1){
int u,v,w;read(u);read(v);read(w);
e[u].pb(mp(v,w));e[v].pb(mp(u,w));
}
max_siz[0]=INF;get_rt(1,0,n);div(rt);
}
}t1,t2;
int n,min_val[N],ans[N];
vi tmp;
inline void calc(int l1){
for(P i:t1.v[l1]){
int x=i.fi;
for(P j:t2.v[x]){
int l2=j.fi,d=i.se+j.se;
if(min_val[l2]!=-1){
cmin(ans[x],min_val[l2]+d),cmin(min_val[l2],d);
// if(x==1){
// printf("l1=%d l2=%d\n",l1,l2);
// printf("min_val[%lld]=%lld d=%lld\n",l2,min_val[l2],d);
// }
}
else{
min_val[l2]=d,tmp.pb(l2);
// if(x==1){
// puts("Here");
// printf("l1=%d l2=%d\n",l1,l2);
// printf("min_val[%lld]=%lld d=%lld\n",l2,min_val[l2],d);
// }
}
}
}
for(int x:tmp) min_val[x]=-1;
tmp.clear();
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);t1.op=1;t1.build(n);t2.build(n);
// for(P now:t1.v[1]){
// printf("now.fi=%lld now.se=%lld\n",now.fi,now.se);
// }
mset(min_val,-1);
fill(ans+1,ans+n+1,INF);
rep(i,1,n){
calc(i);
reverse(t1.v[i].begin(),t1.v[i].end());
calc(i);
}
rep(i,1,n) printf("%lld\n",ans[i]);
return 0;
}
CF contest 1736 C2
顯然，如果不做改動，答案應該是 \(f_i=\min(f_{i-1},a_i)\)，考慮我們改動 \(p\) 這個地方，假設能得到一個 \(q\) 表示改動后的 DP 數組（設為 \(g\)）第一個滿足 \(q>i\) 且 \(g_q=a_q\) 的地方。那么顯然 \(p,q-1\) 這一段的 \(g\) 應該是公差為一的等差數列，而對于 \(i<p\)，我們都有 \(g_i=f_i\)，所以我們可以很容易算出 \(g_p\) 是多少而對于 \(q,n\) 這一段的貢獻，我們考慮能否預處理。
先考慮預處理，相當于我們要假設 \(f_i=a_i\)，然后計算 \(i\) 的一個后綴的所有 DP 數組的和，我們同樣可以找到一個 \(q\) 表示當 \(f_i=a_i\) 時，第一個滿足 \(f_q=a_q\) 的點，然后一樣按照上面分析即可。
現在考慮如何得到 \(q\)，我們都是假設有一個 \(f_i=x\)，然后找一個 \(q\) 要求 \(f_q=a_q\)，這其實等價于需要找到第一個滿足 \(a_q\le q+x-i\) 的 \(q\)，即 \(a_q-q\le x-i\)，在線做法可以用一個線段樹加二分做到兩個 \(\log\)。
實際上我們可以離線，我們所有的詢問等價于對于一個后綴找到第一個小于 \(x\) 的位置，我們按照值域從小到大插入，然后每次詢問把位置放進去二分即可。
這里是線段樹的在線做法。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 200010
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int a[N],b[N],n,m,f[N],pre[N],suf[N];
struct SegmentTree{
#define ls(k) k<<1
#define rs(k) k<<1|1
int val[N<<2];
inline void push_up(int k){
val[k]=min(val[ls(k)],val[rs(k)]);
}
inline void build(int k,int l,int r){
if(l==r){
val[k]=b[l];return;
}
int mid=(l+r)>>1;
build(ls(k),l,mid);build(rs(k),mid+1,r);
push_up(k);
}
inline int ask_min(int k,int l,int r,int z,int y){
if(z<=l&&r<=y){
return val[k];
}int mid=(l+r)>>1,ans=INF;
if(z<=mid) ans=min(ans,ask_min(ls(k),l,mid,z,y));
if(mid<y) ans=min(ans,ask_min(rs(k),mid+1,r,z,y));
return ans;
}
}st;
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);rep(i,1,n) read(a[i]);
rep(i,1,n) b[i]=a[i]-i;
b[n+1]=-INF;
st.build(1,1,n+1);
rep(i,1,n) f[i]=min(f[i-1]+1,a[i]);
rep(i,1,n+1) pre[i]=pre[i-1]+f[i];
suf[n]=a[n];
// printf("spe=%lld\n",st.ask_min(1,1,n+1,4,4));
dec(i,1,n-1){
// printf("i=%d\n",i);
int l=i+1,r=n+1;
while(l<r){
int mid=(l+r)>>1;
if(st.ask_min(1,1,n+1,i+1,mid)<=a[i]-i) r=mid;
else l=mid+1;
}
int q=l;
// printf("q=%d\n",q);
suf[i]=suf[q]+(1+q-i)*(q-i)/2+(a[i]-1)*(q-i);
// printf("suf[i]=%d\n",suf[i]);
}
// rep(i,1,n) printf("%lld ",f[i]);puts("");
read(m);
rep(i,1,m){
int p,x;read(p);read(x);
int upt=min(f[p-1]+1,x);
if(p==n){
printf("%lld\n",pre[n-1]+upt);
continue;
}
int l=p+1,r=n+1;
while(l<r){
int mid=(l+r)>>1;
if(st.ask_min(1,1,n+1,p+1,mid)<=upt-p) r=mid;
else l=mid+1;
}
int q=l;
// printf("q=%lld\n",q);
int ans=pre[p-1]+suf[q];
// printf("ans=%lld\n",ans);
ans=ans+(1+q-p)*(q-p)/2+(upt-1)*(q-p);
printf("%lld\n",ans);
}
return 0;
}
CF contest 1736 D
考慮 \(1\) 的個數為偶數時存在答案的必要條件，不過我們可以通過構造證明這還是一個充分條件。
考慮 \(n\) 組數，每一組數由 \(s_{2i},s_{2i+1}\) 組成，考慮哪些組內數字相同的組，我們不用去管它，因為對于 \(s_1,s_2\) 來說，它們每個人一定可以從該組一人拿一個且不會影響其余組的選取。
現在考慮那些組內數字不相同的組，首先因為 \(1\) 的個數是偶數，所以這種組的個數也是偶數，我們第一個組選 \(1\) 的位置，第二個組選 \(0\) 的位置，一次類推，然后執行循環右移操作，就可以把所有組變成數字相同。
int t,n,a[N];
string s;
vi ans;
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(t);
while(t--){
read(n);
n*=2;
cin>>s;
rep(i,1,n) a[i]=s[i-1]-'0';
ans.clear();
int cnt=0;
rep(i,1,n) if(a[i]) cnt++;
if(cnt&1){
puts("-1");continue;
}
for(int i=1;i<=n;i+=2){
if(a[i]==a[i+1]) continue;
else{
int len=ans.size();
int op=-1;
if(len&1) op=1;
else op=0;
if(a[i]==op) ans.pb(i);
else ans.pb(i+1);
}
}
printf("%d ",(int)ans.size());for(int x:ans) printf("%d ",x);puts("");
for(int i=1;i<=n;i+=2) printf("%d ",i);puts("");
}
}
CF contest 1736 E
考慮我們可以把后面一個大的使勁往前移，然后再往右一個一個移來使得其多次貢獻。我們設 \(p_i\) 表示第 \(i\) 輪做貢獻的數字原來的下標是多少，容易發現最優解一定滿足 \(p\) 不降。
我們設 \(f_{i,j,k}\) 表示考慮前 \(i\) 輪的貢獻，其中 \(p_i=j\)，且目前已經使用過了 \(k\) 次交換的最優解，顯然如果 \(p_i=p_{i-1}\)，也就是某個往左的值往右一個一個移做出貢獻，那么有 \(f_{i,j,k}\leftarrow f_{i-1,j,k-1}\)。
否則，一定是右邊的某個數字交換過來，設之前的數字為 \(lst\)，那么我們就有 \(f_{i,j,k}\leftarrow f_{i-1,lst,k-cnt}\)，其中 \(cnt\) 是把 \(lst\) 移過來所需要的交換次數，由于 \(lst\) 一定是大于等于 \(i\) 的，所以我們用它的位置減去 \(i\) 就是交換次數，即 \(p_i-i\)。
代碼：
這里自己懶得寫了，粘貼了一份題解代碼，侵刪。
#include <bits/stdc++.h>
using namespace std;
const int MAX=505;
vector<vector<vector<int>>> dp(MAX,vector<vector<int>>(MAX,vector<int>(MAX,-(int)(1e9))));
int main()
{
int n; cin>>n;
vector<int> a(n+5);
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<vector<int>> prefix(n+5,vector<int>(n+5,0));
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=0;k<=i;k++){
if(k){
dp[i][j][k]=dp[i-1][j][k-1]+a[j];
}
if(j>=i){
int need=j-i;
if(need>k){
continue;
}
dp[i][j][k]=max(dp[i][j][k],prefix[k-need][j-1]+a[j]);
}
}
}
for(int j=1;j<=n;j++){
for(int k=0;k<=i;k++){
prefix[k][j]=max(prefix[k][j],dp[i][j][k]);
}
}
for(int j=0;j<=i;j++){
for(int k=1;k<=n;k++){
prefix[j][k]=max(prefix[j][k],prefix[j][k-1]);
ans=max(ans,prefix[j][k]);
}
}
}
cout<<ans;
}
浙公網安備 33010602011771號