A 查找最大元素

扫一遍确定最大值，如果是最大值输出字符和"(max)"，不是的话只输出字符

#include <iostream>
#include <cstring>
using namespace std;
char maxx;
string s;
int main() {
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        if (s[i] >= maxx)
            maxx = s[i];
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == maxx)
            cout << s[i] << "(max)";
        else
            cout << s[i];
    }
    return 0;
}

B 最高分问题

排个序，如果自身是最大值输出次大值，否则输出最大值

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int a[N],b[N];
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        if(b[i]==a[n]) printf("%d\n",a[n-1]);
        else printf("%d\n",a[n]);
    }
    return 0;
}

C 回文序列

因为这题是保证有解的，所以我们不需要管无解的情况，我们直接用两个光标指向两端，如果相等都移动，如果 \(a[l]<a[r]\)，那么就让 \(a[l]\) 和 \(a[l+1]\) 合体，另一方向同理
因为如果说小的不合的话，之后就没有机会了，这是一个贪心的思想

#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int a[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = n;
    int cnt = 0;
    while (l < r) {
        if (a[l] == a[r]) {
            l++;
            r--;
        }
        if (a[l] < a[r]) {
            a[l + 1] += a[l];
            l++;
            cnt++;
        }
        if (a[l] > a[r]) {
            a[r - 1] += a[r];
            r--;
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

D 重排列

这里使用一个贪心的思想进行排序，我们肯定是希望开头的越大越好，那么排序的时候就看 a+b 和 b+a 哪个大，这个是系统自带大于小于，直接写 a+b<b+a 就行了
最后记得去除前导0，并且如果结果的长度是0的话输出0

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10005;
string a[N];
bool cmp(string a,string b){return a+b<b+a;}
int main()
{
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1,cmp);
    string res="";
    for(int i=1;i<=n;i++) res+=a[i];
    while(res[0]=='0') res.erase(0,1);
    if(res.size()==0) cout<<0;
    else cout<<res;
    return 0;
}

E 跳跃的小C

因为长度非常大，所以dp数组是放不下的，那么如何解决这个问题呢？ 我们可以用终点减去起点便得到了跳跃的长度
那么 \(f[i][j]\) 就表示从 \(j\) 跳到 \(i\) 所能达到的最高分
然后开始枚举三个点 \(i,j,k\) 因为我们需要保证跳的距离不能比上次短，然后打擂台求最大值
然后是另一个方向，注意因为方向所以两个减数的位置要对调，不要无脑复制

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int f[N][N];  //从 j 跳到 i 所能达到的最高分
struct node {
    int x, p;
} a[N];
bool cmp(node a, node b) { return a.x < b.x; }
bool cmp1(node a, node b) { return a.x > b.x; }
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].p;
    sort(a, a + n, cmp);
    int ans = 0;
    for (int i = n - 2; i >= 0; i--) {
        int k = n - 1, maxx = 0;
        for (int j = 0; j <= i; j++) {
            while (k < n && a[k].x - a[i].x >= a[i].x - a[j].x) {
                maxx = max(maxx, f[k][i] + a[k].p);
                k--;
            }
            f[i][j] = maxx;
        }
        ans = max(ans, a[i].p + maxx);
    }
    sort(a, a + n, cmp1);
    for (int i = n - 2; i >= 0; i--) {
        int k = n - 1, maxx = 0;
        for (int j = 0; j <= i; j++) {
            while (k > i && a[i].x - a[k].x >= a[j].x - a[i].x) {
                maxx = max(maxx, a[k].p + f[k][i]);
                k--;
            }
            f[i][j] = maxx;
        }
        ans = max(ans, a[i].p + maxx);
    }
    cout << ans;
    return 0;
}

F 移动玩具

和八数码非常像，把16个数字都枚举一遍就行了

#include <iostream>
#include <unordered_map>
#include <queue>
#include <cstring>
using namespace std;
string st, ed;
int bfs() {
    queue<string> q;
    unordered_map<string, int> d;
    q.push(st);
    d[st] = 0;
    int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
    while (!q.empty()) {
        string t = q.front();
        q.pop();
        int distance = d[t];
        if (t == ed)
            return distance;
        //枚举16个数字
        for (int k = 0; k < 16; k++) {
            int x = k / 4, y = k % 4;
            for (int i = 0; i < 4; i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < 4 && b >= 0 && b < 4) {
                    swap(t[k], t[a * 4 + b]);
                    if (!d.count(t)) {
                        d[t] = distance + 1;
                        q.push(t);
                    }
                    swap(t[k], t[a * 4 + b]);
                }
            }
        }
    }
    return -1;
}
int main() {
    for (int i = 0; i < 16; i++) {
        char c;
        cin >> c;
        st += c;
    }
    for (int i = 0; i < 16; i++) {
        char c;
        cin >> c;
        ed += c;
    }
    cout << bfs();
    return 0;
}