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

2024/3/22 周赛总结

总分：55

T1 项目贡献度统计

得分：10

原题传送门：P1571

Q：❌原因？
A：想的都不对，本来想着用二分的（确实是对的），但是不知道为啥就用了搜索
Q：最佳做法？
A：模拟，二分，Maps
Q：正确代码？
A：
1.（示例、题解）

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll l,r;//二分用的 
ll a[114514],b[114514];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(b+1,b+m+1);//对输入的B数组初次排序 
	for(int i=1;i<=n;i++){
		l=1;r=m;
		while(l<=r){
		    int mid=(l+r)>>1;
			if(b[mid]==a[i]){//如果这个值在B数组出现过且与a[i]相同 
				cout<<a[i]<<" ";//输出 
				break;//跳过 
			}
			else if(b[mid]<a[i]) l=mid+1;//如果数在右边 
			else r=mid-1;//如果数在左边 
		}
	}
	return 0;
}

2.（同学的）

T2 山地探险

得分：20

原题传送门：P1434

Q：❌原因？
A：思考不正确（以为1是最低的）
Q：最佳做法？
A：DP，搜索，递归，搜索（记忆化）
Q：正确代码？
A：
1.（示例、题解）

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
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,a[201][201],s[201][201],ans;
bool use[201][201];//这个就是所谓的不需要
int dfs(int x,int y){
    if(s[x][y])return s[x][y];//记忆化搜索
    s[x][y]=1;//题目中答案是有包含这个点的
    for(int i=0;i<4;i++)
    {  int xx=dx[i]+x;
       int yy=dy[i]+y;//四个方向
       if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]){
       	  dfs(xx,yy);
          s[x][y]=max(s[x][y],s[xx][yy]+1);
       }
    }
    return s[x][y];
}
int main()
{	
   scanf("%d%d",&n,&m);//同题目的R,C
   for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
       scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)//找从每个出发的最长距离
      for(int j=1;j<=m;j++)
        ans=max(ans,dfs(i,j));//取最大值
    printf("%d",ans);
    return 0;
}
// by 路人七

2.（同学的）

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll r,c,a[114][114],up[1145][1145];
int ans;
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int d(int x,int y){//记忆化搜索 
	if(up[x][y]) return up[x][y];//如果搜过 直接使用保存的结果 
	up[x][y]=1;
	for(int i=0;i<4;i++){
		int tx=dx[i]+x,ty=dy[i]+y;
		if(tx>=1&&tx<=r&&ty>=1&&ty<=c&&a[x][y]>a[tx][ty]){
			d(tx,ty);
			up[x][y]=max(up[x][y],up[tx][ty]+1);//判断最大滑多远
			 
		}
	}
	return up[x][y];
}
signed main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=r;i++)
	for(int j=1;j<=c;j++)
	ans=max(ans,d(i,j));
	cout<<ans;
	
}

T3 山地探险

得分：25

原题传送门：P1023

Q：❌原因？
A：不理解题目意思
Q：最佳做法？
A：数学，枚举
Q：正确代码？
A：

  1. （示例、题解）
    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
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    #include <iostream>
    #include <cmath>
    using namespace std;
    int a[100010][3];//用于存放价格和销量的数组
    int main()
    {
        int i=1,j=1,k,expect,down,max,temp,cha,xl,num,s,price,p;
        cin>>expect;//读入预期价
        while(cin>>a[i][1]>>a[i][2]&&a[i][1]!=-1&&a[i] [2]!=-1)//如果输入的两个数不是-1，-1
        {
    	    i++;//循环变量i++
    	    if(i>2&&a[i-1][1]-a[i-2][1]>1)//如果两个价格之间差大于一
    	    {
    		    i--;//回到上一个读入的销量
    		    cha=(a[i-1][2]-a[i][2])/(a[i][1]-a[i-1][1]);//求出每次销量减少多少：销量差/价格差
    		    temp=a[i][1];//记录下价格
    		    for(j=a[i-1][1]+1;j<=temp;j++)//按价格递增顺序依次写入
    		    {
    		    	a[i][1]=j;//写入价格
    		    	a[i][2]=a[i-1][2]-cha;//按销量差写入销量
    		    	i++;
    		    }
    	    }
        }
        cin>>down;//输入超过最大价格之后每次销量降低多少
        i--;//因为上面的while循环最后有i++所以用i--抵消……
        xl=a[i][2];//记录目前的销量
        while(xl>0)
        {
    	    if(xl-down<0)break;//如销量小于零则退出
    	    else//否则
    	    {
    	    	xl-=down;//销量每次减掉down
    	    	i++;//循环变量++
    	    	a[i][1]=a[i-1][1]+1;//每次价格+1
    	    	a[i][2]=xl;//销量就是xl
    	    }
        }
        for(j=1;j<=10000;j++)//该遍历了，因为收税相当于补贴*-1所以记录一下符号即可
        {
    	    max=-99999;//用于存储最大的总利润
    	    for(k=1;k<=i;k++)//每次扫一遍每一种价格
    	    {
    		    num=(a[k][1]-a[1][1]+j)*a[k][2];//套公式算出总利润
    		    if(num>=max)//如果总利润比目前最大的大
    		    {
    		        max=num;//更新max
    			    price=a[k][1];//记录下价格
    			    p=1;//记录下符号
    		    }
    	    }
    	    if(price==expect){cout<<j*p;return 0;}//如果价格就是政府预期价则打印出来，因为本身就是从小到大遍历所以不用求绝对值最小的
    	    max=-99999;//后面是收税，原理同上
    	    for(k=1;k<=i;k++)
    	    {
    		    num=(a[k][1]-a[1][1]-j)*a[k][2];
    		    if(num>=max)
    		    {
    		       max=num;
    			    price=a[k][1];	
    			    p=-1;
    		    }
    	    }
    	    if(price==expect){cout<<j*p;return 0;}
        }
        //前面有了return 0;这儿就不用了。
    }
  2. （老师的）

代码

T4 下棋

得分：0

原题传送门：P1259

Q：❌原因？
A：没有做（太复杂了）
Q：最佳做法？
A：递归、分治
Q：正确代码？
A：

  1. （示例、题解）
    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
    53
    54
    #include <cstdio>
    #include <iostream>
    using namespace std;
    int n;
    char ch[205];//存储棋子的状态
    void swap(char &a, char &b)//交换函数
    {
        char t = a;
        a = b;
        b = t;
    }
    void output(){//输出
        for (int i = 0; i < 2 * n + 2; i++)
            putchar(ch[i]);
        putchar('\n');
    }
    void movechess(int start, int end)
    {//移动棋子
        swap(ch[start], ch[end]);
        swap(ch[start + 1], ch[end + 1]);
        output();
    }
    string out[4] = {"ooo*o**--*", "o--*o**oo*", "o*o*o*--o*", "--o*o*o*o*"};
    //打表qwq
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            ch[i] = 'o';
        for (int i = n; i < 2 * n; i++)
            ch[i] = '*';
        ch[2 * n] = '-';
        ch[2 * n + 1] = '-';
        //打印初始状态
        output();
        int len = n;
        //需要移动的黑/白棋子
        while (true)
        {
            movechess(len - 1, 2 * len);
            //中间的 "o*" 与 "--" 交换
            len--;
            if (len == 3)
            //不符合上述规律,开始输出打表内容
                break;
            movechess(len, 2 * len);
            //最左边的 "**" 与 "--" 交换
        }
        string ss;
        for (int i = 0; i < n - 4; i++)
            ss += "o*";
        for (int i = 0; i < 4; i++)
            cout << out[i] << ss << endl;
    }
  2. （同学的）
    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
    53
    54
    55
    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int main()
    {
    	cin>>n; 
    	for(int i=1;i<=n;i++)//先输入初始的棋子 
    	cout<<"o";
    	for(int i=1;i<=n;i++)
    	cout<<"*";
    	cout<<"--"<<endl;	 
    	for(int i=2;i<=n-3;i++)//从第2行到倒数第5行都有相同的规律 
    	{						
    		for(int j=n;j>=i;j--)   
    		cout<<"o";
    		cout<<"--";			
    		for(int j=n;j>=i;j--)  
    		cout<<"*";
    		for(int j=1;j<i;j++)	
    		cout<<"o*";
    		cout<<endl;
    		//每两行为一个周期，前后两行的空格位置换了一下 
    		for(int j=n;j>=i;j--)
    		cout<<"o";
    		for(int j=n;j>=i;j--)
    		cout<<"*";
    		cout<<"--";
    		for(int j=1;j<i;j++)
    		cout<<"o*";	
    		cout<<endl;
    	}
    	if(n>4)//规律 
    	{
    		cout<<"ooo--***";
    		for(int i=1;i<=n-3;i++)
    		cout<<"o*";
    		cout<<endl;	
    	}
    	cout<<"ooo*o**--*";
    	for(int i=1;i<=n-4;i++)//每一行都有固定的规律 
    	cout<<"o*";
    	cout<<endl;
    	cout<<"o--*o**o";
    	for(int i=1;i<=n-3;i++)
    	cout<<"o*";
    	cout<<endl;
    	cout<<"o*o*o*--";
    	for(int i=1;i<=n-3;i++)
    	cout<<"o*";
    	cout<<endl;
    	cout<<"--";
    	for(int i=1;i<=n;i++)
    	cout<<"o*";
       return 0; 
    }

总结：

总体来说还行，但是我不太坚定自己的选择，导致第一题的10分（QAQ），下次我会继续努力！