当前位置: 首页 > article >正文

2024.12.18 周三

2024.12.18 周三


Q1. 1000

You have an array of zeros a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an of length n n n.

You can perform two types of operations on it:

  1. Choose an index i i i such that 1 ≤ i ≤ n 1 \le i \le n 1in and a i = 0 a_i = 0 ai=0, and assign 1 1 1 to a i a_i ai;
  2. Choose a pair of indices l l l and r r r such that 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1lrn, a l = 1 a_l = 1 al=1, a r = 1 a_r = 1 ar=1, a l + … + a r ≥ ⌈ r − l + 1 2 ⌉ a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil al++ar2rl+1, and assign 1 1 1 to a i a_i ai for all l ≤ i ≤ r l \le i \le r lir.

What is the minimum number of operations of the first type needed to make all elements of the array equal to one?

Q2. 1000

Fedya is playing a new game called “The Legend of Link”, in which one of the character’s abilities is to combine two materials into one weapon. Each material has its own strength, which can be represented by a positive integer x x x. The strength of the resulting weapon is determined as the sum of the absolute differences of the digits in the decimal representation of the integers at each position.

Formally, let the first material have strength X = x 1 x 2 … x n ‾ X = \overline{x_{1}x_{2} \ldots x_{n}} X=x1x2xn, and the second material have strength Y = y 1 y 2 … y n ‾ Y = \overline{y_{1}y_{2} \ldots y_{n}} Y=y1y2yn. Then the strength of the weapon is calculated as ∣ x 1 − y 1 ∣ + ∣ x 2 − y 2 ∣ + … + ∣ x n − y n ∣ |x_{1} - y_{1}| + |x_{2} - y_{2}| + \ldots + |x_{n} - y_{n}| x1y1+x2y2++xnyn. If the integers have different lengths, then the shorter integer is padded with leading zeros.

Fedya has an unlimited supply of materials with all possible strengths from L L L to R R R, inclusive. Help him find the maximum possible strength of the weapon he can obtain.

An integer C = c 1 c 2 … c k ‾ C = \overline{c_{1}c_{2} \ldots c_{k}} C=c1c2ck is defined as an integer obtained by sequentially writing the digits c 1 , c 2 , … , c k c_1, c_2, \ldots, c_k c1,c2,,ck from left to right, i.e. 1 0 k − 1 ⋅ c 1 + 1 0 k − 2 ⋅ c 2 + … + c k 10^{k-1} \cdot c_1 + 10^{k-2} \cdot c_2 + \ldots + c_k 10k1c1+10k2c2++ck.

Q3. 1000

You are given two arrays a a a and b b b both of length n n n.

You will merge † ^\dagger these arrays forming another array c c c of length 2 ⋅ n 2 \cdot n 2n. You have to find the maximum length of a subarray consisting of equal values across all arrays c c c that could be obtained.

† ^\dagger A merge of two arrays results in an array c c c composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of c c c. We repeat this operation as long as we can (i.e. at least one array is nonempty).

Q4. 1000

LuoTianyi gave an array b b b of n ⋅ m n \cdot m nm integers. She asks you to construct a table a a a of size n × m n \times m n×m, filled with these n ⋅ m n \cdot m nm numbers, and each element of the array must be used exactly once. Also she asked you to maximize the following value:

∑ i = 1 n ∑ j = 1 m ( max ⁡ 1 ≤ x ≤ i , 1 ≤ y ≤ j a x , y − min ⁡ 1 ≤ x ≤ i , 1 ≤ y ≤ j a x , y ) \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left(\max\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}-\min\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}\right) i=1nj=1m(1xi,1yjmaxax,y1xi,1yjminax,y)

This means that we consider n ⋅ m n \cdot m nm subtables with the upper left corner in ( 1 , 1 ) (1,1) (1,1) and the bottom right corner in ( i , j ) (i, j) (i,j) ( 1 ≤ i ≤ n 1 \le i \le n 1in, 1 ≤ j ≤ m 1 \le j \le m 1jm), for each such subtable calculate the difference of the maximum and minimum elements in it, then sum up all these differences. You should maximize the resulting sum.

Help her find the maximal possible value, you don’t need to reconstruct the table itself.

------------------------独自思考分割线------------------------

  • 用时:20 20 40(-2) 14 总:1h34min 虽然都不难,但都不是一眼,需要证明/发现。

A1.

  1. 贪心构造,首先两端必须有,自左向右贪心找中间点,发现其坐标最大为 l a s t + 1 < < 1 last+1<<1 last+1<<1

A2.

  1. 模拟数位发现,在等长度情况下,以第一个不同点为分界线,前面每一位最大贡献就是 b [ i ] − ′ 0 ′ b[i]-'0' b[i]0 ,后面每一位最大贡献就是 9 9 9
  2. 本质就是考虑每一位数的取值范围,相同前缀下 a [ i ] a[i] a[i] 只能取 [ 0 , b [ i ] ] [0,b[i]] [0,b[i]] ,否则可取 [ 0 , 9 ] [0,9] [0,9]

A3.

  1. 将连续相同的数看成一块,根据构造方案,同一数组的相同数的2块不可能合并,不同数组则一定可以合并。
  2. 那答案显而易见,记录每个数所在块的最大值,答案就是每个数在两数组块的和的最大值。
  3. 写的时候直接枚举 a a a 数组去另一数组找另外的数wa2发,扒数据也没找到原因,果然wa了只有思路/代码有问题,这种情况就是没有考虑一个数没有在两个数组都存在的情况。

A4.

  1. 贪心构造,将极差最大的几个数放在左上角, ( 2 , 2 ) (2,2) (2,2) ( n , m ) (n,m) (n,m) 一定可以构造出 m a x − m i n max-min maxmin ,还剩下第一行和第一列。
  2. 考虑将 m a x 1 max1 max1 ( 1 , 1 ) (1,1) (1,1) m i n 1 / m i n 2 min1/min2 min1/min2 ( 2 , 1 ) / ( 1 , 2 ) (2,1)/(1,2) (2,1)/(1,2),同时最小值也可放左上角,维护最大值、次大值、最小值、次小值。同时考虑行列,设置函数进行4次计算即可。显然没有方案更优。

------------------------代码分割线------------------------

A1.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n;
    cin >> n;
    int res = 2;
    int st = 4;
    for (; st < n; st = st + 1 << 1)
        res++;
    if (n == 1)
        res = 1;
    cout << res << endl;
}

A2.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    string t(max(n, m) - min(n, m), '0');
    if (n < m)
        a = t + a;
    else
        b = t + b;
    n = max(n, m);
    int f = 0, res = 0;
    for (int i = 0; i < n; i++)
    {
        if (!f && a[i] == b[i])
            continue;
        res += f ? 9 : abs(b[i] - a[i]);
        if (a[i] - b[i])
            f = 1;
    }
    cout << res << endl;
}

A3.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    map<int, int> la, lb;
    auto get = [&](vector<int> &a, map<int, int> &la)
    {
        for (int i = 1; i <= n; i++)
        {
            int j = i;
            for (; j <= n && a[j] == a[i]; j++)
                ;
            la[a[i]] = max(la[a[i]], j - i);
            i = j - 1;
        }
    };
    get(a, la);
    get(b, lb);
    int res = 0;
    for (int i = 1; i <= n << 1; i++)
        res = max(res, la[i] + lb[i]);
    // for (auto [x, v] : la)
    //     res = max(res, v + lb[x]);
    cout << res << endl;
}

A4.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n * m);
    for (int &x : a)
        cin >> x;
    sort(a.begin(), a.end());
    int max1 = a.back(), max2 = a[a.size() - 2];
    int min1 = a[0], min2 = a[1];
    int res = (n - 1) * (m - 1) * (max1 - min1);
    auto cal = [&](int a, int b, int c)
    {
        return (n - 1) * abs(b - a) + (m - 1) * abs(c - a);
    };
    vector<int> t{cal(max1, min1, min2), cal(max1, min2, min1), cal(min1, max2, max1), cal(min1, max1, max2)};
    sort(t.rbegin(), t.rend());
    res += t[0];
    cout << res << endl;
}
原文地址:https://blog.csdn.net/2302_79354434/article/details/144576066
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/446808.html

相关文章:

  • @LocalBuilder装饰器: 维持组件父子关系
  • HarmonyOS中实现TabBar(相当于Android中的TabLayout+ViewPager)
  • Three.js教程015:全面讲解Three.js的UV与应用
  • 详细分析 Git 分支重命名与同步操作
  • Elasticsearch—索引库操作(增删查改)
  • 贪心算法(五)
  • 对 MYSQL 架构的了解
  • PySide6如何使用自定义委托实现在TableWidget填充颜色
  • CTF 伪造ip的http请求头(学习记录)
  • sql server 查询对象的修改时间
  • 1. 深度学习介绍
  • winpcap抓包原理
  • 记忆组合数据知识
  • 基于LSTM和SSUN模型的高光谱遥感分类实现
  • PCL点云库入门——PCL库中点云数据拓扑关系之K-D树(KDtree)
  • 1、学习大模型总纲
  • FreeRTOS的任务调度
  • 全志H618 Android12修改doucmentsui鼠标单击图片、文件夹选中区域
  • Suno Api V4模型无水印开发「高清音频WAV下载」 —— 「Suno Api系列」第6篇
  • netcore 集成Prometheus
  • 大数据-环保领域
  • 【1.排序】
  • 【Linux】-学习笔记10
  • 呼入机器人:24小时客户服务的未来趋势
  • 秒优科技-供应链管理系统 login/doAction SQL注入漏洞复现
  • Oracle筑基篇-通过一个事务流程筑基Oracle