首页 > 其他分享 >CSP-S 模拟赛 33

CSP-S 模拟赛 33

时间：2024-10-07 12:24:38浏览次数：1  
标签：字符 33 st int MAXN ins buf CSP 模拟

CSP-S 模拟赛 33

rnk19，\(30+20+40+15=105\)。

T1 构造字符串

10pts：输出 \(-1\)。

30pts：对于所有 \(z_i=0\) 的情况，也就是说给定的两个位置字符都不同。记录有哪些位置的字符是不同的，然后从 \(1\) 到 \(n\) 扫一遍，输出除去不同的字符之外的字典序最小的字符。

70pts：暴搜。枚举每个位置可能的字符，对于每一种方案检查是否符合要求。复杂度 \(O(10^nmn)\)，但数据太水加远远跑不满，直接可以通过所有 \(n\le9\) 的数据。

以上为挂分部分。

正解：题目给的信息转化为哪些字符相等、哪些字符不相等。用并查集把相等的字符合并起来，并记录有哪几对字符不相等。然后扫一遍所有不相等的字符对，如果它们在并查集中被合并了，则断定不可能，输出 \(-1\)；否则把这对字符以及后面带的所有相等字符都记录为矛盾关系，最后贪心即可。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
constexpr int MAXN=10005;
int n,m;
struct Edge{
	int x,y,z;
}a[MAXN];
int f[MAXN];
int find(int x){
	if(f[x]^x)f[x]=find(f[x]);
	return f[x];
}
void combine(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy)return;
	if(fx<fy)swap(fx,fy);
	f[fx]=fy;
}
int head[MAXN],tot;
struct{int v,nxt;}e[MAXN<<1];
void addedge(int u,int v){
	e[++tot]={v,head[u]};
	head[u]=tot;
}
int ans[MAXN],vis[MAXN];

int main(){
	freopen("str.in","r",stdin);
	freopen("str.out","w",stdout);
	n=read(),m=read();
	if(n==30)return write(-1),fw,0;
	iota(f+1,f+n+1,1);
	for(int i=1;i<=m;++i){
		a[i]={read(),read(),read()};
		for(int j=0;j<a[i].z;++j)combine(a[i].x+j,a[i].y+j);
	}
	for(int i=1,fx,fy;i<=m;++i){
		fx=find(a[i].x+a[i].z),fy=find(a[i].y+a[i].z);
		if(fx>n||fy>n||!fx||!fy)continue;
		if(find(fx)==find(fy))return write(-1),fw,0;
		addedge(max(fx,fy),min(fx,fy));
	}
	for(int i=1;i<=n;++i){
		if(find(i)^i)continue;
		for(int j=head[i];j;j=e[j].nxt)
			if(ans[e[j].v]>-1)
				vis[ans[e[j].v]]=1;
		ans[i]=0;
		while(vis[ans[i]])++ans[i];
		for(int j=head[i];j;j=e[j].nxt)
			vis[ans[e[j].v]]=0;
	}
	for(int i=1;i<=n;++i)write(ans[find(i)],' ');
	return putchar('\n'),fw,0;
}

T2 寻宝

没看到传送门是有向的，100pts \(\to\) 10pts。

正解也是非常简单哈，先暴力 \(O(nm)\) 给每个连通块染色，然后暴力 \(O(k)\) 从一种颜色向另一种颜色连边，最后暴力 DFS 判断是否在一个连通块。最后就这么暴力地过去了。

#include<bits/stdc++.h>
using namespace std;

constexpr int MAXN=50005,MAXD=105,MAXM=1e5+5;
constexpr int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m,k,q;
string a[MAXN];
struct Door{
	int x1,y1,x2,y2;
}d[MAXD];
struct Men{
	int x1,y1,x2,y2;
}b[MAXM];
int vis[MAXN];
int tot,ok;
int head[MAXN],tot2;
struct{
	int v,nxt;
}e[MAXN<<1];
void addedge(int u,int v){
	e[++tot2]={v,head[u]};
	head[u]=tot2;
}
bool ins[MAXN];
int hsh(int x,int y){
	return (x-1)*m+y;
}
void dfs(int x,int y,int now){
	vis[hsh(x,y)]=now;
	for(int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx<1||xx>n||yy<1||yy>m||vis[hsh(xx,yy)]||a[xx][yy]=='#')continue;
		dfs(xx,yy,now);
	}
}
void dfs2(int u){
	ins[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		if(ins[e[i].v])continue;
		dfs2(e[i].v);
	}
}

int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>k>>q;
	for(int i=1;i<=n;++i)cin>>a[i],a[i]=' '+a[i];
	for(int i=1;i<=k;++i)cin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
	for(int i=1;i<=q;++i)cin>>b[i].x1>>b[i].y1>>b[i].x2>>b[i].y2;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			if(a[i][j]=='#'||vis[hsh(i,j)])continue;
			dfs(i,j,++tot);
		}
	for(int i=1;i<=k;++i)addedge(vis[hsh(d[i].x1,d[i].y1)],vis[hsh(d[i].x2,d[i].y2)]);
	for(int i=1;i<=q;++i){
		memset(ins,0,sizeof(bool)*(tot+5));
		dfs2(vis[hsh(b[i].x1,b[i].y1)]);
		cout<<ins[vis[hsh(b[i].x2,b[i].y2)]]<<'\n';
	}

	return 0;
}

T3 序列

这种一看数据结构的题一般都是暴力的天堂。而正解呢，不是科技就是毒。

40pts：纯暴力。

60pts：拆一下式子转化为 \([l,p_j)\) 的前缀和最小值和 \([p_j,r]\) 的前缀和最大值做差。复杂度 \(O(mn\log n)\)，考场写线段树维护然后炸了，下来一看变相前缀和一下就行。

100pts：还是刚才那个式子，设 \(A_i\) 为 \(A\) 序列的前缀和，\(B_i\) 为 \(B\) 序列的前缀和，刚才的那个式子就是 \(\max\big\{(A_r-A_l)-k(B_r-B_l)\big\}\)。拆成两个式子 \(A_r-kB_r\) 和 \(-A_l+kB_l\)，成功看作是以 \(k\) 为自变量的一次函数。\(l,r,k\) 都是定值，遂想到李超线段树。维护一下即可。复杂度 \(O(n\log n+m\log n)\)。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define fs first
#define sc second
#define lp p<<1
#define rp p<<1|1
#define mid ((s+t)>>1)
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))ch=='-'&&(f=-1),ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
using pii=pair<int,int>;
using ll=long long;
constexpr int MAXN=1e6+5;
int n,m;
pii a[MAXN];
ll suma[MAXN],sumb[MAXN],ans[MAXN];
struct Ask{
	int p,k,id;
	bool operator<(const Ask&b)const{
		return p<b.p; 
	}
}q[MAXN];
struct LICHAO{
	ll k,b;
	LICHAO(){
		k=0,b=LONG_LONG_MIN;
	}
}st[MAXN<<3];
ll Y(ll x,ll k,ll b){
	return k*x+b;
}
void mdf(ll k,ll b,int s=-1e6,int t=1e6,int p=1){
	if(Y(mid,k,b)>Y(mid,st[p].k,st[p].b))swap(k,st[p].k),swap(b,st[p].b);
	if(s==t)return;
	if(Y(s,k,b)>Y(s,st[p].k,st[p].b))mdf(k,b,s,mid,lp);
	if(Y(t,k,b)>Y(t,st[p].k,st[p].b))mdf(k,b,mid+1,t,rp);
}
ll query(int x,int s=-1e6,int t=1e6,int p=1){
	ll res=Y(x,st[p].k,st[p].b);
	if(s==t)return res;
	if(x<=mid)res=max(res,query(x,s,mid,lp));
	else res=max(res,query(x,mid+1,t,rp));
	return res;
}

int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		a[i]={read(),read()};
		suma[i]=suma[i-1]+a[i].fs;
		sumb[i]=sumb[i-1]+a[i].sc;
	}
	for(int i=1;i<=m;++i)q[i]={read(),read(),i};
	sort(q+1,q+m+1);
	int ins=1;
	mdf(0,0);
	for(int i=1;i<=m;++i){
		while(ins<=n&&ins+1<=q[i].p){
			mdf(sumb[ins],-suma[ins]);
			++ins;
		}
		ans[q[i].id]+=query(q[i].k);
	}
	for(int i=1;i<=MAXN<<3;++i)st[i]=LICHAO();
	ins=n;
	for(int i=m;i>=1;--i){
		while(ins&&ins>=q[i].p){
			mdf(-sumb[ins],suma[ins]);
			--ins;
		}
		ans[q[i].id]+=query(q[i].k);
	}
	for(int i=1;i<=m;++i)write(ans[i]);
	return fw,0;
}

T4 构树

只能说是卡空间的好题。

“恰好” 很二项式反演。设 \(f(k)\) 为原树的 \(n\) 条边中至少 \(k\) 条边和原树相同，\(g(k)\) 为恰好 \(k\) 条边和原树相同。有二项式反演：

\[f(k)=\sum_{i=k}^n\binom ikg(i)\iff g(k)=\sum_{i=k}^n(-1)^{i-k}\binom ikf(i) \]

于是考虑如何快速求出 \(f(i)\)。由扩展凯莱公式，对于一棵有 \(n\) 个节点的有标号无根树，已经形成了 \(m\) 个连通块且大小分别为 \(a_1,a_2,\dots,a_m\)，则连边后生成树的方案数为

\[n^{m-2}\prod_{i=1}^ma_i \]

考虑 \(\prod a_i\) 的组合意义，\(\prod a_i\) 等于在每一个连通块中选出一个点的方案数。

于是有树形 DP：设 \(\mathit{dp}_{i,j,0/1}\) 表示在 \(i\) 的子树中选取 \(j\) 条边，\(i\) 所在的连通块中选/未选一个点的方案数。转移有类似树形背包的转移方法。

这样做的时空复杂度都是 \(O(n^2)\) 的，时间能过，空间会炸。于是用 vector 动态使用内存，及时释放不必要的容量，这样同时占用空间的最多只有 \(n\) 个数。然后这题就做完了。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=8005,MOD=1e9+7;
int n,head[MAXN],tot;
struct{int v,nxt;}e[MAXN<<1];
void addedge(int u,int v){
	e[++tot]={v,head[u]};
	head[u]=tot;
}
void add(int&x,int y){
	x=x+y>=MOD?x+y-MOD:x+y;
}
int siz[MAXN],tmp[MAXN][2];
vector<int>v0[MAXN],v1[MAXN];
void dfs(int u,int fno){
	siz[u]=1;
	v0[u].resize(n),v1[u].resize(n);
	v0[u][0]=v1[u][0]=1;
	for(int i=head[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v){
		if(v==fno)continue;
		dfs(v,u);
		for(int j=0;j<siz[u];++j)
			for(int k=0;k<siz[v];++k){
				add(tmp[j+k+1][0],(ll)v0[u][j]*v0[v][k]%MOD);
				add(tmp[j+k+1][1],((ll)v0[u][j]*v1[v][k]%MOD+(ll)v1[u][j]*v0[v][k]%MOD)%MOD);
				add(tmp[j+k][0],(ll)v0[u][j]*v1[v][k]%MOD*n%MOD);
				add(tmp[j+k][1],(ll)v1[u][j]*v1[v][k]%MOD*n%MOD);
			}
		siz[u]+=siz[v];
		for(int j=0;j<siz[u];++j){
			v0[u][j]=tmp[j][0];
			v1[u][j]=tmp[j][1];
			tmp[j][0]=tmp[j][1]=0;
		}
		vector<int>().swap(v0[v]);
		vector<int>().swap(v1[v]);
	}
}
int power(int a,int b){
	int res=1;
	for(;b;a=(ll)a*a%MOD,b>>=1)if(b&1)res=(ll)res*a%MOD;
	return res;
}
int fac[MAXN],inv[MAXN];
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i)fac[i]=(ll)fac[i-1]*i%MOD;
	inv[n]=power(fac[n],MOD-2);
	for(int i=n-1;~i;--i)inv[i]=(ll)inv[i+1]*(i+1)%MOD;
}
int C(int n,int m){
	if(n<m)return 0;
	return (ll)fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=read();
	for(int i=1,u,v;i<n;++i){
		u=read(),v=read();
		addedge(u,v),addedge(v,u);
	}
	dfs(1,0);
	init(n);
	int invn=power(n,MOD-2);
	for(int i=0;i<n;++i)v1[1][i]=(ll)v1[1][i]*invn%MOD;
	for(int i=0,fg,ans;i<n;++i){
		fg=1,ans=0;
		for(int j=i;j<n;++j)add(ans,((ll)fg*C(j,i)%MOD*v1[1][j]%MOD+MOD)%MOD),fg*=-1;
		write(ans,' ');
	}
	return putchar('\n'),fw,0;
}

标签：字符,33,st,int,MAXN,ins,buf,CSP,模拟
From： https://www.cnblogs.com/laoshan-plus/p/18449899

相关文章

  • P3332 K大数查询 题解
    Solution整体二分板子题vector太好写了111#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=50010;intn,m,ans[......
  • 10.5牛客CSP-S考试总结
    10.5牛客CSP-S考试总结为什么牛客不允许我：main(){}T1看到题目感觉是道规律题，就把题目给的式子写出来，跑了几十组随机数据，发现好像是恒等式，于是直接大胆猜测任选三个数都可以满足等式。T2题面数学公式有点诈骗，求自然常数的多个自然对数相加的和的次方，形式化的求\(e^{\ln\......
  • CSP-S 2024 第九次
    A设\(f_{i,S}\)表示考虑前\(i\)行，选出的矩形在第\(i\)行上形成\(S\)中的区间的方案数，每行的\(S\)只有\(O(2^m)\)种，总复杂度\(O(n2^{2m})\)。B考虑先修改再查询怎么做。考虑左下角为\((x_1,y_1)\)，右上角为\((x_2,y_2)\)的矩形，发现斜率在\(\left[\dfrac{y_1}{......
  • 2024-10-6 模拟赛总结
    \(100+80+100+0=280\)，暴力又写挂了。比赛链接：http://172.45.35.5/d/HEIGETWO/homework/67025b796735d3863dc7f60d或者http://yl503.yali.edu.cn/d/HEIGETWO/homework/67025b796735d3863dc7f60dA-fountain题意：给定一条线段和一个圆，求线段上任意一点到圆上任意一点的最大距......
  • 多校A层冲刺NOIP2024模拟赛02 & csp-s模拟9
    多校A层冲刺NOIP2024模拟赛02四道题因为暑假被拉去当模拟赛暑假集训CSP提高模拟22了，遂直接把赛后代码交了上去，然后就被通知换题了。原\(100+100+100+20\)被在accodersNOI上被卡成了\(100+100+90+10\)，更改longlong和int后达到了\(100+100+100+30\)。\(T1\)P318......
  • CCF-CSP认证资格考试题解系列——第4次第2题数字排序
    #include<iostream>#include<algorithm>usingnamespacestd;structre{ intvalue;//数值 intnum;//次数}re[1010];boolcmp(structrea,structreb){ if(a.num==b.num)returna.value<b.value;//次数相同是小的优先 returna.num>b.num;//次数不相同是次数优......
  • CCF-CSP认证资格考试题解系列——第4次第3题节日
    #include<iostream>usingnamespacestd;intm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};intis_run(intyear){ if(year%400==0||(year%4==0&&year%100))return1; return0;}intgetdays(intyear,intmonth){ if(month==2)returnm[month]+i......
  • 『模拟赛』CSP-S模拟9
    Rank烂，知耻而后勇A.邻面合并签。注意到列数\(m\le8\)，我们可以直接先搜出每一行可能的“分块”情况，然后转移时枚举上一行的所有状态和这一行的所有状态，根据拼接情况来更新答案，最终答案即为\(n\)行所有情况的最小值。赛时开始打的错解，错解如果第一行总数计算错了就能过......
  • 傻逼模拟赛搬的时候能不能看看题面改之后还是不是让人能看懂还有不发 checker 是有什
    如题。傻逼模拟赛搬的时候能不能看看题面改之后还是不是让人能看懂还有不发checker是有什么心事吗还在最后一道题放集训队互测什么意思什么叫有\(b_{k}\)种\(k\)类型的货币，同一种流通的货币不会超过二十种什么叫接下来\(n\)个数表示\(a_{1}\sima_{n-1}\)......
  • P7078 [CSP-S2020] 贪吃蛇 题解
    P7078[CSP-S2020]贪吃蛇这题好啊题目传送门看到题之后觉得有点像砍蚯蚓的那道题看看题目可以证明，若一条蛇在吃完之后不是最弱的那一条蛇，那么他一定会选择吃，证明如下设蛇长为\(a_{1,\dots,n}\)且依次递增，那么很明显的因为​......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99