ChiFAN Round 1 & NOIP 膜你赛

最打摆的一集。

前言

有一说一，这里本来要写刚刚想好的没打好的借口的，结果一看怎么啊，所以没啥借口了，~~实力如此~~。

~~下午讲题还被拉去讲最拉跨的~~ 了。

A. 红与黑（A）

题目简介

给定一个字符串，之后每次操作随机生成一个小写字母，添加到初始空串的末尾，若当前操作之后不再是的子串，则游戏结束。

求期望操作数。精度要求

数据范围：

有高手线段树，还有高手爆搓（空间开小遗憾离场）。大家好我是暴力选手，所以我用暴力过了这道题。

考虑期望定义，期望等于概率乘权值，所以我们需要将操作次的概率求出来然后相加即可（考场上这点想了）。

设表示长度为的子串有多少个（不算相同的），再设表示操作次的期望，则有：

$f_i=\frac{c(i-1)}{26^{i-1}}-\sum_{j>i}f_j$

这里有两个是因为题目中定义游戏结束是在操作之后。

所以我们得到了一个。

但是你发现，当足够大的时候，这个时候的答案可以忽略不计，所以大概到的时候，也就是的时候，就可以停止了。

所以时间复杂度，其中。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char c){ putchar(c); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXC=28;
int Len,N;
double Dp[MAXN],P[MAXN],ans;
char Str[MAXN];
inline int f(int x)
{
	std::unordered_map<ll,bool>Hash;
	int cnt=0;
	for(int i=1;i<=Len-x+1;++i)
	{
		ll sum=0;
		for(int j=i;j<=i+x-1;++j) sum=sum*26+(Str[j]-'a');
		if(Hash.find(sum)==Hash.end()) ++cnt,Hash[sum]=1;
	}
	// write(x,' ',cnt,'\n');
	return cnt;
}
int main()
{
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	scanf("%s",Str+1);
	Len=std::strlen(Str+1);
	N=std::min(Len,12);
	P[N+1]=Dp[N+1]=1.0/std::pow(26,N);
	for(int i=N;i;--i)
	{
		Dp[i]=1.0*f(i-1)/std::pow(26,i-1)-P[i+1];
		P[i]=Dp[i]+P[i+1];
	}
	for(int i=1;i<=N+1;++i) ans+=Dp[i]*i;
	printf("%.4lf",ans);
	return 0;
}
/*

*/

B. 罗生门（B）

题目简介

给定个长度为的序列，现在在每个序列中随机选取一个数，组成一个长度为的新序列，求出这个新序列的中位数的期望大小。对取模。

数据范围：

考场上做做了，旁边都切了（~~后来证实写的全是暴力~~），所以这道题没怎么想，搓了一个想法样例全没过直接做去了。（后来发现这居然是正解，还得了）

考虑钦定为中位数，那么我们直接统计另外四个序列中两大两小的个数即可。然后你发现如果出现重复排列就会算重，所以我们排列组合容斥一下就可。时间复杂度。

这边的还有高手，我们钦定一个第二关键字，记即可。直接避免容斥。

这道题有个缺陷是没有值域范围，比较阴间，但是稳过。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char c){ putchar(c); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXS=2.5e6+10;
const int Mod=1145141;
template<class T1,class T2>
inline void add(T1 &x,T2 y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,M,a[6][MAXN],b[6][MAXN];
int Cnt[6][MAXS];
std::vector<int>Nums;
inline ll getCnt(int i,int l,int r){ return l>r?0:Cnt[i][r]-Cnt[i][l-1]; }
inline ll qPow(ll a,ll b=Mod-2)
{
	ll res=1;
	for(;b;b>>=1,a=a*a%Mod) (b&1)&&(res=res*a%Mod);
	return res;
}
signed main()
{
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	read(N);
	for(int i=1;i<=5;++i)
		for(int j=1;j<=N;++j)
			read(a[i][j]),b[i][j]=6*a[i][j]+i,Nums.push_back(b[i][j]);
	std::sort(Nums.begin(),Nums.end());
	Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
	for(int i=1;i<=5;++i)
		for(int j=1;j<=N;++j)
			b[i][j]=std::lower_bound(Nums.begin(),Nums.end(),b[i][j])-Nums.begin()+1;
	M=Nums.size()+1;
	for(int i=1;i<=5;++i)
	{
		for(int j=1;j<=N;++j) ++Cnt[i][b[i][j]];
		for(int j=1;j<=M;++j) Cnt[i][j]+=Cnt[i][j-1];
	}
	ll ans=0,Inv=qPow(qPow(N,5));
	for(int i=1;i<=5;++i)
		for(int j=1;j<=N;++j)
		{
			ll sum=0;
			for(int k1=1;k1<=5;++k1) if(k1!=i)
				for(int k2=k1+1;k2<=5;++k2) if(k2!=i)
					for(int k3=1;k3<=5;++k3) if(k3!=i&&k3!=k1&&k3!=k2)
						for(int k4=k3+1;k4<=5;++k4) if(k4!=i&&k4!=k1&&k4!=k2)
						{
							// write(i,' ',k1,' ',k2,' ',k3,' ',k4,'\n');
							ll sum1=getCnt(k1,1,b[i][j]-1)*getCnt(k2,1,b[i][j]-1)%Mod;
							ll sum2=getCnt(k3,b[i][j]+1,M)*getCnt(k4,b[i][j]+1,M)%Mod;
							add(sum,sum1*sum2%Mod);
						}
			add(ans,sum*Inv%Mod*a[i][j]%Mod);
		}
	write(ans);
	return 0;
}
/*

*/

C. 死魂灵（C）

题目简介

给定张牌，正面背面，初始存在一个数，然后将为正的牌翻面，并将修改为其背面的数，若无法行动则重新选择，求是否存在一种方案使得所有牌恰好被翻一次。一共次询问，每次询问区间内的牌。

数据范围：

从向连接有向边，那么有解的充要条件就是组成了若干个不交的环，那这不就换皮星战吗。

给每个结点随机权值，记录入度和和出度和，判断区间是否相等即可。时间复杂度。

脑瘫的我写了一个一个一个啊，幸好没被卡常。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char c){ putchar(c); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
const ll Mod=1e12+7;
int N,M=1e6,Q;
std::mt19937 rnd((ll)new char);
ll val[MAXN];
struct BIT
{
	ll Tre[MAXN],Siz;
	inline void build(int n){ Siz=n;for(int i=0;i<=n;++i) Tre[i]=0; }
	inline int lowbit(int x){ return x&(-x); }
	inline void add(int x,ll v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]+=v; }
	inline ll query(int x)
	{
		ll res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;
	}
	inline ll get(int l,int r){ return l>r?0ll:query(r)-query(l-1); }
}In,Out;
int main()
{
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
	read(N,Q);In.build(N),Out.build(N);
	for(int i=1;i<=M;++i) val[i]=rnd()%Mod;
	for(int i=1,u,v;i<=N;++i) read(u,v),In.add(i,val[u]),Out.add(i,val[v]);
	for(int ql,qr;Q--;)
	{
		read(ql,qr);
		puts(In.get(ql,qr)==Out.get(ql,qr)?"Yes":"No");
	}
	return 0;
}
/*

*/