HNOI模拟 Day3.23

一、拓扑(top)
【题目描述】：
给你一个有向二分图，求他的拓扑序列的个数。
【输入】：
第一行两个数 N,M，表示点数和边数。
接下来 M 行每行两个数 a,b，表示 a 向 b 有一条有向边。
【输出】：
仅一行，为拓扑序列个数 mod 10007。
【样例输入】：
8 10
1 5
1 6
2 6
2 7
3 5
3 8
3 7
4 5
4 7
4 6
【样例输出】：
972
【说明】：
10%的数据：N≤10；
30%的数据：N≤20；
60%的数据：N≤30；
100%的数据：N≤40；

状压DP

。。。算了

二、矩阵 K 小数(mat)
【题目描述】
给你一个 N*N 的矩阵，每次询问一个子矩形的第 K 小数。
【输入】
第一行两个数 N,Q，表示矩阵大小和询问组数；
接下来 N 行 N 列一共 N*N 个数，表示这个矩阵；
再接下来 Q 行每行 5 个数描述一个询问：x1,y1,x2,y2,k 表示找到以(x1,y1)为左上角、
以(x2,y2)为右下角的子矩形中的第 K 小数。
【输出】
对于每组询问输出第 K 小的数。
【样例输入】
2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3
【样例输出】：
1 3
【说明】：
矩阵中数字是 109 以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。

二维树状数组+整体二分

一开始写来写去，发现莫名其妙WA了，然后学hzwer的，结果发现变得和他一模一样。在神犇XYK帮助下，原来L,R打萎了。。

改了之后就一直TLE。。

60,75,80,95

然后inline，读入优化，剪枝，终于100.。。。太艰辛了

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

#define M 60010

#define N 510

#define lowbit(x) (x & -(x))

struct Node

{

int x,y,v;

}a[N*N];

int cnt;

bool operator<(Node a,Node b)

{

return a.v<b.v;

}

struct Data

{

int x1,y1,x2,y2,k;

}e[M];

int id[M],f[M],ans[M],tmp[M];

int g[N][N];

int n,m;

int T;

inline int read()

{

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

inline void add(int x,int y,int d)

{

for (int i=x;i<=n;i+=lowbit(i))

for (int j=y;j<=n;j+=lowbit(j))

g[i][j]+=d;

}

inline int query(int x,int y)

{

int zzd(0);

for (int i=x;i;i-=lowbit(i))

for (int j=y;j;j-=lowbit(j))

zzd+=g[i][j];

return zzd;

}

inline int query(int k)

{

int x1=e[k].x1,y1=e[k].y1,x2=e[k].x2,y2=e[k].y2;

return query(x2,y2)+query(x1-1,y1-1)-query(x1-1,y2)-query(x2,y1-1);

}

inline void work(int l,int r,int L,int R)

{

if (l>r || L==R)

return ;

int mid=(L+R)>>1;

while (a[T+1].v<=mid && T<cnt)

add(a[T+1].x,a[T+1].y,1),T++;

while (a[T].v>mid)

add(a[T].x,a[T].y,-1),T--;

int res(0);

for (int i=l;i<=r;i++)

{

if (query(id[i])>e[id[i]].k-1)

f[i]=1,ans[id[i]]=mid,res++;

else

f[i]=0;

}

int nowl=l,nowr=l+res;

for (int i=l;i<=r;i++)

if (f[i])

tmp[nowl++]=id[i];

else

tmp[nowr++]=id[i];

for (int i=l;i<=r;i++)

id[i]=tmp[i];

if (nowl-l)

work(l,nowl-1,L,mid);

if (nowr-l-res)

work(nowl,nowr-1,mid+1,R);

}

int main()

{

freopen("mat.in","r",stdin);freopen("mat.out","w",stdout);

n=read(),m=read();

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

{

cnt++;

a[cnt].x=i;

a[cnt].y=j;

a[cnt].v=read();

}

sort(a+1,a+cnt+1);

for (int i=1;i<=m;i++)

e[i].x1=read(),e[i].y1=read(),e[i].x2=read(),e[i].y2=read(),e[i].k=read(),id[i]=i;

work(1,m,0,a[cnt].v+1);

for (int i=1;i<=m;i++)

printf("%d ",ans[i]);

return 0;

}

三、最远点(dis)
【题目描述】：
给你一个 N 个点的凸多边形，求离每一个点最远的点。
【输入】：
本题有多组数据，第一行一个数 T，表示数据组数。
每组数据第一行一个数 N，表示凸多边形点的个数，接下来 N 对数，依次表示 1~N 这
N 个点的坐标，按照逆时针给出。
【输出】：
对于每组数据输出 N 个数，第 i 个数表示离第 i 个点最远的点的编号，如果有多个最远
点，输出编号最小的。
【样例输入】：
1 4
0 0
1 0
1 1
0 1
【样例输出】：
3 4 1 2
【说明】：
坐标的绝对值在 1e9 以内；
任意点对距离数值的平方不会超过 long long；
令 S 为每组数据凸多边形点数之和；
对于 20%的数据，S<=2000；
对于 50%的数据，S<=50000；
对于 100%的数据，S<=500000；
数据有梯度。

鬼畜分治，考试根本想不到。。

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long long LL;

#define N 500010

struct Node

{

int x,y,k;

}a[N<<1];

int T,n;

int g[N];

LL work(int i, int j)

{

return (LL)(a[i].x-a[j].x)*(a[i].x-a[j].x)+(LL)(a[i].y-a[j].y)*(a[i].y-a[j].y);

}

void work(int l,int r,int L,int R)

{

if (l>r)

return ;

int m=(l+r)>>1,j;

LL ans=0;//,nowl=max(m+1,L),nowr=min(m+n,R);

for (int i=max(m+1,L);i<=min(m+n,R);i++)

{

LL tmp=(LL)work(m,i);

if (tmp>ans)

ans=tmp,j=i;

}

g[m]=a[j].k;

work(l,m-1,L,j);

work(m+1,r,j,R);

}

int main()

{

freopen("dis.in","r",stdin);freopen("dis.out","w",stdout);

scanf("%d",&T);

while (T--)

{

scanf("%d",&n);

for (int i=1;i<=n;i++)

scanf("%d%d",&a[i].x,&a[i].y),a[i].k=i;

for (int i=1;i<=n;i++)

a[i+n]=a[i];

work(1,n,1,n<<1);

for (int i=1;i<=n;i++)

printf("%d ",g[i]);

}

return 0;

}