草庐IT

第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）G Fibonacci

--OvO-- 2023-04-19 原文

牛客竞赛传送门：

　　本题链接：G-Fibonacci_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）(重现赛) (nowcoder.com)

　　比赛完整题单：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

 

通过率：702/961

 

题目大意：给定一个整数 n ,计算有多少对 (x,y) 满足 1≤x<y≤n，且fx​∗fy​ 的值为偶数

　　　　【说明】在样例1中，满足条件的数对有（1，3），（2，3），对应f1​∗f3​=1∗2=2，f2​∗f3​=1∗2=2

 

知识点：组合数学、数学推理

 

思路：
　　因为最后只需要找fx∗fy的值为偶数
　　所以，其实斐波那契只是外表的包装，我们只需要找到奇偶规律就行
　　1,1,2,3,5,8,13,21,34
　　1,1,0,1,1,0, 1, 1, 0(1表示奇数，0表示偶数)
　　不难发现，奇偶规律：周期为3的奇数奇数偶数
　　0*0=0，1*0=0，1*1=1
　　所以用所有的组合数 减去 所有奇数的组合数，就是答案
　　本题数字较大，注意要开long long
 
AC代码：
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 long long c(long long x){
 5     return x*(x-1)/2;
 6 }
 7 
 8 int main(){
 9     long long n ; cin>>n;
10     printf("%lld", c(n) - c(n-n/3));
11     return 0;
12 }
13 
14 /*
15 耗时：15min
16 */

 

亚洲区FibonaccispanclassvlistC++

有关第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）G Fibonacci的更多相关文章

  1. 阿里云国际版免费试用：如何注册以及注意事项 - 2

    作为新的阿里云用户，您可以50免费试用多种优惠，价值高达1,700美元（或8,500美元）。这将让您了解和体验阿里云平台上提供的一系列产品和服务。如果您以个人身份注册免费试用，您将获得价值1,700美元的优惠。但是，如果您是注册公司，您可以选择企业免费试用，提交基本信息通过企业实名注册验证，即可开始价值$8,500的免费试用！本教程介绍了如何设置您的帐户并使用您的免费试用版。​关于免费试用在我们开始此试用之前，您还必须遵守以下条款和条件才能访问您的免费试用：只有在一年内创建的账户才有资格获得阿里云免费试用。通过此免费试用优惠，用户可以免费试用免费试用活动页面上列出的每种产品一次。如果您有多个帐

  2. ruby-on-rails - 缺失区域；使用 :region option or export region name to ENV ['AWS_REGION' ] - 2

    我知道还有其他相同的问题，但他们没有解决我的问题。我不断收到错误:Aws::Errors::MissingRegionErrorinBooksController#create,缺少区域；使用:region选项或将区域名称导出到ENV['AWS_REGION']。但是，这是我的配置开发.rb:config.paperclip_defaults={storage::s3,s3_host_name:"s3-us-west-2.amazonaws.com",s3_credentials:{bucket:ENV['AWS_BUCKET'],access_key_id:ENV['AWS_ACCE

  3. ruby - 如何修复此错误 : kernel_require. rb :45:in `require' : cannot load such file? - 2

    我有以下文件结构:执行.rb图书馆我的类(class).rb在execute.rb我有下面的代码:#!/usr/bin/rubyrequire'lib/my_class'my_object=MyClass.newmy_object.some_method这是my_class.rb的代码:classMyClassdefsome_methodputs'OK'endend所以，我尝试运行execute.rb:rubyexecute.rb但是我收到这个错误:/home/vagrant/.rvm/rubies/ruby-2.0.0-p195/lib/ruby/site_ruby/2.0.0/ru

  4. ruby-on-rails - Rails 国际化 : %{record} is not being translated - 2

    我的rails.pt-BR.yml上有这个:br:errors:format:!'%{attribute}%{message}'messages:restrict_dependent_destroy:one:"Nãoépossívelexcluiroregistropoisexisteum%{record}dependente"many:"Nãoépossívelexcluiroregistropoisexistem%{record}dependentes"在我的模型中，我有这个:has_many:entities,dependent::restrict_with_error每当res

  5. ruby - 使用适用于 Ruby 的 AWS 开发工具包发布到 SNS 主题时指定区域 - 2

    我正在使用适用于Ruby的AWS开发工具包向Rails3应用程序发布消息和AWSSNS主题，如下所示:sns=AWS::SNS.newtopic=sns.topics['arn:aws:sns:eu-west-1:55555555555:my_topic']topic.publish("MESSAGE",:subject=>"SUBJECT")当我发布到“us-east-1”中的主题时，它按预期工作，但发布到“eu-west-1”区域中的主题时不起作用:AWS::SNS::Errors::InvalidParameter-Invalidparameter:TopicArn:使用AWSS

  6. ruby - 删除非字母数字字符而不删除 ruby 中的国际字符 - 2

    我想删除字符串中的非字母数字字符，但不删除国际字符，如重音字母。我也想保留空白。这是我目前所拥有的:the_string=the_string.gsub(/[^a-z0-9-]/i,'')虽然这确实会删除国际重音字母字符。我使用的解决方案:the_string=the_string.gsub(/[^\p{Alnum}\p{Space}-]/u,'')有效!谢谢。 最佳答案 您可以使用characterproperties这样做:the_string.gsub(/[^\p{Alnum}-]/,'')您可能还想使用\p{Space}来保

  7. Spring 国际化遇到的坑 No message found under code ‘xxx.xxxx‘ for locale ‘zh_CN‘ - 2

    Spring国际化遇到的坑org.springframework.context.NoSuchMessageException:Nomessagefoundundercode‘xxx.xxxx’forlocale‘zh_CN’背景以前做的项目客户群体只有国内的客户，从来没有考虑过语言文字的问题。这次有一个需求的返回内容，要根据客户设置的语言返回不同的语言。尝试使用了以后，结果发现怎么都不好使，一直报的一个错误如下：org.springframework.context.NoSuchMessageException:Nomessagefoundundercode'user.name'forloc

  8. ruby - 没有 Rails 的国际化？ - 2

    只是在没有Rails环境的情况下让I18n工作有困难:irb>require'i18n'=>trueirb>I18n.load_path=Dir['/usr/lib/ruby/gems/1.9.1/gems/rails-i18n-0.6.6/rails/locale/en.yml']=>["/usr/lib/ruby/gems/1.9.1/gems/rails-i18n-0.6.6/rails/locale/en.yml"]irb>I18n.load_path+=Dir['/usr/lib/ruby/gems/1.9.1/gems/rails-i18n-0.6.6/rails/loca

  9. ruby-on-rails - 如何在 Rails 中格式化这个国际电话号码？ - 2

    如果我有这样的国际电话号码:0541754301我怎样才能格式化它来产生这样的东西:0541-754-301 最佳答案 您可以使用ActionView::Helpers::NumberHelper中的number_to_phone(number,options={})方法但是，文档指出此方法会将数字格式化为美国电话号码(例如(555)123-9876)。相反，您可以使用thispatch它增加了提供数字分组的能力::groupings-Specifiesalternategroupings(mustspecify3-elementa

  10. ruby-on-rails - 国际化 : error message localization for particular model - 2

    我可以为每个验证本地化错误消息，但我如何为特定模型创建错误。普通语言环境看起来像这样:en:mongoid:errors:messages:taken:"Itisalreadytaken"但我想为user模型更改消息:en:mongoid:errors:messages:taken:"Itisalreadytaken"user:taken:"Itisalreadytaken.%{link_to'Rememberpassword',reset_password_path'}" 最佳答案 试试这个:en:mongoid:errors:m

随机推荐