中考假做题记录

2023-10-27 09:13:46

前言

个人认为难度：

T1（难在读题）<T4（代码较长，思路简单）<T2（有一定的思维量，较为经典的要排序的 01 背包问题）<T5（广搜）<T3（难在读题 + 坑点较多的模拟）<T6（线性 DP）<T7（紫题劝退）

T1

\(AC\ \ on\ \ 2021.06.11\)

这题是来考语文的吗？

题目老长，愣是看了半天才看懂。

读懂题后：这不就是给一串数处理之后加在一起咩？？

处理也很简单 （事实证明这道题最难的地方在读题），直接看灯是什么颜色：如果是绿的就变为 \(0\)，如果是红的就不变，如果是黄的就加上 \(r\)。

结果打完之后代码 CE 了后来我才发现 time 是 c++ 的关键词，无语……

\(Code\)

#include<bits/stdc++.h>
using namespace std;
int n,a,b,r,y,g,Time; 
int main(){
	scanf("%d %d %d %d",&r,&y,&g,&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&a,&b);
		if(!a||a==1) Time+=b;
		else if(a==2) Time+=b+r;
	}
	printf("%d",Time);
	return 0;
}

T2

\(AC\ \ on\ \ 2021.06.13\)

吃石头可海星。

背包，考点是怎么排序。

假设要吃两个石头 \(x\) 和 \(y\)，先吃 \(x\) 比先吃 \(y\) 好。

设 \(first\) 为石头的初始能量值，\(lost\) 为每秒石头会浪费的能量值，\(time\) 为吃一块石头要用的时间。

为了方便我们不考虑石头能量值流完的情况。

那么先吃 \(x\) 的表达式为：

\[energy1=x_{first}+y_{first}-x_{time}\times y_{lost} \]

先吃 \(y\) 的表达式为：

\[energy2=y_{first}+x_{first}-y_{time}\times x_{lost} \]

我们知道 \(energy1>energy2\)

代入原式：

\[x_{first}+y_{first}-x_{time}\times y_{lost}>y_{first}+x_{first}-y_{time}\times x_{lost} \]

把相同的地方抵消了就变成：

\[-x_{time}\times y_{lost}>-y_{time}\times x_{lost} \]

把负号搞掉：

\[x_{time}\times y_{lost}<y_{time}\times x_{lost} \]

嗯，式子出来了，排序后再用一个 \(01\) 背包，over。

注意两点：

  1. 背包 dp 初始化是 \(128\)（因为这代表的是时间点要算还剩多少能量值），只有 \(dp_0\) 初始化为 \(0\)；

  2. 开 long long。

\(Code\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,ans,dp[10005];
struct rock{int t,lost,first;}a[105];
bool cmp(rock x,rock y){return x.t*y.lost<y.t*x.lost;}
signed main(){
	scanf("%d",&T);
	for(int r=1;r<=T;r++){
		ans=0;
		memset(dp,128,sizeof(dp));
		dp[0]=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].t,&a[i].first,&a[i].lost);
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++){
			for(int j=10000;j>=a[i].t;j--){
				dp[j]=max(dp[j],dp[j-a[i].t]+a[i].first-(j-a[i].t)*a[i].lost);
			}
		}
		for(int i=0;i<=10000;i++) ans=max(ans,dp[i]); 
		printf("Case #%lld: %lld\n",r,ans);
	}
	return 0;
}

T3

\(AC\ \ on\ \ 2021.06.13\)

就大模拟，没啥好说的，代码调了一个下午。

注意反转数串，注意循环里要先 n++（但是要是你循环里面先 +1 了循环前面就不要再 +1 了），注意每个数都只能走一遍，最重要的是注意读题（注意不能有 0 也不能有相同数字）……

橙题调这么久我还有救吗 qwq

\(Code\)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
bool check(ll i){
	//把i转换为数串形式
	int a[15]={},c[15]={};
	int weishu=0;
	while(i){
		c[++weishu]=(int)i%(ll)10;
		i/=(ll)10; 
	}
	//反转！ 
	for(int i=1;i<=weishu;i++) a[i]=c[weishu-i+1];
	//无重复数字 
	for(int i=1;i<=weishu;i++)
		for(int j=1;j<i;j++)
			if(a[i]==a[j]) return false;
	//去0判断
	for(int i=1;i<=weishu;i++) if(!a[i]) return false;
	//开始模拟 
	int x=1;
	bool b[15]={};
	for(int i=1;i<=weishu;i++){
		int t=a[x];
		while(t--){
			x++;
			if(x==weishu+1) x=1;
		}
		if(b[x]&&x!=1) return false;
		b[x]=1;
		if(x==1){
			bool flag=1;
			for(int i=1;i<=weishu;i++) flag&=b[i];
			if(flag) return true;
			else return false;
		}
	}
	return false;
}
int main(){
	scanf("%lld",&n);
	while(1){
		//printf("%d\n",n);
		n++;
		if(check(n)){
			printf("%lld",n);
			return 0;
		}
	}
	return 0;
}

T4

\(AC\ \ on\ \ 2021.06.13\)

嗯，看来 mjl 是爱上大模拟了（逃。

没什么可说的了，我爱暴力（（。

\(Code\)

#include<bits/stdc++.h>
using namespace std;
int n,x,y,a[20][20];
char zt='A';
int main(){
	scanf("%d",&n);
	for(int t=1;t<=n;t++){
		scanf("%d %d",&x,&y);
		if(t&1) zt='A',a[x][y]=1;
		else zt='B',a[x][y]=2;
		for(int i=1;i<=15;i++){
			for(int j=1;j<=15;j++){
				//横着的 
				if(i>=5){
					if(a[i][j]==1&&a[i-1][j]==1&&a[i-2][j]==1&&a[i-3][j]==1&&a[i-4][j]==1){
						printf("A %d",t);
						return 0;
					}
					if(a[i][j]==2&&a[i-1][j]==2&&a[i-2][j]==2&&a[i-3][j]==2&&a[i-4][j]==2){
						printf("B %d",t);
						return 0;
					}
				}
				if(i<=11){
					if(a[i][j]==1&&a[i+1][j]==1&&a[i+2][j]==1&&a[i+3][j]==1&&a[i+4][j]==1){
						printf("A %d",t);
						return 0;
					}
					if(a[i][j]==2&&a[i+1][j]==2&&a[i+2][j]==2&&a[i+3][j]==2&&a[i+4][j]==2){
						printf("B %d",t);
						return 0;
					}
				}
				//竖着的 
				if(j>=5){
					if(a[i][j]==1&&a[i][j-1]==1&&a[i][j-2]==1&&a[i][j-3]==1&&a[i][j-4]==1){
						printf("A %d",t);
						return 0;
					}
					if(a[i][j]==2&&a[i][j-1]==2&&a[i][j-2]==2&&a[i][j-3]==2&&a[i][j-4]==2){
						printf("B %d",t);
						return 0;
					}
				}
				if(j<=11){
					if(a[i][j]==1&&a[i][j+1]==1&&a[i][j+2]==1&&a[i][j+3]==1&&a[i][j+4]==1){
						printf("A %d",t);
						return 0;
					}
					if(a[i][j]==2&&a[i][j+1]==2&&a[i][j+2]==2&&a[i][j+3]==2&&a[i][j+4]==2){
						printf("B %d",t);
						return 0;
					}
				}
				//左上右下斜
				if(i>=5&&j>=5){
					if(a[i][j]==1&&a[i-1][j-1]==1&&a[i-2][j-2]==1&&a[i-3][j-3]==1&&a[i-4][j-4]==1){
						printf("A %d",t);
						return 0;
					}
					if(a[i][j]==2&&a[i-1][j-1]==2&&a[i-2][j-2]==2&&a[i-3][j-3]==2&&a[i-4][j-4]==2){
						printf("B %d",t);
						return 0;
					}
				} 
				if(i<=11&&j<=11){
					if(a[i][j]==1&&a[i+1][j+1]==1&&a[i+2][j+2]==1&&a[i+3][j+3]==1&&a[i+4][j+4]==1){
						printf("A %d",t);
						return 0;
					}
					if(a[i][j]==2&&a[i+1][j+1]==2&&a[i+2][j+2]==2&&a[i+3][j+3]==2&&a[i+4][j+4]==2){
						printf("B %d",t);
						return 0;
					}
				}
				//左下右上斜
				if(j>=5&&i<=11){
					if(a[i][j]==1&&a[i+1][j-1]==1&&a[i+2][j-2]==1&&a[i+3][j-3]==1&&a[i+4][j-4]==1){
						printf("A %d",t);
						return 0;
					}
					if(a[i][j]==2&&a[i+1][j-1]==2&&a[i+2][j-2]==2&&a[i+3][j-3]==2&&a[i+4][j-4]==2){
						printf("B %d",t);
						return 0;
					}
				}
				if(i>=5&&j<=11){
					if(a[i][j]==1&&a[i-1][j+1]==1&&a[i-2][j+2]==1&&a[i-3][j+3]==1&&a[i-4][j+4]==1){
						printf("A %d",t);
						return 0;
					}
					if(a[i][j]==2&&a[i-1][j+1]==2&&a[i-2][j+2]==2&&a[i-3][j+3]==2&&a[i-4][j+4]==2){
						printf("B %d",t);
						return 0;
					}
				}
			}
		}
	}
	printf("Tie");
	return 0;
}

据说有个小五打了 5.6K，好可怕

T5

\(AC\ \ on\ \ 2021.06.14\)

广搜（数据范围很水），不过要注意，在算这个点能不能走到终点的时候，必须老老实实地从这个点出发走到终点，不能从终点倒回来枚举 （别问我怎么知道的）。

不会 T 掉，数据范围是真的水。

这里我打了两个差不多的 bfs 函数，只不过一个没有返回值一个是 bool 型的。其实这里可以用数组实现，一个 bfs 函数就够了，但是我懒得打，反正能 A。

\(Code\)

#include<bits/stdc++.h>
using namespace std;
char a[55][55];
int m,n,sx,sy,tx,ty;
bool b[55][55],c[55][55];
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
struct node{int x,y;}t1,t2;
void bfs(int x,int y){
	queue<node> q;
	t1.x=x,t1.y=y;
	q.push(t1);
	while(!q.empty()){
		t1=q.front();
		q.pop();
		int dx,dy;
		int start,end; //循环开始与结束 
		if(a[t1.x][t1.y]=='.'&&a[t1.x+1][t1.y]=='#') continue;
		if(a[t1.x][t1.y]=='+'||a[t1.x][t1.y]=='S'||a[t1.x][t1.y]=='T') start=0,end=4;
		else if(a[t1.x][t1.y]=='-') start=0,end=2;
		else if(a[t1.x][t1.y]=='|') start=2,end=4;
		else if(a[t1.x][t1.y]=='.') start=3,end=4;
		else continue;
		for(int i=start;i<end;i++){
			dx=t1.x+dir[i][0];
			dy=t1.y+dir[i][1];
			if(dx>=1&&dx<=m&&dy>=1&&dy<=n&&a[dx][dy]!='#'){
				if(b[dx][dy]) continue;
				b[dx][dy]=1;
				t2.x=dx,t2.y=dy;
				q.push(t2);
			}
		}
	}
	return; 
}
//判断是否能到达终点
bool bfs2(int x,int y){
	memset(c,0,sizeof(c));
	queue<node> q;
	t1.x=x,t1.y=y;
	q.push(t1);
	while(!q.empty()){
		t1=q.front();
		q.pop();
		if(t1.x==tx&&t1.y==ty) return true;
		int dx,dy;
		int start,end; 
		if(a[t1.x][t1.y]=='.'&&a[t1.x+1][t1.y]=='#') continue;
		if(a[t1.x][t1.y]=='+'||a[t1.x][t1.y]=='S'||a[t1.x][t1.y]=='T') start=0,end=4;
		else if(a[t1.x][t1.y]=='-') start=0,end=2;
		else if(a[t1.x][t1.y]=='|') start=2,end=4;
		else if(a[t1.x][t1.y]=='.') start=3,end=4;
		else continue;
		for(int i=start;i<end;i++){
			dx=t1.x+dir[i][0];
			dy=t1.y+dir[i][1];
			if(dx>=1&&dx<=m&&dy>=1&&dy<=n&&a[dx][dy]!='#'){
				if(c[dx][dy]) continue;
				c[dx][dy]=1;
				t2.x=dx,t2.y=dy;
				q.push(t2);
			}
		}
	}
	return false; 
}
int main(){
	scanf("%d %d",&m,&n);
	for(int i=1;i<=m;i++){
		scanf("\n");
		for(int j=1;j<=n;j++){
			scanf("%c",&a[i][j]);
			if(a[i][j]=='S') sx=i,sy=j;
			else if(a[i][j]=='T') tx=i,ty=j;
		}
	}
	bfs(sx,sy);
	if(!b[tx][ty]){
		printf("I'm stuck!");
		return 0;
	}
	int sum=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(!bfs2(i,j)&&b[i][j]) sum++;
		}
	}
	printf("%d",sum);
	return 0;
}

T6

\(AC\ \ on\ \ 2021.06.15\)（只可惜比赛已经结束了 qwq）

30 分一定是万恶的全排列了 qwq

不！我们不能思想只停留在部分分！

好吧这题是道 DP。

思路和大家的差不多，不讲！

话说我竟然不看 TJ 想到了这个思路就很那啥。

最关键的是我竟然没想到区间求和的优化就很那啥。

\(Code\)

#include<bits/stdc++.h>
using namespace std;
int n,m,sum,dp[1005][1005];
const int p=10000;
int main(){
	scanf("%d %d",&n,&m);
	dp[1][0]=1;
	for(int i=2;i<=n;i++){
		sum=0;
		for(int j=0;j<=m;j++){
			sum=(sum+dp[i-1][j])%p;
			dp[i][j]=sum;
			if(j+1>=i) sum=(sum-dp[i-1][j-i+1]+p)%p; //括号里要加上取余的数不然会取爆 
		}
	}
	printf("%d",dp[n][m]);
	return 0;
}

T7

易证：mjl 爱上了大模拟之后一定又爱上了 HAOI……

紫题搞毛线啊。

溜了溜了。

The end.

上一篇：scp ssh: connect to host 192.168.6.129 port 22: Connection refused lost connection


下一篇：造成错误“ORA-12547: TNS:lost contact”的常见原因有哪些？