首页 > 其他分享 >2023年 8月15日普及组南外集训题解

2023年 8月15日普及组南外集训题解

时间:2023-08-18 12:11:48浏览次数:51  
标签:maxx 组南外 string int 题解 ++ 2023 using include

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;
}

标签:maxx,组南外,string,int,题解,++,2023,using,include
From: https://www.cnblogs.com/xiaozhu0602/p/17640169.html

相关文章

  • Atcoder_[abc284E]Count Simple Paths题解
    题目链接这题就是很简单的图上深搜,我觉得放在E题太水了,代码里有详细注释。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvector<int>v[200010];//邻接表intans;//答案boolvis[200010];//vis[i]记录i号点有没有被访问过voiddfs(intx)......
  • ARC145C 题解
    problem&blog。小清新结论题。提供一个不需要脑子就可以AC的方法:看样例解释,猜到一定是\((1,2)(3,4)\)这样子,于是暴力,把前几项输进OEIS里,做完了。显然取\(\forall|A_i-B_i|=1\)最优。证明:对于\(x-3,x-2,x-1,x\),配对:\((x-3,x-2)(x-1,x)\)的贡献为\((x-3)(x-2)+......
  • 【2023-08-17】工作思想
    20:00一个人的名字,早晚是要没有的,能把微薄的力量融进祖国的强盛之中,便足以自慰了。                                                 ——于敏昨天听到何太跟她同事相......
  • vue3项目,vie框架,相对路径图片,测试时正常显示,发布后不显示问题解决方案
    参考Vite官网的说明,修改图片的引用路径后,图片发布后可以正常显示constimgUrl=newURL('./img.png',import.meta.url).hrefdocument.getElementById('hero-img').src=imgUrl官网地址: https://cn.vitejs.dev/guide/assets.html ......
  • CLion的远程同步功能,删除文件没有进行同步问题解决
    在使用CLion的deployment功能时。正常修改增加都会自动同步到远程。但是删除文件或者文件夹时,远程的文件没有删除,重新同步后,原来删除的文件又出现了。这是因为Clion默认没有将删除的同步打开:Settings->Deployment->Options->勾选:Deleteremotefileswhenlocalaredele......
  • [AGC001E] BBQ Hard 题解
    计数题好题。思路考虑\(\dbinom{n+k}{k}\)的几何意义。即从\((1,1)\)到\((k,n)\)只往上或往右走的方案数。由于这个在几何上坐标可以平移。也就是\((1-x,1-y)\)到\((k-x,n-y)\)的方案与\((1,1)\)到\((k,n)\)的方案数是一样的。那么我们就可以求出所有\((1-a_......
  • [AGC002F] Leftmost Ball 题解
    很好的一道组合题。思路直接设\(dp_{i,j}\)表示已经放了\(i\)个白点与\(j\)中颜色。然后直接组合数算即可。CodeAC记录。......
  • [AGC002E] Candy Piles 题解
    比较简单的题。思路考虑这个玩意在几何上的意义。发现就是要么往上走,要么往右走。那么就十分容易找到规律。找到规律后也很容易感性理解。CodeAC记录。......
  • [AGC002D] Stamp Rally 题解
    可以看做一道比较套路的的$kruskal$重构树。但或许也是一道复习与入门的好题。思路考虑把图论问题转化为树上问题。发现所求的为路径上最大的最小。容易想到$kruskal$重构树。发现由于从两端一起走,不能直接处理。那么就可以在外面套一个二分,内部直接倍增处理即可。Cod......
  • [AGC001F] Wide Swap 题解
    特别有意思的思维题。思路参考题解第一位的神仙思路。将排列\(a_i\)变为\(b_{a_i}\)。限制便变为了只能交换相邻的两个差大于\(k\)的点。那么这个限制就已经与普通排序很相似。考虑使用归并排序。一个点可以跑到其他点的前面要求这一连续段都是比它加\(k\)都不大。......