首页 > 其他分享 >刷题记录

刷题记录

时间:2024-07-27 19:50:30浏览次数:17  
标签:std GCD 记录 leq u128 字符串 ldots 刷题

给你两个正整数序列 \(a_1, \ldots, a_n\) 和 \(b_1, \ldots, b_m\) 。求每个 \(j = 1, \ldots, m\) 的最大公约数 \(a_1 + b_j, \ldots, a_n + b_j\) 。
输入

第一行包含两个整数 \(n\) 和 \(m\) ( \(1 \leq n, m \leq 2 \cdot 10^5\) )。

第二行包含 \(n\) 个整数 \(a_1, \ldots, a_n\) ( \(1 \leq a_i \leq 10^{18})\) .

第三行包含 \(m\) 个整数 \(b_1, \ldots, b_m\) ( \(1 \leq b_j \leq 10^{18})\) 。
输出

打印 \(m\) 个整数。其中的 \(j\) -th 应该等于 GCD \((a_1 + b_j, \ldots, a_n + b_j)\) .

题解

根据 GCD 的基本性质,我们知道 \(GCD(x, y) = GCD(x - y, y)\) 。多个参数也是如此: \(GCD(x, y, z, \ldots) = GCD(x - y, y, z, \ldots)\) .我们将其用于 \(GCD(a_1 + b_j, \ldots, a_n + b_j)\) 并从所有其他参数中减去 \(a_1 + b_j\) : \(GCD(a_1 + b_j, \ldots, a_n + b_j) = GCD(a_1 + b_j, a_2 - a_1, \ldots, a_n - a_1)\) .

如果我们找到 \(G = GCD(a_2 - a_1, \ldots, a_n - a_1)\) ,那么任何答案都可以找到 \(GCD(a_1 + b_j, G)\) 。需要注意的是,我们必须假设空集的 GCD 是 \(0\) ,而对于任意 \(x\) 都是 \(GCD(x, 0) = x\) ,因为 \(0\) 是唯一能被任何其他数整除的数。

AC code:



#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
inline i64 gcd(i64 x, i64 y)
{
    return y == 0 ?  x:  gcd(y, x % y);
}
int main()
{
    i64 n, m;
    std::ios::sync_with_stdio(0);

    std::cin.tie(0);
    std::cin >> n >> m;
    vector<i64> a(n + 1), b(m + 1), c(n + 1);
    for (int i = 1; i <= n; i++)
    {
        std::cin >> a[i];
    }
    for (int j = 1; j <= m; j++)
        std::cin >> b[j];
    i64 x = 0;
    for (int i = 1; i <= n; i++)
    {
        x = gcd(x, a[i]-a[1]);
    }
    for (int i = 1; i <= m; i++)
    {
        i64 t = gcd(x, a[1] + b[i]);
        std::cout << abs(t) << (i == m ? '\n' : ' ');
    }
    return 0;
}

  • 反思 gcd求最大公约数具有内部可随意减的性质,可以利用这个性质来完成转化,但是如果是随意减的话得出的gcd 可能是最大公约数的相反数!!!


宏定义的妙用

#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include<time.h>
#endif
using i64 = long long;
i64 M,D;
int main()
{
   #ifndef ONLINE_JUDGE
       time_t a=clock();
   #endif
   #ifdef ONLINE_JUDGE
   std::ios::sync_with_stdio(0);
   std::cin.tie(0);
   #endif
   std::cin>>M>>D;
   #ifndef ONLINE_JUDGE
       std::cout<<clock()-a<<"ms\n";
   #endif
   
   return 0;
}

LCM Challenge

题面翻译

找到3个不超过n的正整数(可以相同),使得它们的lcm(最小公倍数)最大。输出最大的lcm

题目描述

Some days ago, I learned the concept of LCM (least common multiple). I've played with it for several times and I want to make a big number with it.

But I also don't want to use many numbers, so I'll choose three positive integers (they don't have to be distinct) which are not greater than $ n $ . Can you help me to find the maximum possible least common multiple of these three integers?

输入格式

The first line contains an integer $ n $ ( $ 1<=n<=10^{6} $ ) — the $ n $ mentioned in the statement.

输出格式

Print a single integer — the maximum possible LCM of three not necessarily distinct positive integers that are not greater than $ n $ .

样例 #1

样例输入 #1

9

样例输出 #1

504

样例 #2

样例输入 #2

7

样例输出 #2

210

提示

The least common multiple of some positive integers is the least positive integer which is multiple for each of them.

The result may become very large, 32-bit integer won't be enough. So using 64-bit integers is recommended.

For the last example, we can chose numbers $ 7 $ , $ 6 $ , $ 5 $ and the LCM of them is $ 7·6·5=210 $ . It is the maximum value we can get.

  • 这题是一道思维题,结合了一部分基本数论知识,如果 \(n\) 为奇数则三个数互质,否则它们的最小公倍数的就是他们三个数的乘积除以最小公倍数 \(2\) ,所以这里如果n是偶数的话,如果\(gcd(n,n-3)==1\),选择\(n \cdot (n-1) \cdot (n-3)\) ,否则就选择\((n-1)\cdot(n-2)\cdot(n-3)\)

【模板】字符串哈希

题目描述

如题,给定 \(N\) 个字符串(第 \(i\) 个字符串长度为 \(M_i\),字符串内包含数字、大小写字母,大小写敏感),请求出 \(N\) 个字符串中共有多少个不同的字符串。

友情提醒:如果真的想好好练习哈希的话,请自觉。

输入格式

第一行包含一个整数 \(N\),为字符串的个数。

接下来 \(N\) 行每行包含一个字符串,为所提供的字符串。

输出格式

输出包含一行,包含一个整数,为不同的字符串个数。

样例 #1

样例输入 #1

5
abc
aaaa
abc
abcc
12345

样例输出 #1

4

提示

对于 \(30\%\) 的数据:\(N\leq 10\),\(M_i≈6\),\(Mmax\leq 15\)。

对于 \(70\%\) 的数据:\(N\leq 1000\),\(M_i≈100\),\(Mmax\leq 150\)。

对于 \(100\%\) 的数据:\(N\leq 10000\),\(M_i≈1000\),\(Mmax\leq 1500\)。

样例说明:

样例中第一个字符串(abc)和第三个字符串(abc)是一样的,所以所提供字符串的集合为{aaaa,abc,abcc,12345},故共计4个不同的字符串。

Tip:
感兴趣的话,你们可以先看一看以下三题:

BZOJ3097:http://www.lydsy.com/JudgeOnline/problem.php?id=3097

BZOJ3098:http://www.lydsy.com/JudgeOnline/problem.php?id=3098

BZOJ3099:http://www.lydsy.com/JudgeOnline/problem.php?id=3099

如果你仔细研究过了(或者至少仔细看过AC人数的话),我想你一定会明白字符串哈希的正确姿势的_

  • 字符串哈希,模数尽量选取大质数:
using u128 = unsigned long long;
u128 base = 131;
const u128 maxn = 100009;
const u128 N = 212370440130137957ll;
const u128 num = 233;
const u128 num2 = 100000007;

然后选取合适的哈希函数可以减少冲突的次数!!!

  • 同时在比较一个数组中相同元素个数的时候可以选择先根据\(hash\) 值排序,然后再通过判断附近的字符串是否与自己相同毕竟如果键值都不同也不会到一起去

AC code:

#include <bits/stdc++.h>
using namespace std;
using u128 = unsigned long long;
u128 base = 131;
const u128 maxn = 100009;
const u128 N = 212370440130137957ll;
const u128 num = 233;
const u128 num2 = 100000007;
u128 check[maxn];
u128 _hash(const char *s)
{
    int l = strlen(s);
    u128 ans = 0;
    for (int i = 0; i < l; i++)
    {
        ans = (ans * base + s[i]) % N;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0),cout.tie(0);
    string a;
    int n;
    std::cin >> n;
    int count=n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        const char *ans = a.c_str();
        u128 a2 = _hash(ans) % num%maxn;
        bool OK = false;
        u128 a1 =_hash(ans);
        while (check[a2])
        {
            if(check[a2]==a1)
            {
                OK=true;
                break;
            }
            a2 = (a2 + num2) % maxn;
        }
        if(OK)
        {
            count--;
        }
        else
        check[a2] += a1;
    }
    cout<<count<<endl;
    return 0;
}

标签:std,GCD,记录,leq,u128,字符串,ldots,刷题
From: https://www.cnblogs.com/cxjy0322/p/18327391

相关文章

  • 搭建极狐GitLab(基于Docker): 步骤整合汇总记录
    执行背景:(1)CentOS7(虚拟机ISO映像文件=CentOS-7-x86_64-DVD-2009.iso);(2)repo(yum)源已切换为国内源;命令汇总:1.安装Docker相关命令:#查看仓库源中可使用版本yumlistdocker-ce--showduplicates|sort-r#安装指定版本yuminstalldocker-ce-docker完整......
  • Linux捣鼓记录:debian12日志警告:firmware: failed to load iwl-debug-yoyo.bin (-2)
    问题现象:网卡为intelax200,系统为debian12蓝牙wifi使用功能一切正常,根据wiki检查了驱动也都已经安装,但每次开机后,查看cockpit日志会看到警告:firmware:failedtoloadiwl-debug-yoyo.bin(-2)......问题分析:检索网络得到初步结论:iwl-debug-yoyo.bin是一个intel网卡相关的de......
  • linux学习记录(docker)
    DockeDocker是基于Go语言实现的开源容器项目。它诞生于2013年年初,最初发起者是dotCloud公司。Docker自开源后受到业界广泛的关注与参与,目前已有80多个开源组件,逐渐形成了围绕Docker容器的完整的生态体系。dotCloud公司于2013年年底改名为DockerIoc,专注于Docker相关技术和产......
  • 菜鸟通关sqli-labs记录(1-54)
    目录基础环境所需知识Mysql系统数据库union联合查询通关过程通用思路1.第一关2.第二关2.1判断有无注入点2.2猜解列名数量(字段数量)2.3报错,判断回显点2.4信息收集2.5使用对应的SQL注入3.第三关4.第四关5.第五关6.第六关7.第七关8.第八关9.第九关10.第十关11.第十一关12.......
  • 记录--终于搞懂了!原来vue3中template使用ref无需.value是因为这个
    ......
  • Linux捣鼓记录:debian配置语言环境
    1.安装区域设置sudoaptupdatesudoaptinstalllocales2.配置语言环境sudodpkg-reconfigurelocales按空格多选,选中en_US.UTF-8和zh_CN.UTF-8这里多选择了英文,可以避免有些软件比如steamcmd报警告:WARNING:setlocale('en_US.UTF-8')failed,usinglocale:'C'.......
  • 算法力扣刷题记录 五十八【701.二叉搜索树中的插入操作】
    前言本文是二叉搜索树操作。二叉树篇继续。一、题目阅读给定二叉搜索树(BST)的根节点root和要插入树中的值value,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。注意,可能存在多种有效的插入方式,只......
  • 探索Memcached的守护神眼:日志记录与分析工具全攻略
    探索Memcached的守护神眼:日志记录与分析工具全攻略Memcached作为一种高性能的分布式内存缓存系统,其日志记录和分析对于维护系统稳定性、优化性能和排查问题至关重要。本文将详细介绍Memcached的日志记录机制以及如何使用各种工具和方法来分析这些日志。1.Memcached日志:系......
  • 从996到副业过百万,程序员的副业新思路:在FlowUs上记录成长,分享知识,开启收益之旅
    在当今这个信息爆炸的时代,程序员们拥有的不仅仅是编码的能力,更是将技术转化为商业价值的潜力。下面,我将详细阐述一种适合程序员的生意思路,以展示如何利用技术背景和零散时间,实现个人成长与财富积累。一、技术积累与个人成长程序员的职业生涯是一个不断学习和成长的过程。利......
  • Sqlserver 处理两条完全一样的记录
    想要删除重复记录(所有字段值相同),怎么处理? withcteAS(selectrow_number()over(partitionbywo_woid,wo_lxorderby(selectnull))asrn,*fromjserp.Wo_Modified_Record_Backupwherewo_woidlike'MO24%'andwo_woid>='MO240601'andlen(......