{"id":428,"date":"2009-03-28T20:02:36","date_gmt":"2009-03-28T12:02:36","guid":{"rendered":"http:\/\/sinyalee.com\/blog\/?p=428"},"modified":"2009-03-28T20:02:36","modified_gmt":"2009-03-28T12:02:36","slug":"apio-2007-%e5%8a%a8%e7%89%a9%e5%9b%ad%ef%bc%88zoo%ef%bc%89-%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a","status":"publish","type":"post","link":"https:\/\/sinyalee.com\/blog\/?p=428","title":{"rendered":"APIO 2007 \u52a8\u7269\u56ed\uff08Zoo\uff09 \u89e3\u9898\u62a5\u544a"},"content":{"rendered":"

\u9898\u76ee\u4e0e\u6570\u636e\u79fb\u6b65APIO\u5b98\u65b9\u7f51\u7ad9\uff1ahttp:\/\/www.apio.olympiad.org\/<\/a> <\/p>\n

\u5982\u679c\u6ca1\u6709\u505a\u8fc7Naptime\u8fd9\u9053\u9898\u76ee\uff0c\u90a3\u4e48\u8fd9\u9053\u9898\u8fd8\u662f\u6bd4\u8f83\u56f0\u96be\u7684\uff0c\u5f53\u5e74\u6211\u60f3\u4e86Naptime\u60f3\u4e86\u5f88\u4e45\u3002\u7136\u800c\u5982\u679c\u505a\u4e86Naptime\uff0c\u8fd9\u9053\u9898\u4fbf\u53d8\u5f97\u5f02\u5e38\u7b80\u5355\uff01 <\/p>\n

\u56e0\u4e3a\u6bcf\u4e2a\u5b69\u5b50\u53ef\u4ee5\u770b\u52305\u53ea\u52a8\u7269\uff0c\u6240\u4ee5\u5bf9\u4e8e\u6bcf\u4e2a\u4f4d\u7f6e\uff0c\u90fd\u4e0e\u524d\u97624\u4e2a\u4f4d\u7f6e\u6709\u5173\u3002\u6240\u4ee5DP\u7684\u65f6\u5019\u89814\u4e2a\u4f4d\u7f6e4\u4e2a\u4f4d\u7f6e\u5730\u63a8\u79fb\u3002\u7136\u540e\u53c8\u7531\u4e8e\u5b83\u662f\u4e00\u4e2a\u73af\uff0c\u9700\u8981\u6709\u4e00\u4e2a\u5148\u56fa\u5b9a\uff0c\u5728\u672c\u9898\u8981\u56fa\u5b9a4\u4e2a\u4f4d\u7f6e\u3002\u53c8\u56e0\u4e3a\u6bcf\u6b21DP\uff0c\u72b6\u6001\u8f6c\u79fb\u90fd\u8981\u679a\u4e3e\u8fd9\u4e2a\u4f4d\u7f6e\u8981\u4e0d\u8981\u53d6\uff0c\u53c8\u8981\u8003\u8651\u8fd9\u4e2a\u4f4d\u7f6e\u7684\u6240\u6709\u5c0f\u5b69\u5b50\uff0c\u6240\u4ee5\u65f6\u95f4\u590d\u6742\u5ea6\u662fO( 2^9 * (c+n) )\uff0c\u8fd8\u662f\u53ef\u4ee5\u627f\u53d7\u7684\u3002 <\/p>\n

\u8fd9\u9053\u9898\u6211\u7528\u4e86\u4f4d\u8fd0\u7b97\u4f18\u5316\uff0c\u628a\u6bcf\u4e2a\u5c0f\u5b69\u5b50\u559c\u6b22\u7684\u548c\u4e0d\u559c\u6b22\u7684\u52a8\u7269\u538b\u6210\u4e00\u4e2a\u4e8c\u8fdb\u5236\u6570\u5b57\u3002\u7136\u540e\u5bf9\u6bcf\u4e2a\u4f4d\u7f6e\u5c31\u679a\u4e3e\u4ece\u8fd9\u4e2a\u4f4d\u7f6e\u5f00\u59cb\u76845\u4e2a\u7b3c\u5b50\u52a8\u7269\u6709\u6ca1\u6709\u88ab\u548c\u8c10\u6389\uff0c\u75285\u4f4d\u6570\u8868\u793a\uff1afor ( int i=0 ; i < 1<<5 ; i++) {\u2026} \u3002\u7136\u540e\u8fd9\u4e2a\u4f4d\u7f6e\u7684k>>1\u7684\u72b6\u6001\u53ef\u4ee5\u7531\u540e\u97621\u4e2a\u4f4d\u7f6e\u7684k &0xf \u6765\u66f4\u65b0\u3002 <\/p>\n

\u7a0b\u5e8f\u5982\u4e0b\uff1a <\/p>\n

\/*
ID: sinya1
PROG: zoo
LANG: C++
*\/ <\/p>\n

#include <iostream> <\/p>\n

#define maxn 10000
#define maxc 50000 <\/p>\n

using namespace std; <\/p>\n

int n,c,i,j,k,l,f,x,y,sol,temp,temp1;
int e[maxc],fear[maxc],love[maxc];
int be[maxn+1];
int dp[2][16]; <\/p>\n

void init() {
  scanf(“%d%d”,&n,&c);
  for (i=0;i<c;i++) {
    scanf(“%d”,&e[i]);
    fear[i]=love[i]=0;
    scanf(“%d%d”,&f,&l);
    for (j=0;j<f;j++) {
      scanf(“%d”,&k);
      k=k-e[i];
      if (k<0) k=k+n;
      k=4-k;
      fear[i]|=(1 << k);
    }
    for (j=0;j<l;j++) {
      scanf(“%d”,&k);     
      k=k-e[i];
      if (k<0) k=k+n;
      k=4-k;
      love[i]|=(1 << k);
    }
  }
  be[0]=0;
  for (i=1;i<=n;i++) {
    be[i]=be[i-1];
    while (be[i]<=c && e[be[i]]==i) be[i]++;
  }
} <\/p>\n

void work() {
  sol=0;
  for (i=0;i<1<<4;i++) {
    memset(dp[0],128,sizeof(dp[0]));
    dp[0][i]=0;
    for (x=0,y=1,j=n;j>4;j–,swap(x,y)) {
      memset(dp[y],128,sizeof(dp[y]));
      for (k=0;k<1<<5;k++) {
        temp1=dp[x][k&0xf];
        for (l=be[j-1];l<be[j];l++)
          if ((love[l] & k)>0 || ((fear[l])&(k^fear[l]))>0)
            temp1++;
        dp[y][k>>1]>?=temp1;
      }
    }
    for (j=4;j>=1;j–,swap(x,y)) {
      memset(dp[y],128,sizeof(dp[y]));
      temp=(i>>(4-j))&1;
      for (f=0;f<1<<4;f++) {
        k=f|(temp<<4);
        temp1=dp[x][k&0xf];
        for (l=be[j-1];l<be[j];l++)
          if ((love[l] & k)>0 || ((fear[l])&(k^fear[l]))>0)
            temp1++;
        dp[y][k>>1]>?=temp1;
      }
    }
    for (j=0;j<1<<4;j++) sol>?=dp[x][j];
  }
  printf(“%d\\n”,sol);
} <\/p>\n

int main() {
  freopen(“zoo.in”,”r”,stdin);
  freopen(“zoo.out”,”w”,stdout);
  init();
  work();
  return 0;
}<\/p>\n","protected":false},"excerpt":{"rendered":"

\u9898\u76ee\u4e0e\u6570\u636e\u79fb\u6b65APIO\u5b98\u65b9\u7f51\u7ad9\uff1ahttp:\/\/www.apio.olympiad.org\/ \u5982\u679c\u6ca1\u6709\u505a\u8fc7Nap […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13],"tags":[23,131,344],"class_list":["post-428","post","type-post","status-publish","format-standard","hentry","category-13","tag-apio","tag-131","tag-344"],"_links":{"self":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/428","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=428"}],"version-history":[{"count":1,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/428\/revisions"}],"predecessor-version":[{"id":824,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/428\/revisions\/824"}],"wp:attachment":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=428"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=428"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}