2017 ZSTU寒假排位赛 #7-白红宇

2017 ZSTU寒假排位赛 #7

阅读量：7031 次

发布时间：2019-06-28

本文共 2318 字，大约阅读时间需要 7 分钟。

　　题目链接：。

　　A题，水题，直接按照题意模拟一下即可。

　　B题，我用的是线段树。大力用的差分标记（上次听zy说过，下次再做些类似的题目好了），lyf的方法也不错。

　　C题，不难发现，00是不能变成其他的，而11可以变成10或者01，01/10也可以变成11。那么，如果字符串a中全是0，而b中有1，那么a是不能变成b的；同理，如果b全是0，而a中有1存在，也是不能够转化的。

　　D题，floyd即可。具体见代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
           6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #define t_mid (l+r>>1)10 #define ls (o<<1)11 #define rs (o<<1|1)12 #define lson ls,l,t_mid13 #define rson rs,t_mid+1,r14 using namespace std;15 typedef long long ll;16 typedef pair
              
                pii;17 const int N = 500 + 5;18 const int inf = 0x3f3f3f3f;19 20 int d[N][N];21 int a[N];22 int on[N];23 ll ans[N];24 25 int main()26 {27 int n;28 cin >> n;29 for(int i=1;i<=n;i++)30 {31 for(int j=1;j<=n;j++)32 {33 scanf("%d",&d[i][j]);34 }35 }36 for(int i=1;i<=n;i++) scanf("%d",a+i);37 for(int k=n;k>=1;k--)38 {39 on[a[k]] = 1;40 for(int i=1;i<=n;i++)41 {42 for(int j=1;j<=n;j++)43 {44 d[i][j] = min(d[i][j], d[i][a[k]]+d[a[k]][j]);45 if(on[i] && on[j]) ans[k] += d[i][j];46 }47 }48 }49 for(int i=1;i<=n;i++) printf("%I64d%c",ans[i],i==n?'\n':' ');50 return 0;51 }

　　E题，依稀记得以前做过不能换行的DP。现在整个模型全部温故了一遍=。=思路参见：。能换行，那么保存下同一列中每一行能够向左延伸的最大距离，排序一遍，再按照之前的做法dp一下即可。那么如果是能够换列，道理也是类似的。AC代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
           6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #define t_mid (l+r>>1)10 #define ls (o<<1)11 #define rs (o<<1|1)12 #define lson ls,l,t_mid13 #define rson rs,t_mid+1,r14 using namespace std;15 typedef long long ll;16 typedef pair
              
                pii;17 const int N = 5000 + 5;18 const int inf = 0x3f3f3f3f;19 20 int n,m;21 char s[N][N];22 int dp[N][N];23 24 int main()25 {26 cin >> n >> m;27 for(int i=1;i<=n;i++) scanf("%s",s[i]+1);28 for(int i=1;i<=n;i++)29 {30 for(int j=1;j<=m;j++)31 {32 if(s[i][j] == '1') dp[j][i] = dp[j-1][i] + 1;33 else dp[j][i] = 0;34 }35 }36 int ans = 0;37 for(int j=1;j<=m;j++)38 {39 sort(dp[j]+1,dp[j]+1+n);40 for(int i=n;i>=1;i--) ans = max(ans, dp[j][i]*(n-i+1));41 }42 cout << ans << endl;43 return 0;44 }

——————————————————2017.2.4分割线——————————————————

　　注意！上面这个人的博客中第一个问题的解法是错误的，正确做法参照后面一篇博客中的两种解法。

转载于:https://www.cnblogs.com/zzyDS/p/6362437.html

你可能感兴趣的文章