草庐IT

第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）-L Bit Sequence

4VDP 2023-03-28 原文

题意

给你两个数l，m，大小为m的数组a，求[0,l]之间满足以下条件的数x的个数:
对于任何i输入[0,m-1],f(x+i)%2=a[i]；f(k)：代表k在二进制下1的个数
m的范围<=100，l<=1e18,a[i] = 0/1

思路

显然l的范围1e18,大概率就是数位DP了

  1. 观察到m是<=100的，因此x+m只会改变后7位置，对于前面的位数，则只会进1，使得前面连续的0变成1；
  2. 那么只要对前半部分进行数位DP,dp[pos][lim][cnt][d]代表位置在pos处，lim代表有无达到上限，cnt为1代表前面有奇数个1为0代表偶数个1，d代表从pos起向前有偶数还是奇数个1；
  3. 对于第七位以后的部分，直接暴力计算就好了，统计一下是否进位；

代码

#include<bits/stdc++.h>

using namespace std;
#define  int long long
int a[105];
vector<int> b;
int mp[80][2][2][2];
int mx;
int m, l;

int clc(int lim, int cnt, int h) {
   int up = (1 << 7) - 1;
   if (lim) up = mx;
   int all = 0;
   int cc = cnt;
   for (int i = 0; i <= up; i++) {
       bool flag = 1;
       for (int j = 0; j < m; j++) {
           cnt = cc;
           int res = i + j;
           int sum = __builtin_popcount(res);
           cnt += sum;
           cnt &= 1;
           if (res > ((1 << 7) - 1))cnt = (cnt + h) & 1;
           if (cnt != a[j])flag = 0;
       }
//        if (flag)cout << i << '\n';
       all += flag;
   }
   return all;
}

long long DFS(int pos, int lim, int cnt, int h) {
   if (mp[pos][lim][cnt][h] != -1)return mp[pos][lim][cnt][h];
   long long ans = 0;
   if (pos <= 6)return clc(lim, cnt, h);
   if (lim) {
       for (int i = 0; i <= b[pos]; i++) {
           bool ok = (i == b[pos]);
           int hh = 0;
           if (i == 0)hh = 0;
           else
               hh = (h + 1) & 1;
           ans += DFS(pos - 1, ok, (cnt + (i == 1)) & 1, hh);
       }
   } else {
       for (int i = 0; i <= 1; i++) {
//            bool ok = (i == b[pos]);
           int hh = 0;
           if (i == 0)hh = 0;
           else
               hh = (h + 1) & 1;
           ans += DFS(pos - 1, 0, (cnt + (i == 1)) & 1, hh);
       }
   }
   return mp[pos][lim][cnt][h] = ans;
}

void run() {

   cin >> m >> l;
   for (int i = 0; i < m; i++) {
       cin >> a[i];
   }
   b.clear();
   memset(mp, -1, sizeof mp);
   for (int i = l; i; i >>= 1) {
       b.emplace_back(i & 1);
   }
   mx = l & ((1 << 7) - 1);
   cout << DFS(b.size() - 1, 1, 0, 0) << '\n';


}

signed main() {

   int t;
   cin >> t;
   while (t--)
       run();
   return 0;
}
亚洲区Sequenceintcntlt算法与数据结构

有关第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）-L Bit Sequence的更多相关文章

  1. 计算机毕业设计ssm+vue基本微信小程序的小学生兴趣延时班预约小程序 - 2

    项目介绍随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱小学生兴趣延时班预约小程序的设计与开发被用户普遍使用,为方便用户能够可以随时进行小学生兴趣延时班预约小程序的设计与开发的数据信息管理,特开发了小程序的设计与开发的管理系统。小学生兴趣延时班预约小程序的设计与开发的开发利用现有的成熟技术参考,以源代码为模板,分析功能调整与小学生兴趣延时班预约小程序的设计与开发的实际需求相结合,讨论了小学生兴趣延时班预约小程序的设计与开发的使用。开发环境开发说明：前端使用微信微信小程序开发工具：后端使用ssm：VU

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

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

  3. 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

  4. 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

  5. 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

  6. 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

  7. 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}来保

  8. 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

  9. 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

  10. 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

随机推荐