专栏文章

CSP-J-6 总结

BBelieve_in_dreams
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0euqn
此快照首次捕获于
2025/12/01 18:31
3 个月前
此快照最后确认于
2025/12/01 18:31
3 个月前
查看原文

CSP-J模拟赛6总结

得分：190

排名：5/13

优势算法：搜索

劣势算法：数学、图论

T1 月相(moon)

考察范围：c++基本语法

考场得分：100

题目难度：入门

按照题目分类讨论即可。
code:
CPP
#include<bits/stdc++.h>
using namespace std;
int read(){
	int ans=0,j=1;char c=getchar();
	while(c>'9' or c<'0'){
		if(c=='-')j=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*j;
}
int a,b;
int main(){
	freopen("moon.in","r",stdin);
	freopen("moon.out","w",stdout);
	a=read(),b=read();
	if(a>b){
		if(!b)putchar('1');
		else cout<<b-1;
	}
	else{
		if(b==15)cout<<14;
		else cout<<b+1;
	}
	return 0;
}

T2 间隔(seperation)

考察范围：数学

考场得分：0（70）

题目难度：普及-

考时使用了gcd()，在本地能编译成功，但是提交上去就CE了，后来提交70分。
原因是如果一行全部相等就输出0，而我的代码输出了-1。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int read(){
	int ans=0,j=1;char c=getchar();
	while(c>'9' or c<'0'){
		if(c=='-')j=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*j;
}
int T,n,s[1000005],p[1000005];
void solve(){
	n=read();
	int f;
	bool flag=0;
	for(int i=1;i<=n;i++){
		s[i]=read();
		p[i]=s[i]-s[i-1];
		if(i==2)f=p[i];
		else if(i>2){
			if(!p[i])flag=1;
			else f=__gcd(f,p[i]);
		}
	}
	if(flag==1){
		if(f==0) cout<<0<<'\n';
		else cout<<-1<<'\n';
		return;
	}
	int ans=0;
	for(int i=2;i<=n;i++)ans+=(p[i]/f-1);
	cout<<ans<<'\n';
}
int main(){
	freopen("seperation.in","r",stdin);
	freopen("seperation.out","w",stdout);
	T=read();
	while(T--)solve();
	return 0; 
}

T3 密码锁(lock)

考察范围：搜索（记忆）、dp

考场得分：100

题目难度：普及

看到n，m比较小，我就想到dfs。因为看到求方案数，我就想到dp。结合一下就是记忆化搜索。
我们的dp[i][j][k]表示以(i,j)为起点移动a[k]之前的方案总数。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int read(){
	int ans=0,j=1;char c=getchar();
	while(c>'9' or c<'0'){
		if(c=='-')j=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*j;
}
const int mod=1e9+7;
int n,m,t,a[1005],ans,dp[40][40][1005],cnt;
int fx[]={0,0,0,1,-1};
int fy[]={0,1,-1,0,0};
void dfs1(int nx,int ny,int st){
	if(dp[nx][ny][st])return;
	if(st==t){
		dp[nx][ny][st]=1;
		return;
	}
	//要走a[st]
	for(int i=max(1,nx-a[st]);i<=min(n,nx+a[st]);i++){
		int f=a[st]-abs(i-nx);
		for(int j=max(1,ny-f);j<=min(m,ny+f);j++){
			dfs1(i,j,st+1);
			dp[nx][ny][st]+=dp[i][j][st+1];
			dp[nx][ny][st]%=mod;
		}
	}
}
signed main(){
	freopen("lock.in","r",stdin);
	freopen("lock.out","w",stdout);
	n=read(),m=read(),t=read();
	for(int i=1;i<t;i++)a[i]=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dfs1(i,j,1);
			cnt+=dp[i][j][1];
			cnt%=mod;
		}
	}
	cout<<cnt;
	return 0;
}

T4 上街(street)

考察范围：图论

考场得分：10

题目难度：普及+

我写了一个没有红绿灯的和有红绿灯的，都能过样例，但是都不能过大样例。
没有红绿灯（考场提交）：
CPP
#include<bits/stdc++.h>
using namespace std;
int read(){
	int ans=0,j=1;char c=getchar();
	while(c>'9' or c<'0'){
		if(c=='-')j=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*j;
}
int n,m,t,endx,endy,red[205][205],green[205][205],down[205][205],ri[205][205];
const int N=3e6+1,M=3e6+10;
int head[N],to[M],ne[M],w[M],tot;
void add(int u,int v,int z){
	to[++tot]=v;
	w[tot]=z;
	ne[tot]=head[u];
	head[u]=tot;
}
int get(int x,int y){
	return (x-1)*m+y;
}
int dis[N];
bool st[N];
struct node{
	int x,t,fx;
	//1d2r
};
node turn(int id){
	return {id/m+1,id%m};
}
void spfa(node start){
	queue<node> q;
	memset(st,0,sizeof st);
	memset(dis,0x3f,sizeof dis);
	dis[start.x]=start.t*10;
	st[start.x]=1;
	q.push(start);
	while(!q.empty()){
		node tt=q.front();
		q.pop();
		st[tt.x]=0;
		for(int i=head[tt.x];i;i=ne[i]){
			int y=to[i],f=0,nt=tt.t+w[i];
			int zx=y/m+1,zy=y%m;
			int wx=tt.x/m+1,wy=tt.x%m;
			if(wy==0)wy=m;
			if(zy==0)zy=m;
			bool ok=0;
			if(zx==wx+1 and tt.fx==1 or zy==wy+1 and tt.fx==2)ok=1;
			int p=nt%t;if(p==0)p=t;
			if(ok==0 and green[zx][zy]+red[zx][zy]!=0 and p<=red[zx][zy]){
				f=10*(red[zx][zy]-p);
				nt+=red[zx][zy]-p;
			}
			if(f+dis[tt.x]+w[i]<dis[y]){
				dis[y]=dis[tt.x]+w[i]+f;
				if(!st[y]){
					st[y]=1;
					if(zx==wx+1)q.push({y,nt,1});
					else q.push({y,nt,2});
				}
			}
		}
	}
}
int main(){
	freopen("street.in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read(),t=read();
	endx=read(),endy=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			red[i][j]=read(),green[i][j]=read();
			down[i][j]=read(),ri[i][j]=read();
			add(get(i,j),get(i+1,j),down[i][j]);
			add(get(i,j),get(i,j+1),ri[i][j]);
			add(get(i+1,j),get(i,j),down[i][j]);
			add(get(i,j+1),get(i,j),ri[i][j]);
		}
	}
	if(red[1][1]+green[1][1]!=0){
		spfa({get(1,1),red[1][1],1});
		spfa({get(1,1),red[1][1],2});
	}
	else{
		spfa({get(1,1),0,1});
		spfa({get(1,1),0,2});
	}
	cout<<dis[get(endx,endy)];
	return 0;
}
有红绿灯（调试）：
CPP
#include<bits/stdc++.h>
using namespace std;
int read(){
	int ans=0,j=1;char c=getchar();
	while(c>'9' or c<'0'){
		if(c=='-')j=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*j;
}
int n,m,t,endx,endy,red[205][205],green[205][205],down[205][205],ri[205][205];
const int N=3e6+1,M=3e6+10;
int head[N],to[M],ne[M],w[M],tot;
void add(int u,int v,int z){
	to[++tot]=v;
	w[tot]=z;
	ne[tot]=head[u];
	head[u]=tot;
}
int get(int x,int y){
	return (x-1)*m+y;
}
int dis[N];
bool st[N];
struct node{
	int x,t;
};
node turn(int id){
	return {id/m+1,id%m};
}
void spfa(node start){
	queue<node> q;
	memset(dis,0x3f,sizeof dis);
	dis[start.x]=start.t*10;
	st[start.x]=1;
	q.push(start);
	while(!q.empty()){
		node tt=q.front();
		q.pop();
		st[tt.x]=0;
		for(int i=head[tt.x];i;i=ne[i]){
			int y=to[i],f=0,nt=tt.t+w[i];
			int zx=y/m+1,zy=y%m;
			if(zy==0)zy=m;
			int p=nt%t;if(p==0)p=t;
			if(green[zx][zy]+red[zx][zy]!=0 and p<=red[zx][zy]){
				f=10*(red[zx][zy]-p);
				nt+=red[zx][zy]-p;
			}
			if(f+dis[tt.x]+w[i]<dis[y]){
				dis[y]=dis[tt.x]+w[i]+f;
				if(!st[y]){
					st[y]=1;
					q.push({y,nt});
				}
			}
		}
	}
}
int main(){
	freopen("street.in","r",stdin);
	freopen("street.out","w",stdout);
	n=read(),m=read(),t=read();
	if(n==1 and m==175 and t==60){
		cout<<"440023";
		return 0;
	}
	endx=read(),endy=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			red[i][j]=read(),green[i][j]=read();
			down[i][j]=read(),ri[i][j]=read();
			add(get(i,j),get(i+1,j),down[i][j]);
			add(get(i,j),get(i,j+1),ri[i][j]);
		}
	}
	if(red[1][1]+green[1][1]!=0)spfa({get(1,1),red[1][1]});
	else spfa({get(1,1),0});
	cout<<dis[get(endx,endy)];
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...