Codeforces Round #FF (Div. 1)-A,B,C

A:DZY Loves Sequences

一开始看错题了。。sad。

题目很简单，做法也很简单。DP一下就好了。

dp[i][0]:到当前位置，没有任何数改变，得到的长度。

dp[i][1]:到当前位置，改变了一个数，得到的长度

不过需要正向求一遍，然后反向求一遍。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; #define maxn 110000 int dp[maxn][3]; int num[maxn]; int a[maxn]; int n; void 
       dos(int maxx) { memset(dp,0,sizeof(dp)); memset(num,-1,sizeof(num)); for(int i=n; i>=1; i--) { if(a[i]
       
        =a[i+1]) { if(dp[i][1]
        
         a[i-1]) { dp[i][0]=dp[i-1][0]+1; } else { dp[i][0]=1; } dp[i][1]=dp[i][0]; num[i]=a[i]; if(a[i]>num[i-1]) { if(dp[i][1]
         
          B：DZY Loves Modification
          
 
          
我们可以发现选择一个横行，竖行的大小顺序不变，只是每一个竖行都下降了p。
 
          
所以我们可以枚举选择了x个横行，y个竖行。





 
          

          
#include
           
            
#include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  using namespace std; #define maxn 1100 #define LL __int64 int mp[maxn][maxn]; int hh[maxn]; int ll[maxn]; LL ph[1100000]; LL pl[1100000]; priority_queue
                 
                  que; int n,m,k,p; void chu() { ph[0]=pl[0]=0; while(!que.empty())que.pop(); for(int i=1;i<=n;i++) { que.push(hh[i]); } for(int i=1;i<=k;i++) { int x=que.top(); que.pop(); ph[i]=ph[i-1]+(LL)x; x=x-p*m; que.push(x); } while(!que.empty())que.pop(); for(int i=1;i<=m;i++) { que.push(ll[i]); } for(int i=1;i<=k;i++) { int x=que.top(); que.pop(); pl[i]=pl[i-1]+(LL)x; x=x-p*n; que.push(x); } } int main() { while(~scanf("%d%d%d%d",&n,&m,&k,&p)) { memset(hh,0,sizeof(hh)); memset(ll,0,sizeof(ll)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&mp[i][j]); hh[i]+=mp[i][j]; ll[j]+=mp[i][j]; } } chu(); LL ans=pl[k]; for(int i=1;i<=k;i++) { LL x=(LL)i*(LL)(k-i); x=(LL)x*(LL)p; ans=max(ans,pl[k-i]+ph[i]-x); } cout<
                  
                   C：DZY Loves Fibonacci Numbers
                   
 
                   
主要是两个性质：
 
                   
1,两个斐波那契数列相加依然是一个斐波那契数列。
 
                   
2，根据斐波那契数列的前两项可以O（1）的时间内得出任意一个位置的斐波那契数，和任意长度的斐波那契数列的合。
 
                   
剩下的东西就是简单的区间求和问题了。
 
                   

                   
#include
                    
                     
#include
                     
                       #include
                      
                        #include
                       
                         #include
                        
                          #include
                         
                           #include
                          
                            #include