2019.07.09【NOIP提高組】模拟 A 組

解題報告

• 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;
}