首页 > 其他分享 >2025.1.12——1200

2025.1.12——1200

时间:2025-01-14 19:22:36浏览次数:1  
标签:integers le 2025.1 int 1200 mid 12 array define

2025.1.12——1200


Q1. 1200

You are given a sequence \(a\), consisting of \(n\) integers, where the \(i\)-th element of the sequence is equal to \(a_i\). You are also given two integers \(x\) and \(y\) (\(x \le y\)).

A pair of integers \((i, j)\) is considered interesting if the following conditions are met:

  • \(1 <= i < j <= n\);
  • if you simultaneously remove the elements at positions \(i\) and \(j\) from the sequence \(a\), the sum of the remaining elements is at least \(x\) and at most \(y\).

Your task is to determine the number of interesting pairs of integers for the given sequence \(a\).
Input

  • The first line contains three integers \(n, x, y\) (\(3 \le n \le 2 \cdot 10^5\), \(1 \le x \le y \le 2 \cdot 10^{14}\));
  • The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^{9}\)).

Q2. 1200

Vasya has two hobbies — adding permutations\(^{\dagger}\) to arrays and finding the most frequently occurring element. Recently, he found an array \(a\) and decided to find out the maximum number of elements equal to the same number in the array \(a\) that he can obtain after adding some permutation to the array \(a\).

More formally, Vasya must choose exactly one permutation \(p_1, p_2, p_3, \ldots, p_n\) of length \(n\), and then change the elements of the array \(a\) according to the rule \(a_i := a_i + p_i\). After that, Vasya counts how many times each number occurs in the array \(a\) and takes the maximum of these values. You need to determine the maximum value he can obtain.

\(^{\dagger}\)A permutation of length \(n\) is an array consisting of \(n\) distinct integers from \(1\) to \(n\) in arbitrary order. For example, \([2,3,1,5,4]\) is a permutation, but \([1,2,2]\) is not a permutation (\(2\) appears twice in the array), and \([1,3,4]\) is also not a permutation (\(n=3\) but there is \(4\) in the array).
Input
The first line of each test case contains a single integer \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — the length of the array \(a\).

The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — the elements of the array \(a\).


Q3. 1200

Jay managed to create a problem of difficulty \(x\) and decided to make it the second problem for Codeforces Round #921.

But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of \(n\) sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to \(x\).

The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.

Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.
Input

Each test case contains a single line of input containing two integers \(x\) (\(1\leq x\leq 10^8\)) and \(n\) (\(1\leq n\leq x\)).


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

  • 观察+数论


A1.

  1. 优化:排序后对于每个数二分找两侧边界。
  2. 有点细节

A2.

  1. 发现性质:最后选择的数上下界差小于 \(n\)。
  2. 排序后二分找到最多的数。

A3.

  1. 从答案 \(v\) 开始考虑,每个数必然是 \(v\) 的倍数,\(x\) 亦为 \(v\) 的倍数,则 \(v\) 必然为 \(x\) 的因子,对于每个因子若能够分为至少 \(n\) 份,则可以作为答案。

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

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, x, y;
    cin >> n >> x >> y;
    vector<int> a(n + 2);
    int sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];
    sort(a.begin() + 1, a.end() - 1, [](int &e1, int &e2)
         { return e1 > e2; });
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int s = sum - a[i];
        int l = 0, r = n + 1;
        while (r - l - 1)
        {
            int mid = l + r >> 1;
            if (s - a[mid] >= x)
                r = mid;
            else
                l = mid;
        }
        int d = r;
        l = 0, r = n + 1;
        while (r - l - 1)
        {
            int mid = l + r >> 1;
            if (s - a[mid] <= y)
                l = mid;
            else
                r = mid;
        }
        int u = l;
        // bug2(d, u);
        if (d <= u)
            res += u - d + 1 - (i >= d && i <= u);
    }
    cout << res / 2 << 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 _()
{
    int n;
    cin >> n;
    map<int, int> has;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        has[x] = 1;
    }
    vector<int> a(1, 0);
    for (auto [x, c] : has)
        a.push_back(x);
    int _n = has.size();
    int res = 1;
    for (int i = 1; i <= _n; i++)
    {
        int l = i, r = _n + 1;
        while (r - l - 1)
        {
            int mid = l + r >> 1;
            if (a[mid] - a[i] < n)
                l = mid;
            else
                r = mid;
            res = max(res, l - i + 1);
        }
    }
    // for (auto v : a)
    //     cout << v << ' ';
    // cout << endl;
    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 x, n;
    cin >> x >> n;
    int res = 1;
    vector<int> t;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
        {
            t.push_back(i);
            if (x / i - i)
                t.push_back(x / i);
        }
    t.push_back(x);
    for (auto v : t)
        if (x / v >= n)
            res = max(res, v);
    cout << res << endl;
}

标签:integers,le,2025.1,int,1200,mid,12,array,define
From: https://www.cnblogs.com/jkkk/p/18671427

相关文章

  • 2025.1.5——1200
    2025.1.5——1200Q1.1200Kevindiscoveredabinarystring$s$thatstartswith1intheriveratMoonlitRiverParkandhandeditovertoyou.Yourtaskistoselecttwonon-emptysubstrings$^{\text{∗}}$of$s$(whichcanbeoverlapped)tomaximizetheX......
  • 【Vim Masterclass 笔记12】第 7 章:Vim 核心操作之——文本对象与宏操作 + S07L28:Vim
    文章目录Section7:TextObjectsandMacrosS07L28TextObjects1文本对象的含义2操作文本对象的基本语法3操作光标所在的整个单词4删除光标所在的整个句子5操作光标所在的整个段落6删除光标所在的中括号内的文本7删除光标所在的小括号内的文本8操作尖括号内的文......
  • springboot投票管理系统-计算机设计毕业源码33128
    摘 要本文介绍了基于微信小程序和SpringBoot的投票管理系统的设计与实现。该系统结合了移动互联网技术和后端开发框架,旨在为各类组织或活动提供一个高效、便捷、用户友好的在线投票平台。系统采用微信小程序作为前端展示与交互界面,用户无需下载安装即可通过微信快速访......
  • VP Toyota Programming Contest 2024#12(AtCoder Beginner Contest 384)
    A-aaaadaa题意:给你一个字符串和两个字符\(c_1\),\(c_2\),把字符串里的所有不等于\(c_1\)的字符都换成\(c_2\)。模拟即可。点击查看代码voidsolve(){intn;chara,b;std::cin>>n>>a>>b;std::strings;std::cin>>s;for(auto&c:......
  • 高级java每日一道面试题-2025年01月12日-框架篇[Mybatis]-什么是MyBatis?
    如果有遗漏,评论区告诉我进行补充面试官:什么是MyBatis?我回答:在Java高级面试中,MyBatis是一个常见的讨论话题。以下是对MyBatis的详细解释:一、MyBatis简介MyBatis是一个开源的持久层框架,它提供了将SQL语句和Java对象进行映射的功能。MyBatis简化了JDBC的开发,减少了手......
  • 【事件分析】20250112-Usual 赎回机制调整事件
    背景信息https://docs.usual.money/Usual是一个聚合RWA的稳定币发行协议,经济模型中存在三种代币:USD0:Usual发行的稳定币。USD0++:USD0++是USD0的质押版本,为期4年,可获得USUAL代币奖励。USUAL:Usual协议的治理代币。事发缘由https://usual.money/blog/usual-s-next-......
  • abb涂装机械手维修齿轮泵电机3HNA012841-001
    ABB喷涂机器人齿轮泵电机维修步骤1、拆卸与检查环节严格按照拆卸指南,将ABB涂装机械手上的齿轮泵电机拆解下来。对拆卸下来的齿轮泵电机进行全面仔细检查,包括电机外壳、轴承、密封件等关键部件的磨损与损坏情况。 2、清洁与润滑步骤彻底清洗ABB喷涂机械臂齿轮泵电机3HNA012841-00......
  • oracle12.2.0.1交互快速部署脚本(shell)
    背景有些项目会用到oracle,以前大佬写的脚本不好用,拿来改一改,能用起来先,回头再适配更高版本的oracle。如果使用过程中有什么问题,还请批评指正。脚本#!/bin/bash####################Steup1Installoraclesoftware#####################script_name:oracle12.2.0.1_inst......
  • 1.12-1.13总结
    这两天读了本小说,余华的《活着》。讲的是徐福贵的人生,开头写福贵骑着牛,牛叫福贵,福贵还骗牛,说还有家珍,有庆,凤霞,二喜都在地里耕作,让牛不觉得自己孤单,我当时以为名字是随便取的。早年福贵是个地主少爷,他有一个老婆家珍,家珍是个千金,福贵什么浪荡事都干过,吃喝嫖赌,在赌博上,他觉得自己能......
  • 12.矩阵的秩及相关性质
    12.矩阵的秩及相关性质12.1k阶子式12.1.1k阶子式示例设存在以下矩阵:\[X_{mn}=\begin{bmatrix}x_{11}&x_{12}&x_{13}&...&x_{1n}\\x_{21}&x_{22}&x_{23}&...&x_{2n}\\x_{31}&x_{32}&x_{33}&...&x_{3n}\\&......