首页 > 其他分享 >冲刺 CSP 联训模拟2

冲刺 CSP 联训模拟2

时间：2024-10-05 09:44:00浏览次数：6  
标签：return 若栈 int long 联训 冲刺 rtr frac CSP

题面

温馨提示

代码中的变量名可能与题意、题解不同。
代码不删缺省源，可以直接拿来对拍。

T1 挤压

Solution

众所周知，异或是一种按位运算，不好进行十进制的数间合并。我们考虑将每个数拆分为二进制的形式进行处理。
此时，对于每一种情况，假设表示 \(2^i\) 二进制位的值为 \(b_i\)，我们的答案（平方）的形式应为：

\[\left( \sum_{i=0}^{i<30}{2^ib_i}\right)^2=\sum_{i=0}^{i<30}{\sum_{j=i+1}^{j<30}{2^{i+j+1}b_ib_j}}+\sum_{i=0}^{i<30}{2^{2i}b_i} \]

这相当于对于第 \(i\) 位与第 \(j\) 位（\(i\leq{j}\)），对答案产生贡献的应为这两位是否同时为 \(1\)。对于本题，允许实现 \(\log^2\) 级别的算法，所以考虑对于每个数，枚举每两个数位，根据该数这两位的情况确定这两个数位在选择是否异或该数后分别为 \(00\)，\(01\)，\(10\)，\(11\) 的概率（等于期望）并带入上面式子。

Optimise

考虑上面这个实现分讨的量很大，我们考虑将第 \(i\) 和 \(j\) 位是否为 \(1\) 的情况转为 \(2b_i+b_j\)，即将 \(00\) 的情况记作 \(0\)，\(01\) 的情况记作 \(1\)，以此类推。考虑将枚举到的数的这两位的情况记作 \(t\)，将已经得到的记作 \(i\) 的概率记为 \(dp_i\)，则新的 \(dp_i\) 包含两种情况：一种是根本没有选到，从 \(dp_i\) 转移，另一种是取到该数，从 \(dp_x\) 转移，其中 \(x \operatorname{xor} t=i\)。根据异或的自反律，可得：

\[dp_i=dp_i(1-p)+dp_{i \operatorname{xor} t}p \]

其中 \(p\) 表示当前的数被选中的概率。

Code

代码（$793$ ms $2.8$ Mib） 
#include<bits/stdc++.h>
using namespace std;
const long long p=1000000007;
inline long long qpow(long long x,long long y){
	long long rtr=1;
	for(;y;y>>=1){
		if(y&1)
		rtr=rtr*x%p;
		x=x*x%p;
	}
	return rtr;
}
long long n,m,a[100100],tinv,ps[200100],ne[200100],dp[8][64][64],ans;
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%lld",&n);
	tinv=qpow(1000000000,p-2);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%lld",&ps[i]);
		ps[i]=ps[i]*tinv%p;
		ne[i]=((1-ps[i])%p+p)%p;
	}
	for(int i=0;i<30;++i){
		for(int j=0;j<30;++j){
			dp[0][i][j]=1;
		}
	}
	int tb;
	long long tem[8];
	for(int i=1;i<=n;++i){
		for(int j=0;j<30;++j){
			for(int k=j;k<30;++k){
				tem[0]=dp[0][j][k];
				tem[1]=dp[1][j][k];
				tem[2]=dp[2][j][k];
				tem[3]=dp[3][j][k];
				tb=(((a[i]>>j)&1)<<1)|((a[i]>>k)&1);
				for(int l=0;l<4;++l){
					dp[l][j][k]=(tem[l]*ne[i]%p+tem[l^tb]*ps[i]%p)%p;
				}
			}
		}
	}
	for(int i=0;i<30;++i){
		for(int j=0;j<30;++j){
			if(i^j)
			ans=(ans+(((1ll<<(i+j))%p*dp[3][i][j]%p)<<1)%p)%p;
			else
			ans=(ans+(1ll<<(i+j))%p*dp[3][i][j]%p)%p;
		}
	}
	printf("%lld",ans);
	return 0;
}

T2 工地难题

Solution

假设不考虑 \(k\)，相当于将 \(n-m\) 个 \(0\) 插进 \(m\) 个 \(1\)，方案数为 \(\dbinom{n}{n-m}\)。考虑取出 \(1\) 组 \(k+1\) 个点再加进去，也就是说钦定 \(1\) 组大于 \(k\)，方案数为 \(\dbinom{n-k-1}{n-m}\dbinom{1}{n-m+1}\)，即现将剩下的数插板再将钦定的放入 \(n-m\) 个 \(0\) 之间的空中。然而我们发现，有其中一组在 \(k\) 与 \(2k\) 之间的可以通过在全在剩下的中取或取一部分剩下的再加上钦定的被算重两次，我们再钦定 \(2k+2\) 减去贡献。以此类推进行容斥，最终最大连续段的长度小于等于\(k\) 的值为：

\[\sum_{i=0}^{i(k+1)\leq{m}}{(-1)^i \dbinom{n-i(k+1)}{n-m} \dbinom{n-m+1}{k}} \]

进行差分即可得到每个 \(k\) 的答案。
对于 \(1\leq{k}\leq{m}\)，每一个 \(k\) 至多进行 \(O(\frac{n}{k})\) 级别的计算，总的复杂度为调和级数的，即 \(O(n\log{m})\)。

证明

考虑将 \(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{m}\) 拆成 \(1+\frac{1}{2}+(\frac{1}{3}+\frac{1}{4})+(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8})+\cdots\)，之后每一组的元素个数为上一组的两倍，发现每一组的和都小于 \(1\)，有对数级别的组数，乘上分子 \(n\) 得到 \(O(n\log{m})\)。

Code

代码（$45$ ms $7.7$ Mib） 
#include<bits/stdc++.h>
using namespace std;
const long long p=1000000007;
long long n,m,t[400100],invt[400100],lans;
inline long long qpow(long long x,long long y){
	long long rtr=1;
	for(;y;y>>=1){
		if(y&1){
			rtr=rtr*x%p;
		}
		x=x*x%p;
	}
	return rtr;
}
inline long long c(long long x,long long y){
	if(x>y)
	return 0;
	return t[y]*invt[x]%p*invt[y-x]%p;
}
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	t[0]=1;
	invt[0]=1;
	for(int i=1;i<=(n<<1);++i){
		t[i]=i*t[i-1]%p;
	}
	invt[n<<1]=qpow(t[n<<1],p-2);
	for(int i=(n<<1)-1;i;--i){
		invt[i]=(i+1)*invt[i+1]%p;
	}
	for(int i=1;i<=m;++i){
		long long ans=c(n-m,n);
		for(int j=m-i-1,k=1;j>=0;j-=i+1,++k){
			if(k&1)
			ans=((ans-c(n-m,j+n-m)*c(k,n-m+1)%p)%p+p)%p;
			else
			ans=(ans+c(n-m,j+n-m)*c(k,n-m+1)%p)%p;
		}
		printf("%lld ",((ans-lans)%p+p)%p);
		lans=ans;
	}
	return 0;
}

T3 星空遗迹

Solution

我们先考虑对“最终胜者”操作进行化简，可以发现以下性质：

  • 对于 \(AAAA\) ，只有前一个和后一个影响比较结果，如果后面大了前面所有的 \(A\) 也跟着变，所以 \(AAAA\) 等价于 \(A\)。
  • 对于 \(ABA\) ，其中 \(A\) 能赢 \(B\)，在第一局必定为 \(AAX\)，\(X\) 表不确定。我们发现这个字符串只要最后一个字母是 \(A\) 就不会影响他与后面比较的结果，即 \(X\) 不变，所以 \(ABA\) 等价于只有一个 \(A\)。

至此，我们将某个字母前面是该字母或它能赢的字母的情况进行了化简，得到一种稳定情况：某个字母前面是他赢不了的一个字母，反映到本题，则稳定的串一定为 \(RSPRSPRSPRSP\cdots\) 的一个子串。考虑维护一个单调栈，在栈内维护稳定结构，即当当前字母为 \(A\) 且 \(A\) 赢 \(B\)，\(C\) 赢 \(A\) 时：

  • 若栈为空，则将 \(A\) 入栈。
  • 若栈顶为 \(C\)，加入 \(A\) 后依旧稳定，直接入栈。
  • 若栈顶为 \(A\)，因为栈是稳定结构要么只有 \(A\) 要么 \(A\) 前面有 \(C\)，只需弹出原来的 \(A\) 再入栈就稳定了。
  • 若栈顶为 \(B\)，因为栈是稳定结构要么只有 \(B\) 要么 \(B\) 前面有 \(A\)，只有 \(B\) 则清栈加 \(A\)，否则按照上文第二个性质去掉 \(AB\) 并将 \(A\) 入栈。

容易发现，由于稳定结构每个字符都无法更新前一个字符，所以加入每个字符后“最终胜者”为此时栈顶字母。
以上操作放到本题复杂度为 \(O(nq)\)，考虑将整个字符串入栈，对某个区间查询有以下情况：

  • 存在栈的大小为 \(1\)，则最后一次出现这种情况的时候进栈的元素即为栈底。
  • 不存在这种情况，考虑忽略前面字符，最后一次栈最小时入栈元素要么是第一个进来没被消除，要么就是清空了栈，所以他就是栈底。

现在考虑与上文相对应的，\(A\) 入栈是如何统计栈的大小。设上一次大小为 \(f_{i-1}\)，此次为 \(f_i\)。

  • 若栈为空，\(f_i=1\)。
  • 若栈顶为 \(C\)，直接入栈，\(f_i=f_{i-1}+1\)。
  • 若栈顶为 \(A\)，弹出 \(A\) 再入栈，\(f_i=f_{i-1}\)。
  • 若栈顶为 \(B\)，弹出 \(AB\) 再入栈，\(f_i=\max(f_{i-1}-1,1)\)。

考虑对于 \(1\) 取 \(\max\) 很麻烦，我们考虑在 \(f_{i-1}\leq{1}\) 时仍然减 \(1\)，考虑如果出现连续减 \(1\)，说明后加的优于前面的，取后面，也就是 \(f\) 较小的。而且可以发现，如果存在多个最小值，说明当前栈顶无法在被更新。问题转化为：求区间内任意一个 \(f\) 最小的点的字符，即线段树区间求最小值位置。
对于修改，我们考虑每次修改 \(i\) 位置只会影响 \(f_i-f_{i-1}\) 和 \(f_{i+1}-f{i}\)，这样会影响后面所有的 \(f\)，记录每个 \(f_i-f_{i-1}\) 并据此区间修改 \(f\) 即可。

Code

代码（$180$ ms $8.3$ Mib） 
#include<bits/stdc++.h>
using namespace std;
struct node{
	int data[800100],pos[800100],tag[800100];
	inline void pushdown(int now){
		if(tag[now]){
			data[now<<1]+=tag[now];
			tag[now<<1]+=tag[now];
			data[now<<1|1]+=tag[now];
			tag[now<<1|1]+=tag[now];
			tag[now]=0;
		}
	}
	void build(int now,int lft,int rgt,int* dt){
		if(lft==rgt){
			data[now]=dt[lft];
			pos[now]=lft;
			return;
		}
		pushdown(now);
		int mid=(lft+rgt)>>1;
		build(now<<1,lft,mid,dt);
		build(now<<1|1,mid+1,rgt,dt);
		if(data[now<<1]<data[now<<1|1]){
			data[now]=data[now<<1];
			pos[now]=pos[now<<1];
		}else{
			data[now]=data[now<<1|1];
			pos[now]=pos[now<<1|1];
		}
	}
	void add(int now,int lft,int rgt,int ll,int rr,int dt){
		if(ll<=lft&&rgt<=rr){
			data[now]+=dt;
			tag[now]+=dt;
			return;
		}
		pushdown(now);
		int mid=(lft+rgt)>>1;
		if(ll<=mid)
		add(now<<1,lft,mid,ll,rr,dt);
		if(rr>mid)
		add(now<<1|1,mid+1,rgt,ll,rr,dt);
		if(data[now<<1]<data[now<<1|1]){
			data[now]=data[now<<1];
			pos[now]=pos[now<<1];
		}else{
			data[now]=data[now<<1|1];
			pos[now]=pos[now<<1|1];
		}
	}
	pair<int,int> query(int now,int lft,int rgt,int ll,int rr){
		if(ll<=lft&&rgt<=rr){
			return {data[now],pos[now]};
		}
		pushdown(now);
		bool vis=0;
		int mid=(lft+rgt)>>1;
		pair<int,int> rtr,tem;
		if(ll<=mid){
			rtr=query(now<<1,lft,mid,ll,rr);
			vis=1;
		}
		if(rr>mid){
			tem=query(now<<1|1,mid+1,rgt,ll,rr);
			if(vis){
				if(rtr.first>tem.first)
				rtr=tem;
			}else{
				rtr=tem;
			}
		}
		return rtr;
	}
}tree;
char a[200100];
int n,q,f[200100],s[200100];
inline int getv(char x){
	if(x=='R')
	return 2;
	if(x=='S')
	return 1;
	return 0;
}
inline int cmp(char x,char y){
	if(x==y)
	return 0;
	x=getv(x);
	y=getv(y);
	if((!x)&&y==2)
	return 1;
	if(x==2&&(!y))
	return -1;
	if(x>y)
	return 1;
	return -1;
}
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%d%d %s ",&n,&q,a+1);
	f[1]=1;
	s[1]=1;
	for(int i=2;i<=n;++i){
		f[i]=cmp(a[i-1],a[i]);
		s[i]=f[i]+s[i-1];
	}
	tree.build(1,1,n,s);
	char tc;
	int ta,tb,td,tem;
	for(;q;--q){
		scanf("%d",&ta);
		if(ta==1){
			scanf("%d %c ",&tb,&tc);
			a[tb]=tc;
			if(tb^1){
				tem=cmp(a[tb-1],a[tb]);
				tree.add(1,1,n,tb,n,tem-f[tb]);
				f[tb]=tem;
			}
			if(tb^n){
				tem=cmp(a[tb],a[tb+1]);
				tree.add(1,1,n,tb+1,n,tem-f[tb+1]);
				f[tb+1]=tem;
			}
		}else{
			scanf("%d%d",&tb,&td);
			printf("%c\n",a[tree.query(1,1,n,tb,td).second]);
		}
	}
	return 0;
}

T4

待更。

标签：return,若栈,int,long,联训,冲刺,rtr,frac,CSP
From： https://www.cnblogs.com/blog21012004/p/18447583

相关文章

  • 冲刺 CSP 联训模拟 2
    T1挤压概率期望，二进制拆位看到异或想到拆位算贡献\[\begin{aligned}ans&=\sum_xx^2P(x)\\&=\sum_x(b_1+b_2+...+b_{30})^2P(x)\\\(b_i表示\x\二进制下\i\位的值)\\&=\sum_x(b_1b_1+b_1b_2+...b_{30}b_{29}+b_{30}b_{30})P(x)\\&=\sum_i^{30}\sum_j^{30......
  • 代码源CSP-S模拟赛Day7-9赛后总结
    代码源CSP-S模拟赛Day7-9赛后总结Day7赛时先扫一遍题，T1显然数位dp，感觉放在T1应该不难，而且题面有一种很亲切的感觉，感觉很可做。T2简单思考一下发现最终合成的数就是\(a_1\)，\(a_2\)，\(a_3\)……，\(a_n\)这n个数填正负号再加上一个k的倍数，估计会有一些比较智慧的手法，感觉很......
  • CSP-S 模拟赛34
    CSP-S模拟赛34T1考虑对原序列将\(k\)的左右分成两个序列。simple的想法是分别从\(1\)开始跑前缀和，每一次总跑到下一个小于它的点，然后依次类推。发现这样做碰到序列最小值之后难以继续。然而我们发现这样跑点的过程从前往后和从后往前是等价的。这样考虑的原因是发现这样......
  • CSP-S 模拟赛 32
    CSP-S模拟赛32rnk25，\(0+0+9+0=9\)。T1[CF1578K]KingdomofIslands还没改出来。T2[CF1578L]Labyrinth警钟嚼烂：改代码改干净。首先考虑如果从\(a\)走到\(b\)，人最胖是多少。毫无疑问，这是一个最大生成树问题。在这个基础上考虑原问题，我们发现由于人会越来越胖，一定有边......
  • CSP-S模拟赛20241004
    A你考虑可以把这个数组当中的每个数表示成另一种形式：\(a_i=k_i\timesx+b\)(其中\(x\)是模数，\(b\)为余数)。对于求两个数是否对于某个余数同余，显然你要判断他们两个的差，即\(a_i-a_j\)，那么我们用上面那种形式表示其实就是\(a_i-a_j=(k_i-k_j)\timesx\),所以你要判断整个数......
  • CSP-JS多省分数线分析！复赛如何准备？（附复赛流程视频）
    截止目前已经有多个省份CSP-JS的分数线已经出了，很多省份比去年提升了不少，像河南等地都提升了20多分，不过也有一些省份，天津比去年提升分数却不是很多。还有很多省份分数线没出，各位家长想要预估是否能够晋级的，以下是已出分数线省份表格统计：目前已出分数线省份省份入门组......
  • [CSP-J 2023] 小苹果（apple）-----------用数组
    1#include<iostream>2usingnamespacestd;3intmain(){4intn,m;5cin>>n>>m;6intg=n,t=0,li,s[n+1],b;7for(inti=1;i<=n;i++){8s[i]=i;9}10while(g){11t+=1,b=0,li=0,g-=(g+......
  • CSP小苹果详细解法
    #include<bits/stdc++.h>usingnamespacestd;intmain(){intn,ant=0,t,j;cin>>n;cout<<"小苞的桌上一共放了"<<n<<"个苹果。"<<endl;inta[n+5],b[n+5];for(inti=1;i<=n;i++){a[i......
  • 信息学奥赛复赛复习11-CSP-J2020-04方格取数-动态规划、斐波那契数列、最优子结构、重
    PDF文档公众号回复关键字:202410041P7074[CSP-J2020]方格取数[题目描述]设有n×m的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中......
  • 冲刺CSP联训模拟2
    冲刺CSP联训模拟2过T2了，赢了T3T4暴力没写满，输了A挤压我是唐诗老哥一个半小时才过T1发现要求的是\(E(s^2)\)，因为有个异或，所以直接考虑拆贡献到每一位\[E(s^2)=E(\sums_i\sums_j)=\sumE(s_is_j)\]所以直接考虑后面那个咋做，就是\(i,j\)位同时是一的时候贡献\(2^......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99