2023.10.27初一编程马拉松赛赛后总结

总分：273

总叙：有亿点难（太菜了），发挥的不好，学过的知识点运用不好

P1003 [NOIP2011 提高组] 铺地毯

题目链接：P1003

考点：(模拟题）从后往前枚举地毯（因为后覆盖的地毯在上面，而题目正好要求最上面的地毯），如果有一个地毯满足条件（满足什么条件在下面讲解）就直接输出，并退出。如果没有地毯满足条件，就输出-1

难点：模拟，枚举

比赛时自己的思路：先输入数据，找地毯覆盖的位置，累加cnt

情况：$\mathbf\color{red} WA$

正确解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
long long a[114514],b[114514],x[114514],y[114514],n,sx,sy,ans=-1;
//初始化ans为-1 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i]>>x[i]>>y[i];
	}
	cin>>sx>>sy;
	for(int i=1;i<=n;i++)
	{
		if(a[i]<=sx&&b[i]<=sy&&x[i]+a[i]>=sx&&y[i]+b[i]>=sy)
		{
			//判断是否覆盖所求的点
			ans=i; 
		}
	}
	cout<<ans;
}

P1031 [NOIP2002 提高组] 均分纸牌

题目链接：P1031

考点：（模拟，贪心） 每堆牌只能移到相邻的堆，一堆堆处理，且只考虑后一堆

难点：贪心算法

比赛时自己的思路：平分每一堆得纸牌

结果：$\mathbf\color{red} WA$

正确解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<cstdio>
using namespace std;
#define FOR(i,n,m) for(int i=n;i<=m;i++)//宏定义节省代码长度
int n,a[110],c[110],p,ans;
int main()
{
    scanf("%d",&n);FOR(i,1,n) scanf("%d",&a[i]); //读入
    FOR(i,1,n) c[i]=c[i-1]+a[i];  //求前缀和
    p=c[n]/n; //求平均数
    FOR(i,1,n-1) if(p*i!=c[i]) ans++;
    //当此时牌堆1-i总牌数!=i*总平均数，需要移动一次
    printf("%d",ans);
    return 0;
}

P1055 [NOIP2008 普及组] ISBN 号码

题目链接：P1055

考点：（模拟，字符串） 首先，可以把ISBN号码分割成三个int和一个char，用scanf输入，最后一位是char型是因为它可能是‘X’，然后将X换成10，依次分解，判断

难点：字符串

比赛时自己的思路：输入，分别为 int-int-int-char(char防止输入X,X换成10),分解每一个数的各个数位的数，分别乘起来，最后mod11,判断是否为正确结果，对输出“Yes”，不对就输出新的结果

结果：$\mathbf\color{red} WA$

正确结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
using namespace std;
int main()
{
	int a,b,c,d,s=0,m;
	char d1;
	scanf("%d-%d-%d-%c",&a,&b,&c,&d1);
	if(d1=='X')
	{
		d=10;
	}
	else
	{
		d=d1-48;
	}
	m=(a*1000+b)*100000+c;
	for(int i=1;i<=9;i++)
	{
		s+=m%10*(9-i+1);
		//s%=11;
		m/=10;
	}
	s%=11;
	if(s==d)
		cout<<"Right"<<endl;
	else
	{
		printf("%d-%d-%d-",a,b,c);
		if (s==10)
		{
			cout<<'X'<<endl;
		}
		else
		{
			cout<<s<<endl;
		}	
	}
		
	return 0;
}

P1102 A-B 数对

题目链接：P1102

考点：重复是算的， A-B=C 那么 A-C=B 所以就把A的个数累加，然后把A减去C就可以了，B的值的和就是答案。 当然MLE是可能得。所以绕一下做就行了。

难点：模拟；数学；二分；排序；哈希, hash；双指针,two-pointer

比赛时自己的思路：遍历数对，一个个数相减然后判断（当时也想着可能会RE或TLE）

结果：WA(76pts)

正确解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[200001],ans;
int fun(int x)
{
	int l=0,r=n+1,mid;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(a[mid]<=x)
		{
			l=mid;
		}
		else
		{
			r=mid;
		}
	}
	return l;
}
int far(int x)
{
	int l=0,r=n+1,mid;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(a[mid]<x)
		{
			l=mid;
		}
		else
		{
			r=mid;
		}
	}
	return l;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n); 
	for(int i=1;i<=n;i++)
	{
		ans+=fun(a[i]+k)-far(a[i]+k);
	}
	cout<<ans;
	return 0;
}

总结：

考的不好，再努力