首页 > 其他分享 >2024信友队蓝润暑期集训提高1班②Day2

2024信友队蓝润暑期集训提高1班②Day2

时间：2024-07-16 15:58:02浏览次数：13  
标签：cnt ab bc int Day2 ret 2024 ++ 蓝润

知识总结

转化、构造、模拟。

转化：将算法转化为其他形式。

构造：通过算法构造一个模型。

模拟：通过算法模拟一个过程。

随堂练习

T1 排行榜

题目描述

https://www.luogu.com.cn/problem/P1159

思路解析

显然这题可以直接贪心。把一首一首歌往排行榜上放。
对于 SAME 的歌，直接放在原位。UP 的尽量往后放，DOWN 的尽量往前。由于题目保证有一解，所以同为 UP 或 DOWN 的相对位置不需发生变化。所以扫一遍就可以了。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
string cina, cinb;
int n, up, down, now1, now2;
string Sup[N], Sdown[N], ans[N];
inline void init(int id) {
    if (cinb == "UP") {
        Sup[++up] = cina;
    } else if (cinb == "DOWN") {
        Sdown[++down] = cina;
    } else {
        ans[id] = cina;
    }
    return;
}
signed main() {
    scanf("%d", &n);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 1; i <= n; i++) {
        cin >> cina >> cinb;
        init(i);
    }
    for (int i = 1; i <= n; i++) {
        if (ans[i] == "") {
            if (now1 < down) {
                ans[i] = Sdown[++now1];
            } else {
                ans[i] = Sup[++now2];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

T2 左右构造机

给你一个数组 S，包含 n 个元素，它们构成一个环，
$S_0$ 的左边是 $S_{n-1}$ ，$S_n-1$ 的右边是 $S_0$ 。
再给你一个同样长度的目标数组 T，每次你可以对 S 做的操作有如下两种：
L：每个数都加上左边的数
R：每个数都加上右边的数
以上两种加法对于每个数都是同时完成的，即每次操作完后数组中的某个数是本次操作前数组中的两个数之和。
输出一个可以使得 $S$ 变成 $T$ 的操作序列，序列长度不能超过 $100$。

思路解析

1：由于无论什么操作每次总和都会乘以 2，所以总的操作次数 sum 可以根据总和的变化来确定

2：观察到 L 操作与 R 操作产生的序列

a0 a1 a2 a3

L 操作产生 a0+a3 a1+a0 a2+a1 a3+a2

R 操作产生 a0+a1 a1+a2 a2+a3 a3+a0

相邻两个数都会相加一次，唯一的区别是所有的数瞬移了一个位置

所以可以先进行 sum 次 L 操作，然后再判断需要移动几次到达 t 数组

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10;
bool flag = true;
int n, s[N], t[N], c[N], sum, tum, cnt, f = 1, ans;
inline void input() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &s[i]);
        sum += s[i];
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &t[i]);
        tum += t[i];
    }
    return;
}
inline void check() {
    for (int i = 1; i <= n; i++) {
        if (s[i] != t[i]) {
            flag = false;
            break;
        }
    }
    if ((sum == 0 && tum == 0) || flag) {
        printf("null\n");
        exit(0);
    }
    if ((sum == 0 && tum != 0)) {
        printf("No solution\n");
        exit(0);
    }
    return;
}
inline void solve() {
    s[n + 1] = s[1];
    for (;;) {
        ++cnt;
        if (sum * 2 > tum) {
            flag = true;
            break;
        } else if (sum * 2 == tum) {
            break;
        } else {
            sum *= 2;
        }
    }
    if (flag) {
        printf("No solution\n");
        exit(0);
    }
    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= n; j++) {
            c[j] = s[j] + s[j + 1];
        }
        c[n + 1] = c[1];
        for (int j = 1; j <= n + 1; j++) {
            s[j] = c[j];
        }
    }
    for (;;) {
        flag = false;
        for (int i = 1; i <= n; i++) {
            if (c[i] != t[i]) {
                flag = true;
                break;
            }
        }
        if (!flag) {
            break;
        }
        ans++;
        for (int i = n + 1; i >= 2; i--) {
            c[i] = s[i - 1];
        }
        c[1] = c[n + 1];
        for (int i = 1; i <= n + 1; i++) {
            s[i] = c[i];
        }
        if (ans > cnt) {
            printf("No solution\n");
            exit(0);
        }
    }
    return;
}
inline void output() {
    for (int i = 1; i <= ans; i++) {
        printf("L");
    }
    for (int i = 1; i <= cnt - ans; i++) {
        printf("R");
    }
    return;
}
signed main() {
    input();
    check();
    solve();
    output();
    return 0;
}

T3 回文构造机

题目描述

XTX 非常喜欢回文串，他认为回文会给自己带来好运,有一天他看到一个字符串突发奇想，如果将这个字符串所有字符打乱，然后每次操作只能挑选若干个能构成回文串的字符组合成一个字符串，XTX 最少需要操作几次才能取完所有字符。

思路解析

回文串的个数是由有多少种奇数个数的字符来决定的，每次可以将奇数次的字符放在中间，其他字符往两边放就可以了

代码实现

#include <bits/stdc++.h>
using namespace std;
string s;
int c, i, k, times, cnt[128];
int main() {
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        cnt[s[i]]++;
    }
    for (i = 0; i < 128; i++) {
        if (cnt[i] % 2 > 0) {
            times++;
        }
    }
    if (!times) {
        times = 1;
    }
    printf("%d\n", times);
    for (i = 127; i >= 0; i--)
        for (int j = 0; j < cnt[i] / 2; j++)
            printf("%c", i);
    for (k = 0; k < 128 && cnt[k] % 2 == 0; k++);
    if (k < 128)
        putchar(k++);
    for (i = 0; i < 128; i++)
        for (int j = 0; j < cnt[i] / 2; j++)
            putchar(i);
    for (; k < 128; k++)
        if (cnt[k] % 2 > 0) {
            putchar('\n');
            putchar(k);
        }
    return 0;
}

T4 LCS 构造机

题目描述

一个字符串的子序列可以通过删除这个字符串的若干个字符得到,两个字符串的最长公共子序列是这两个字符串所有的公共子序列中最长的一个，比如 lcs("101","111000")=2,f("101","11011")=3,f("00","1111")=0,给你三个正整数,ab,bc,ca,请找出三个字符串 A,B,C 满足以下条件

  • 每一个字符串只包含 0 或者 1

  • 每个字符串的长度是 1 到 1000

  • lcs(A, B) = ab, lcs(B, C) = bc, lcs(C, A) = ca

求满足条件的任意一组 A，B，C

思路解析

我们尝试着先去满足其中两个条件

比如 A 与 B 可以先选择 ab 个 0

A = 0000...000(ab 个 0)

B = 0000...000(ab 个 0)

B 与 C 可以选择 bc 个 1 作为 lcs

那么 B 就变成

B = 000...000111...111(ab 个 0，bc 个 1)

C = 1111.....11(bc 个 1)

接下来我们观察 A C 的 LCS 为 0，要使得 A C 的 LCS 为 ac，可以在 A 和 C 后面添加 ac 个 0 或者 ac 个 1，添加之后不能影响 AB BC 之间 的 LCS

假设现在添加了 ac 个 0

那么

A = 0000...000(ab 个 0)

B = 000...000111...111(ab 个 0，bc 个 1)

C = 1111.....11000...000(bc 个 1，ac 个 0)

要想不破坏之前的 lcs 情况，要满足 ac<=bc，ac<=ab,因此找到三个整数中最小的那个就可以构造出答案了

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<string> solve(int ab, int bc, int ca) {
    if (ca <= ab && ca <= bc) {
        vector<string> ret;
        ret.push_back(string(ab, '0'));
        ret.push_back(string(ab, '0') + string(bc, '1'));
        ret.push_back(string(bc, '1') + string(ca, '0'));
        return ret;
    }
    vector<string> ret = solve(bc, ca, ab);
    return {ret[2], ret[0], ret[1]};
}
void construct(int ab, int bc, int ca) {
    vector<string> r = solve(ab, bc, ca);
    cout << r[0] << endl
         << r[1] << endl
         << r[2] << endl;
}
signed main() {
    int ab, ac, bc;
    cin >> ab >> bc >> ac;
    construct(ab, bc, ac);
    return 0;
}

T5 奇数幻方

https://www.luogu.com.cn/problem/P2615

题目描述

N阶奇数幻方是指 $NN$的矩阵，里面包含 $1-NN$这 $N*N$ 个数字。

幻方的每一行每一列对角线的和都是相等的。

给出 $N$，输出一种 $N$ 阶幻方的方案。

思路解析

考虑幻方的通解情况求解

当 $N$ 为奇数时，我们可以通过下方法构建一个幻方：

首先将 $1$ 写在第一行的中间。

之后，按如下方式从小到大依次填写每个数 $K \ (K=2,3,\cdots,N \times N)$ ：

  1. 若 $(K-1)$ 在第一行但不在最后一列，则将 $K$ 填在最后一行， $(K-1)$ 所在列的右一列；
  2. 若 $(K-1)$ 在最后一列但不在第一行，则将 $K$ 填在第一列， $(K-1)$ 所在行的上一行；
  3. 若 $(K-1)$ 在第一行最后一列，则将 $K$ 填在 $(K-1)$ 的正下方；
  4. 若 $(K-1)$ 既不在第一行，也不在最后一列，如果 $(K-1)$ 的右上方还未填数，则将 $K$ 填在 $(K-1)$ 的右上方，否则将 $K$ 填在 $(K-1)$ 的正下方。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n, x, y, a[N][N];
signed main() {
    scanf("%d", &n);
    x = (n + 1) / 2, y = 1;
    a[x][y] = 1;
    for (int i = 2; i <= n * n; i++) {
        if (x != n && y == 1) {
            x++;
            y = n;
        } else if (x == n && y != 1) {
            x = 1;
            y--;
        } else if (x == n && y == 1) {
            y++;
        } else if (x != n && y != 1) {
            if (a[x + 1][y - 1]) {
                y++;
            } else {
                x++;
                y--;
            }
        }
        a[x][y] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", a[j][i]);
        }
        printf("\n");
    }
    return 0;
}

初赛

image-20240710190558001

image-20240710190608154

image-20240710190618550

image-20240710190629096

image-20240710190644319

image-20240710190658898

image-20240710190714596

image-20240710190725479

image-20240710190736954

image-20240710191047085

image-20240710191124195

image-20240710191224235

image-20240710191353993

image-20240710191433936

标签：cnt,ab,bc,int,Day2,ret,2024,++,蓝润
From： https://www.cnblogs.com/TangyixiaoQAQ/p/18292634

相关文章

  • 2024信友队蓝润暑期集训提高1班②Day5
    知识总结最小生成树最小生成树的定义：在一个无向连通图中，找出权值最小的生成树，使得生成树中任意两个顶点间都有且仅有一条路径。最小生成树的性质：无向连通图的最小生成树是唯一的。最小生成树的权值是图中所有边的权值的最小值。最小生成树的边数等于图的顶点数减一。最小......
  • 2024信友队蓝润暑期集训提高1班②Day4
    知识总结搜索算法剪枝剪枝是指在搜索树的构造过程中，对某些分支不必继续探索，从而减少搜索树的大小，提高搜索效率。启发式搜索启发式搜索是指根据某种启发式函数对搜索树进行排序，使得搜索树中优先扩展那些有可能产生最优解的分支。迭代加深搜索迭代加深搜索是指在搜索树的构造......
  • [2024] springboot Hadoop技术下的校园二手交易系统的设计与实现
    博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......
  • 2024最新版Python安装详细教程！一键安装，永久使用
    打开上面的Python官网地址，如下图所示，鼠标放入网页Downloads栏目，选择里面的windows操作系统。三、进入windows对应的页面，选择python版本(1)选择python的稳定发布版本StableReleases点击进入windows操作系统对应的页面，显示python安装版本，这些python安装版本适合windows操......
  • 2024-07-16 代码高亮插件highlight.js安装使用以及排错日志
    highlight.js—— 一个开源语法高亮库，用于在网页上对源代码进行语法高亮显示。安装npmihighlight.jsyarnaddhighlight.js引入//main.jsimport{createApp}from'vue';importAppfrom"./App.vue";importhljsfrom"highlight.js";//代码高亮插件import......
  • SMU Summer 2024 Contest Round 4
    SMUSummer2024ContestRound4MadeUp题意给你三个序列\(A，B，C\)，问你满足\(A_i=B_{C_j}\)的\((i,j)\)对有多少。思路由于\(1\leA_i,B_i,C_i\leN\)，所以可以统计\(Cnt[A_i]\)和\(Cnt[B_{C_i}]\)的个数，两者相乘累加即可。代码#include<bits/stdc++.h>using......
  • 2024-07-16 记录vue内置组件（ps：内容来自GPT）
    1. Transition和TransitionGroup用途：用于为单个元素或组件提供过渡效果。TransitionGroup则用于列表中的多个元素或组件的过渡效果。特点：Transition：只影响单个元素或组件，不会额外渲染DOM元素。TransitionGroup：渲染一个真实的DOM元素（默认为<span>），可以通过tag属性改变渲染......
  • 2024年7月JLPT日语N2真题试卷、答案解析、听力原文
    本套真题由【学日语的師夫】制作排版，分享下载日语等级考试N1N2N3N4N5专四专八历年真题PDF文件，树先生日语真题的平替内容，精讲版答案解析非常适合复习备考，听力原文真是还原听力场景，多听多练习。如果你正在备考12月份的考试，可以参考【学日语的師夫】排版的真题内容，刷真题是最有效......
  • 【2024】springboot校服订购系统设计与实现
     博主介绍：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围：SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......
  • android学习day2
    activity是应用程序的组件xml：描绘应用界面java：编写程序逻辑1.完整页面的创建过程：在layout目录下创建xml文件创建xml文件对应的java代码在AndroidManifest中注册页面配置 <?xmlversion="1.0"encoding="utf-8"?><manifestxmlns:android="http://schemas.android......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99