第七周 10.11-10.17

10.11

ZOJ Monthly。

ZOJ 3903 Ant

推公式。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 const LL mod=1e9+7;
 6 const LL re=83333334LL;
 7 LL n[4];
 8 
 9 int main(void)
10 {
11     int T; cin>>T;
12     while(T--)
13     {
14         scanf("%lld",&n[0]);
15         n[0]%=mod;
16         for(int i=1;i<4;i++) n[i]=(n[i-1]*n[0])%mod;
17         LL ans=13*n[3]%mod+26*n[2]%mod+17*n[1]%mod+4*n[0]%mod;
18         ans=(ans%mod*re%mod+mod)%mod;
19         printf("%lld
",ans);
20     }
21     return 0;
22 }

Aguin

ZOJ 3905 Cake

按b排序后。考虑按b降序每次加上一对物品。

这两件物品中第二件是当前所有物品中b最小的。必取。

第一件物品如果和前面的物品放在一组。就必取。

如果和第二件物品放一起。就不取。

所以比较第一件物品与前面已取物品中的最小值。取a大的一件即可。

已取物品的最小值用优先队列维护。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 using namespace std;
 6 priority_queue<int> q;
 7 
 8 struct node
 9 {
10     int a,b;
11 }p[1000];
12 
13 bool cmp(node x,node y)
14 {
15     return x.b>y.b;
16 }
17 
18 int main(void)
19 {
20     int T; cin>>T;
21     while(T--)
22     {
23         int n; scanf("%d",&n);
24         for(int i=0;i<n;i++) scanf("%d%d",&p[i].a,&p[i].b);
25         sort(p,p+n,cmp);
26         while(!q.empty()) q.pop();
27         int ans=p[1].a;
28         q.push(-p[1].a);
29         for(int i=2;i<n;i+=2)
30         {
31             int cur=-q.top();
32             if(p[i].a>cur)
33             {
34                 q.pop();
35                 q.push(-p[i].a);
36                 ans+=p[i].a-cur;
37             }
38             ans+=p[i+1].a;
39             q.push(-p[i+1].a);
40         }
41         printf("%d
",ans);
42     }
43     return 0;
44 }

Aguin

ZOJ 3914 Semantic Version

题意：给两个版本号。判断第一个是否小于第二个。

比较版本号的规则如下。

一。X.Y.Z小的在先。

二。相同X.Y.Z的预发布版本(即-blabla形式)先于非预发布版本。

三。同为预发布版本。比较后面用 . 隔开的每一段直至出现不相同为止。

　　比较每一段时有三种情况 1.纯数字 2.字符 3.没有了

　　i)没有先于纯数字先于字符

　　ii)纯数字数值小的在先

　　iii)字符字典序小的在先

写个结构体。重载<比较即可。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 struct p
  8 {
  9     bool num;
 10     int n;
 11     char s[30];
 12 };
 13 
 14 struct node
 15 {
 16     int x,y,z;
 17     int sz;
 18     p suf[30];
 19     node(){x=y=z=sz=0;memset(suf,0,sizeof(suf));}
 20     friend bool operator < (node A,node B)
 21     {
 22         if(A.x!=B.x) return A.x<B.x;
 23         if(A.y!=B.y) return A.y<B.y;
 24         if(A.z!=B.z) return A.z<B.z;
 25         if(A.sz==0||B.sz==0) return A.sz>B.sz;
 26         int sz=max(A.sz,B.sz);
 27         for(int i=0;i<=sz;i++)
 28         {
 29             if(i==A.sz||i==B.sz) return A.sz<B.sz;
 30             if(A.suf[i].num)
 31             {
 32                 if(B.suf[i].num&&A.suf[i].n!=B.suf[i].n) return A.suf[i].n<B.suf[i].n;
 33                 if(!B.suf[i].num) return true;
 34             }
 35             else
 36             {
 37                 if(B.suf[i].num) return false;
 38                 else
 39                 {
 40                     int tmp=strcmp(A.suf[i].s,B.suf[i].s);
 41                     if(tmp) return tmp<0;
 42                 }
 43             }
 44         }
 45     }
 46 };
 47 
 48 bool is_num(char c)
 49 {
 50     return c>='0'&&c<='9';
 51 }
 52 
 53 void get(node & A,char * a)
 54 {
 55     int pos=1,cnt=0,ok=1;
 56     for(int i=0;i<strlen(a);i++)
 57     {
 58         if(pos<4)
 59         {
 60             if(a[i]=='-') {pos++;continue;}
 61             if(a[i]=='.') pos++;
 62             else
 63             {
 64                 if(pos==1) A.x=A.x*10+a[i]-'0';
 65                 else if(pos==2) A.y=A.y*10+a[i]-'0';
 66                 else A.z=A.z*10+a[i]-'0';
 67             }
 68         }
 69         else
 70         {
 71             if(i==strlen(a)-1||a[i]=='.')
 72             {
 73                 if(i==strlen(a)-1)
 74                 {
 75                     A.suf[A.sz].s[cnt++]=a[i];
 76                     if(!is_num(a[i])) ok=0;
 77                 }
 78                 A.suf[A.sz].s[cnt]=0;
 79                 if(ok)
 80                 {
 81                     for(int j=0;j<strlen(A.suf[A.sz].s);j++)
 82                         A.suf[A.sz].n=A.suf[A.sz].n*10+A.suf[A.sz].s[j]-'0';
 83                     A.suf[A.sz].num=1;
 84                 }
 85                 cnt=0; ok=1;
 86                 A.sz++;
 87             }
 88             else
 89             {
 90                 A.suf[A.sz].s[cnt++]=a[i];
 91                 if(!is_num(a[i])) ok=0;
 92             }
 93         }
 94     }
 95 }
 96 
 97 int main(void)
 98 {
 99     char a[50],b[50];
100     while(~scanf("%s%s",a,b))
101     {
102         node A,B;
103         get(A,a);
104         get(B,b);
105         if(A<B) puts("Wow! Such feature! Very smart! I'm excited!");
106         else puts("I'm angry!");
107     }
108     return 0;
109 }

Aguin

10.12

什么都没干。

10.13

CF 585B Phillip and Trains

dfs写矬T了。改BFS标记下过。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 typedef pair<int,int> pii;
 8 bool ok,vis[4][200];
 9 char G[4][200];
10 int n,m,k;
11 queue<pii> q;
12 
13 bool f(int x,int y)
14 {
15     return y>=m||G[x][y]=='.';
16 }
17 
18 int main(void)
19 {
20     int T; cin>>T;
21     while(T--)
22     {
23         scanf("%d%d",&n,&k);
24         int s;
25         memset(G,0,sizeof(G));
26         memset(vis,0,sizeof(vis));
27         for(int i=1;i<=3;i++)
28         {
29             scanf("%s",G[i]);
30             if(G[i][0]=='s') s=i;
31         }
32         m=strlen(G[1]); ok=0;
33         while(!q.empty()) q.pop();
34         q.push(pii(s,0));
35         while(!q.empty())
36         {
37             pii tem=q.front(); q.pop();
38             int x=tem.first,y=tem.second+1;
39             if(y>=m) {ok=1;break;}
40             if(G[x][y]!='.') continue;
41             if(x>1&&f(x-1,y)&&f(x-1,y+1)&&f(x-1,y+2)&&!vis[x-1][y+2])
42                 q.push(pii(x-1,y+2)),vis[x-1][y+2]=1;
43             if(x<3&&f(x+1,y)&&f(x+1,y+1)&&f(x+1,y+2)&&!vis[x+1][y+2])
44                 q.push(pii(x+1,y+2)),vis[x+1][y+2]=1;
45             if(f(x,y+1)&&f(x,y+2)&&!vis[x][y+2])
46                 q.push(pii(x,y+2)),vis[x][y+2]=1;
47         }
48         puts(ok?"YES":"NO");
49     }
50     return 0;
51 }

Aguin

10.14

HDU 2222 Keywords Search

AC自动机。终于有板了？

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 const int maxnode=5e5+10,sigma_size=26;
  8 const int maxn=1e6+10;
  9 char a[maxn];
 10 
 11 struct Ac_auto
 12 {
 13     int Next[maxnode][sigma_size];
 14     int val[maxnode];
 15     int fail[maxnode];
 16     int sz;
 17     Ac_auto(){sz=1;memset(Next[0],0,sizeof(Next[0]));}
 18     void init(){sz=1;memset(Next[0],0,sizeof(Next[0]));}
 19     int idx(char c) {return c-'a';}
 20 
 21     void insert(char *s)
 22     {
 23         int u=0,n=strlen(s);
 24         for(int i=0;i<n;i++)
 25         {
 26             int c=idx(s[i]);
 27             if(!Next[u][c])
 28             {
 29                 memset(Next[sz],0,sizeof(Next[sz]));
 30                 val[sz]=0;
 31                 Next[u][c]=sz++;
 32             }
 33             u=Next[u][c];
 34         }
 35         val[u]++;
 36     }
 37 
 38     void build()
 39     {
 40         queue<int> q;
 41         fail[0]=0;
 42         for(int i=0;i<sigma_size;i++) if(Next[0][i])
 43         {
 44             fail[Next[0][i]]=0;
 45             q.push(Next[0][i]);
 46         }
 47         while(!q.empty())
 48         {
 49             int pos=q.front(); q.pop();
 50             for(int i=0;i<sigma_size;i++)
 51             {
 52                 if(!Next[pos][i]) Next[pos][i]=Next[fail[pos]][i];
 53                 else
 54                 {
 55                     fail[Next[pos][i]]=Next[fail[pos]][i];
 56                     q.push(Next[pos][i]);
 57                 }
 58             }
 59         }
 60     }
 61 
 62     int query(char * s)
 63     {
 64         int len=strlen(s);
 65         int pos=0,ret=0;
 66         for(int i=0;i<len;i++)
 67         {
 68             pos=Next[pos][idx(s[i])];
 69             int tmp=pos;
 70             while(tmp)
 71             {
 72                 ret+=val[tmp];
 73                 val[tmp]=0;
 74                 tmp=fail[tmp];
 75             }
 76         }
 77         return ret;
 78     }
 79 
 80 }ACA;
 81 
 82 int main(void)
 83 {
 84     int T; cin>>T;
 85     while(T--)
 86     {
 87         ACA.init();
 88         int N; scanf("%d",&N);
 89         for(int i=0;i<N;i++)
 90         {
 91             char m[100];
 92             scanf("%s",m);
 93             ACA.insert(m);
 94         }
 95         ACA.build();
 96         scanf("%s",a);
 97         printf("%d
",ACA.query(a));
 98     }
 99     return 0;
100 }

Aguin

HDU 2896 病毒侵袭

板子应该能用？

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 const int maxnode=1e5+10,sigma_size=128;
  9 const int maxn=1e4+10;
 10 vector<int> ans;
 11 char a[maxn];
 12 
 13 struct Ac_auto
 14 {
 15     int Next[maxnode][sigma_size];
 16     int val[maxnode];
 17     int fail[maxnode];
 18     int sz;
 19     Ac_auto(){sz=1;memset(Next[0],0,sizeof(Next[0]));}
 20     void init(){sz=1;memset(Next[0],0,sizeof(Next[0]));}
 21     int idx(char c) {return c;}
 22 
 23     void insert(char *s,int v)
 24     {
 25         int u=0,n=strlen(s);
 26         for(int i=0;i<n;i++)
 27         {
 28             int c=idx(s[i]);
 29             if(!Next[u][c])
 30             {
 31                 memset(Next[sz],0,sizeof(Next[sz]));
 32                 val[sz]=0;
 33                 Next[u][c]=sz++;
 34             }
 35             u=Next[u][c];
 36         }
 37         val[u]=v;
 38     }
 39 
 40     void build()
 41     {
 42         queue<int> q;
 43         fail[0]=0;
 44         for(int i=0;i<sigma_size;i++) if(Next[0][i])
 45         {
 46             fail[Next[0][i]]=0;
 47             q.push(Next[0][i]);
 48         }
 49         while(!q.empty())
 50         {
 51             int pos=q.front(); q.pop();
 52             for(int i=0;i<sigma_size;i++)
 53             {
 54                 if(!Next[pos][i]) Next[pos][i]=Next[fail[pos]][i];
 55                 else
 56                 {
 57                     fail[Next[pos][i]]=Next[fail[pos]][i];
 58                     q.push(Next[pos][i]);
 59                 }
 60             }
 61         }
 62     }
 63 
 64     void query(char * s)
 65     {
 66         int len=strlen(s);
 67         int pos=0;
 68         ans.clear();
 69         for(int i=0;i<len;i++)
 70         {
 71             pos=Next[pos][idx(s[i])];
 72             int tmp=pos;
 73             while(tmp)
 74             {
 75                 if(val[tmp]) ans.push_back(val[tmp]);
 76                 tmp=fail[tmp];
 77             }
 78         }
 79         sort(ans.begin(),ans.end());
 80     }
 81 
 82 }ACA;
 83 
 84 int main(void)
 85 {
 86     int N;
 87     while(~scanf("%d",&N))
 88     {
 89         ACA.init();
 90         for(int i=1;i<=N;i++)
 91         {
 92             scanf("%s",a);
 93             ACA.insert(a,i);
 94         }
 95         ACA.build();
 96         int M; scanf("%d",&M);
 97         int tot=0;
 98         for(int i=1;i<=M;i++)
 99         {
100             scanf("%s",a);
101             ACA.query(a);
102             if(ans.size())
103             {
104                 printf("web %d:",i);
105                 for(int j=0;j<ans.size();j++) printf(" %d",ans[j]);
106                 puts("");
107                 tot++;
108             }
109         }
110         printf("total: %d
",tot);
111     }
112     return 0;
113 }

Aguin

HDU 3065 病毒侵袭持续中

应该没有问题吧。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 const int maxnode=1e5+10,sigma_size=128;
 8 const int maxn=2e6+10;
 9 char a[1001][100],b[maxn];
10 int cnt[1001];
11 
12 struct Ac_auto
13 {
14     int Next[maxnode][sigma_size];
15     int val[maxnode];
16     int fail[maxnode];
17     int sz;
18     Ac_auto(){sz=1;memset(Next[0],0,sizeof(Next[0]));}
19     void init(){sz=1;memset(Next[0],0,sizeof(Next[0]));}
20     int idx(char c) {return c;}
21 
22     void insert(char *s,int v)
23     {
24         int u=0,n=strlen(s);
25         for(int i=0;i<n;i++)
26         {
27             int c=idx(s[i]);
28             if(!Next[u][c])
29             {
30                 memset(Next[sz],0,sizeof(Next[sz]));
31                 val[sz]=0;
32                 Next[u][c]=sz++;
33             }
34             u=Next[u][c];
35         }
36         val[u]=v;
37     }
38 
39     void build()
40     {
41         queue<int> q;
42         fail[0]=0;
43         for(int i=0;i<sigma_size;i++) if(Next[0][i])
44         {
45             fail[Next[0][i]]=0;
46             q.push(Next[0][i]);
47         }
48         while(!q.empty())
49         {
50             int pos=q.front(); q.pop();
51             for(int i=0;i<sigma_size;i++)
52             {
53                 if(!Next[pos][i]) Next[pos][i]=Next[fail[pos]][i];
54                 else
55                 {
56                     fail[Next[pos][i]]=Next[fail[pos]][i];
57                     q.push(Next[pos][i]);
58                 }
59             }
60         }
61     }
62 
63     void query(char * s)
64     {
65         int len=strlen(s);
66         int pos=0;
67         for(int i=0;i<len;i++)
68         {
69             pos=Next[pos][idx(s[i])];
70             int tmp=pos;
71             while(tmp)
72             {
73                 if(val[tmp]) cnt[val[tmp]]++;
74                 tmp=fail[tmp];
75             }
76         }
77     }
78 
79 }ACA;
80 
81 int main(void)
82 {
83     int N;
84     while(~scanf("%d",&N))
85     {
86         ACA.init();
87         for(int i=1;i<=N;i++)
88         {
89             scanf("%s",a[i]);
90             ACA.insert(a[i],i);
91         }
92         ACA.build();
93         memset(cnt,0,sizeof(cnt));
94         scanf("%s",b);
95         ACA.query(b);
96         for(int i=1;i<=N;i++) if(cnt[i]) printf("%s: %d
",a[i],cnt[i]);
97     }
98     return 0;
99 }

Aguin

10.15

HDU 3695 Computer Virus on Planet Pandora

我可以不服吗- -。

明明是个板题样。一直T。加个used标记过了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 const int maxnode=3e5,sigma_size=26;
  8 const int maxn=6e6;
  9 char a[maxn];
 10 
 11 struct Ac_auto
 12 {
 13     int Next[maxnode][sigma_size];
 14     int val[maxnode];
 15     int fail[maxnode];
 16     bool used[maxnode];
 17     int sz;
 18     Ac_auto(){sz=1;memset(Next[0],0,sizeof(Next[0]));}
 19     void init(){sz=1;memset(Next[0],0,sizeof(Next[0]));}
 20     int idx(char c) {return c-'A';}
 21 
 22     void insert(char *s)
 23     {
 24         int u=0,n=strlen(s);
 25         for(int i=0;i<n;i++)
 26         {
 27             int c=idx(s[i]);
 28             if(!Next[u][c])
 29             {
 30                 memset(Next[sz],0,sizeof(Next[sz]));
 31                 val[sz]=used[sz]=0;
 32                 Next[u][c]=sz++;
 33             }
 34             u=Next[u][c];
 35         }
 36         val[u]++;
 37     }
 38 
 39     void build()
 40     {
 41         queue<int> q;
 42         fail[0]=0;
 43         for(int i=0;i<sigma_size;i++) if(Next[0][i])
 44         {
 45             fail[Next[0][i]]=0;
 46             q.push(Next[0][i]);
 47         }
 48         while(!q.empty())
 49         {
 50             int pos=q.front(); q.pop();
 51             for(int i=0;i<sigma_size;i++)
 52             {
 53                 if(!Next[pos][i]) Next[pos][i]=Next[fail[pos]][i];
 54                 else
 55                 {
 56                     fail[Next[pos][i]]=Next[fail[pos]][i];
 57                     q.push(Next[pos][i]);
 58                 }
 59             }
 60         }
 61     }
 62 
 63     int query(char * s)
 64     {
 65         int len=strlen(s);
 66         int pos=0,ret=0;
 67         for(int i=0;i<len;i++)
 68         {
 69             pos=Next[pos][idx(s[i])];
 70             int tmp=pos;
 71             while(tmp&&!used[tmp])
 72             {
 73                 used[tmp]=1;
 74                 if(val[tmp]) ret++;
 75                 val[tmp]=0;
 76                 tmp=fail[tmp];
 77             }
 78         }
 79         return ret;
 80     }
 81 
 82 }ACA;
 83 
 84 int main(void)
 85 {
 86     int T; cin>>T;
 87     while(T--)
 88     {
 89         ACA.init();
 90         int N; scanf("%d",&N);
 91         for(int i=1;i<=N;i++)
 92         {
 93             scanf("%s",a);
 94             ACA.insert(a);
 95         }
 96         ACA.build();
 97         char c;
 98         int t=0;
 99         getchar();
100         while((c=getchar())!='
')
101         {
102             if(c=='[')
103             {
104                 int n; scanf("%d",&n);
105                 c=getchar();
106                 while(n--) a[t++]=c;
107                 getchar();
108             }
109             else a[t++]=c;
110         }
111         a[t]=0;
112         int ans=ACA.query(a);
113         reverse(a,a+t);
114         ans+=ACA.query(a);
115         printf("%d
",ans);
116     }
117     return 0;
118 }

Aguin

10.16

CF 588B Duff in Love

真是有点数学就sb了。QAQ

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 
 6 int main(void)
 7 {
 8     LL n,ans=1LL;
 9     scanf("%I64d",&n);
10     for(LL i=2;i*i<=n;i++)
11     {
12         if(n%i==0)
13         {
14             ans*=i;
15             while(n%i==0) n/=i;
16         }
17     }
18     ans*=n;
19     printf("%I64d
",ans);
20     return 0;
21 }

Aguin

10.17

打个BC。

fst2题。