2018_10_24 模拟賽

解題報告

• JZOJ 5182 碼靈鼠
• • 題目
  • 分析
  • 代碼
• JZOJ 5178 So many prefix?
• • 題目
  • 分析
  • 代碼
• JZOJ 5177 TRAVEL
• • 題目
  • 分析
  • 代碼

JZOJ 5182 碼靈鼠

題目

a 0 = 1 a_0=1 a0​=1

a n = a i + a j ( n ≥ 1 , i , j a_n=a_i+a_j (n\geq 1, i,j an​=ai​+aj​(n≥1,i,j均在 [ 0 , n − 1 ] [0,n-1] [0,n−1]内均勻随機 ) ) )

問 a n a_n an​的期望值

分析

由于是等機率的，也就是 a n = 2 ∗ a i ( 1 ≤ i ≤ n ) a_n=2*a_i(1\leq i\leq n) an​=2∗ai​(1≤i≤n)

等差數列告訴我們， a n = 2 ∗ ( 1 + n ) n 2 ÷ n a_n=2*\frac{(1+n)n}{2}\div n an​=2∗2(1+n)n​÷n

綜上所述， a n = n + 1 a_n=n+1 an​=n+1

代碼

#include <cstdio>
#define rr register
using namespace std;
unsigned n,t;
inline signed iut(){
	rr unsigned ans=0; rr char c=getchar();
	while (c<48||c>57) c=getchar();
	while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
	return ans;
}
void print(unsigned ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
signed main(){
	t=iut();
	while (t--){
		n=iut();
		print(n+1);
		putchar(10);
	}
	return 0;
}
           

JZOJ 5178 So many prefix?

題目

求所有長度是偶數的字首在字元串出現的次數和

分析

這道題其實就是kmp了，其實可以說是一道動态規劃的題目

設 f [ i ] f[i] f[i]表示以 s [ i ] s[i] s[i]結尾的字首出現的次數

f [ i ] = f [ f a i l [ i ] ] + [ e v e n ( i ) ] f[i]=f[fail[i]]+[even(i)] f[i]=f[fail[i]]+[even(i)]

然後統計和就行了

代碼

#include <cstdio>
#include <cstring>
#define rr register
using namespace std;
char s[200001]; int len,fail[200001],f[200001];
signed main(){
	scanf("%s",s+1); len=strlen(s+1);
	for (rr int i=1,j=0;i<len;++i){
		while (j&&s[i+1]!=s[j+1]) j=fail[j];//失敗指針
		fail[i+1]=(j+=(s[i+1]==s[j+1]));
		f[i+1]=(i&1)+f[fail[i+1]];//動态規劃
	}
	for (rr int i=2;i<=len;++i) f[i]+=f[i-1];
	printf("%d",f[len]);
	return 0;
}
           

JZOJ 5177 TRAVEL

題目

分析

枚舉通道的 l l l，spfa求出最大的 r r r，因為字典序需要最小，是以 l l l要從小到大排序,雖然分析短，但是代碼畢竟也是打了很長時間的

代碼

#include <cstdio>
#include <algorithm>
#include <deque>
#define rr register
using namespace std;
struct node{
	int x,y,l,r,next;
	bool operator <(const node &a)const{
	    return l<a.l;
	}
}e[6003];
int n,k,m,ls[1003],v[1003],dis[1003],ans,lll,rrr;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (c<48||c>57) c=getchar();
	while (c>47&&c<58) ans=(ans<<3)+(ans<<1)+c-48,c=getchar();
	return ans;
}
inline signed spfa(int val){
    rr deque<int>q; q.push_back(1); v[1]=1; dis[1]=1000001;
    for (rr int i=2;i<=n;++i) v[i]=dis[i]=0;
    while (q.size()){
    	int x=q.front(); q.pop_front();
    	for (rr int i=ls[x];i;i=e[i].next)
    	if (e[i].l<=val&&e[i].r>=val&&dis[e[i].y]<min(dis[x],e[i].r)){//如果必然會有val且目前蟲洞可行
    		dis[e[i].y]=min(dis[x],e[i].r);
    		if (!v[e[i].y]){
    		    v[e[i].y]=1;
				if (q.size()&&dis[e[i].y]>dis[q.front()]) q.push_front(e[i].y);
				    else q.push_back(e[i].y);	
			}
		}
		v[x]=0;
	}    
	return dis[n];
}
inline void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
signed main(){
	n=iut(); k=iut();
	for (rr int i=1;i<=k;++i){
		rr int x=iut(),y=iut(),l=iut(),r=iut();
		if (x==y) continue;
		e[++m]=(node){x,y,l,r,0};
	}
	sort(e+1,e+1+m);
	for (rr int i=1;i<=m;++i){
		e[i+m]=e[i]; swap(e[i+m].x,e[i+m].y);
	    e[i].next=ls[e[i].x]; ls[e[i].x]=i;
	    e[i+m].next=ls[e[i+m].x]; ls[e[i+m].x]=i+m;
	}
	for (rr int i=1;i<=m;++i){
		rr int r=spfa(e[i].l);
		if (ans<r-e[i].l+1){
			ans=r-e[i].l+1;
			lll=e[i].l; rrr=r;
		}
	}
	if (ans){
		print(ans);
		for (rr int i=lll;i<=rrr;++i) 
		    putchar(i==lll?10:32),print(i);
	}
	else putchar(48);
	return 0;
}