第十六周 12.13-12.19

12.13

补个BC。

讨厌打表。

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

Aguin

HDU 5598 GTW likes czf

当然是去搜。然而赛时没调好。赛后仍wa。最后偷看别人代码才发现挖点QAQ。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 const LL mod = 1e9 + 7;
 7 LL cnt, l, r, pow[100];
 8 int d[100], sz;
 9 
10 void dfs(int sz, LL a, LL b)
11 {
12     if( a > r || a + pow[sz+1] <= l || b > r || b + pow[sz+1] <= l ) return;
13     if( a >= l && a + pow[sz+1] - 1 <= r && b >= l && b + pow[sz+1] - 1 <= r )
14     {
15         cnt += pow[sz+1];
16         return;
17     }
18     if(d[sz])
19     {
20         dfs(sz-1, a + pow[sz], b);
21         dfs(sz-1, a, b + pow[sz]);
22     }
23     else
24     {
25         dfs(sz-1, a , b);
26         dfs(sz-1, a + pow[sz], b + pow[sz]);
27     }
28     return;
29 }
30 
31 int main(void)
32 {
33     pow[1] = 1LL;
34     for(int i = 2; i <= 63; i++) pow[i] = pow[i-1] * 2LL;
35     int k;
36     scanf("%d", &k);
37     while(k--)
38     {
39         memset(d, 0, sizeof(d));
40         LL G, T, ans;
41         sz = cnt = 0LL;
42         scanf("%I64d %I64d %I64d %I64d", &l, &r, &G, &T);
43         if(G == T) ans = r - l + 1LL;
44         else
45         {
46             int s = 0;
47             ans = 2 * (r - l + 1LL);
48             LL tmp = G ^ T, p = r;
49             while( tmp )
50             {
51                 d[++sz] = tmp % 2LL;
52                 tmp /= 2LL;
53             }
54             while(p) {p /= 2LL; s++;}
55             dfs(max(sz, s), 0LL, 0LL);
56         }
57         printf("%I64d
", ( ans - cnt ) % mod);
58     }
59     return 0;
60 }

Aguin

ZOJ 3535 Gao the String II

如果构好A串在B串的AC自动机上跑就可以了。

然而不会构A。

偷看题解预处理A连接方式。复杂度不会算。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <vector>
  7 using namespace std;
  8 const int maxnode = 2555, sigma_size = 26;
  9 char o[55][55], len[55];
 10 int m, n, L, dp[55][2555][55];
 11 
 12 struct node
 13 {
 14     char s[55];
 15     int l, id;
 16     node(char * str, int t, int j){l = t; id = j; strcpy(s, str);}
 17 };vector<node> v[55];
 18 
 19 struct Ac_auto
 20 {
 21     int Next[maxnode][sigma_size];
 22     int fail[maxnode];
 23     int val[maxnode];
 24     int sz;
 25 
 26     Ac_auto(){sz = 1; memset(Next[0], 0, sizeof(Next[0]));}
 27     void init(){sz = 1; memset(Next[0], 0, sizeof(Next[0]));}
 28 
 29     int idx(char c){return c - 'a';}
 30 
 31     void insert(char *s)
 32     {
 33         int u = 0, n = strlen(s);
 34         for(int i = 0; i < n; i++)
 35         {
 36             int c = idx(s[i]);
 37             if(!Next[u][c])
 38             {
 39                 memset(Next[sz], 0, sizeof(Next[sz]));
 40                 val[sz] = 0;
 41                 Next[u][c] = sz++;
 42             }
 43             u = Next[u][c];
 44         }
 45         val[u] += 1;
 46     }
 47 
 48     void build()
 49     {
 50         queue<int> q;
 51         fail[0] = 0;
 52         for(int i = 0; i < sigma_size; i++) if(Next[0][i])
 53         {
 54             fail[Next[0][i]] = 0;
 55             q.push(Next[0][i]);
 56         }
 57         while(!q.empty())
 58         {
 59             int pos = q.front(); q.pop();
 60             for(int i = 0; i < sigma_size; i++)
 61             {
 62                 if(!Next[pos][i]) Next[pos][i] = Next[fail[pos]][i];
 63                 else
 64                 {
 65                     fail[Next[pos][i]] = Next[fail[pos]][i];
 66                     q.push(Next[pos][i]);
 67                     val[Next[pos][i]] += val[fail[Next[pos][i]]]; //update val[]
 68                 }
 69             }
 70         }
 71     }
 72 
 73     int solve()
 74     {
 75         int ret = 0;
 76         memset(dp, -1, sizeof(dp));
 77         dp[0][0][0] = 0;
 78         for(int i = 0; i <= L; i++)
 79         {
 80             for(int j = 0; j < sz; j++)
 81             {
 82                 for(int k = 0; k <= m; k++)
 83                 {
 84                     if(dp[i][j][k] == -1) continue;
 85                     for(int p = 1; p <= m; p++)
 86                     {
 87                         if(i + len[p] > L) continue;
 88                         int pos = j, tag = 0;
 89                         for(int q = 0; q < len[p]; q++)
 90                         {
 91                             pos = Next[pos][idx(o[p][q])];
 92                             tag += val[pos];
 93                         }
 94                         dp[i+len[p]][pos][p] = max(dp[i+len[p]][pos][p], dp[i][j][k] + tag);
 95                     }
 96                     for(vector<node>::iterator p = v[k].begin(); p != v[k].end(); p++)
 97                     {
 98                         if(i + (*p).l > L) continue;
 99                         int pos = j, tag = 0;
100                         for(int q = 0; q < (*p).l; q++)
101                         {
102                             pos = Next[pos][idx((*p).s[q])];
103                             tag += val[pos];
104                         }
105                         dp[i+(*p).l][pos][(*p).id] = max(dp[i+(*p).l][pos][(*p).id], dp[i][j][k] + tag);
106                     }
107                     ret = max(ret, dp[i][j][k]);
108                 }
109             }
110         }
111         return ret;
112     }
113 
114 }ACA;
115 
116 int main(void)
117 {
118     while(~scanf("%d%d%d", &m, &n, &L))
119     {
120         ACA.init();
121         for(int i = 1; i <= m; i++)
122         {
123             scanf("%s", o[i]);
124             len[i] = strlen(o[i]);
125         }
126         for(int i = 1; i <= n; i++)
127         {
128             char tmp[111];
129             scanf("%s", tmp);
130             ACA.insert(tmp);
131         }
132         ACA.build();
133         for(int i = 1; i <= m; i++) v[i].clear();
134         for(int i = 1; i <= m; i++)
135         {
136             for(int j = 1; j <= m; j++)
137             {
138                 for(int s = 0; s < len[i]; s++)
139                 {
140                     int ok = 1, c = len[i] - s, r = len[j] - c;
141                     for(int p = s; p < len[i]; p++) if(o[i][p] != o[j][p-s]) {ok = 0; break;}
142                     if(ok && r) v[i].push_back(node(o[j] + c, r, j));
143                 }
144             }
145         }
146         printf("%d
", ACA.solve());
147     }
148     return 0;
149 }

Aguin

12.14

BZOJ 2434 [Noi2011]阿狸的打字机

因为太有名被剧透了的题？

反构fail树用树状数组离线处理询问。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <queue>
  6 #include <vector>
  7 using namespace std;
  8 typedef pair<int,int> pii;
  9 const int maxnode = 111111, sigma_size = 26;
 10 int ans[111111], Map[111111];
 11 vector<pii> Q[111111];
 12 char s[111111];
 13 
 14 //fail_tree
 15 int cnt,headlist[maxnode];
 16 int timer,dfn[maxnode][2];
 17 struct e
 18 {
 19     int to,pre;
 20 } edge[2*maxnode];
 21 void add(int from,int to)
 22 {
 23     cnt++;
 24     edge[cnt].pre=headlist[from];
 25     edge[cnt].to=to;
 26     headlist[from]=cnt;
 27 }
 28 void dfs(int pos,int fa)
 29 {
 30     dfn[pos][0]=++timer;
 31     for(int i=headlist[pos];i;i=edge[i].pre)
 32     {
 33         int to=edge[i].to;
 34         if(to==fa) continue;
 35         dfs(to,pos);
 36     }
 37     dfn[pos][1]=++timer;
 38 }
 39 
 40 //BIT
 41 int c[222222];
 42 int lowbit(int s)
 43 {
 44     return s & (-s);
 45 }
 46 void update(int i, int x)
 47 {
 48     while(i <= timer) {c[i] += x; i += lowbit(i);}
 49     return;
 50 }
 51 int query(int i)
 52 {
 53     int ret = 0;
 54     while(i > 0) {ret += c[i]; i -= lowbit(i);}
 55     return ret;
 56 }
 57 
 58 //ACA
 59 struct Ac_auto
 60 {
 61     int Next[maxnode][sigma_size];
 62     int fail[maxnode];
 63     int fa[maxnode];
 64     int sz;
 65 
 66     Ac_auto(){sz = 1; memset(Next[0], 0, sizeof(Next[0]));}
 67     void init(){sz = 1; memset(Next[0], 0, sizeof(Next[0]));}
 68 
 69     int idx(char c){return c - 'a';}
 70 
 71     void insert()
 72     {
 73         int u = 0, n = strlen(s), tt = 0;
 74         for(int i = 0; i < n; i++)
 75         {
 76             if(s[i] == 'B') {u = fa[u]; continue;}
 77             if(s[i] == 'P') {Map[++tt] = u; continue;}
 78             int c = idx(s[i]);
 79             if(!Next[u][c])
 80             {
 81                 memset(Next[sz], 0, sizeof(Next[sz]));
 82                 fa[sz] = u;
 83                 Next[u][c] = sz++;
 84             }
 85             u = Next[u][c];
 86         }
 87     }
 88 
 89     void build()
 90     {
 91         queue<int> q;
 92         fail[0] = 0;
 93         for(int i = 0; i < sigma_size; i++) if(Next[0][i])
 94         {
 95             fail[Next[0][i]] = 0;
 96             q.push(Next[0][i]);
 97         }
 98         while(!q.empty())
 99         {
100             int pos = q.front(); q.pop();
101             for(int i = 0; i < sigma_size; i++)
102             {
103                 if(!Next[pos][i]) Next[pos][i] = Next[fail[pos]][i];
104                 else
105                 {
106                     fail[Next[pos][i]] = Next[fail[pos]][i];
107                     q.push(Next[pos][i]);
108                 }
109             }
110         }
111     }
112 
113     void fail_tree()
114     {
115         for(int i=1;i<sz;i++)
116         {
117             add(i,fail[i]);
118             add(fail[i],i);
119         }
120         dfs(0,-1);
121     }
122 
123     void solve()
124     {
125         int u = 0, n = strlen(s), tt = 0;
126         for(int i = 0; i < n; i++)
127         {
128             if(s[i] == 'B')
129             {
130                 update(dfn[u][0], -1);
131                 u = fa[u];
132             }
133             else if(s[i] == 'P')
134             {
135                 tt++;
136                 for(int j = 0; j < Q[tt].size(); j++)
137                 {
138                     int x = Map[Q[tt][j].first], i = Q[tt][j].second;
139                     ans[i] = query(dfn[x][1]) - query(dfn[x][0] - 1);
140                 }
141             }
142             else
143             {
144                 u = Next[u][idx(s[i])];
145                 update(dfn[u][0], 1);
146             }
147         }
148     }
149 
150 }ACA;
151 
152 int main(void)
153 {
154     scanf("%s", s);
155     ACA.insert();
156     ACA.build();
157     ACA.fail_tree();
158     int m; scanf("%d", &m);
159     for(int i = 1; i <= m; i++)
160     {
161         int x, y;
162         scanf("%d %d", &x, &y);
163         Q[y].push_back(pii(x, i));
164     }
165     ACA.solve();
166     for(int i = 1; i <= m; i++) printf("%d
", ans[i]);
167     return 0;
168 }

Aguin

于是AC自动机不想做了。后面再学点乱七八糟的？

12.15-12.18

什么都没干。

12.19

后缀数组。

白薯板。倍增桶排。

 1 char s[maxn];
 2 int n, SA[maxn], t1[maxn], t2[maxn], c[maxn];
 3 void get_SA(int m)
 4 {
 5     int * x = t1, * y = t2;
 6     for(int i = 0; i < m; i++) c[i] = 0;
 7     for(int i = 0; i < n; i++) c[x[i] = s[i]]++;
 8     for(int i = 1; i < m; i++) c[i] += c[i-1];
 9     for(int i = n - 1; i >= 0; i--) SA[--c[x[i]]] = i;
10     for(int k = 1; k <= n; k <<= 1)
11     {
12         int p = 0;
13         for(int i = n - k; i < n; i++) y[p++] = i;
14         for(int i = 0; i < n; i++) c[x[y[i]]]++;
15         for(int i = 0; i < m; i++) c[i] += c[i-1];
16         for(int i = n - 1; i >= 0; i--) SA[--c[x[y[i]]]] = y[i];
17         swap(x, y);
18         p = 1; x[SA[0]] = 0;
19         for(int i = 1; i < n; i++)
20             x[SA[i]] = y[SA[i-1]] == y[SA[i]] && y[SA[i-1]+k] == y[SA[i]+k] ? p - 1 : p++;
21         if(p >= n) break;
22         m = p;
23     }
24     return;
25 }

Aguin

挑战板。倍增快排。

 1 char s[maxn];
 2 int n, k, SA[maxn], r[maxn], tmp[maxn];
 3 bool cmp(int i, int j)
 4 {
 5     if(r[i] != r[j]) return r[i] < r[j];
 6     return ( i + k <= n ? r[i+k] : -1 ) < ( j + k <= n ? r[j+k] : -1 );
 7 }
 8 void get_SA()
 9 {
10     n = strlen(s);
11     for(int i = 0; i <= n; i++)
12     {
13         SA[i] = i;
14         r[i] = i < n ? s[i] : -1;
15     }
16     for(k = 1; k <= n; k <<= 1)
17     {
18         sort(SA, SA + n + 1, cmp);
19         tmp[SA[0]] = 0;
20         for(int i = 1; i <= n; i++) tmp[SA[i]] = tmp[SA[i-1]] + cmp(SA[i-1], SA[i]);
21         memcpy(r, tmp, sizeof(r));
22     }
23     return;
24 }

Aguin