注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj2003(hnoi2010) 矩阵 + 各种扯淡  

2013-02-26 18:06:24|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Hnoi的写题解速度远远赶不上做题速度怎么办……

好多东西只可意会不可言传

而且事实上我也应该存在着明明就没有完全弄懂的东西吧

现在04~12年中除了没人做的和只有一个人做的以外,04年差一题,07年差一题

但是我看了多少题解呢??

 

不过还是很高兴的。rank竟然如此飙升

今天还第一次鼓起勇气写了平面区域(也就是冬令营讲的将平面图的各个域都抠出来的算法),过掉了bzoj 1035

 

简单的讲下矩阵这道题吧

先求出一个相加等于那个矩阵的错误矩阵(甚至可以不合法)

如果在(1,1)加上k,那么对于(i,j),它要加上(-1)^(i+j-2)

如果在(1,i)加上k,那么对于(i,j),他要加上(-1)^(i)

在(i,1)同理

于是有(i,j)关于(1,1),(1,j),(i,1)的公式

所以先枚举(1,1),再枚举(1,i)并通过公式推出其它元素的上下界,上界>下界即可剪枝

这题我很想吐槽,那就是网上的代码(除了翱犇)以外都长得一模一样……

所以我的代码也就和他们长的一模一样的了……

具体的公式自己推下吧,何朴帆写了的

友情提示:似乎他的公式有个指数是错误的样子

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 210
using namespace std;
int type[]={1,-1};
int digit[MAXN][MAXN],add[MAXN][MAXN],n,m,p;
int C[MAXN][MAXN],L[MAXN][MAXN],R[MAXN][MAXN];
void read()
{
    scanf("%d %d %d",&n,&m,&p);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&digit[i][j]);
            L[i][j]=0,R[i][j]=p-1,C[i][j]=digit[i][j]-C[i-1][j]-C[i][j-1]-C[i-1][j-1];
        }
}
bool dfs(int j)
{
    if(j>m)  return true;
    for(add[1][j]=0;add[1][j]<p;add[1][j]++)
    {
        bool flag=true;
        for(int i=2;i<=n&&flag;i++)
        {
            int vtop=(C[i][j]+add[1][1]*type[(i+j+1)&1]+type[(i-1)&1]*add[1][j]-0)*type[j&1];
            int vbottom=(C[i][j]+add[1][1]*type[(i+j+1)&1]+type[(i-1)&1]*add[1][j]-p+1)*type[j&1];
            if(vbottom>vtop)  swap(vtop,vbottom);
            L[i][j]=max(L[i][j-1],vbottom),R[i][j]=min(R[i][j-1],vtop);
            if(L[i][j]>R[i][j])  flag=false;
        }
        if(flag&&dfs(j+1))  return true;
    }
    return false;
}
void print()
{
    for(add[1][1]=0;!dfs(2);add[1][1]++);
    for(int i=2;i<=n;i++)
        add[i][1]=L[i][m];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            printf("%d%c",C[i][j]+type[(i+j+1)&1]*add[1][1]+type[(i-1)&1]*add[1][j]+type[(j-1)&1]*add[i][1],j<m?' ':'\n');
}
int main()
{
    read();
    print();
    return 0;
}


  评论这张
 
阅读(462)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017