2018.10.28 练习赛

T1 蒜头君的兔子

题解：

设定一个初始矩阵:

\(A[10]\)表示这一年每种岁数的兔子有几只，显然初始化\(A[1]=1\)即可，然后开始推转移；

每到下一年，所有的兔子长大一岁，满十岁的兔子当场去世，然后新出生的兔子（即矩阵中的0号位）等于去年1-9岁的兔子总数之和，于是转移矩阵也搞出来了：

\(T[i-1][i]=1,T[i][0]=1\)

\(code\):

#include
#include
#include
#include
#include
#define reint register int
#define mod 1000000007
#define ll long long
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
    if(flag) x=-x;
}

const int maxn=21;
inline ll add(ll a,ll b){return a+b>=1; 
	}
	return ans;
}

ll n,out_;
arr a,b,ans;
int main()
{
	read(n);
	a=arr(1,11);
	a.a[0][1]=1;
	b=arr(11,11);
	for(reint i=1;i<=9;i++)
	b.a[i][0]=1,b.a[i-1][i]=1;
	b.a[10][0]=1;
    ans=a*mg(b,n-1);
    for(reint i=0;i<11;i++)
    out_=add(out_,ans.a[0][i]);
    printf("%lld",out_);
}

T2 蒜头君的排序

题解：

莫队维护区间逆序对个数，考虑每次增加或减去当前\(Pos\)对逆序对总数做出的贡献；

\(code:\)

#include
#include
#include
#include
#include
#include
#include
#define reint register int
#define mod 1000000007
#define ll long long
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
    if(flag) x=-x;
}
const int maxn=30002;

struct node{
	int x,y,id;
	inline node(int a=0,int b=0,int c=0)
	{x=a,y=b,id=c;}
}q[maxn];

int c[maxn],n,a[maxn],s,m,Ans;
int l=1,r,ans[maxn],block[maxn];

bool cmp(node a,node b)
{
	return block[a.x]==block[b.x]?a.yq[i].y) del(r--,1);
		while(lq[i].x) add(--l,0);
		ans[q[i].id]=Ans;
	}
	for(int i=1;i<=m;i++)
	printf("%d\n",ans[i]);
}

T3 【AMPPZ2014】船长

题解：

本题较水，显然暴力所有点连边会瞬间飞起，于是考虑优化建图；

对横坐标排序，相邻连边；对纵坐标排序，相邻连边；一遍迪杰斯特拉，完；

\(code:\)

#include
#include
#include
#include
#include
#include
#include
#define reint register int
#define ll long long
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
    if(flag) x=-x;
}

const int maxn=200002;
struct point{
	int x,y,id;
	inline point(int a=0,int b=0,int c=0)
	{x=a,y=b;id=c;}
}a[maxn];

struct node{
	int x,len;
	inline node(int a=0,int b=0)
	{x=a,len=b;}
	inline bool operator<(node a)const
	{return len>a.len;}
};

bool cmpx(point a,point b)
{return a.xG[maxn];
priority_queueq;

int cal(point a,point b)
{
	return min(abs(a.x-b.x),abs(a.y-b.y));
}

void djs()
{
	for(reint i=1;i<=n;i++) dis[i]=1e9;
	dis[1]=0;
	q.push(node(1,0));
	while(!q.empty())
	{
		int x=q.top().x;
		int len=q.top().len;
		q.pop();
		if(dis[x]!=len) continue;
		for(reint i=G[x].size()-1;i>=0;i--)
		{
			int p=G[x][i].x;
			len=G[x][i].len;
			if(dis[p]<=dis[x]+len) continue;
			dis[p]=dis[x]+len;
			q.push(node(p,dis[p]));
		}
	}
}

int main()
{
	read(n);
	for(reint i=1;i<=n;i++)
	{
		int x,y;
		read(x),read(y);
		a[i]=point(x,y,i);
	}
	sort(a+1,a+1+n,cmpx);
	for(reint i=1;i