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

冲刺CSP联训模拟2

时间:2024-10-05 20:00:52浏览次数:10  
标签:cout int 冲刺 CSP 联训 maxn ans id mod

A. 挤压

拆位算贡献,一个数二进制表示平方为 \(\sum_{i,j}s_i*s_j*2^{i+j}\) ,单独算每一项的贡献,枚举 \(i,j\),只有当这两位都为1时

结果才是1,所以我们要找异或后这两位都是1的方案数,这里需要 \(dp\) 用 \(f_{i,j,k}\) 表示前 \(i\) 个数异或出来的 \(j,k\) 两位

是1/0的方案数,对于每个数考虑是否选即可。

点击查看代码
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
const int maxn=2e5+10;
using namespace std;
int n,a[maxn],p[maxn],ans,f[maxn][2][2];
inline int qpow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}

signed main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>p[i],p[i]=p[i]*qpow(1000000000,mod-2)%mod;
	for(int i=0;i<=29;i++)
	{
		for(int j=0;j<=29;j++)
		{
			f[0][0][0]=1,f[0][0][1]=f[0][1][0]=f[0][1][1]=0;
			for(int k=1;k<=n;k++)
			{
				for(int x=0;x<=1;x++)
				{
					for(int y=0;y<=1;y++)
					{
						f[k][x][y]=f[k-1][x][y]*(1+mod-p[k])%mod;
						bool xx=a[k]&(1<<i),yy=a[k]&(1<<j);
						int aa=x^(xx?1:0),bb=y^(yy?1:0);
						f[k][x][y]=(f[k][x][y]+f[k-1][aa][bb]*p[k]%mod)%mod;
					}
				}
			}
			ans=(ans+(f[n][1][1]*((1ll<<(i+j))%mod)%mod))%mod;
		}
	}
	cout<<ans;
	
	return 0;
}
/*

*/

B. 工地难题

跟 \(5k\) 学的,这里直接粘了(\(5k\) 果然比题解好用)
image

点击查看代码
#include<bits/stdc++.h>
#define int long long
const int maxn=2e5+10;
const int mod=1e9+7;
using namespace std;
int n,m,jc[maxn],ny[maxn],ans,last;

int qpow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}

int c(int n,int m)
{
	return jc[n]*ny[m]%mod*ny[n-m]%mod;
}

void pre()
{
	jc[0]=1;
	for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
	ny[n]=qpow(jc[n],mod-2);
	for(int i=n-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
} 

signed main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	pre();
	for(int k=1;k<=m;k++)
	{
		int temp=c(n,m);
		for(int i=1;i<=n-m+1;i++)
		{
			if(i*(k+1)>m) break;
			temp=(temp+(i&1?mod-1:1)*c(n-i*(k+1),n-m)%mod*c(n-m+1,i)%mod)%mod;
		}
		cout<<(temp-last+mod)%mod<<" ";last=temp;
	}


	return 0;
}
/*

*/

C. 星空遗迹

考虑加入一个字符,他要么被前面胜者覆盖,无影响,要么直接覆盖前面,变成新的答案,所以我们维护一个栈,使得栈中

靠下的字符会赢他上面的字符,所以一个字符进栈要么输于栈顶,无影响,要么直接清空栈变成新答案,可以发现,当栈

内数量最小时,栈底的就是答案,对每个字符记录与上一个字符输赢,自己赢了为-1,输了为1,平局0,现在我们要维护

一个前缀最小值,和单点修改,这里用前缀和转换为区间修改,区间查询,线段树实现

点击查看代码
#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
const int maxn=3e5+10;
using namespace std;
int n,q,a[maxn];
string s;
struct lsx
{
	int l,r,minn,pos,flag;
}m[maxn<<2];

int cmp(char a,char b)
{
	if(a==b) return 0;
	if(a=='R'&&b=='S') return 1;
	if(a=='S'&&b=='P') return 1;
	if(a=='P'&&b=='R') return 1;
	return -1;
} 

void up(int id)
{
	m[id].minn=min(m[lid].minn,m[rid].minn); 
	m[id].pos=m[lid].minn<m[rid].minn?m[lid].pos:m[rid].pos;
}

void down(int id)
{
	if(!m[id].flag) return ;
	m[lid].flag+=m[id].flag,m[rid].flag+=m[id].flag;
	m[lid].minn+=m[id].flag,m[rid].minn+=m[id].flag;
	m[id].flag=0; 
}

void build(int id,int l,int r)
{
	m[id].l=l,m[id].r=r;
	if(l==r)
	{
		m[id].minn=a[l];
		m[id].pos=l;
		return ;
	}
	int mid=l+r>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
	up(id);
}

int querx(int id,int x)
{
	int l=m[id].l,r=m[id].r;
	if(l==r) return m[id].minn;
	down(id);
	int mid=l+r>>1,temp;
	if(x<=mid) temp=querx(lid,x);
	else temp=querx(rid,x);
	up(id);
	return temp;
} 

void update(int id,int s,int t,int x)
{
	int l=m[id].l,r=m[id].r;
	if(l>=s&&r<=t)
	{
		m[id].minn+=x;
		m[id].flag+=x;
		return ;	
	}
	down(id);
	int mid=l+r>>1;
	if(s<=mid) update(lid,s,t,x);
	if(mid<t) update(rid,s,t,x);
	up(id);
}

pair<int,int> query(int id,int s,int t)
{ 
	int l=m[id].l,r=m[id].r;
//	cout<<id<<" "<<l<<" "<<r<<" "<<m[id].minn<<endl;
	if(l>=s&&r<=t)
	{
		return {m[id].minn,m[id].pos};
	}
	down(id);
	int mid=l+r>>1;
	pair<int,int> k={1e9,0};
	if(s<=mid) 
	{
		pair<int,int> tem=query(lid,s,t);
		if(tem.first<k.first) k=tem;
	}
	if(mid<t) 
	{
		pair<int,int> tem=query(rid,s,t);
		if(tem.first<k.first) k=tem;
	}
	up(id); 
	return k;
}

int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q; 
	cin>>s;s=" "+s;
	a[1]=1;
	for(int i=2;i<=n;i++) a[i]=cmp(s[i-1],s[i]),a[i]+=a[i-1];
	build(1,1,n);
    int op,x,y;
    char k;
	for(int i=1;i<=q;i++)
	{
		cin>>op;
		if(op==1)
		{
			cin>>x>>k;
			s[x]=k;
			int s1=querx(1,x-1),s2=querx(1,x),s3;
			if(x!=n) s3=querx(1,x+1);
//			cout<<s1-s2+cmp(s[x-1],s[x])<<" "<<s2-s3+cmp(s[x],s[x+1])<<endl;
			update(1,x,n,s1-s2+cmp(s[x-1],s[x]));
			if(x!=n)update(1,x+1,n,s2-s3+cmp(s[x],s[x+1]));
		}
		else
		{
			cin>>x>>y;
			pair<int,int> p=query(1,x,y);
//			cout<<p.second<<endl;
			cout<<s[p.second]<<'\n';
		}
	}

	return 0;
}

标签:cout,int,冲刺,CSP,联训,maxn,ans,id,mod
From: https://www.cnblogs.com/oceansofstars/p/18448381

相关文章

  • 信息学奥赛复赛复习12-CSP-J2021-01分糖果-模运算、余数、打擂台求最值、最大值、最小
    PDF文档公众号回复关键字:202410051P7909[CSP-J2021]分糖果[题目描述]红太阳幼儿园有n个小朋友,你是其中之一。保证n≥2有一天你在幼儿园的后花园里发现无穷多颗糖果,你打算拿一些糖果回去分给幼儿园的小朋友们由于你只是个平平无奇的幼儿园小朋友,所以你的体力有限,至......
  • [赛记] 冲刺CSP联训模拟2
    三道计数+一道数据结构也是没谁了这场可是好好锻炼了我的写暴搜能力。。。挤压20pts暴搜20pts;把最后的答案进行二进制拆解,即$ans=2^i+2^j+2^k+...$,那么答案的平方为$\sum_{i=0}^{30}\sum_{j=0}^{30}s_is_j2^{i+j}$,其中$s_i,s_j$代表答案二......
  • [DMY]2024 CSP-S 模拟赛 Day 10
    赛时对于T1,看懂题面以后感觉很可做。首先明确正解复杂度应该是基于\(N\)额度线性做法。把输入按照开始时间排序,然后依次处理。赛时考虑到一个元素在覆盖过程中遇到其他元素时无法确定时间先后,确定后想要找到该元素的当前位置和重新覆盖有些困难,写了1h以后先放弃了。舍远......
  • [赛记] 多校A层冲刺NOIP2024模拟赛01【衡中】
    构造字符串50pts错解50pts;考虑正解,对于题目中的要求,我们可以转换成若干个相等与不等的操作,若相等则用并查集合并一下,不等则连边,若同块连边则无解,否则从前往后遍历赋值,每次找所连边其它块值的$\operatorname{mex}$即可;时间复杂度:$\Theta(nm\alpha(n))$;点击查看代码#i......
  • [赛记] 冲刺CSP联训模拟1[衡中]
    几何100pts赛时打的$DP$没有用bitset优化过了,也是放过了暴力;考虑设状态$f_{i,j,k}$表示考虑到第$i$位,到第$j$位$x$和第$k$位$y$可不可取,直接转移即可;时间复杂度:$\Theta(|s||x||y|)$,应该是过不了的;点击查看暴力#include<iostream>#incl......
  • [赛记] csp-s模拟7
    median50pts错解50pts(有重复的数就不行);赛时想容斥了,其实不用容斥(好像也不能容斥);题解做法:将每个数存一个二元组,按大小排序,枚举每一个数作为中位数,再枚举每个位置的种类,看它前面和后面有多少这些种类的数,乘起来即可;这样就巧妙地避免了重复的情况,如果直接枚举,则有相同的数会被重......
  • [赛记] csp-s模拟6
    一般图最小匹配35pts纯纯的错解35pts;考虑将原数列排序,那么我们选的边就只能是相邻两个点的;发现这玩意能够递推(赛时没发现),所以直接$DP$,设$f_{i,j}$表示当前考虑到第$i$位,有$j$条边被选的最小权值,转移时考虑第$i$个点连不连第$i-1$个点即可;时间复杂......
  • 冲刺 CSP 联训模拟2
    题面温馨提示代码中的变量名可能与题意、题解不同。代码不删缺省源,可以直接拿来对拍。T1挤压Solution众所周知,异或是一种按位运算,不好进行十进制的数间合并。我们考虑将每个数拆分为二进制的形式进行处理。此时,对于每一种情况,假设表示\(2^i\)二进制位的值为\(b_i\),我......
  • 冲刺 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的倍数,估计会有一些比较智慧的手法,感觉很......