首页 > 代码库 > CSU-ACM暑假集训基础组训练赛(4)解题报告
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 }
•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, mid10 #define Rson o<<1|1 , mid+1 , R11 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\n" , query(1, 1 ,N) ) ;62 }63 return 0;64 }
•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\n" , ans[i]) ;50 51 return 0;52 }
•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 }
•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 }
•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 }else24 {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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。