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

CSP-S 模拟赛 34

时间：2024-10-07 12:43:50浏览次数：7  
标签：tmp ch int 34 getchar e1 CSP 模拟 dis

CSP-S 模拟赛 34

rnk12，\(24+50+20+0=94\)。

T1 玩游戏

有一个痿正解：从 \(k\) 到 \(1\) 扫左端点，对于每个左端点扫它最远能到达的右端点。如果在任何一时刻它的右端点位置 \(<k\)，则断定输出 No。否则检查当左端点到 \(1\) 时右端点能否到 \(n\)。注意这里扫右端点的方式，不要每次都从 \(k\) 向右扫，而是把右端点定义在外面，然后用和莫队类似的那种方法扫，就极大地降低了复杂度。实测最终 TLE 91pts，很可以了。

考场上连这都想不到？该退役了。

真正的正解貌似更复杂？唐了。

#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];
template<typename T=int>
T read(){
	T 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);
}
void writes(string s){
	for(auto x:s)putchar(x);
	putchar('\n');
}
using ll=long long;
constexpr int MAXN=1e5+5;
int T,n,k;
ll a[MAXN],sum[MAXN];

int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	T=read();
	while(T--){
		n=read(),k=read();
		memset(sum,0,sizeof(ll)*(n+5));
		for(int i=1;i<=n;++i)a[i]=read<ll>();
		if(sum[n]-sum[1]>0){
			writes("No");
			continue;
		}
		for(int i=k-1;i;--i)sum[i]=sum[i+1]+a[i+1];
		for(int i=k+1;i<=n;++i)sum[i]=sum[i-1]+a[i];
		int r=k;
		for(int i=k;i;--i){
			while(sum[r+1]+sum[i]<=0&&r<n)++r;
			while(sum[r]+sum[i]>0&&r)--r;
			if(r<k){
				writes("No");
				goto byby;
			}
		}
		writes(r==n?"Yes":"No");
		byby:;
	}
	return fw,0;
}

T2 排列

不用笛卡尔树。设 \(f_{i,j,0/1,0/1}\) 表示长度为 \(i\) 的区间 \(j\) 次合并完，左右两边是否靠墙的前缀和。用前缀和优化 DP。

  • 对于 00 的情况（两边都靠墙），可以由 \(j\) 相同的 01 和 10 转移。
  • 对于 10 的情况，可以由 \(j-1\) 的 11 和 \(j\) 相同的 10 转移。
  • 对于 01 的情况，同理。
  • 对于 11 的情况，前缀和神秘转移。

神秘题没什么好说的。

#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 int long long 
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
template<typename T=int>
T read(){
	T 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);
}
constexpr int MAXN=1005;
int n,K,P;
int C[MAXN][MAXN];
int f[MAXN][MAXN][2][2];
void add(int&x,int y){
	x=x+y>=P?x+y-P:x+y;
}
int sub(int x,int y){
	return x-y<0?x-y+P:x-y;
}

signed main(){
	freopen("per.in","r",stdin);
	freopen("per.out","w",stdout);
	n=read(),K=read(),P=read();
	for(int i=0;i<=n;++i){
		C[i][0]=1;
		for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%P/*,write(C[i][j])*/;
	}
	for(int i=0;i<=K;++i)
		f[0][i][0][0]=f[0][i][0][1]=f[0][i][1][0]=f[0][i][1][1]=1;
	for(int i=1;i<=n;++i)
		for(int k=1;k<=K;++k)
			for(int j=1;j<=i;++j){
				add(f[i][k][0][0],f[j-1][k][0][1]*f[i-j][k][1][0]%P*C[i-1][j-1]%P);
				add(f[i][k][0][1],f[j-1][k][0][1]*f[i-j][k-1][1][1]%P*C[i-1][j-1]%P);
				add(f[i][k][1][0],f[j-1][k-1][1][1]*f[i-j][k][1][0]%P*C[i-1][j-1]%P);
				add(f[i][k][1][1],sub(f[j-1][k][1][1]*f[i-j][k][1][1]%P,sub(f[j-1][k][1][1],f[j-1][k-1][1][1])*sub(f[i-j][k][1][1],f[i-j][k-1][1][1])%P)*C[i-1][j-1]%P);
			}
	write(sub(f[n][K][0][0],f[n][K-1][0][0]));
	return fw,0;
}

T3 最短路

假做法：两遍 Dijkstra。

真假做法：对于每一条边建一条反边，跑二维 Dij。设 \(\mathit{dis}_{i,j}\) 表示沿正边到 \(i\) 点和反边到 \(j\) 的距离之和，则 \(\mathit{dis}_{n,n}\) 即为题中所求。用 bitset 维护原本的 \(\mathit{vis}\) 数组。

#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];
template<typename T=int>
T read(){
	T 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);
}
constexpr int MAXN=255;
int n,m,p[MAXN];
int hd1[MAXN],tot1,hd2[MAXN],tot2;
struct{int v,nxt;}e1[MAXN*MAXN],e2[MAXN*MAXN];
void addedge(int typ,int u,int v){
	if(typ==1){
		e1[++tot1]={v,hd1[u]};
		hd1[u]=tot1;
	}else{
		e2[++tot2]={v,hd2[u]};
		hd2[u]=tot2;
	}
}
struct Node{
	int s,x,y;
	Node(){}
	Node(int s,int x,int y):s(s),x(x),y(y){}
	bool operator<(const Node&b)const{
		return s>b.s;
	}
};
int dis[MAXN][MAXN],vis[MAXN][MAXN];
bitset<MAXN>bit[MAXN][MAXN];
void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[1][1]=p[1];
	bit[1][1][1]=1;
	priority_queue<Node>q;
	q.emplace(dis[1][1],1,1);
	while(!q.empty()){
		int x=q.top().x,y=q.top().y;
		q.pop();
		if(vis[x][y])continue;
		vis[x][y]=1;
		for(int i=hd1[x],tmp;i;i=e1[i].nxt){
			tmp=0;
			if(!bit[x][y][e1[i].v])tmp=p[e1[i].v];
			if(dis[e1[i].v][y]>dis[x][y]+tmp){
				dis[e1[i].v][y]=dis[x][y]+tmp;
				bit[e1[i].v][y]=bit[x][y];
				bit[e1[i].v][y][e1[i].v]=1;
				q.emplace(dis[e1[i].v][y],e1[i].v,y);
			}
		}
		for(int i=hd2[y],tmp;i;i=e2[i].nxt){
			tmp=0;
			if(!bit[x][y][e2[i].v])tmp=p[e2[i].v];
			if(dis[x][e2[i].v]>dis[x][y]+tmp){
				dis[x][e2[i].v]=dis[x][y]+tmp;
				bit[x][e2[i].v]=bit[x][y];
				bit[x][e2[i].v][e2[i].v]=1;
				q.emplace(dis[x][e2[i].v],x,e2[i].v);
			}
		}
	}
}

int main(){
	freopen("tour.in","r",stdin);
	freopen("tour.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)p[i]=read();
	for(int i=1,u,v;i<=m;++i){
		u=read(),v=read();
		addedge(1,u,v),addedge(2,v,u);
	}
	dijkstra();
	write(dis[n][n]==0x3f3f3f3f?-1:dis[n][n]);
	return fw,0;
}

T4 矩形

扫描线 + 并查集。讲得很清楚了。

#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];
template<typename T=int>
T read(){
	T 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);
}
constexpr int MAXN=1e5+5;
int n,f[MAXN];
int find(int x){
	if(f[x]^x)f[x]=find(f[x]);
	return f[x];
}
void combine(int u,int v){
	int fu=find(u),fv=find(v);
	if(fu^fv)f[fu]=fv;
}
struct JUX{
	int x1,y1,x2,y2;
	bool operator<(const JUX&b)const{
		return y1<b.y1;
	}
}a[MAXN];
bool check(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
	if(x2<x3||x4<x1||y2<y3||y4<y1)return 0;
	return 1;
}

namespace zj{
#define lp p<<1
#define rp p<<1|1
#define mid ((s+t)>>1)
struct SegTree{
	int id,lim,typ,lazy;
}st[MAXN<<2];
void pushup(int p){
	if(st[lp].id==st[rp].id){
		st[p].id=st[lp].id;
		st[p].lim=st[lp].lim;
		st[p].typ=0;
	}else st[p].typ=1;
	if(st[lp].typ||st[rp].typ)st[p].typ=1;
}
void pushdown(int p){
	if(!st[p].lazy)return;
	st[lp].lazy=st[rp].lazy=1;
	st[lp].id=st[rp].id=st[p].id;
	st[lp].lim=st[rp].lim=st[p].lim;
	st[p].lazy=0;
}
void mdf(int l,int r,int lim,int id,int s=1,int t=1e5,int p=1){
	if(l<=s&&t<=r&&!st[p].typ){
		if(st[p].lim>lim)return;
		st[p].lazy=1,st[p].id=id,st[p].lim=lim;
		return;
	}
	pushdown(p);
	if(l<=mid)mdf(l,r,lim,id,s,mid,lp);
	if(mid<r)mdf(l,r,lim,id,mid+1,t,rp);
	pushup(p);
}
void Merge(int l,int r,int lim,int id,int s=1,int t=1e5,int p=1){
	if(l<=s&&t<=r&&!st[p].typ){
		if(st[p].lim>=lim)combine(id,st[p].id);
		return;
	}
	pushdown(p);
	if(l<=mid)Merge(l,r,lim,id,s,mid,lp);
	if(mid<r)Merge(l,r,lim,id,mid+1,t,rp);
	pushup(p);
}
int solve(){
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i){
		Merge(a[i].x1,a[i].x2,a[i].y1,i);
		mdf(a[i].x1,a[i].x2,a[i].y2,i);
	}
	int ans=0;
	for(int i=1;i<=n;++i)if(find(i)==i)++ans;
	write(ans);
	return fw,0;
}
}

int main(){
	freopen("jux.in","r",stdin);
	freopen("jux.out","w",stdout);
	n=read();
	iota(f+1,f+n+1,1);
	for(int i=1;i<=n;++i)a[i]={read(),read(),read(),read()};
	if(n>=40000)return zj::solve();
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)
			if(check(a[i].x1,a[i].y1,a[i].x2,a[i].y2,a[j].x1,a[j].y1,a[j].x2,a[j].y2))
				combine(i,j);
	int ans=0;
	for(int i=1;i<=n;++i)ans+=(find(i)==i);
	write(ans);
	return fw,0;
}

标签：tmp,ch,int,34,getchar,e1,CSP,模拟,dis
From： https://www.cnblogs.com/laoshan-plus/p/18449918

相关文章

  • CSP-S 模拟赛 33
    CSP-S模拟赛33rnk19，\(30+20+40+15=105\)。T1构造字符串10pts：输出\(-1\)。30pts：对于所有\(z_i=0\)的情况，也就是说给定的两个位置字符都不同。记录有哪些位置的字符是不同的，然后从\(1\)到\(n\)扫一遍，输出除去不同的字符之外的字典序最小的字符。70pts：暴搜。枚举每个......
  • 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