第九周 7.12-7.18

7.12

HDU 5280 Senior's Array

补一个O(n)的dp方法。

dp1[i]为i左端最大连续和。dp2[i]为i右端最大连续和。

枚举改p的位置。

若p在最大区间和中。则ans为p左右最大连续和加上p。

若p不在最大区间和中。则ans为所有最大连续和中最大的。

注意区间取整个数组时。p是一定包含在内的。

即第二种情况不能取整个数组。

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 LL dp1[1001],dp2[1001],a[1001];
 6 
 7 int main(void)
 8 {
 9     int T; cin>>T;
10     while(T--)
11     {
12         int n,p; scanf("%d%d",&n,&p);
13         for(int i=1;i<=n;i++) scanf("%I64d",a+i);
14         dp1[1]=a[1]; dp2[n]=a[n];
15         for(int i=2;i<=n;i++) dp1[i]=max(a[i],dp1[i-1]+a[i]);
16         for(int i=n-1;i>=1;i--) dp2[i]=max(a[i],dp2[i+1]+a[i]);
17         LL ans=-10000000000000LL;
18         for(int i=1;i<=n;i++) ans=max(ans,dp1[i]+dp2[i]-2*a[i]+p);
19         for(int i=1;i<n;i++) ans=max(ans,dp1[i]);
20         for(int i=n;i>1;i--) ans=max(ans,dp2[i]);
21         printf("%I64d
",ans);
22     }
23     return 0;
24 }

Aguin

7.13

结果上讲的确什么都没干。

7.14

补一个上次的BC

HDU 5282 Senior's String

本来是想昨天补的。毕竟高代考完≈放假了。

然而磨磨唧唧没看懂状态转移方程。

今天反复看那截官方题解。又看了别人代码。才算差不多懂。

dp数组就是求LCS。

用f[i][j]表示在X串的前i个字符中，有多少个长度为dp[i][j]的子序列在Y的前j个字符中也出现了。

注意一下空串的情况。所以f初始化是dp[i][j]==0时f[i][j]=1。其余为0。

转移分两个情况。

i) X[i]不属于长度为dp[i][j]的子列。只有dp[i][j]==dp[i-1][j]时才会有这种情况。那么f[i][j]+=f[i−1][j]。

ii) X[i]属于长度为dp[i][j]的子列。这时要先找到Y中最后一个和X[i]的字符。位置标识为p。

因为X[i]结尾的长度为dp[i][j]的子列数等于在最后一对匹配的字符前面且长度为dp[i][j]-1的子列数。

即满足dp[i−1][p−1]+1==dp[i][j]时。有f[i][j]+=f[i−1][p−1]。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 # define MOD 1000000007
 6 char x[1005],y[1005];
 7 long long dp[1005][1005],f[1005][1005];
 8 
 9 int main(void)
10 {
11     int T;cin>>T;
12     while(T--)
13     {
14         scanf("%s %s",x+1,y+1);
15         int lx=strlen(x+1),ly=strlen(y+1);
16     
17         memset(dp,0,sizeof(dp));    
18         for(int i=1;i<=lx;i++)
19             for(int j=1;j<=ly;j++)
20             {
21                 if(x[i]==y[j]) dp[i][j]=dp[i-1][j-1]+1;
22                 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
23             }
24 
25         memset(f,0,sizeof(f));
26         for(int i=0;i<=lx;i++)
27             for(int j=0;j<=ly;j++)
28             {
29                 if(dp[i][j]==0) f[i][j]=1;
30                 else
31                 {
32                     if(dp[i-1][j]==dp[i][j]) {f[i][j]+=f[i-1][j]; f[i][j]%=MOD;}
33                     for(int p=j;p>0;p--)
34                         if(y[p]==x[i])
35                         {
36                             if(dp[i-1][p-1]+1==dp[i][j]) {f[i][j]+=f[i-1][p-1]; f[i][j]%=MOD;}
37                             break;
38                         }
39                 }
40             }
41         printf("%I64d
",f[lx][ly]);
42     }
43     return 0;
44 }

Aguin

可以先把所有p用一个数组先记下。然而并没有快。

7.15

背英语。

7.16

考完心情坏坏。补BC。

迷之RE。明日再调。

7.17

HDU 5283 Senior's Fish

发现自己蠢死了。

#define maxn 100000+10

然后线段树大小写tree[maxn*4]。

。。。。。。。。。。。。。。。。

算是温习了一下线段树和lazytag。第一次补完一套BC。

  1 # include <iostream>
  2 # include <cstdio>
  3 # include <algorithm>
  4 using namespace std;
  5 # define maxn 100010
  6 # define INF 2147483647
  7 int X[4],Y[4],cX[maxn],cY[maxn];
  8 
  9 struct node
 10 {
 11     int l,r,Xmax[4],Ymax[4],Xlazy,Ylazy,sum[4];
 12 } tree[maxn*4];
 13 
 14 void pushup(int pos)
 15 {
 16     for(int i=0;i<4;i++)
 17     {
 18         tree[pos].Xmax[i]=max(tree[pos*2].Xmax[i],tree[pos*2+1].Xmax[i]);
 19         tree[pos].Ymax[i]=max(tree[pos*2].Ymax[i],tree[pos*2+1].Ymax[i]);
 20         tree[pos].sum[i]=tree[2*pos].sum[i]+tree[2*pos+1].sum[i];
 21     }
 22     return;
 23 }
 24 
 25 void pushdown(int pos)
 26 {
 27     if(tree[pos].Xlazy)
 28     {
 29         tree[2*pos].Xlazy+=tree[pos].Xlazy;
 30         tree[2*pos+1].Xlazy+=tree[pos].Xlazy;
 31         for(int i=0;i<4;i++)
 32         {
 33             tree[pos*2].Xmax[i]+=tree[pos].Xlazy;
 34             tree[pos*2+1].Xmax[i]+=tree[pos].Xlazy;
 35         }
 36         tree[pos].Xlazy=0;
 37     }
 38     if(tree[pos].Ylazy)
 39     {
 40         tree[2*pos].Ylazy+=tree[pos].Ylazy;
 41         tree[2*pos+1].Ylazy+=tree[pos].Ylazy;
 42         for(int i=0;i<4;i++)
 43         {
 44             tree[pos*2].Ymax[i]+=tree[pos].Ylazy;
 45             tree[pos*2+1].Ymax[i]+=tree[pos].Ylazy;
 46         }
 47         tree[pos].Ylazy=0;
 48     }
 49     return;
 50 }
 51 
 52 void buildtree(int pos,int l,int r)
 53 {
 54     tree[pos].l=l; tree[pos].r=r;
 55     tree[pos].Xlazy=tree[pos].Ylazy=0;
 56     if(l<r)
 57     {
 58         buildtree(2*pos,l,(l+r)/2);
 59         buildtree(2*pos+1,(l+r)/2+1,r);
 60         pushup(pos);
 61     }
 62     else
 63     {
 64         for(int i=0;i<4;i++)
 65         {
 66             if(cX[l]<=X[i]&&cY[l]<=Y[i])
 67             {
 68                 tree[pos].Xmax[i]=cX[l];
 69                 tree[pos].Ymax[i]=cY[l];
 70                 tree[pos].sum[i]=1;
 71             }
 72             else
 73             {
 74                 tree[pos].Xmax[i]=tree[pos].Ymax[i]=-INF;
 75                 tree[pos].sum[i]=0;
 76             }
 77         }
 78     }
 79     return;
 80 }
 81 
 82 void Xmove(int pos,int l,int r,int d)
 83 {
 84     if(tree[pos].l>=l&&tree[pos].r<=r)
 85     {
 86         tree[pos].Xlazy+=d;
 87         for(int i=0;i<4;i++)
 88             if(tree[pos].Xmax[i]!=-INF)
 89                 tree[pos].Xmax[i]+=d;
 90     }
 91     else
 92     {
 93         pushdown(pos);
 94         if(l<=(tree[pos].l+tree[pos].r)/2) Xmove(2*pos,l,r,d);
 95         if(r>=(tree[pos].l+tree[pos].r)/2+1) Xmove(2*pos+1,l,r,d); 
 96         pushup(pos);
 97     }
 98     return;
 99 }
100 
101 void Ymove(int pos,int l,int r,int d)
102 {
103     if(tree[pos].l>=l&&tree[pos].r<=r)
104     {
105         tree[pos].Ylazy+=d;
106         for(int i=0;i<4;i++)
107             if(tree[pos].Ymax[i]!=-INF)
108                 tree[pos].Ymax[i]+=d;
109     }
110     else
111     {
112         pushdown(pos);
113         if(l<=(tree[pos].l+tree[pos].r)/2) Ymove(2*pos,l,r,d);
114         if(r>=(tree[pos].l+tree[pos].r)/2+1) Ymove(2*pos+1,l,r,d); 
115         pushup(pos);
116     }
117     return;
118 }
119 
120 void refresh(int pos)
121 {
122     for(int i=0;i<4;i++)
123     {
124         if(tree[pos].Xmax[i]>X[i]||tree[pos].Ymax[i]>Y[i])
125         {
126             tree[pos].Xmax[i]=tree[pos].Ymax[i]=-INF;
127             tree[pos].sum[i]=0;
128             if(tree[pos].l!=tree[pos].r)
129             {
130                 pushdown(pos);
131                 refresh(2*pos); refresh(2*pos+1);
132                 pushup(pos);
133             }
134         }
135     }
136     return;
137 }
138 
139 int query(int pos,int l,int r,int i)
140 {
141     if(tree[pos].l>=l&&tree[pos].r<=r) return tree[pos].sum[i];
142     int ret=0;
143     if(l<=(tree[pos].l+tree[pos].r)/2) ret+=query(2*pos,l,r,i);
144     if(r>=(tree[pos].l+tree[pos].r)/2+1) ret+=query(2*pos+1,l,r,i);
145     return ret;
146 }
147 
148 int main(void)
149 {
150     int T; cin>>T;
151     while(T--)
152     {
153         int n; scanf("%d",&n);
154         int x1,y1,x2,y2;
155         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
156         X[0]=X[3]=x2; X[1]=X[2]=x1-1;
157         Y[0]=Y[2]=y2; Y[1]=Y[3]=y1-1;
158         for(int i=1;i<=n;i++) scanf("%d%d",cX+i,cY+i);
159         buildtree(1,1,n);
160         int m; scanf("%d",&m);
161         while(m--)
162         {
163             int type; scanf("%d",&type);
164             if(type==1)
165             {
166                 int l,r,d; scanf("%d%d%d",&l,&r,&d);
167                 Xmove(1,l,r,d); refresh(1);
168             }
169             else if(type==2)
170             {
171                 int l,r,d; scanf("%d%d%d",&l,&r,&d);
172                 Ymove(1,l,r,d); refresh(1);
173             }
174             else
175             {
176                 int l,r; scanf("%d%d",&l,&r);
177                 printf("%d
",query(1,l,r,0)+query(1,l,r,1)-query(1,l,r,2)-query(1,l,r,3));
178             }
179         }
180     }
181     return 0;
182 }

Aguin

7.18

打了个BC。几个计算客。待补。