2019.07.09【NOIP提高組】模拟 A 組 比賽總結

題目

wyl8899的TLE

Time Limits: 1000 ms

Memory Limits: 262144 KB

Description

wyl8899今天也很刻苦的在做老師布置下來的題目！

這一天老師布置的題目是這樣的：

給出兩個僅含小寫字母的字元串A和B，輸出最大的k，使得A[1…k]是B的子串。

A和B的長度都不會超過50000。

很顯然他并不知道正确的做法，但是他居然卡着時間過掉了老師給的資料！

你找到了他送出給老師的程式，經過測試你驚訝的發現，他的程式運作時間恰好是最終答案，機關是毫秒。

你現在找到了老師給的資料中的一筆，你決定至多修改A串中的一個字母，使得他的程式盡可能的慢。

現在，你能告訴我修改資料之後他的程式在這個測試點的運作時間麼？（機關當然還是毫秒）

Input

兩行，每行一個僅含小寫字母的字元串，分别是A和B。

保證A和B的長度都不超過50000。

Output

你修改資料之後，wyl8899的程式在這個測試點的運作時間，機關是毫秒。

Sample Input

輸入1：

adbc

aabbabd

輸入2：

aab

aabcc

Sample Output

輸出1：

3

輸出2：

3

Data Constraint

保證A和B的長度都不超過50000。

Hint

資料是在Windows下生成的，測評環境是Linux。

由于換行符的差異，對于C/C++選手，請不要使用gets(s)讀入一行字元，建議使用scanf("%s",s)的形式。

Pascal選手直接使用readln()讀入一行即可，理論上readln()不會受到不同換行符的影響。

法法塔的獎勵

Time Limits: 1000 ms

Memory Limits: 524288 KB

Description

法法塔是很喜歡寫程式的。是以冒着就算碼農屌絲一輩子的風險也大無畏地寫着程式。

碼農們為了表彰法法塔的堅持與執着，決定給法法塔頒布獎勵，為了展現碼農的屌絲氣質，獎勵也将由法法塔自己做出選擇！

所有的獎勵被組織成了一棵樹的形态，每個點都有一個權值。法法塔首先選擇一個子樹，然後選擇從該子樹内的一個葉子節點到該子樹的根的一條路徑，将路徑上節點的權值依次排成一個序列，求得這個序列的最長不下降子序列長度，這個長度就是他能得到的獎品數目。要求該子樹的根必須被選擇。

接下來就是法法塔進行選擇的時間了。盡可能多地得到獎品是自然的。那麼法法塔到底能夠得到多少獎品呢？這是個很糾結的問題，他決定交給你來解決。對于每個子樹，他都希望你能求出他首先選擇了這個子樹後，他能得到的最多的獎品數目。

Input

第一行一個數n，描述樹上節點的個數。

接下來一行n個數，描述樹上每個點的父親，點1為根，其父親設為-1，其餘每個點的父親的标号都小于自己。

接下來一行n個數，表示樹上每個點的權值。

Output

一行n個數，第i個數表示法法塔選擇了以第i個節點為根的子樹後，他可以獲得的最多的獎品個數。

Sample Input

輸入1：

2

-1 1

1 1

輸入2：

6

-1 1 2 1 2 4

4 3 4 3 6 2

Sample Output

輸出1：

2 1

輸出2：

3 1 1 2 1 1

Data Constraint

n ≤ 100000 n\leq 100000 n≤100000，每個數的權值都是1到n的正整數。

wyl8899和法法塔的遊戲

Time Limits: 3000 ms

Memory Limits: 524288 KB

Description

法法塔和wyl8899都喜歡玩遊戲。但是每次玩遊戲法法塔都被wyl8899虐。

為了安慰可憐的法法塔，wyl8899決定大發慈悲，修改了一下遊戲規則。

是這樣的，這兒有一堆石子排成一列，每次wyl8899讓hza選擇一個區間進行遊戲。遊戲嘛，就是采用最普通的規則：兩人輪流操作，每次選擇一堆石子，取掉不為0的石子數，沒法操作者失敗。法法塔要做的是這樣的：

我們現在定義一個區間的弱菜值：表示如果法法塔先取石子，而且法法塔第一步取的石子規定是最右邊的那堆的話，為了必勝，第一步需要取的石子數。如果沒法獲勝的話，那麼弱菜值就是-1。

法法塔要選擇一個區間[l,r]，使得r為wyl8899給定的某個數，l屬于[a,b]，a，b也是wyl8899給定的，要求這個區間的弱菜值是滿足前面的條件中最大。請給出這個最大的弱菜值。

如果最大弱菜值不為-1，法法塔就會馬上取走該區間最右端的石子堆最大弱菜值數量的石子。

Input

第一行一個正整數n，描述了石子的堆數，接下來一行n個數，描述每堆石子的數目。

接下來一行m，表示将進行要進行m次遊戲，每次遊戲由三個值刻畫，r,a,b。r表示被標明的右端點，[a,b]表示選擇的區間的左端點的範圍

Output

對于每個詢問輸出最大的弱菜值。

Sample Input

輸入1：

12

662 477 125 483 17 560 232 59 176 928 807 659

5

5 2 5

4 4 4

2 1 2

6 4 6

6 2 3

輸入2：

7

230 883 456 1020 966 899 610

2

7 1 2

2 1 2

輸入3：

11

392 808 14 71 393 79 11 74 713 232 142

5

8 3 8

9 5 9

3 1 1

8 2 8

7 4 6

Sample Output

輸出1：

17

483

477

560

-1

輸出2：

352

883

輸出3：

74

713

-1

-1

-1

Data Constraint

n ≤ 100000 , m ≤ 10000 n\leq 100000,m\leq 10000 n≤100000,m≤10000，每堆的石子數<=1000。

總結

今天的題目不算太難，暴力的分數是很可觀的，然而我

Emmmmmmm，我比賽的政策出了問題！

首先，我看到T1，覺得是字尾數組或是擴充KMP等神犇算法，就跳過了。

看了T2，我不知怎樣地冒出了一個奇怪的念頭：這題可以把最長不下降子序列倒過來，從根向兒子做最長不上升子序列！

然後就GG了。

比賽過程中，我用了半個小時讀題，再用1個多小時回憶最長不下降子序列的 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2​n)算法并證明它的正确性。

接着思路跟不上了，發現我的做法有問題，于是苦思冥想了30分鐘，比賽還有1個小時左右就要結束了，于是急急忙忙地打水法（即我一開始是以為的正解），再打T1暴力，不料把“修改一個字元”看作了“删除一個字元”了……

于是愉快地爆了〇。

其實今天的比賽是名副其實的資料水，T1和T3暴力、水法碾壓正解！

然而我卻錯誤地選擇了打正解、并且錯誤地選擇了T2

滿臉黑線。。。

第一題正解有很多，我認為的2個神犇算法便在其中，當然還有二分+字元串哈希。可以枚舉B串的一個起點 i i i，二分出A串中的最長比對位置 j j j，那麼最優解顯然是把 j + 1 j+1 j+1修改了，于是再從 i + j + 1 i+j+1 i+j+1繼續比對，把2段的答案加起來。

第二題可以設 f i f_i fi​表示根為 i i i的子樹答案。于是有狀态轉移方程：

f i = 1 + max ⁡ j 在 以 i 為 根 的 子 樹 内 f j ( a i ≤ a j ) f_i=1+\max_{j在以i為根的子樹内}f_j\quad(a_i\leq a_j) fi​=1+j在以i為根的子樹内max​fj​(ai​≤aj​)

那麼那個最大值怎麼維護了，可以用權值線段樹，其中下标為 a a a，權值是 f f f。

這裡涉及到線段樹的合并，這個類似于主席樹，使點數不至于太多。

P.S：這題居然把指針給卡了！

第三題暴力。

可以參考nim遊戲，當幾堆石子的異或和為0時，先手必敗；否則存在最優解。

O ( n 2 ) O(n^2) O(n2)就可以過了（沒有吸氧、臭氧哦！）。

感悟：暴力還是要打的，萬一AC了呢？

CODE

T1

#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define mod 998244353
#define N 50005
#define prime 29
char a[N],b[N];
ll n,m,suma[N],sumb[N],pow[N];
inline ll get1(ll l,ll r){return (suma[r]+mod-suma[l-1]*pow[r-l+1]%mod)%mod;}
inline ll get2(ll l,ll r){return (sumb[r]+mod-sumb[l-1]*pow[r-l+1]%mod)%mod;}
inline ll match(ll l1,ll l2)
{
	if(l1>n||l2>m) return 0;
	ll mid,l=1,r=n-l1<m-l2?n-l1+1:m-l2+1,s=0;
	while(l<=r)
	{
		mid=l+r>>1;
		if(get1(l1,l1+mid-1)==get2(l2,l2+mid-1)) l=mid+1,s=mid;
		else r=mid-1;
	}
	return s;
}
int main()
{
	ll i,j,k,ans=0,max,s;
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1),m=strlen(b+1),max=n>m?n:m,pow[0]=1;
	for(i=1;i<=n;i++) suma[i]=(suma[i-1]*prime%mod+a[i]-'a')%mod;
	for(i=1;i<=m;i++) sumb[i]=(sumb[i-1]*prime%mod+b[i]-'a')%mod;
	for(i=1;i<=max+3;i++) pow[i]=pow[i-1]*prime%mod;
	for(i=1;i<=m;i++)
	{
		j=match(1,i);
		if(j==n||i+j-1==m){if(ans<j) ans=j;break;}
		k=match(j+2,i+j+1);
		if(j+k+1>ans) ans=j+k+1;
	}
	printf("%lld\n",ans);
	return 0;
}
           

T2

#include<cstdio>
using namespace std;
#define N 100005
struct node
{
	int max,lson,rson;
	node(){max=lson=rson=0;}
}set[2000005];
int root[N],fir[N],nex[N],ans[N],a[N],n,cnt;
inline int mymax(int x,int y){return x>y?x:y;}
void add(int &k,int l,int r,int id,int num)
{
	if(!k) k=++cnt;
	if(set[k].max<num) set[k].max=num;
	if(l==r) return;
	int mid=l+r>>1;
	if(id<=mid) add(set[k].lson,l,mid,id,num);
	else add(set[k].rson,mid+1,r,id,num);
}
int merge(int x,int y)
{
	if(!x) return y;if(!y) return x;
	if(set[x].max<set[y].max) set[x].max=set[y].max;
	set[x].lson=merge(set[x].lson,set[y].lson);
	set[x].rson=merge(set[x].rson,set[y].rson);
	return x;
}
int qry(int k,int l,int r,int x,int y)
{
	if(!k) return 0;
	if(l==x&&r==y) return set[k].max;
	int mid=l+r>>1;
	if(y<=mid) return qry(set[k].lson,l,mid,x,y);
	if(x>mid) return qry(set[k].rson,mid+1,r,x,y);
	return mymax(qry(set[k].lson,l,mid,x,mid),qry(set[k].rson,mid+1,r,mid+1,y));
}
void dfs(int k)
{
	for(int i=fir[k];i;i=nex[i])
		dfs(i),root[k]=merge(root[k],root[i]);
	ans[k]=qry(root[k],1,n,1,a[k])+1;
	add(root[k],1,n,a[k],ans[k]);
}
int main()
{
	int i,j;
	scanf("%d%d",&n,&j);
	for(i=2;i<=n;i++) scanf("%d",&j),nex[i]=fir[j],fir[j]=i;
	for(i=1;i<=n;i++) scanf("%d",a+i);
	dfs(1);
	for(i=1;i<=n;i++) printf("%d ",ans[i]);
	return 0;
}
           

T3

#include<cstdio>
using namespace std;
#define N 100005
int s[N];
int main()
{
	int n,m,i,a,b,k,sum,ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",s+i);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d%d%d",&k,&a,&b);
		if(b==k)
		{
			if(s[k]) printf("%d\n",s[k]),s[k]=0;
			else puts("-1");continue;
		}
		for(i=k-1,sum=0;i>b;i--) sum^=s[i];
		for(ans=0;i>=a;i--)
		{
			sum^=s[i];
			if(ans<s[k]-sum) ans=s[k]-sum;
			if(ans==s[k]) break;
		}
		if(ans) s[k]-=ans,printf("%d\n",ans);
		else puts("-1");
	}
	return 0;
}