首页 > 编程语言 >[题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Cute Rabbit

[题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Cute Rabbit

时间:2024-04-17 16:55:31浏览次数:23  
标签:竞赛 gcd int 题解 兔子 程序设计 涂为

题目描述

有n只兔子,每个兔子上有一个数ai。要将所有兔子分为白色和绿色两堆,使所有白色兔子的数对绿色兔子取余结果相等。求绿色兔子的最大数量。

题解

考虑一种情况:把所有除了最小值的数都涂为绿色,此时显然满足条件。
对于一般情况:可以枚举白绿兔子的分割线x。

  • 对于小于x,试将其全部涂为白色,计算x前缀的最小公倍数,记为lcm(x-1) 。
  • 对于大于等于x,试将其全部涂为绿色,计算其后缀差分的最大公因数。记为gcd(x)。
    此时可知满足涂色规则的充要条件即:gcd(x)%lcm(x-1)==0。

代码

#include<bits/stdc++.h>
#define  int  long long
using namespace std;
const int N=1e5+7;
int a[N],q[N],p[N];
int gcd(int a,int b){
    return b!=0?gcd(b,a%b):a;
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
signed main(){
    bool flag=false;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int minn=a[1],cnt=0,ans, tot = 2;
    for(int i=1;i<=n;i++)if(a[i]==minn)cnt++;
    q[1]=a[1];
    if (cnt == 1 || cnt == n) {
        cout << n - 1;
        return 0;
    } 
    ans = n - cnt;
    for(int i=2;i<=n;i++) {
        q[i]=lcm(q[i-1],a[i]);
        if (q[i] <= a[n]) tot++;
    }
    for(int i=n-1;i>=1;i--)p[i]=gcd(p[i+1],a[i+1]-a[i]);
    p[n]=a[n];
    for(int i=1; i <= n - 1 && i <= tot - 1; i++){
        if(p[i+1]%q[i]==0){
            ans=max(ans, i);
            flag=true;
        }
    }
    cout << ans << "\n";
} 

标签:竞赛,gcd,int,题解,兔子,程序设计,涂为
From: https://www.cnblogs.com/zwzww/p/18141174

相关文章

  • 前端项目安装node-sass依赖问题解决
    前端项目安装依赖node-sass问题解决记录:(项目中node版本14.16.0node-sass版本4.14.1)问题1:pnpnrunall:install后报错MSBUILD:errorMSB3428:解决方法:需要安装npminstall--globalwindows-build-tools1.1、npm全局安装windows-build-tools1.1安装过程中可能会出现......
  • [题解] [CCPC陕西省赛2022 H题] Cute Rabbit
    [CCPC陕西省赛2022H题]CuteRabbit题目描述有\(n\)只白色的兔子,把其中\(m\)只染成绿色。每只兔子上有一个数\(a_i\),如果所有白色兔子上的数对所有绿色兔子上的数两两取余的值均相同,则该种染色方式合法,求能够使染色合法的最大的\(m\)。输入格式第一行有一个整数\(n(......
  • uoj32 跳蚤公路题解
    题目链接点击打开链接题目解法首先问题等价于有一个负环可以到\(v\)假设环边的\(w\)之和为\(b\),\(c\)之和为\(k\),则这个环的长度就为\(kx+b\)如果是负环,需要满足\(kx+b<0\)钦定负环上的一个点\(st\),令\(f_{i,j}\)表示从\(st\)到\(i\)的路径中,\(\sumc=j\)的......
  • 【问题解决】Fatal error "unsafe repository ('git目录名' is owned by someone else
    问题复现近期升级了Gitv2.37.0,发现在gitbash进入git目录执行git命令时出现错误:Fatalerror"unsaferepository('git目录名'isownedbysomeoneelse)",无法使用git做一些操作。问题解决两个方法:降级到v2.35.2之前,或者,gitconfig--global--addsafe.directory仓库目录......
  • 再次进入虚拟机找不到共享文件夹的内容了---问题解决
    问题描述在重新开启虚拟机之后,发现原来的路径上没有上次共享文件夹的内容了,查看虚拟机设置,发现共享文件夹还在启用,也不是这里的问题;问题解决因为我们是用链接的方式实现的本地和虚拟机文件共享,所以,每次重新进入虚拟机时,就需要重新链接一下,用下面这行代码就能够再次看到共享文件......
  • 2024/4/15考试题解
    目录成绩报告A.排座位题目内容思路代码B.梦中的学校题目内容思路代码C.激突冲击题目内容思路代码D.奖学金题目内容思路代码成绩报告T1说是快排,其实跟快排没有任何关系,就是单纯考了个语法。T2不会推式子,但是输出1有20分。T3不会差分约束(打拓扑排序导致的),同理输出-1得18分。T4fre......
  • P6864 [RC-03] 记忆 题解(评分:8.1)(2023.12.13)
    前言这下又不是官解了吧?模拟赛题,在一个月后又出现在了数据结构讲稿上,令人忍俊不禁。Solution官方解法是用线段树加矩阵,不过赛时的我显然没这么聪明,是想不到的。赛时我就只知道先发掘一些答案的性质。一、一些性质首先,发现这个撤销操作比较棘手,考虑没有撤销操作的情况下,每一......
  • P2178 [NOI2015] 品酒大会 题解(评分:8.0)(2024.2.23)
    前言"I'mfree."做法与题解区都不同,虽然麻烦,但是毕竟复杂度是对的,而且想法很自然,还是写一写吧!Solution题意:给定长为\(n\)的字符串\(s\)和长为\(n\)的数组\(A\),对于每个\(r\),求满足\(\text{LCP}(\text{Suffix}(x),\text{Suffix}(y))\ger,x<y\)的数对\((x,y)\)数......
  • [error] Error: Fail to open IDE 问题解决
    在使用HBuilder编译器,控制台报[error]Error:FailtoopenIDE 错误如下所示: 有两个原因所致:  其一:微信小程序AppID错误  解决方案:点击项目目录 manifest.json,打开项目配置,将AppID填到配置界面的微信小程序AppID输入框中,重新运行即可,如下所示: 其二:小程序打......
  • 【题解】P4307 [JSOI2009] 球队收益 / 球队预算
    P4307[JSOI2009]球队收益/球队预算题解题目传送门题意简述一共有\(n\)个球队比赛,输了赢了都会有相应的支出,现在让你安排\(m\)场比赛的输赢,是总支出最少。思路首先看到最小支出,状态不好定义,直接费用流,启动!。后文如果没有特殊说明,边的费用均为\(0\)。考虑建图,其......