2016 Multi-University Training Contest 4

HDU 5773 LIS

题意：0可以替换任意一个数字，求最长严格上升序列

官方题解

最后答案加上0的个数肯定没错，但为什么每个数减去它之前0的个数？看下面这个数据

0 1 2 3 4 0 5

如果不减答案是7显然是错的

要满足严格递增，只有这样

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 // const int N = 1010;
22 // const int M = 1e6+10;
23 const long long MOD = 1LL<<32;
24 #define LL long long
25 #define LB long double
26 #define mi() (l+r)>>1
27 double const pi = acos(-1);
28 const double eps = 1e-8;
29 void fre(){freopen("in.txt","r",stdin);}
30 const int N=1e5+10;
31 int a[N];
32 int b[N];
33 int main(){
34     int T;
35     scanf("%d",&T);
36     for(int cas=1;cas<=T;cas++){
37         int n;
38         scanf("%d",&n);
39         int cnt=0,j=0;
40         for(int i=1;i<=n;i++){
41             int x;
42             scanf("%d",&x);
43             if(!x) cnt++;
44             else a[++j]=x-cnt;
45         }
46         printf("Case #%d: ",cas);
47         if(cnt==n){
48             printf("%d
",n);
49             continue;
50         }
51         b[1]=a[1];
52         int len=1;
53         for(int i=2;i<=j;i++){
54             if(a[i]>b[len]) b[++len]=a[i];
55             else{
56                 int pos=lower_bound(b+1,b+len+1,a[i])-b;
57                 b[pos]=a[i];
58             }
59         }
60         printf("%d
",len+cnt);
61     }
62     return 0;
63 }

View Code

HDU5763 DP

题意：母串匹配主串，匹配到的位置可以变成星号或不变，问最终的方案数

思路：dp[i]表示匹配到i总共有所少方案

dp[i]=dp[i-1]

第i位是匹配位置则：

dp[i+len2-1]+=dp[i-1];

之前写成了 dp[i+len2-1]+=dp[i-1]*2;

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 1e5+10;
22 const int M = 1e6+10;
23 const int MOD = 1e9+7;
24 #define LL long long
25 #define LB long double
26 #define mi() (l+r)>>1
27 double const pi = acos(-1);
28 const double eps = 1e-8;
29 void fre() {
30     freopen("in.txt","r",stdin);
31 }
32 
33 bool yes[N];
34 int Next[N];
35 char T[N],P[N];
36 void MakeNext(int m){
37     Next[0]=-1;
38     int i=0,j=-1;
39     while(i<m){
40         if(j==-1||P[i]==P[j]){
41             ++i,++j;
42             Next[i]=j;
43         }
44         else j=Next[j];
45     }
46 }
47 void KMP(int n,int m){
48     MakeNext(m);
49     int i=0,j=0,ret=0;
50     while(i<n){
51         if(T[i]==P[j]||j==-1)++i,++j;
52         else j=Next[j];
53         if(j==m){
54             ++ret;
55             yes[i-m+1]=1;
56             j=Next[j];//可以记录重复的
57             /*j=0;//不记录重复的*/
58         }
59     }
60     // return ret;
61 }
62 int dp[N];
63 int main(){
64     int t;
65     scanf("%d",&t);
66     for(int cas=1;cas<=t;cas++){
67         clc(yes,0);
68         clc(dp,0);
69         scanf("%s%s",T,P);
70         int len1=strlen(T),len2=strlen(P);
71         KMP(len1,len2);
72         dp[0]=1;
73         for(int i=1;i<=len1;i++){
74            dp[i]=(dp[i]+dp[i-1])%MOD;
75            if(yes[i])
76             dp[i+len2-1]=(dp[i+len2-1]+dp[i-1])%MOD;
77         }
78         printf("Case #%d: %d
",cas,dp[len1]);
79     }
80     return 0;
81 }

View Code

HDU5768 中国剩余定理+容斥+快速乘法

题意：[l,r] 内是7的倍数除去模a[i]余b[i]的数求个数

思路：

求个数显然用容斥原理。

枚举出每种状态以后中国剩余定理求满足条件的最小正整数解，注意在用中国剩余定理的时候乘法会爆longlong，这道题的GC就是快速乘法，长知识了。。。

mi两两互质，ans=(r-x)/M+1

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 1e5+10;
22 const int M = 1e6+10;
23 const int MOD = 1e9+7;
24 #define LL long long
25 #define LB long long double
26 #define mi() (l+r)>>1
27 double const pi = acos(-1);
28 const double eps = 1e-8;
29 void fre() {
30     freopen("in.txt","r",stdin);
31 }
32 
33 LL Q_mul(LL a,LL b,LL Mod){
34     LL ret;  
35     for(ret=0; b; b>>=1,a=(a+a)%Mod) if(b&1) ret=(ret+a)%Mod;
36     return ret; 
37 }
38 
39 void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y) {
40     if (!b) {
41         d = a;
42         x = 1;
43         y = 0;
44     }
45     else {
46         ex_gcd(b, a%b, d, y, x);
47         y -= x*(a/b);
48     }
49 }
50 
51 LL CRT(LL ai[],LL mi[],LL M,LL k){
52     LL ans=0;
53     for(int i=0; i<=k; ++i){
54         LL x,y,d,Mi=M/mi[i];
55         ex_gcd(Mi,mi[i],d,x,y);
56         ans=(ans+Q_mul(Q_mul(x,Mi,M),ai[i],M))%M;
57     }
58     return (ans+M)%M;
59 }
60 
61 LL a[N],b[N],ai[N],mi[N];
62 LL I_e(int n,LL r){
63     LL cnt=0,M,ans=0;
64     for(int i=1;i<(1<<n);i++){
65         cnt=0,M=1;
66         for(int j=1;j<=n;j++){
67             if(i&(1<<(j-1))){
68                 ai[cnt]=b[j],mi[cnt++]=a[j];
69                 M*=a[j];
70             }
71         }
72         mi[cnt]=7,ai[cnt]=0,M*=7;
73         LL x=CRT(ai,mi,M,cnt);
74         if(x>r) continue;
75         if(cnt&1) ans+=(r-x)/M+1;
76         else ans-=(r-x)/M+1;
77     }
78     return ans;
79 }
80 
81 int main(){
82     int T,n;
83     LL l,r;
84     scanf("%d",&T);
85     for(int cas=1;cas<=T;cas++){
86         scanf("%d%I64d%I64d",&n,&l,&r);
87         for(int i=1;i<=n;i++){
88             scanf("%d%d",&a[i],&b[i]);
89         }
90        printf("Case #%d: %I64d
",cas,r/7-(l-1)/7-I_e(n,r)+I_e(n,l));
91     }
92     return 0;
93 }

View Code

HDU 5769 后缀数组

题意：统计s2多少不同子串中含有s1

思路：

先看这个abcde

后缀abcde 不同子串(后缀的前缀) a ab abc abcd abcde

bcde b bc bcd bcde

....

所以不同子串数目为

这题要求包含x的不同子串，所以是

nxt[i]表示，i后面最近的x

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 // #define rson mid+1,r,rt<<1|1
21 const int N = 1e5+10;
22 const int M = 1e6+10;
23 const int MOD = 1e9+7;
24 #define LL long long
25 #define LB long double
26 // #define mi() (l+r)>>1
27 double const pi = acos(-1);
28 const double eps = 1e-8;
29 void fre(){freopen("in.txt","r",stdin);}
30 inline int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;}
31 
32 
33 //sa[] height[]从1开始到n结束
34 int wss[N],wv[N];
35 int sa[N],r[N],wx[N],wy[N];
36 bool cmp(int *r,int a,int b,int l){
37   return r[a]==r[b]&&r[a+l]==r[b+l];
38 }
39 void da(char *r,int n,int m){
40   //注意，这里的n必须比原始数组大小大1
41   n+=1;
42   int *x=wx,*y=wy;
43   for(int i=0;i<m;i++) wss[i]=0;
44   for(int i=0;i<n;i++) wss[x[i]=r[i]]++;
45   for(int i=1;i<m;i++) wss[i]+=wss[i-1];
46   for(int i=n-1;i>=0;i--) sa[--wss[x[i]]]=i;
47   //这里的x[i] 表示下标i的第一关键字排名
48   int i,j,p,*t;
49   for(j=1,p=1;p<n;j*=2,m=p){
50     for(p=0,i=n-j;i<n;i++) y[p++]=i;
51     for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
52     //此时的y[i] 表示第二关键字排第i的下标是y[i]
53     for(i=0;i<n;i++) wv[i]=x[y[i]];
54     for(i=0;i<m;i++) wss[i]=0;
55     for(i=0;i<n;i++) wss[wv[i]]++;
56     for(i=1;i<m;i++) wss[i]+=wss[i-1];
57     for(i=n-1;i>=0;i--) sa[--wss[wv[i]]]=y[i];
58     for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
59       x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++;
60   }
61 }
62 int rankk[N],height[N];
63 void calheight(char *r,int *sa,int n)  
64 {  
65      int  k=0;  
66      for(int i=1;i<=n;i++)  
67          rankk[sa[i]]=i;  
68      for(int i=0;i<n;i++)  
69      {  
70          if(rankk[i]==0)  
71              continue;  
72          k=max(0,k-1);  
73          int j=sa[rankk[i]-1];  
74          while(r[i+k]==r[j+k])  
75              k++;  
76          height[rankk[i]]=k;  
77      }  
78      return;  
79 }  
80 
81 char s1[N],s2[N];
82 int nx[N];
83 int main(){
84     int T;
85     scanf("%d",&T);
86     for(int cas=1;cas<=T;cas++){
87        scanf("%s%s",s1,s2);
88        int len=strlen(s2);
89        da(s2,len,128);
90        calheight(s2,sa,len);
91        nx[len]=len;
92        LL ans=0;
93        for(int i=len-1;i>=0;i--) nx[i]=(s2[i]==s1[0]?i:nx[i+1]);
94        for(int i=1;i<=len;i++) ans+=len-max(sa[i]+height[i],nx[sa[i]]);
95        printf("Case #%d: %I64d
", cas,ans);
96     }
97     return 0;
98 }

View Code