解题报告
- JZOJ 3337 wyl8899的TLE
-
- 题目
- 分析
- 代码
- JZOJ 3338 法法塔的奖励
-
- 题目
- 分析
- 代码
- JZOJ 3339 wyl8899和法法塔的游戏
-
- 题目
- 分析
- 代码
JZOJ 3337 wyl8899的TLE
题目
可以最多修改字符串 A A A的一个字母,若 A A A长度为 k k k的前缀是 B B B的子串,问 k k k的最大值
分析
枚举公共子串在 B B B中的起始位置,二分在完全相同的情况下最长能延长到哪里,因为有一次修改的机会,也就是默许下一位可以为任意字母,那么从下下一位重新二分,求出最终答案,时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
代码
#include <cstdio>
#include <cstring>
#define rr register
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
typedef unsigned long long ull;
const int N=50101; char S1[N],S2[N];
ull h[N],s1[N],s2[N]; int len1,len2;
inline ull hash1(int l,int r){return s1[r]-s1[l-1]*h[r-l+1];}
inline ull hash2(int l,int r){return s2[r]-s2[l-1]*h[r-l+1];}
inline signed getf(int l1,int l2){
if (l1>len1||l2>len2) return 0;
rr int l=-1,r=min(len1-l1,len2-l2)+1;
while (l<r){
rr int mid=(l+r+1)>>1;
if (hash1(l1,l1+mid-1)==hash2(l2,l2+mid-1)) l=mid;
else r=mid-1;
}
return l;
}
signed main(){
h[0]=1; for (rr int i=1;i<N;++i) h[i]=h[i-1]*37; rr int ans=0;
scanf("%s%s",S1+1,S2+1),len1=strlen(S1+1),len2=strlen(S2+1);
for (rr int i=1;i<=len1;++i) s1[i]=s1[i-1]*37+(S1[i]^96);
for (rr int i=1;i<=len2;++i) s2[i]=s2[i-1]*37+(S2[i]^96);
for (rr int i=1;i<=len2;++i){
rr int k1=getf(1,i),k2;
if (i+k1-1==len2||k1==len1) {ans=max(ans,k1); continue;}
k2=getf(k1+2,i+k1+1),ans=max(ans,k1+k2+1);
}
return !printf("%d",ans);
}
JZOJ 3338 法法塔的奖励
题目
树上最长不下降子序列
分析
显然 f i = f j + 1 ( w i ≥ w j ) f_i=f_j+1(w_i\geq w_j) fi=fj+1(wi≥wj),对于每个节点用线段树维护 f f f的最大值。每次就是询问权值在 1 ∼ w i 1\sim wi 1∼wi中 f f f值的最大值。而之前的合并操作就变成了简单的线段树合并。总时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=100011;
struct node{int y,next;}e[N];
int w[N<<4],a[N],hs[N],ls[N<<4],rs[N<<4],rt[N],ans[N],n,tot;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void add(int x,int y){e[y]=(node){y+1,hs[x]}; hs[x]=y;}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed max(int a,int b){return a>b?a:b;}
inline signed query(int rt,int l,int r,int x,int y){
if (!rt) return 0;
if (l==x&&r==y) return w[rt];
rr int mid=(l+r)>>1;
if (y<=mid) return query(ls[rt],l,mid,x,y);
else if (x>mid) return query(rs[rt],mid+1,r,x,y);
else return max(query(ls[rt],l,mid,x,mid),query(rs[rt],mid+1,r,mid+1,y));
}
inline void update(int &rt,int l,int r,int x,int z){
if (!rt) rt=++tot;
if (l==r) {w[rt]=max(w[rt],z); return;}
rr int mid=(l+r)>>1;
if (x<=mid) update(ls[rt],l,mid,x,z);
else update(rs[rt],mid+1,r,x,z);
w[rt]=max(w[ls[rt]],w[rs[rt]]);
}
inline signed merge(int now,int last,int l,int r){
if (!now||!last) return now+last;
w[now]=max(w[now],w[last]);
if (l==r) return now;
rr int mid=(l+r)>>1;
ls[now]=merge(ls[now],ls[last],l,mid);
rs[now]=merge(rs[now],rs[last],mid+1,r);
return now;
}
inline void dfs(int x){
rr int root=0;
for (rr int i=hs[x];i;i=e[i].next){
dfs(e[i].y);
root=merge(root,rt[e[i].y],1,n);
}
ans[x]=query(root,1,n,1,a[x])+1;
update(root,1,n,a[x],ans[x]);
rt[x]=root;
}
signed main(){
n=iut(); iut();
for (rr int i=1;i<n;++i) add(iut(),i);
for (rr int i=1;i<=n;++i) a[i]=iut();
dfs(1);
for (rr int i=1;i<=n;++i) print(ans[i]),putchar(i==n?10:32);
}
JZOJ 3339 wyl8899和法法塔的游戏
题目
一个序列,每次将一段数异或一个值,或者询问一段区间中与某个数异或结果最小的数是多少。
分析
正解可持久化trie+分块,暴力可过
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
int n,a[100101],ans;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
signed main(){
n=iut();
for (rr int i=1;i<=n;++i) a[i]=iut();
for (rr int m=iut();m;--m){
rr int r=iut(),lef=iut(),rig=iut(),sum=0,ans=-1;
if (rig==r){
if (a[r]) print(a[r]);
else putchar('-'),putchar(49);
putchar(10),a[r]=0; continue;
}
for (rr int j=rig+1;j<r;++j) sum^=a[j];
for (rr int j=rig;j>=lef;--j){
sum^=a[j],ans=ans>a[r]-sum?ans:a[r]-sum;
if (ans==a[r]) break;
}
ans-=!ans;
if (ans>-1) a[r]-=ans,print(ans);
else putchar('-'),putchar(49); putchar(10);
}
return 0;
}