上海青少年算法竞赛-6月月赛参考代码

浅浅的花香味﹌ 2023-02-20 02:41 22阅读 0赞

# T1 #

#include <iostream>
    using namespace std;
    
    int main()
    { 
        int n;
        cin >> n;
    
        int a = 1;//初始化，0刀是一块
        for(int i = 1; i <= n; i++)
        { 
            //切第i刀时会多i块
            a += i;
        }
    
        cout << a;
    
        return 0;
    }

# T2 #

#include <iostream>
    
    using namespace std;
    
    int main()
    { 
        string s;
        cin >> s;
        int len = s.size();
        for(int i = 0; i < len - 4; i++)
        { 
            if('b' == s[i] && 'l' == s[i + 1] && 'a' == s[i + 2] && 'c' == s[i + 3] && 'k' == s[i + 4])
            { 
                s[i + 2] = 'o';
            }
        }
    
        cout << s;
    
        return 0;
    }

# T3 #

解法一

#include <iostream>
    #include <cmath>
    using namespace std;
    
    int main()
    { 
        int n;
        cin >> n;
        for(int i = -n; i <= n; i++)
        { 
            cout << "**";
    
            int x = abs(i);
            if(0 == x)  //中间那行特判
            { 
                cout << '*';
            }
    
            for(int j = 1; j <= x; j++)
            { 
                cout << ' ';
            }
            for(int j = 1; j <= x; j++)
            { 
                cout << '*';
            }
            cout << endl;
        }
    
        return 0;
    }

解法二：Zirui代码

#include <iostream>
    #include <cmath>
    using namespace std;
    
    int main()
    { 
    	int n;
    	cin>>n;
    	int tmp=n;
    	for ( int i=0; i<n*2+1; i++ )
    	{ 
    		cout << "**";
    		for ( int j=0; j<abs(tmp); j++ )
    		{ 
    			cout << " ";
    		}
    		if ( tmp==0 ) //中间行加空格
    		{ 
    			cout << "*";
    		}
    		for ( int j=0; j<abs(tmp); j++ )
    		{ 
    			cout << "*";
    		}
    		tmp--;
    		cout << endl;
    	}
    
    	return 0;
     }

# T4 #

解法一

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxN = 100000 + 5;
    long long p[maxN];
    
    int main()
    { 
        //freopen("T4.in", "r", stdin);
    
        int n, m;
        long long c;
        cin >> n >> m;
        long long total = 0;
        for(int i = 1; i <= n; i++)
        { 
            cin >> p[i] >> c;
            if(c > 0)
            { 
                //j必须在保质期内
                for(int j = max(1, i - m); j <= i; j++)
                { 
    
                    if(p[j] >= c)//第j天的牛奶满足需求，且有剩余
                    { 
                        total += c;
                        p[j] -= c;
                        c = 0;
                        break;
                    }
                    else    //第j天的牛奶少于需求，则下一天的牛奶也要卖
                    { 
                        total += p[j];
                        c -= p[j];
                        p[j] = 0;
                    }
                }
            }
        }
    
        cout << total;
    
        return 0;
    }

解法二：Theo代码

#include <iostream>
    #include <queue>
    #define LL long long
    using namespace std;
    
    struct milk
    { 
        int amount;
        int produced;
    };
    
    int n, m;
    deque<milk> que;
    
    int main()
    { 
        cin >> n >> m;
        LL tot = 0;
        for(int i = 1; i <= n; i++)
        { 
            int p, c;
            cin >> p >> c;
            que.push_back({ p, i});
            while (!que.empty())
            { 
                if(i - que.front().produced > m)
                { 
                    que.pop_front();
                }
                if(que.front().amount > c)
                { 
                    tot += c;
                    que.front().amount -= c;
                    break;
                }
                if(que.front().amount == c)
                { 
                    tot += c;
                    que.pop_front();
                    break;
                }
                if(que.front().amount < c)
                { 
                    tot += que.front().amount;
                    c -= que.front().amount;
                    que.pop_front();
                }
            }
        }
        cout << tot << endl;
        return 0;
    }

# T5 #

解法一：70分代码

#include <iostream>
    using namespace std;
    
    const int maxN = 100;
    int n, m, k, sum[maxN][maxN];
    char  a[maxN][maxN];
    
    void input()
    { 
        cin >> n >> m >> k;
        for(int r=1; r<=n; r++)
        { 
            for(int c=1; c<=m; c++)
            { 
                cin >> a[r][c];
            }
        }
    }
    
    //求二维数组前缀和
    void getPreSum()
    { 
    	for(int r=1; r<=n; r++)
        { 
            for(int c=1; c<=m; c++)
            { 
                sum[r][c] = sum[r-1][c] + sum[r][c-1] - sum[r-1][c-1] + (a[r][c] == '.');
            }
        }
    }
    
    int getSum(int r1, int c1, int r2, int c2)
    { 
        return sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1];
    }
    
    int main()
    { 
        //freopen("T5.in", "r", stdin);
    
        input();
        getPreSum();
    
        const int INF = 2100000000;
        int minArea = INF;
    
        for(int r1 = 1; r1 <= n; r1++)
        { 
            for(int c1 = 1; c1 <= m; c1++)
            { 
                for(int r2 = r1; r2 <= n; r2++)
                { 
                    for(int c2 = c1; c2 <= m; c2++)
                    { 
                        if(getSum(r1, c1, r2, c2) >= k && (r2 - r1 + 1) * (c2 - c1 + 1) < minArea)
                        { 
                            minArea = (r2 - r1 + 1) * (c2 - c1 + 1);
                        }
                    }
                }
            }
        }
    
        if(minArea == INF)
        { 
            cout << "No Solution";
        }
        else
        { 
            cout << minArea;
        }
    
        return 0;
    }

解法二： 尺取法

#include<bits/stdc++.h>
    using namespace std;
    char x;
    int n,m,num,need,ans = 1e9,a[1101][1101];
    
    void getSectionSum(int l,int r)
    { 
    	int emptySeats = 0, up = 1, down = 1;
    	for(; up <= n; up++)
        { 
    		for(; down <= n && emptySeats < need; down++)
    		{ 
    		    emptySeats += a[down][r] - a[down][l - 1];
    		}
    
    		if(emptySeats < need)
            { 
                break;
            }
    
            //down最后又自加了一次，所以down-up不用再+1
    		ans = min(ans,(r - l + 1) * (down - up));
    		emptySeats -= a[up][r] - a[up][l - 1];
    	}
    }
    
    int main()
    { 
        //freopen("T5.in", "r", stdin);
    
        cin >> n >> m >> need;
        for(int i = 1; i <= n; i++)
        { 
            for(int j = 1; j <= m; j++)
            { 
                cin>>x;
                num += (x == '.');
                a[i][j] = a[i][j - 1] + (x == '.');
            }
        }
    
    	if(num < need)
        { 
            cout<<"No Solution"<<endl;
            return 0;
    	}
    
        for(int l = 1; l <= n; l++)
        { 
            for(int r = l; r <= m; r++)
            { 
                getSectionSum(l, r);
            }
        }
    
        cout<<ans<<endl;
    
        return 0;
    }

了解中小学信息学竞赛请加微信307591841（QQ同号）