CSU-ACM暑假集训基础组训练赛(4)解题报告

•Problem A SPOJ SUB_PROB AC自动机

•题意：给定一个长为M（M≤100000 ）的文本串，和N（N≤1000）个长度不超过2000的模式串，问每个模式串是否在文本串中出现过？

•几乎和周一课件上的第一个例题一模一样。。

•把文本串丢到AC自动机里面去跑。

•注意：

•1.可能有两个相同的模式串（略坑吧。）

•2.一个模式串可能是另一个模式串的后缀，即如果一个点的fail指针指向的点是一个“危险节点”，那么它本身也是一个“危险节点”。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 const int maxn = 1000050 ;
 8 const int sigma_size = 52 ;
 9 
10 int ID[1010] , tot ;
11 char text[100050] , word[2111] ;
12 bool flag[1010] ;
13 int son[maxn][sigma_size] , val[maxn] , f[maxn] , last[maxn] , q[maxn], sz ;
14 
15 inline int idx(char c) {
16     if(c<='Z') return c - 'A' ;
17     else return c - 'a' + 26 ;
18 }
19 
20 int Insert(char *s){
21     int u = 0 ;
22     for(int i=0 ; s[i] ; i++) {
23         int v = idx(s[i]) ;
24         if(!son[u][v]) son[u][v] = ++sz ;
25         u = son[u][v] ;
26     }
27     if(!val[u]) val[u] = ++tot ;
28     return val[u];
29 }
30 
31 void get_fail() {
32     int rear = 0 ;
33     f[0] = 0 ;
34     for(int c=0; c<sigma_size ; c++) {
35         int u = son[0][c] ;
36         if(u) f[u] = last[u] = 0 , q[rear++] = u ;
37     }
38     for(int _i=0; _i<rear ; _i++) {
39         int u = q[_i] ;
40         for(int c=0; c<sigma_size; c++){
41             int v = son[u][c] ;
42             if(!v) { son[u][c] = son[f[u]][c] ; continue ; }
43             q[rear++] = v;
44             int x = f[u] ;
45             while(x && !son[x][c]) x = f[x] ;
46             f[v] = son[x][c] ;
47             last[v] = val[f[v]] ? f[v] : last[f[v]] ;
48         }
49     }
50 }
51 
52 void print(int u){
53     while(u) {
54         flag[val[u]] = true ;
55         u = last[u] ;
56     }
57 }
58 
59 void Find(char *s){
60     int j = 0;
61     for(int i=0; s[i] ; i++) {
62         int c=idx(s[i]);
63         while(j && !son[j][c]) j = f[j] ;
64         j = son[j][c] ;
65         print(j) ;
66     }
67 }
68 
69 int main()
70 {
71     gets(text) ;
72     int n ;
73     scanf("%d", &n) ; getchar() ;
74     for(int i=1; i<=n; i++) {
75         scanf("%s" , word) ;
76         ID[i] = Insert(word);
77     }
78     Find(text) ;
79     for(int i=1; i<=n; i++) {
80         if(flag[ ID[i] ]) puts("Y") ;
81         else puts("N") ;
82     }
83     return 0 ;
84 }

View Code

•Problem B SPOJ DCEPC11I 线段树

•题意：对一个长为N（N≤100000）的序列A[]进行Q（Q≤100000）次操作，2种操作：

•(1)“0 st en” : A[st]增加1 , A[st+1]增加2 ...... A[en]增加 en - st + 1 .

•(2)“1 st en” : 询问区间和A[st] + A[st+1] + ..... + A[en]

•典型的线段树成段更新，成段查询。

•利用到的性质：两个等差数列对应项相加得到的任是等差数列。

•因此“懒惰标记”只需要记录首项a[]和公比d[]即可。

•要记得等差数列求和公式。

•数据类型的范围long long

•难点：标记记录什么，标记如何下传。

 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 = 100005 ;
 8 
 9 #define Lson o<<1, L, mid
10 #define Rson o<<1|1 , mid+1 , R
11 
12 LL a[maxn<<2] , d[maxn<<2] , sum[maxn<<2] ;
13 
14 void pushup(int o){
15     sum[o] = sum[o<<1] + sum[o<<1|1] ;
16 }
17 void pushdown(int o , int c1 , int c2) {
18     if(a[o] || d[o]) {
19         LL a1 = a[o] , a2 = a[o] + (LL)d[o] * c1 ;
20         sum[o<<1] += a1*c1 + c1*(c1-1)*d[o]/2 ;
21         sum[o<<1|1] += a2*c2 + c2*(c2-1)*d[o]/2;
22         a[o<<1] += a1 , a[o<<1|1] += a2 ;
23         d[o<<1] += d[o] , d[o<<1|1] += d[o] ;
24         a[o] = d[o] = 0 ;
25     }
26 }
27 
28 int l , r ;
29 void update(int o ,int L ,int R){
30     if(l<=L && R<=r) {
31         LL a1 = L - l + 1 , c1 = R - L + 1 ;
32         sum[o] += a1*c1 + c1*(c1-1)/2;
33         a[o] += a1 , d[o]++ ;
34         return ;
35     }
36     int mid = (L+R)>>1;
37     pushdown(o, mid-L+1 , R-mid);
38     if(l<=mid) update(Lson) ;
39     if(r>mid)  update(Rson) ;
40     pushup(o);
41 }
42 
43 LL query(int o ,int L ,int R) {
44     if(l<=L && R<=r) return sum[o];
45     int mid = (L+R)>>1 ;
46     pushdown(o , mid-L+1 , R-mid) ;
47     LL ret = 0 ;
48     if(l<=mid) ret += query(Lson) ;
49     if(r> mid) ret += query(Rson) ;
50     return ret;
51 }
52 
53 int main()
54 {
55     int N , Q;
56     scanf("%d%d", &N ,&Q);
57     while(Q--){
58         int op ;
59         scanf("%d%d%d", &op, &l ,&r) ;
60         if(op == 0) update(1, 1 , N) ;
61         else printf("%lld
" , query(1, 1 ,N) ) ;
62     }
63     return 0;
64 }

View Code

•Problem C SPOJ RATING 二分、树状数组

•题意：有N（N≤300000）coder，每个coder[i]有两个属性A[i] 和 H[i] , 。

•当(A[i] ≥ A[j] && H[i] ≥ H[j]) && (A[i] > A[j] || H[i] > H[j]) 时，认为coder[i] 比 coder[j]优秀，问每个coder[i]比多少个其他的coder优秀？

•一个可行的方法：

•分为两类：

• ① A[i] >A[j] && H[i] >= H[j]

• ② A[i] == A[j] && H[i] > H[j]

•按属性A[]从小到大依次考虑每个coder[i] , 用树状数组动态维护所有在i前面且属性A比i的属性A小的 coder的属性H的信息 , 这样就可以在O(logn)统计第①类的个数, 第②类的个数随便搞搞就可以了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 #define F first
 7 #define S second
 8 #define MP(a,b) make_pair( make_pair(a,b) , -1 )
 9 typedef pair< pair<int,int> , int> coder ;
10 const int maxn = 300010 ;
11 const int N = 100000 ;
12 
13 int sum[N+1] , ans[maxn] ;
14 coder p[maxn] ;
15 
16 inline int lowbit(int x){
17     return x & -x ;
18 }
19 void update(int x) {
20     for(; x<=N; x+=lowbit(x))  sum[x]++ ;
21 }
22 int query(int x) {
23     int ret = 0 ;
24     for(; x>0 ; x-=lowbit(x)) ret += sum[x] ;
25     return ret ;
26 }
27 
28 int main()
29 {
30     int n ;
31     scanf("%d", &n);
32     for(int i=1; i<=n; i++)
33         scanf("%d%d", &p[i].F.F , &p[i].F.S) , p[i].S = i ;
34     sort(p+1 , p+1+n) ;
35     int y = 1;
36 
37     for(int i=1; i<=n; i++) {
38         int u = p[i].S ;
39         while(y<i && p[y].F.F < p[i].F.F) {
40             update(p[y++].F.S) ;
41         }
42         ans[u] += query(p[i].F.S) ;
43         if(y < i) {
44             ans[u] += lower_bound(p+y , p+i , MP(p[i].F.F , p[i].F.S)) - p  - y ;
45         }
46     }
47 
48     for(int i=1; i<=n; i++)
49         printf("%d
" , ans[i]) ;
50 
51     return 0;
52 }

View Code

•Problem D UVA - 10319 2-SAT

•详情见解题报告PPT

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 using namespace std;
 7 const int maxn = 65;
 8 
 9 int N , M , K;
10 struct TwoSat{
11     int n ;
12     vector<int> g[maxn*2] ;
13     bool mark[maxn*2] ;
14     int S[maxn*2] , c;
15 
16     bool dfs(int x) {
17         if(mark[x^1]) return false ;
18         if(mark[x] ) return true ;
19         mark[x] = true ;
20         S[c++] =  x ;
21         for(size_t i=0; i <g[x].size() ; i++)
22             if(!dfs(g[x][i])) return false ;
23         return true ;
24     }
25 
26     void init(int n) {
27         this->n = n;
28         for(int i=0; i<n*2; i++) g[i].clear() ;
29         memset(mark , 0, sizeof(mark)) ;
30     }
31 
32     void add(int u , int v) {
33         g[u].push_back(v) ;
34     }
35 
36     bool solve() {
37         for(int i=0; i<n*2; i+=2) {
38             if(!mark[i] && !mark[i^1]) {
39                 c= 0 ;
40                 if(!dfs(i)) {
41                     while(c > 0) mark[S[--c]] = false ;
42                     if(!dfs(i^1)) return false ;
43                 }
44             }
45         }
46         return true ;
47     }
48 }t;
49 
50 int main()
51 {
52     int T;
53     scanf("%d", &T) ;
54     while(T--) {
55         scanf("%d%d%d" ,&N ,&M, &K);
56         t.init(N+M) ;
57         int u1 , v1 , u2 , v2 ;
58         int p1 , p2 , p3 , p4 ;
59 
60         while(K--) {
61             scanf("%d%d%d%d", &u1 ,&v1 , &u2 ,&v2)  ;
62             u1-- , u2-- , v1-- , v2-- ;
63             if(u1 == u2 && v1 == v2) continue ;
64             else if(u1 == u2) {
65                 p1 = u1*2 + (v1 < v2) ;
66                 t.add(p1^1 , p1) ;
67             }
68             else if(v1 == v2) {
69                 p1 = (N+v1)*2 + (u1 < u2) ;
70                 t.add(p1^1 , p1) ;
71             }
72             else {
73                 p1 = u1*2 + (v1 < v2);
74                 p2 = (N+v2)*2 + (u1 < u2) ;
75                 p3 = (N+v1)*2 + (u1 < u2) ;
76                 p4 = u2*2 + (v1 < v2) ;
77                 t.add(p1^1 , p3) , t.add(p1^1 , p4) ;
78                 t.add(p2^1 , p3) , t.add(p2^1 , p4) ;
79                 t.add(p3^1 , p1) , t.add(p3^1 , p2) ;
80                 t.add(p4^1 , p1) , t.add(p4^1 , p2) ;
81             }
82         }
83 
84         if(t.solve()) puts("Yes") ;
85         else puts("No") ;
86     }
87     return 0;
88 }

View Code

•Problem E AIZU 0024 签到题

 1 #include <iostream> 
 2 #include <cmath> 
 3 using namespace std; 
 4 int main() 
 5 {
 6        double y,t,mv; 
 7        while(cin>>mv)
 8       { 
 9               t=mv/9.8; y=t*t*4.9; double n=(y+5)/5;        
10               cout<<ceil(n)<<endl; 
11       } 
12       return 0; 
13      }

View Code

•Problem F Codeforces 81A 模拟

•这是阮俊同学写的。

 1 #include <iostream>
 2 #include <string>
 3 #include <stack>
 4 using namespace std;
 5 
 6 
 7 int main()
 8 {
 9     string s;
10     cin>>s;
11     stack<char> sta;
12     for(int i=0;i<s.length();i++)
13     {
14         if(sta.empty())
15         {
16             sta.push(s.at(i));
17             continue;
18         }
19         char ch = sta.top();
20         if(s.at(i)!=ch)
21         {
22             sta.push(s.at(i));
23         }else
24         {
25             sta.pop();
26         }
27     }
28     stack<char> sta1;
29     while(!sta.empty())
30     {
31         sta1.push(sta.top());
32         sta.pop();
33     }
34     while(!sta1.empty())
35     {
36         cout<<sta1.top();
37         sta1.pop();
38     }
39 
40     return 0;
41 }

View Code