noip模拟50 solutions
队奶奶暴力打满(即使是暴力也比我的暴力高明)，拿到rank1,220pts,而我只有可怜的60pts
好丧啊，连续两次都在中游，考场上脑子就像浆糊一样，啥也想不到
还有一个就是懒，暴力懒得打，算算复杂度，知道不可能拿到更多的分就不打有优化的暴力
可是有时候出题人就很SB，数据做的非常水，导致我想到的可以卡掉优化暴力的数据是没有的
然后稍微优化一下就可以AC，我却懒得做了。
总之我出现了一个新的问题，太懒了，以至于该拿到的分根本拿不到
所以以后要注意打暴力。。。。。
T1 第零题
仍然是暴力出奇迹的一道玄学题，不是做法玄学，而是数据玄学
我一开始认为是树剖+神奇线段树，然后想了半天如何处理边界问题
开场想暴力的时候想到了要处理向上的第一个复活的地方，但是我没有想到倍增，就差一点点
我知道一定会有一个结论来方便我处理从上向下的链
也就是题解里的神秘的观察：从上到下和从下到上是一样的
我确实是想到了，而且也尝试证明了，没有证出来，所以没有敢用
然后我想要一个一个复活点的跳，但是想了想没有啥用，因为特殊构造一定可以卡掉
最后直接弃掉了这个题，40pts就走人了。
刚才的神秘观察：对于一条链，如果体力都是满的从两边开始走，那么复活的次数是一样的
这个在沈队爷的提醒之下，应用了调整法
我们将从s到t的路径记录下来成为一个序列，这样我们按照题目说的走一遍。
我们可以对于每一个复活区间删掉左端点，那么区间就会一点一点的向后平移
这样复活的次数是一定的，所以我们就可以以lca为中心，两侧的向两侧移动，让中间空出来
这样我们就可以直接从s和t开始向上倍增，最后看看剩下的那一段是否大于k，大于的话就+1
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int
const int N=2e5+5;
int n,k,q;
int to[N*2],nxt[N*2],c[N*2],head[N],rp;
void add_edg(int x,int y,int z){
to[++rp]=y;
c[rp]=z;
nxt[rp]=head[x];
head[x]=rp;
}
int siz[N],son[N],dep[N],fa[N],top[N];
int dfn[N],idf[N],cnt;
int sum[N],val[N];
void dfs_fi(int x){
siz[x]=1;son[x]=0;
for(re i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa[x])continue;
dep[y]=dep[x]+1;
fa[y]=x;
val[y]=c[i];
dfs_fi(y);
siz[x]+=siz[y];
if(!son[x]||siz[y]>siz[son[x]])son[x]=y;
}
}
int st[N][21],ji[N],cj;
int find(int x){
int l=0,r=x-1,mid;
while(l<r){
mid=l+r+1>>1;
if(sum[ji[x]]-sum[ji[mid]]<k)r=mid-1;
else l=mid;
}
return ji[l];
}
void dfs_se(int x,int f){
top[x]=f;dfn[x]=++cnt;idf[cnt]=x;
cj++;ji[cj]=x;
sum[x]=sum[ji[cj-1]]+val[x];
st[x][0]=find(cj);
for(re i=1;i<=20;i++)st[x][i]=st[st[x][i-1]][i-1];
if(son[x])dfs_se(son[x],f);
for(re i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa[x]||y==son[x])continue;
dfs_se(y,y);
}
cj--;
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
signed main(){
scanf("%lld%lld",&n,&k);
for(re i=1;i<n;i++){
int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
add_edg(x,y,z);add_edg(y,x,z);
}
dep[0]=0;dep[1]=1;
dfs_fi(1);dfs_se(1,1);
scanf("%lld",&q);
while(q--){
int x,y,ans=0;
scanf("%lld%lld",&x,&y);
int lca=LCA(x,y);
//cout<<lca<<endl;
for(re i=20;i>=0;i--){
if(dep[st[x][i]]>=dep[lca])x=st[x][i],ans+=pow(2,i);
if(dep[st[y][i]]>=dep[lca])y=st[y][i],ans+=pow(2,i);
}
if(sum[x]-sum[lca]+sum[y]-sum[lca]>=k)ans++;
printf("%lld\n",ans);
}
}
T2 第负一题
这个题是真的难，我考场上一直在枚举左端点，然后找到不同起点的dp数组的关系
甚至还想用矩阵快速幂直接找答案，后来发现好像这个矩阵并不符合乘法分配律
所以我又弃掉了这个题，然而此时已经过去了两个半小时。。。。
正解是分治，就是通过分治跨越当前分治中心的贡献
对题解进行阐述，官方的确实说的不是人话。。。。
设f[i][1/0]表示，在分治中心(就是mid)的左侧走到的i节点的最大值(就是i～mid这个区间)0表示不选mid，1就是选mid
设g[i][1/0]表示，右侧走到i节点的最大值(就是mid+1～r这个区间)，0/1意义同上
这时候就明朗了，我们的答案就是要求跨过中心的所有区间的和。
也就是左右两侧任选节点求和，答案就是
\[\displaystyle\sum^{mid}_{i=l}\sum^{r}_{j=mid+1}max(f[i][0]+g[j][1],f[i][1]+g[j][0],f[i][0]+g[j][0])
\]
你会发现后面的式子好麻烦，所以我们直接换掉它，
设\(cf[i]=max(f[i][1]-f[i][0],0),cg[i]=max(g[i][1]-g[i][0],0)\)
这样的话，上面的就可以化简成
\[\displaystyle\sum^{mid}_{i=l}\sum^{r}_{j=mid+1}(f[i][0]+g[j][0]+max(cf[i],cg[j]))
\]
那就好说了，拆开来看，前面的两项可以直接\(\mathcal{O(n)}\)求
后面的max可以直接对cf，cg进行排序，直接单调指针扫一遍就好了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int
const int N=2e5+5;
const int mod=998244353;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,a[N],ans;
int f[N][2],g[N][2];
int cf[N],cg[N];
int dp[N][2];
void get(int l,int r){
if(l==r){
ans=(ans+a[l])%mod;
//cout<<l<<" "<<ans<<endl;
return ;
}
int mid=l+r>>1;
get(l,mid);get(mid+1,r);
for(re i=l;i<=r;i++)dp[i][0]=dp[i][1]=0;
dp[mid][0]=0;dp[mid][1]=-inf;f[mid][0]=0;
for(re i=mid-1;i>=l;i--)dp[i][0]=max(dp[i+1][0],dp[i+1][1]),dp[i][1]=dp[i+1][0]+a[i],f[i][0]=max(dp[i][0],dp[i][1]);
dp[mid+1][0]=0;dp[mid][1]=-inf;g[mid+1][0]=0;
for(re i=mid+2;i<=r;i++)dp[i][0]=max(dp[i-1][0],dp[i-1][1]),dp[i][1]=dp[i-1][0]+a[i],g[i][0]=max(dp[i][0],dp[i][1]);
for(re i=l;i<=r;i++)dp[i][0]=dp[i][1]=0;
dp[mid][0]=-inf;dp[mid][1]=a[mid];f[mid][1]=a[mid];
for(re i=mid-1;i>=l;i--)dp[i][0]=max(dp[i+1][0],dp[i+1][1]),dp[i][1]=dp[i+1][0]+a[i],f[i][1]=max(dp[i][0],dp[i][1]);
dp[mid+1][0]=-inf;dp[mid+1][1]=a[mid+1];g[mid+1][1]=a[mid+1];
for(re i=mid+2;i<=r;i++)dp[i][0]=max(dp[i-1][0],dp[i-1][1]),dp[i][1]=dp[i-1][0]+a[i],g[i][1]=max(dp[i][0],dp[i][1]);
for(re i=l;i<=mid;i++)cf[i]=max(f[i][1]-f[i][0],0ll),ans=(ans+f[i][0]*(r-mid))%mod;
for(re i=mid+1;i<=r;i++)cg[i]=max(g[i][1]-g[i][0],0ll),ans=(ans+g[i][0]*(mid-l+1))%mod;
sort(cf+l,cf+mid+1);sort(cg+mid+1,cg+r+1);
int il=l,ir=mid;
while(il<=mid){
while(cg[ir+1]<=cf[il]&&ir<r)ir++,ans=(ans+cg[ir]*(il-l))%mod;
ans=(ans+cf[il]*(ir-mid))%mod;il++;
}
while(ir<r){ir++;ans=(ans+cg[ir]*(mid-l+1))%mod;}
//cout<<ans<<endl;
return ;
}
signed main(){
scanf("%lld",&n);
for(re i=1;i<=n;i++)scanf("%lld",&a[i]);
get(1,n);
printf("%lld",ans);
}
T3 第负二题
所以这个题我是\(\mathcal{O(n^2)}\)水过去的
就直接枚举删第几次，然后去枚举每一行怎么删
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int
const int N=5e6+5;
const int mod=998244353;
int n,L,X,Y,l[N],r[N],ql[N],qr[N];
typedef unsigned long long u64;
u64 A,B;
u64 xorshift128p(u64 &A, u64 &B) {
u64 T=A,S=B;
A=S;
T^=T<<23;
T^=T>>17;
T^=S^(S>>26);
B=T;
return T+S;
}
void gen(int n,int L,int X,int Y,u64 A,u64 B,int l[],int r[]){
for(int i=1;i<=n;i++){
l[i]=xorshift128p(A,B)%L+X;
r[i]=xorshift128p(A,B)%L+Y;
if(l[i]>r[i])swap(l[i],r[i]);
}
}
int f[N],ans,nxt[N],head=1,pre[N];
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
bool vis[N];
signed main(){
scanf("%lld%lld%lld%lld%llu%llu",&n,&L,&X,&Y,&A,&B);
gen(n,L,X,Y,A,B,l,r);
for(re i=1;i<n;i++)nxt[i]=i+1,pre[i+1]=i;
for(re i=1;i<=n;i++){
if(!nxt[1])break;
for(re j=head;j;j=nxt[j]){
ql[j]=l[j]+1;qr[j]=r[j]-1;
ql[j]=max(ql[j],max(l[j-1],l[j+1]));
qr[j]=min(qr[j],min(r[j-1],r[j+1]));
//cout<<j<<" "<<ql[j]<<" "<<qr[j]<<endl;
}
for(re j=head;j;j=nxt[j]){
l[j]=ql[j],r[j]=qr[j];
if(qr[j]<ql[j]){
f[j]=i,vis[j]=true;
if(j!=head)nxt[pre[j]]=nxt[j],pre[nxt[j]]=pre[j];
else head=nxt[j];
//cout<<j<<" "<<f[j]<<endl;
}
}
//cout<<head<<endl;
}
for(re i=1;i<=n;i++)ans=(ans+ksm(3,i-1)*f[i]%mod)%mod;//cout<<f[i]<<endl;
printf("%lld",ans);
}