Codeforces Round #221 (Div. 2) B. I.O.U. C. Divisible by Seven D. Maximum Submatrix 2 解题报告 - c++编程基础

B. I.O.U.

题目链接：点击打开链接

思路：

将每个人得多少、欠多少综合起来看，一个关系内的debts最小就是得的总和或者欠的总和.

ps：这题数据貌似很水，很多代码都水过了...

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,/STACK:102400000,102400000) #define maxn 1005 #define MAXN 100005 #define mod 1000000007 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,ans,flag,cnt,best; int in[maxn],out[maxn]; void solve() { int i,j,t; ans=0; for(i=1;i<=n;i++) { ans+=max(0,in[i]-out[i]); } } int main() { int i,j,t,pos,x,y,u,v,w; while(~scanf(%d%d,&n,&m)) { memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(i=1;i<=m;i++) { scanf(%d%d%d,&u,&v,&w); out[u]+=w; in[v]+=w; } solve(); printf(%d ,ans); } return 0; } /* 3 3 1 2 2 2 3 3 3 1 4 7 5 1 2 10 2 3 1 2 4 1 4 1 5 6 7 8 */

C. Divisible by Seven

题目链接：点击打开链接

思路：将1、6、8、9取出来，因为1689的排列所有除7的余数都能得到，所以可以将其他的数放在最前面，然后后面的缺几就用1689的排列去补充就够了。举例：P为1689的排列，xxxP%7=((xxx0000%7)+(P%7))%7，求出xxx0000%7的余数为5的话，那么构造一个P使得(P%7)余2就能够使这个数被7整除了。

ps:当然，不能有前导0，所以还要分一个小情况。

感想：

比赛时想的就是这个构造方法，但是我SB的把1689的排列放在前面构造Pxxx的形式了，使处理变得复杂，而且这样不能一定能构造到，所以就无尽的WA。。。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,/STACK:102400000,102400000) #define maxn 1005 #define MAXN 100005 #define mod 1000000007 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,ans,flag; bool vis[10]; string fac[7]= { 1869,1968,1689, 6198,8691,8916,1896 }; string s,ss,anss,xx=0000; int main() { int i,j,t,pos,x,y,u,v,w; while(cin>>s) { memset(vis,0,sizeof(vis)); ss=; for(i=0;i
             
               
                D. Maximum Submatrix 2
              题目链接：点击打开链接
               
              思路：
              因为行可交换，列不能交换，所以每个数左边右边的数是不能变的。
              先构造一个dp[i][j] 表示第i行第j个位置前面有多少个连续的1，这个很简单，不用多说。
              然后我们分析一下最优解的在未发生交换的形式，肯定是每一行都有几个连续的1，然后拼起来就构成了一个最大的矩阵了。
              那么我们再构造一个cnt[col][j]，记录一下第col列前面1的个数>=j的种行数，那么最大值可以在dp[i][j]*cnt[j][dp[i][j]]中更新了。
               
              代码：
               
              #include 
               
                
#include 
                
                  #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include
                      #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #pragma comment (linker,/STACK:102400000,102400000) #define maxn 5005 #define MAXN 100005 #define mod 1000000007 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,ans; char mp[maxn][maxn]; int dp[maxn][maxn],cnt[maxn][maxn]; void presolve() { int i,j,t; memset(cnt,0,sizeof(cnt)); for(i=1;i<=n;i++) { dp[i][0]=0; for(j=1;j<=m;j++) { if(mp[i][j]=='1') dp[i][j]=dp[i][j-1]+1; else dp[i][j]=0; cnt[j][dp[i][j]]++; } } for(int col=m;col>=1;col--) { for(j=m;j>=1;j--) { cnt[col][j]+=cnt[col][j+1]; } } } void solve() { int i,j,t; ans=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { t=dp[i][j]*cnt[j][dp[i][j]]; ans=max(ans,t); } } } int main() { int i,j,t; while(~scanf(%d%d,&n,&m)) { for(i=1;i<=n;i++) { scanf(%s,mp[i]+1); } presolve(); solve(); printf(%d ,ans); } return 0; } /* 4 7 1001111 1110010 0111001 0110011 */