A：岛屿的周长

知识点：二维数组、迭代

思路：对于一个陆地格子的每条边，它被算作岛屿的周长当且仅当这条边为网格的边界或者相邻的另一个格子为水域。 因此，我们可以遍历每个陆地格子，看其四个方向是否为边界或者水域，如果是，将这条边的贡献（即 1）加入答案 ans 中即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101][101],ans,dx[]={0, 1, 0, -1},dy[]={1, 0, -1, 0};
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]){
                int cnt=0;
                for(int k=0;k<4;k++) {
                    int xx=i+dx[k];
                    int yy=j+dy[k];
                    if(xx<1||xx>n||yy<1||yy>m||!a[xx][yy]){
                        cnt++;
                    }
                }
                ans+=cnt;
            }
        }
    }
    cout<<ans;
    return 0;
}

B：买球

知识点：贪心、前缀和

思路：首先，按降序对a和b数组进行排序。然后令aa[i]为a[1]+a[2]+......+a[i]，bb[i]为b[1]+b[2]+......b[i]。则所求的答案为0<=i<=n,0<=j<=m,j<=i中的最大值aa[i]+bb[j]。但是遍历i,j时间复杂度为O(m*n),超时。

所以，可以固定i，考虑aa[i]+bb[j]何时可以达到最大值，由于j可以取0<=j<=min(i,m)中的任意值，因此使用bbb[0],bbb[1],......bbb[min(i,m)]中的最大值。通过预先计算bbb的累计最大值，可以在O(m)的时间内完成。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[200001],b[200001],aa[200001],bb[200001],bbb[200001],pos,ans; 
bool cmp(int a,int b){
    return a>b;
}
signed main(){     
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) aa[i]=aa[i-1]+a[i];//前缀和 
    for(int j=1;j<=m;j++) cin>>b[j];
    sort(b+1,b+1+m,cmp);
    for(int j=1;j<=m;j++) bb[j]=bb[j-1]+b[j];//前缀和 
    for(int j=1;j<=m;j++) bbb[j]=max(bbb[j-1],bb[j]);
    for(int i=1;i<=n;i++) ans=max(ans,aa[i]+bbb[min(i,m)]);
    cout<<ans;
    return 0;
}

C：两个子序列

知识点：贪心

思路：如果 B 没有在 A 中出现，输出 No。

否则肯定有至少一个 A 的子序列与 B 相等。

通过从前往后匹配可以找到满足条件的字典序最小的子序列。

通过从后往前匹配可以找到满足条件的字典序最大的子序列。

容易把这两个子序列每一位对应 A 中的下标记录下来。

看一看两个子序列在 A 中对应的位置是否存在不同即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,a[N],b[N],A[N],B[N],ind=1; 
int main(){    
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        if(a[i]==b[ind]){
            A[ind++]=i;
        }
    }
    if(ind!=m+1){
        cout<<"No\n";
        return 0;
    }
    ind=m;
    for(int i=n;i>=1;i--){
        if(a[i]==b[ind]){
            B[ind--]=i;
        }
    }
    if(ind!=0){
        cout<<"No\n";
        return 0;
    }
    for(int i=1;i<=m;i++){
        if(A[i]!=B[i]){
            cout<<"Yes\n";
            return 0;
        }
    }
    cout<<"No\n";
    return 0;
}

D：顺手牵羊

知识点：二分

思路：一个比较经典的二分套路。如果 check(mid) 是检查 mid 能不能做第 k 名，那显然不具有单调性，可以做第 k 名的位置是离散的。

可以考虑 check(mid) 检查答案是否大于等于 mid。那就只需要检查是否存在一条路劲使得大于等于 mid 的数不少于 k 个了。此时就有单调性了，答案就是符合条件的 mid 中最大的一个。

这个检查也是个经典的套路，显然只有 ≥mid 的数有贡献，那么可以把所有 ≥mid 的数看作 1，所有 <mid 的数看作 0。然后看看左上到右下的最大路径和。此时就是最多路上能经过的 ≥mid 的数的数量了。如果大于等于 k，那么 check 就是真。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int n,k,a[1001][1001],f[1001][1001],l = 1,r = 1e9,ans;
bool check(int x) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + (a[i][j] >= x);
            //找任意路径有没有超过x的个数是超过k的 
        }
    return f[n][n] >= k;
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d",&a[i][j]); 
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    printf("%d",ans);
    return 0;
}