为什么没有8.20的考试？因为博主太蒟蒻不会NTT或是FFT。

 

T1 题意简述：

 

Description

GZOI队员们到X镇游玩。X镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成m*n个区域，这些区域标从北到南、从西到东的坐标标识为从坐标 (1,1) 到坐标(m,n)。 GZOI队员们预先对这m*n个区域打分V(i，j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便游玩，队员们需要选定一个连续的区域集合作为活动范围。例如，如果他们选择了最西北的区域(m1，nl)和最东南(m2，n2)区域(m1<=m2，n1<=n2),那他们的活动范围是 {D(i，j)|m1<=i<=m2，n1<=j<=n2}，其游览总分则为这些活动范围的区域总分。 GZOI队员们希望他们活动范围内的区域的分值总和最大。你的任务是编写一个程序，求出他们的活动范围(m1，nl)，(m2，n2〉。 

Input

输入第一行为整数m(1<=m<=200)，n(1<=n<=200)，用空格隔开 下面为m行，每行有n列整数，其中第i行第j列的整数，代表V(i,j)，每个整数之间用空格隔开，每个整数的范围是 [-200000,200000]，输入数据保证这些整数中，至少存在一个正整数。

Output

输出只有一行，为最高的分值。

 

   解题思路：求最大子矩阵。

             每一列的元素求前缀和后求最大子段和即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long longusing namespace std;ll n,m,ans,a[201][201],sum[201][201],dp[201],mns[201];ll sol(){ ll tmp=0; memset(dp,0,sizeof(dp)); for(ll i=1;i<=m;i++) dp[i]=max(dp[i-1]+mns[i],mns[i]),tmp=max(tmp,dp[i]); return tmp;}int main(){ scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) scanf("%lld",&a[i][j]); for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) sum[i][j]=sum[i-1][j]+a[i][j]; for(ll i=1;i<=n;i++) for(ll j=i;j<=n;j++) { for(ll k=1;k<=m;k++) mns[k]=sum[j][k]-sum[i-1][k]; ans=max(ans,sol()); } printf("%lld\n",ans); return 0;}
          
         
        
       
      
     

 

---

 

T2 题意简述：

 

Description

Input

Output

Data Constraint

 

   解题思路：二分答案。

             横纵坐标分开计算。输入时记录下物体输入顺序。

             把物体按坐标排序，然后按照i*a[i]-sum[i-1]统计距离。

             发现这样是O(nlog^2(n))，没法过全部测试点。

             出题人提供了一个特鬼畜的方法：

             在二分答案前先把物体按坐标排序，记录下坐标排名。

             二分答案时按照排名直接O(n)排序。此法叫做小学生排序(真的有这个排序)。

             咳咳咳...做的时候才发现出题人的方法好像会T...吸氧才能过...

             GZZ大佬提供了一个4个树状数组的方法。由于博主太懒所以没改。

#pragma GCC optimize(3)#include
     
      #include
      
       #include
       
         #include
        
         #include
         
          #include
          
           #define ll long longusing namespace std;ll n,m,ans,xar[600001],yar[600001],xno[600001],yno[600001],hlp[600001];bool cmpx(ll x,ll y){ return xar[x]
           
            m);}int main(){ scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) { scanf("%lld%lld",&xar[i],&yar[i]); xno[i]=i,yno[i]=i; } sort(xno+1,xno+1+n,cmpx); sort(yno+1,yno+1+n,cmpy); for(ll i=1;i<=n;i++) hlp[xno[i]]=i; memcpy(xno,hlp,sizeof(hlp)); for(ll i=1;i<=n;i++) hlp[yno[i]]=i; memcpy(yno,hlp,sizeof(hlp)); ll l=1,r=n; while(l<=r) { ll mid=(l+r)>>1; if(chk(mid)) ans=mid,r=mid-1; else l=mid+1; } if(l>n) printf("-1\n"); else printf("%lld\n",ans); return 0;}
           
          
         
        
       
      
     

 

---

 

T3 题意简述：

 

Description

Input

Output

Data Constraint

 

   解题思路：dp。

             设dp[i]表示枚举到第i个人的总方案数，sum[i]表示前i个人中0的个数-1的个数。

             转移方程为dp[i]+=dp[j] (abs(sum[i]-sum[j])<=k)

             O(n^2)过不了，可以用树状数组或线段树优化。这里介绍线段树做法。

             每次转移时统计[sum[i]-k,sum[i]+k]的方案数，然后把dp[i]加到线段树的sum[i]处。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define MOD 1000000007using namespace std;ll n,k,a[100001],sum[100001],dp[100001];ll tree[800001];void revise(ll now,ll l,ll r,ll pos,ll num){ if(l==r) {(tree[now]+=num)%=MOD;return;} ll mid=(l+r)>>1; if(pos<=mid) revise(now<<1,l,mid,pos,num); else revise(now<<1|1,mid+1,r,pos,num); tree[now]=tree[now<<1]+tree[now<<1|1];}ll query(ll now,ll l,ll r,ll L,ll R){ if(L<=l&&r<=R) return tree[now]%MOD; ll mid=(l+r)>>1; if(R<=mid) return query(now<<1,l,mid,L,R)%MOD; else if(L>mid) return query(now<<1|1,mid+1,r,L,R)%MOD; else return (query(now<<1,l,mid,L,R)%MOD+query(now<<1|1,mid+1,r,L,R)%MOD)%MOD;}int main(){ scanf("%lld%lld",&n,&k); for(ll i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]; if(!a[i]) sum[i]++; else sum[i]--; } dp[0]=1; revise(1,0,n<<1,n,1); for(ll i=1;i<=n;i++) { dp[i]=query(1,0,n<<1,max(sum[i]+n-k,0ll),min(sum[i]+n+k,n<<1)); revise(1,0,n<<1,sum[i]+n,dp[i]); }// for(ll i=1;i<=n;i++)// for(ll j=0;j