hdu 4331 Image Recognition
wa的有点无语,细节比较多的题对我来说真伤不起。。。
#include<iostream>
#include<vector>
#include<string>
#include<cstdio>
#include<iomanip>
#include<algorithm>
using namespace std;
#define pb push_back
#define read freopen("out.txt","r",stdin)
#define write freopen("zz.txt","w",stdout)
const int maxn = 1005;
struct zz
{
int now;
bool w;
}zx;
vector<zz>g[maxn];
int a[maxn][maxn];
int u[maxn][maxn];
int d[maxn][maxn];
int r[maxn][maxn];
int l[maxn][maxn];
int x[maxn][maxn];
int fd[maxn];
int n;
int lowbit(int x)
{
return x&(-x);
}
void insert(int x)
{
while(x<maxn)
{
fd[x]++;
x+=lowbit(x);
}
return ;
}
int find(int x)
{
int temp = x - 1;
int re=0;
while(temp>0)
{
re+=fd[temp];
temp-=lowbit(temp);
}
return re;
}
int start()
{
int temp;
int now;
int tot;
for(int k=2;k<=2*n;k++)
{
tot = 0;
for(int i=0;i<=n;i++)
{
g[i].clear();
}
for(int i=1;i<=n;i++)
{
if(k-i<1 || k-i>n) continue;
if(!a[i][k-i]) continue;
temp = i-min(u[i][k-i],r[i][k-i]);
zx.now = i;
zx.w = false;
g[temp].pb(zx);
zx.w = true;
temp = i;
g[temp].pb(zx);
}
memset(fd,0,sizeof(fd));
for(int i=1;i<=n;i++)
{
if(k-i<1 || k-i>n) continue;
if(a[i][k-i])
{
temp = i+min(l[i][k-i],d[i][k-i])-1;
insert(temp);
tot++;
}
for(int j=0;j<g[i].size();j++)
{
if(g[i][j].w)
{
now = g[i][j].now;
x[now][k-now]+=tot-find(now);
}
else
{
now = g[i][j].now;
x[now][k-now]-=tot-find(now);
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
ans+=x[i][j];
}
}
return ans;
}
int main()
{
int T;
cin>>T;
for(int tt=1;tt<=T;tt++)
{
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
x[i][j]=u[i][j]=d[i][j]=r[i][j]=l[i][j]=0;
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j])
补充:软件开发 , C++ ,