第一周 1.17-1.23

1.17

类似于函数图像有两条对称轴必然是周期的。

如果循环次数是奇数每一循环节都要是回文把奇数的放中间偶数放两边（所以奇数的不止1个就无解）。

循环次数偶随便放一个循环节相邻的对称一下即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int maxn = 1e5 + 10;
 5 int num[26];
 6 char s[maxn];
 7 
 8 int gcd(int a, int b)
 9 {
10     return a % b ? gcd(b, a % b) : b;
11 }
12 
13 int main(void)
14 {
15     int n, cnt = 0;
16     scanf("%d", &n);
17     for(int i = 0; i < n; i++) scanf("%d", num + i);
18     int tmp = num[0];
19     for(int i = 1; i < n; i++) tmp = gcd(tmp, num[i]);
20     for(int i = 0; i < n; i++) num[i] /= tmp;
21     if(tmp & 1)
22     {
23         int pos1 = -1;
24         for(int i = 0; i < n; i++)
25         {
26             if(num[i] & 1)
27             {
28                 if(pos1 == -1) pos1 = i;
29                 else
30                 {
31                     puts("0");
32                     for(int k = 0; k < n; k++)
33                         for(int j = 0; j < tmp * num[k]; j++)
34                             putchar('a' + k);
35                     puts("");
36                     return 0;
37                 }
38             }
39         }
40         for(int i = 0; i < n; i++)
41         {
42             if(num[i] & 1) num[i]--;
43             for(int j = 0; j < num[i] / 2; j++)
44                 s[cnt++] = 'a' + i;
45         }
46         int l = cnt;
47         if(pos1 != -1) s[cnt++] = 'a' + pos1;
48         for(int j = 1; j <= l; j++) s[cnt++] = s[l-j];
49         s[cnt] = 0;
50         printf("%d
", tmp);
51         for(int j = 0; j < tmp; j++) printf("%s", s);
52         puts("");
53     }
54     else
55     {
56         for(int i = 0; i < n; i++)
57             for(int j = 0; j < num[i]; j++)
58                 s[cnt++] = 'a' + i;
59         for(int i = cnt; i; i--)
60             s[cnt++] = s[i-1];
61         s[cnt] = 0;
62         printf("%d
", tmp);
63         for(int j = 0; j < tmp / 2; j++) printf("%s", s);
64         puts("");
65     }
66     return 0;
67 }

Aguin

原来看后缀数组是上个月的事情了？

POJ 2217 Secretary

最长公共子串。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 22222;
 7 char s[maxn];
 8 int n, k, SA[maxn], r[maxn], tmp[maxn], h[maxn];
 9 bool cmp(int i, int j)
10 {
11     if(r[i] != r[j]) return r[i] < r[j];
12     return ( i + k <= n ? r[i+k] : -1 ) < ( j + k <= n ? r[j+k] : -1 );
13 }
14 void get_SA()
15 {
16     for(int i = 0; i <= n; i++)
17     {
18         SA[i] = i;
19         r[i] = i < n ? s[i] : -1;
20     }
21     for(k = 1; k <= n; k <<= 1)
22     {
23         sort(SA, SA + n + 1, cmp);
24         tmp[SA[0]] = 0;
25         for(int i = 1; i <= n; i++) tmp[SA[i]] = tmp[SA[i-1]] + cmp(SA[i-1], SA[i]);
26         memcpy(r, tmp, sizeof(r));
27     }
28     return;
29 }
30 void get_height()
31 {
32     for(int i = 0; i <= n; i++) r[SA[i]] = i;
33     int k = 0;
34     for(int i = 0; i < n; i++)
35     {
36         if(k) k--;
37         int j = SA[r[i]-1];
38         while(s[i+k] == s[j+k]) k++;
39         h[r[i]] = k;
40     }
41     return;
42 }
43 
44 int main(void)
45 {
46     int N;
47     scanf("%d", &N);
48     getchar();
49     while(N--)
50     {
51         gets(s);
52         int m = strlen(s);
53         s[m] = '~';
54         gets(s + m + 1);
55         n = strlen(s);
56         get_SA();
57         get_height();
58         int ans = 0;
59         for(int i = 1; i <= n; i++)
60             if( ( SA[i] <= m ) != ( SA[i-1] <= m ) && h[i] > ans)
61                 ans = h[i];
62         printf("Nejdelsi spolecny retezec ma delku %d.
", ans);
63     }
64     return 0;
65 }

Aguin

UVA 11107 Life Forms

讨厌UVA。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 const int maxn = 111111;
  7 int n, k, SA[maxn], r[maxn], tmp[maxn], h[maxn];
  8 int range[maxn], flag[111];
  9 char s[maxn];
 10 
 11 bool cmp(int i, int j)
 12 {
 13     if(r[i] != r[j]) return r[i] < r[j];
 14     return ( i + k <= n ? r[i+k] : -1 ) < ( j + k <= n ? r[j+k] : -1 );
 15 }
 16 
 17 void get_SA()
 18 {
 19     for(int i = 0; i <= n; i++)
 20     {
 21         SA[i] = i;
 22         r[i] = i < n ? s[i] : -1;
 23     }
 24     for(k = 1; k <= n; k <<= 1)
 25     {
 26         sort(SA, SA + n + 1, cmp);
 27         tmp[SA[0]] = 0;
 28         for(int i = 1; i <= n; i++) tmp[SA[i]] = tmp[SA[i-1]] + cmp(SA[i-1], SA[i]);
 29         memcpy(r, tmp, sizeof(r));
 30     }
 31     return;
 32 }
 33 
 34 void get_height()
 35 {
 36     for(int i = 0; i <= n; i++) r[SA[i]] = i;
 37     int k = 0;
 38     for(int i = 0; i < n; i++)
 39     {
 40         if(k) k--;
 41         int j = SA[r[i]-1];
 42         while(s[i+k] == s[j+k]) k++;
 43         h[r[i]] = k;
 44     }
 45     return;
 46 }
 47 
 48 int main(void)
 49 {
 50     int N, fir = 1;
 51     while(~scanf("%d", &N) && N)
 52     {
 53         if(!fir) puts("");
 54         fir = 0;
 55         if(N == 1)
 56         {
 57             scanf("%s", s);
 58             printf("%s

", s);
 59             continue;
 60         }
 61         int pos = 0;
 62         for(int i = 1; i <= N; i++)
 63         {
 64             scanf("%s", s + pos);
 65             for(int j = pos; s[j]; j++) range[j] = i;
 66             pos = strlen(s);
 67             s[pos++] = 130 + i;
 68         }
 69         s[pos] = 0;
 70         n = strlen(s);
 71         get_SA();
 72         get_height();
 73         int l = 0, r = n, mid;
 74         while(l < r)
 75         {
 76             int ok = 0;
 77             mid = (l + r + 1) / 2;
 78             for(int i = 1; i <= n; i++)
 79             {
 80                 if(h[i] < mid) continue;
 81                 int cnt = 0;
 82                 memset(flag, 0, sizeof(flag));
 83                 for(int j = i; j <= n; j++)
 84                 {
 85                     if(h[j] < mid) break;
 86                     int a = range[SA[j]], b = range[SA[j-1]];
 87                     if(a == b) continue;
 88                     if(!flag[a]) cnt++;
 89                     if(!flag[b]) cnt++;
 90                     flag[a] = flag[b] = 1;
 91                 }
 92                 if(cnt > N / 2) {ok = 1;break;}
 93             }
 94             if(ok) l = mid;
 95             else r = mid - 1;
 96         }
 97         if(l) for(int i = 1; i <= n; i++)
 98         {
 99             if(h[i] < l) continue;
100             int cnt = 0;
101             memset(flag, 0, sizeof(flag));
102             for(int j = i; j <= n; j++)
103             {
104                 if(h[j] < l) break;
105                 int a = range[SA[j]], b = range[SA[j-1]];
106                 if(!a || !b || a == b) continue;
107                 if(!flag[a]) cnt++;
108                 if(!flag[b]) cnt++;
109                 flag[a] = flag[b] = 1;
110                 i = j;
111             }
112             if(cnt > N / 2)
113             {
114                 for(int j = 0; j < l; j++) putchar(s[SA[i]+j]);
115                 puts("");
116             }
117         }
118         else puts("?");
119     }
120     return 0;
121 }

Aguin

POJ 1743 Musical Theme

做差搞SA。相邻要大于mid而不是大于等于mid才不重叠。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 111111;
 7 int n, k, SA[maxn], r[maxn], tmp[maxn], h[maxn];
 8 int s[maxn];
 9 
10 bool cmp(int i, int j)
11 {
12     if(r[i] != r[j]) return r[i] < r[j];
13     return ( i + k <= n ? r[i+k] : -1 ) < ( j + k <= n ? r[j+k] : -1 );
14 }
15 
16 void get_SA()
17 {
18     for(int i = 0; i <= n; i++)
19     {
20         SA[i] = i;
21         r[i] = i < n ? s[i] : -1;
22     }
23     for(k = 1; k <= n; k <<= 1)
24     {
25         sort(SA, SA + n + 1, cmp);
26         tmp[SA[0]] = 0;
27         for(int i = 1; i <= n; i++) tmp[SA[i]] = tmp[SA[i-1]] + cmp(SA[i-1], SA[i]);
28         memcpy(r, tmp, sizeof(r));
29     }
30     return;
31 }
32 
33 void get_height()
34 {
35     for(int i = 0; i <= n; i++) r[SA[i]] = i;
36     int k = 0;
37     for(int i = 0; i < n; i++)
38     {
39         if(k) k--;
40         int j = SA[r[i]-1];
41         while(s[i+k] == s[j+k]) k++;
42         h[r[i]] = k;
43     }
44     return;
45 }
46 
47 int main(void)
48 {
49     int N;
50     while(~scanf("%d", &N) && N)
51     {
52         for(int i = 0; i < N; i++) scanf("%d", s + i);
53         for(int i = 1; i < N; i++) s[i-1] -= s[i];
54         n = N - 1;
55         get_SA();
56         get_height();
57         int l = 0, r = n - 1, mid;
58         while(l < r)
59         {
60             int ok = 0;
61             mid = (l + r + 1) / 2;
62             for(int i = 1; i < n; i++) if(h[i] >= mid)
63             {
64                 int Max = SA[i-1], Min = SA[i-1];
65                 for(int j = i; j < n; j++)
66                 {
67                     if(h[j] < mid) break;
68                     Max = max(Max, SA[j]);
69                     Min = min(Min, SA[j]);
70                     i = j;
71                 }
72                 if(Max - Min > mid) {ok = 1;break;}
73             }
74             if(ok) l = mid;
75             else r = mid - 1;
76         }
77         if(l > 3) printf("%d
", l + 1);
78         else puts("0");
79     }
80     return 0;
81 }

Aguin

POJ 3261 Milk Patterns

上面改改就好啦。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 111111;
 7 int n, k, SA[maxn], r[maxn], tmp[maxn], h[maxn];
 8 int s[maxn];
 9 
10 bool cmp(int i, int j)
11 {
12     if(r[i] != r[j]) return r[i] < r[j];
13     return ( i + k <= n ? r[i+k] : -1 ) < ( j + k <= n ? r[j+k] : -1 );
14 }
15 
16 void get_SA()
17 {
18     for(int i = 0; i <= n; i++)
19     {
20         SA[i] = i;
21         r[i] = i < n ? s[i] : -1;
22     }
23     for(k = 1; k <= n; k <<= 1)
24     {
25         sort(SA, SA + n + 1, cmp);
26         tmp[SA[0]] = 0;
27         for(int i = 1; i <= n; i++) tmp[SA[i]] = tmp[SA[i-1]] + cmp(SA[i-1], SA[i]);
28         memcpy(r, tmp, sizeof(r));
29     }
30     return;
31 }
32 
33 void get_height()
34 {
35     for(int i = 0; i <= n; i++) r[SA[i]] = i;
36     int k = 0;
37     for(int i = 0; i < n; i++)
38     {
39         if(k) k--;
40         int j = SA[r[i]-1];
41         while(s[i+k] == s[j+k]) k++;
42         h[r[i]] = k;
43     }
44     return;
45 }
46 
47 int main(void)
48 {
49     int K;
50     while(~scanf("%d%d", &n, &K))
51     {
52         for(int i = 0; i < n; i++) scanf("%d", s + i);
53         get_SA();
54         get_height();
55         int l = 0, r = n, mid;
56         while(l < r)
57         {
58             int ok = 0;
59             mid = (l + r + 1) / 2;
60             for(int i = 1; i <= n; i++) if(h[i] >= mid)
61             {
62                 int cnt = 1;
63                 for(int j = i; j <= n; j++)
64                 {
65                     if(h[j] < mid) break;
66                     cnt++;
67                     i = j;
68                 }
69                 if(cnt >= K) {ok = 1;break;}
70             }
71             if(ok) l = mid;
72             else r = mid - 1;
73         }
74         printf("%d
", l);
75     }
76     return 0;
77 }

Aguin

SPOJ DISUBSTR Distinct Substrings

每个后缀对答案的贡献是n - sa[i] - height[i]。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 111111;
 7 int n, k, SA[maxn], r[maxn], tmp[maxn], h[maxn];
 8 char s[maxn];
 9 
10 bool cmp(int i, int j)
11 {
12     if(r[i] != r[j]) return r[i] < r[j];
13     return ( i + k <= n ? r[i+k] : -1 ) < ( j + k <= n ? r[j+k] : -1 );
14 }
15 
16 void get_SA()
17 {
18     for(int i = 0; i <= n; i++)
19     {
20         SA[i] = i;
21         r[i] = i < n ? s[i] : -1;
22     }
23     for(k = 1; k <= n; k <<= 1)
24     {
25         sort(SA, SA + n + 1, cmp);
26         tmp[SA[0]] = 0;
27         for(int i = 1; i <= n; i++) tmp[SA[i]] = tmp[SA[i-1]] + cmp(SA[i-1], SA[i]);
28         memcpy(r, tmp, sizeof(r));
29     }
30     return;
31 }
32 
33 void get_height()
34 {
35     for(int i = 0; i <= n; i++) r[SA[i]] = i;
36     int k = 0;
37     for(int i = 0; i < n; i++)
38     {
39         if(k) k--;
40         int j = SA[r[i]-1];
41         while(s[i+k] == s[j+k]) k++;
42         h[r[i]] = k;
43     }
44     return;
45 }
46 
47 int main(void)
48 {
49     int T;
50     scanf("%d", &T);
51     for(int kase = 1; kase <= T; kase++)
52     {
53         scanf("%s", s);
54         n = strlen(s);
55         get_SA();
56         get_height();
57         int ans = n - SA[0];
58         for(int i = 1; i <= n; i++) ans += n - SA[i] - h[i];
59         printf("%d
", ans);
60     }
61     return 0;
62 }

Aguin

1.18

什么都没干。

1.19

POJ 3693 Maximum repetition substring

看了好多题解才看懂。然而并不好想阿。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 const int maxn = 111111;
  7 int n, k, SA[maxn], r[maxn], tmp[maxn], h[maxn], rmq[maxn][20];
  8 char s[maxn];
  9 
 10 bool cmp(int i, int j)
 11 {
 12     if(r[i] != r[j]) return r[i] < r[j];
 13     return ( i + k <= n ? r[i+k] : -1 ) < ( j + k <= n ? r[j+k] : -1 );
 14 }
 15 
 16 void get_SA()
 17 {
 18     for(int i = 0; i <= n; i++)
 19     {
 20         SA[i] = i;
 21         r[i] = i < n ? s[i] : -1;
 22     }
 23     for(k = 1; k <= n; k <<= 1)
 24     {
 25         sort(SA, SA + n + 1, cmp);
 26         tmp[SA[0]] = 0;
 27         for(int i = 1; i <= n; i++) tmp[SA[i]] = tmp[SA[i-1]] + cmp(SA[i-1], SA[i]);
 28         memcpy(r, tmp, sizeof(r));
 29     }
 30     return;
 31 }
 32 
 33 void get_height()
 34 {
 35     for(int i = 0; i <= n; i++) r[SA[i]] = i;
 36     int k = 0;
 37     for(int i = 0; i < n; i++)
 38     {
 39         if(k) k--;
 40         int j = SA[r[i]-1];
 41         while(s[i+k] == s[j+k]) k++;
 42         h[r[i]] = k;
 43     }
 44     return;
 45 }
 46 
 47 void RMQ_init()
 48 {
 49     for(int i = 1; i <= n; i++) rmq[i][0] = h[i];
 50     for(int j = 1; (1 << j) <= n; j++)
 51         for(int i = 1; i + ( 1 << j ) - 1 <= n; i++)
 52             rmq[i][j] = min(rmq[i][j-1] , rmq[i+(1<<j-1)][j-1]);
 53 }
 54 
 55 int RMQ_query(int l, int r)
 56 {
 57     int k = 0;
 58     while( ( 1 << (k + 1) ) <= r - l + 1 ) k++;
 59     return min(rmq[l][k], rmq[r-(1<<k)+1][k]);
 60 }
 61 
 62 int lcp(int i, int j)
 63 {
 64     i = r[i], j = r[j];
 65     if(i > j) swap(i, j);
 66     return RMQ_query(i + 1, j);
 67 }
 68 
 69 int main(void)
 70 {
 71     int kase = 0;
 72     while(~scanf("%s", s) && s[0] != '#')
 73     {
 74         n = strlen(s);
 75         get_SA();
 76         get_height();
 77         RMQ_init();
 78         int Max = 1, MaxL = 1;
 79         for(int L = 1; L < n; L++)
 80         {
 81             for(int i = 0; i + L < n; i += L)
 82             {
 83                 int cur = lcp(i, i + L), tmp = cur / L + 1;
 84                 int pos = i - L + cur % L;
 85                 if(pos >= 0 && lcp(pos, pos + L) >= tmp * L) tmp++;
 86                 if(tmp > Max) Max = tmp, MaxL = L;
 87             }
 88         }
 89         for(int i = 1; i <= n; i++)
 90         {
 91             if(SA[i] + MaxL <= n && lcp(SA[i], SA[i] + MaxL) >= Max  * MaxL - MaxL)
 92             {
 93                 printf("Case %d: ", ++kase);
 94                 for(int j = 0; j < MaxL * Max; j++) putchar(s[SA[i]+j]);
 95                 puts(""); break;
 96             }
 97         }
 98     }
 99     return 0;
100 }

Aguin

POJ 3415 Common Substrings

好烦啊。还要搞个单调栈。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 const int maxn = 222222;
 8 int n, m, k, K, SA[maxn], r[maxn], tmp[maxn], h[maxn];
 9 LL sta[maxn], cnt[maxn];
10 char s[maxn];
11 
12 bool cmp(int i, int j)
13 {
14     if(r[i] != r[j]) return r[i] < r[j];
15     return ( i + k <= n ? r[i+k] : -1 ) < ( j + k <= n ? r[j+k] : -1 );
16 }
17 
18 void get_SA()
19 {
20     for(int i = 0; i <= n; i++)
21     {
22         SA[i] = i;
23         r[i] = i < n ? s[i] : -1;
24     }
25     for(k = 1; k <= n; k <<= 1)
26     {
27         sort(SA, SA + n + 1, cmp);
28         tmp[SA[0]] = 0;
29         for(int i = 1; i <= n; i++) tmp[SA[i]] = tmp[SA[i-1]] + cmp(SA[i-1], SA[i]);
30         memcpy(r, tmp, sizeof(r));
31     }
32     return;
33 }
34 
35 void get_height()
36 {
37     for(int i = 0; i <= n; i++) r[SA[i]] = i;
38     int k = 0;
39     for(int i = 0; i < n; i++)
40     {
41         if(k) k--;
42         int j = SA[r[i]-1];
43         while(s[i+k] == s[j+k]) k++;
44         h[r[i]] = k;
45     }
46     return;
47 }
48 
49 LL cal(int flag)
50 {
51     LL ret = 0, top = 0, sum = 0;
52     for(int i = 1; i <= n; i++)
53     {
54         if(h[i] < K) top = sum = 0;
55         else
56         {
57             int tmp = 0;
58             if( (SA[i-1] < m) ^ flag ) tmp = 1, sum += (LL) h[i] - K + 1;
59             while(top && sta[top-1] > h[i])
60             {
61                 top--;
62                 sum -= cnt[top] * (sta[top] - h[i]);
63                 tmp += cnt[top];
64             }
65             sta[top] = h[i], cnt[top++] = tmp;
66             if( (SA[i] > m) ^ flag ) ret += sum;
67         }
68     }
69     return ret;
70 }
71 
72 int main(void)
73 {
74     while(~scanf("%d", &K) && K)
75     {
76         scanf("%s", s);
77         m = strlen(s);
78         s[m] = '~';
79         scanf("%s", s + m + 1);
80         n = strlen(s);
81         get_SA();
82         get_height();
83         printf("%I64d
",cal(0) + cal(1));
84     }
85     return 0;
86 }

Aguin

1.20

打个TC。没上黄。

TC SRM 679 DIV2 500 ContestScoreboard

FST了。就是一个模拟题。

感觉学习到了就是sstream这个玩意儿。- -

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <sstream>
 6 #include <vector>
 7 #include <algorithm>
 8 using namespace std;
 9 typedef long long LL;
10 typedef pair<int, int> pii;
11 
12 struct team
13 {
14     string Name;
15     int id;
16     LL Score;
17 }T[111];
18 
19 bool cmp(team A, team B)
20 {
21     if(A.Score != B.Score) return A.Score > B.Score;
22     return A.Name < B.Name;
23 }
24 
25 class ContestScoreboard
26 {
27 public:
28     vector <int> findWinner(vector <string> scores)
29     {
30         int N = scores.size();
31         vector<pii> tmp[111];
32         vector<int> time;
33         int ans[111];
34         memset(ans, 0, sizeof(ans));
35         for(int i = 0; i < N; i++)
36         {
37             char c;
38             T[i].id = i;
39             stringstream ss;
40             ss.str(scores[i]);
41             ss >> T[i].Name;
42             int Sc, Ti;
43             while( ss >> Sc >> c >> Ti) tmp[i].push_back(pii(Ti,Sc)), time.push_back(Ti + 1);
44             sort(tmp[i].begin(), tmp[i].end());
45         }
46         time.push_back(0);
47         sort(time.begin(), time.end());
48         for(int i = 0; i < time.size(); i++)
49         {
50             for(int j = 0; j < N; j++)
51             {
52                 T[j].Score = 0LL;
53                 for(int k = 0; k < tmp[T[j].id].size(); k++)
54                 {
55                     if(tmp[T[j].id][k].first >= time[i]) break;
56                     T[j].Score += (LL) tmp[T[j].id][k].second;
57                 }
58             }
59             sort(T, T + N, cmp);
60             ans[T[0].id] = 1;
61         }
62         vector<int> ret;
63         for(int i = 0; i < N; i++) ret.push_back(ans[i]);
64         return ret;
65     }
66 };

Aguin

1.21

TC SRM 679 DIV2 1000 ForbiddenStreets

暴力思路很正确阿。然而没写完。

Floyd时每两点维护一个边集。又一次用了SLT的集合运算。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <set>
 6 #include <algorithm>
 7 using namespace std;
 8 int G[111][111];
 9 
10 class ForbiddenStreets
11 {
12 public:
13     vector <int> find(int N, vector <int> A, vector <int> B, vector <int> time)
14     {
15         int m = A.size();
16         memset(G, 0 ,sizeof(G));
17         set<int> r[111][111];
18         for(int i = 0; i < m; i++)
19         {
20             int a = A[i], b = B[i], d = time[i];
21             G[a][b] = G[b][a] = d;
22             r[a][b].insert(i);
23             r[b][a].insert(i);
24         }
25         for(int k = 0; k < N; k++)
26         {
27             for(int i = 0; i < N; i++)
28             {
29                 for(int j = 0; j < N; j++)
30                 {
31                     if(!G[i][k] || !G[k][j]) continue;
32                     if(!G[i][j] || G[i][k] + G[k][j] < G[i][j])
33                     {
34                         G[i][j] = G[i][k] + G[k][j];
35                         r[i][j].clear();
36                         set_union(r[i][k].begin(), r[i][k].end(), r[k][j].begin(), r[k][j].end(), inserter(r[i][j], r[i][j].begin()));
37                     }
38                     else if(G[i][k] + G[k][j] == G[i][j])
39                     {
40                         set<int> a, b;
41                         set_union(r[i][k].begin(), r[i][k].end(), r[k][j].begin(), r[k][j].end(), inserter(a, a.begin()));
42                         set_intersection(a.begin(), a.end(), r[i][j].begin(), r[i][j].end(), inserter(b, b.begin()));
43                         r[i][j] = b;
44                     }
45                 }
46             }
47         }
48         int cnt[2222];
49         memset(cnt, 0, sizeof(cnt));
50         for(int i = 0; i < N; i++)
51             for(int j = i + 1; j < N; j++)
52                 for(set<int>::iterator it = r[i][j].begin(); it != r[i][j].end(); it++) cnt[*it]++;
53         vector<int> ret;
54         for(int i = 0; i < m; i++) ret.push_back(cnt[i]);
55         return ret;
56     }
57 };

Aguin

1.22

CF 620 D Professor GukiZ and Two Arrays

场上比较sb。一直在贪。

swap2次的话。把a的组合丢map里，再遍历b的组合去二分a。

麻烦一点就是二分要检查两边的值，比如用lower_bound()要检查it和it--的key。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <map>
 6 using namespace std;
 7 typedef long long LL;
 8 typedef pair<int, int> pii;
 9 LL a[2222], b[2222];
10 map<LL, pii> M;
11 map<LL, pii>::iterator it;
12 
13 int main(void)
14 {
15     int n, m;
16     LL sa = 0, sb = 0;
17     scanf("%d", &n);
18     for(int i = 1; i <= n; i++) scanf("%I64d", a + i), sa += a[i];
19     scanf("%d", &m);
20     for(int i = 1; i <= m; i++) scanf("%I64d", b + i), sb += b[i];
21     LL v = abs(sa - sb), pa = 0, pb = 0;
22     for(int i = 1; i <= n; i++)
23         for(int j = 1; j <= m; j++)
24             if(abs(sa - a[i] * 2LL - sb + b[j] * 2LL) < v)
25                 v = abs(sa - a[i] * 2LL - sb + b[j] * 2LL), pa = i, pb = j;
26     if(!pa) {printf("%I64d
0
", v); return 0;}
27 
28     for(int i = 1; i <= n; i++)
29         for(int j = i + 1; j <= n; j++)
30             M[(a[i] + a[j]) * 2LL] = pii(i, j);
31 
32     LL ppa = 0, ppb = 0;
33 
34     for(int i = 1; i <= m; i++)
35     {
36         for(int j = i + 1; j <= m; j++)
37         {
38             LL x = sa - sb + b[i] + b[i] + b[j] + b[j];
39             it = M.lower_bound(x);
40             if(it != M.end() && abs((*it).first - x) < v)
41             {
42                 v = abs((*it).first - x);
43                 pii tmp = (*it).second;
44                 pa = tmp.first, pb = i, ppa = tmp.second, ppb = j;
45             }
46             if(it != M.begin())
47             {
48                 it--;
49                 if(abs((*it).first - x) >= v) continue;
50                 v = abs((*it).first - x);
51                 pii tmp = (*it).second;
52                 pa = tmp.first, pb = i, ppa = tmp.second, ppb = j;
53             }
54         }
55     }
56 
57     if(!ppa) printf("%I64d
1
%I64d %I64d
", v, pa, pb);
58     else printf("%I64d
2
%I64d %I64d
%I64d %I64d
",v, pa, pb, ppa, ppb);
59     return 0;
60 }

Aguin

CF 620 E New Year Tree

哭了太久没写不会写线段树了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #define lson (2 * p)
  4 #define rson (2 * p + 1)
  5 #define mid ( (tr[p].l + tr[p].r) / 2 )
  6 using namespace std;
  7 typedef long long LL;
  8 const int maxn = 4e5 + 10;
  9 int cnt , h[maxn];
 10 int timer, dfn[maxn][2];
 11 int id[maxn<<1], col[maxn];
 12 
 13 struct edge
 14 {
 15     int to, pre;
 16 } e[maxn<<1];
 17 
 18 void add(int from, int to)
 19 {
 20     cnt++;
 21     e[cnt].pre = h[from];
 22     e[cnt].to = to;
 23     h[from] = cnt;
 24 }
 25 
 26 void dfs(int p, int fa)
 27 {
 28     dfn[p][0] = ++timer;
 29     id[timer] = p;
 30     for(int i = h[p]; i; i = e[i].pre)
 31     {
 32         int to = e[i].to;
 33         if(to == fa) continue;
 34         dfs(to, p);
 35     }
 36     dfn[p][1] = ++timer;
 37 }
 38 
 39 struct seg_tree
 40 {
 41     int l, r, tag;
 42     LL c;
 43 }tr[maxn<<3];
 44 
 45 void pushdown(int p)
 46 {
 47     if(tr[p].tag) tr[p].c = 1LL << tr[p].tag;
 48     if(tr[p].tag && tr[p].l != tr[p].r) tr[lson].tag = tr[rson].tag = tr[p].tag;
 49     tr[p].tag = 0;
 50 }
 51 
 52 void pushup(int p)
 53 {
 54     pushdown(lson), pushdown(rson);
 55     tr[p].c = tr[lson].c | tr[rson].c;
 56 }
 57 
 58 void build(int p, int l, int r)
 59 {
 60     tr[p].l = l, tr[p].r = r, tr[p].tag = tr[p].c = 0LL;
 61     if(l < r) build(lson, l, mid), build(rson, mid + 1, r), pushup(p);
 62     else if(id[l]) tr[p].c = 1LL << col[id[l]];
 63 }
 64 
 65 void modify(int p, int l, int r, int c)
 66 {
 67     if(tr[p].l >= l && tr[p].r <= r) tr[p].tag = c;
 68     pushdown(p);
 69     if(tr[p].l >= l && tr[p].r <= r) return;
 70     if(l <= mid) modify(lson, l, r, c);
 71     if(r > mid) modify(rson, l, r, c);
 72     pushup(p);
 73 }
 74 
 75 LL query(int p, int l, int r)
 76 {
 77     pushdown(p);
 78     if(tr[p].l >= l && tr[p].r <= r) return tr[p].c;
 79     LL ret = 0LL;
 80     if(l <= mid) ret |= query(lson, l, r);
 81     if(r > mid) ret |= query(rson, l, r);
 82     pushup(p);
 83     return ret;
 84 }
 85 
 86 int main(void)
 87 {
 88     int n, m;
 89     scanf("%d %d", &n, &m);
 90     for(int i = 1; i <= n; i++) scanf("%d", col + i);
 91     for(int i = 1; i < n; i++)
 92     {
 93         int u, v;
 94         scanf("%d %d", &u, &v);
 95         add(u, v), add(v, u);
 96     }
 97     dfs(1, 0);
 98     build(1, 1, timer);
 99     for(int i = 1; i <= m; i++)
100     {
101         int op, v, c, ans = 0;
102         scanf("%d", &op);
103         if(op == 1)
104         {
105             scanf("%d %d", &v, &c);
106             modify(1, dfn[v][0], dfn[v][1], c);
107         }
108         else
109         {
110             scanf("%d", &v);
111             LL ret = query(1, dfn[v][0], dfn[v][1]);
112             while(ret) ans += ret & 1LL, ret >>= 1LL;
113             printf("%d
", ans);
114         }
115     }
116     return 0;
117 }

Aguin

1.23

HDU 5611 Baby Ming and phone number

SBSBSBSBSBSB

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 int d[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
 7 char * num[22] = {
 8     "00000", "11111", "22222", "33333", "44444", "55555", "66666", "77777", "88888", "99999",
 9     "01234", "12345", "23456", "34567", "45678", "56789",
10     "98765", "87654", "76543", "65432", "54321", "43210"
11 };
12 
13 bool judge(char * s)
14 {
15     for(int i = 0; i < 22; i++) if(strcmp(num[i], s + 6) == 0) return true;
16     int y = ( s[3] - '0' ) * 1000 + ( s[4] - '0' ) * 100 + ( s[5] - '0' ) * 10 + ( s[6] - '0' );
17     int m = ( s[7] - '0' ) * 10 + ( s[8] - '0' );
18     int da = ( s[9] - '0' ) * 10 + ( s[10] - '0' );
19     if(y < 1980 || y > 2016) return false;
20     int leap = 0;
21     if( ( (y % 4 == 0) && (y % 100 != 0) ) || (y % 400 == 0) ) leap = 1;
22     if(m < 1 || m > 12) return false;
23     if(da >= 1 && da <= d[m] + (m == 2 && leap) ) return true;
24     return false;
25 }
26 
27 int main(void)
28 {
29     int T;
30     scanf("%d", &T);
31     while(T--)
32     {
33         LL n, a, b, ans = 0;
34         scanf("%I64d%I64d%I64d", &n, &a, &b);
35         for(int i = 0; i < n; i++)
36         {
37             char ss[20];
38             scanf("%s", ss);
39             if(judge(ss)) ans += a;
40             else ans += b;
41         }
42         printf("%I64d
", ans);
43     }
44     return 0;
45 }

Aguin