PKUSC 2014 #2

2015年6月1日3,5020

A:Quad Tiling

对于某一层来说，状态只有6种，所以手推下转移方程，矩阵乘法加速即可

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int n,m;
struct M{
	ll a[7][7];
	M(){
		memset(a,0,sizeof(a));
	}
	friend M operator*(M a,M b){
		M c;
		for(int i=1;i<=6;i++)
			for(int j=1;j<=6;j++)
				for(int k=1;k<=6;k++)
				{
					c.a[i][j]+=a.a[i][k]*b.a[k][j];
					c.a[i][j]%=m;
				}
		return c;
	}
	friend M operator^(M a,int b){
		M ans;
		for(int i=1;i<=6;i++)ans.a[i][i]=1;
		for(int i=b;i;i>>=1,a=a*a)
			if(i&1)ans=ans*a;
		return ans;
	}
}b;
void link(int x,int y)
{
	b.a[x][y]=1;
}
int main()
{
	link(1,1);link(3,1);link(4,1);link(5,1);link(6,1);
	link(5,2);link(4,3);link(1,3);
	link(3,4);link(1,4);
	link(1,5);link(2,5);link(1,6);
	while(scanf("%d%d",&n,&m))
	{
		if(n==0)return 0;
		M ans;
		ans.a[1][1]=1;
		printf("%lld\n",(ans*(b^n)).a[1][1]);
	}
	return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char c=getchar();

while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

return x*f;

}

int n,m;

struct M{

ll a[7][7];

M(){

memset(a,0,sizeof(a));

}

friend M operator*(M a,M b){

M c;

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

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

for(int k=1;k<=6;k++)

{

c.a[i][j]+=a.a[i][k]*b.a[k][j];

c.a[i][j]%=m;

}

return c;

}

friend M operator^(M a,int b){

M ans;

for(int i=1;i<=6;i++)ans.a[i][i]=1;

for(int i=b;i;i>>=1,a=a*a)

if(i&1)ans=ans*a;

return ans;

}

}b;

void link(int x,int y)

{

b.a[x][y]=1;

}

int main()

{

link(1,1);link(3,1);link(4,1);link(5,1);link(6,1);

link(5,2);link(4,3);link(1,3);

link(3,4);link(1,4);

link(1,5);link(2,5);link(1,6);

while(scanf("%d%d",&n,&m))

{

if(n==0)return 0;

M ans;

ans.a[1][1]=1;

printf("%lld\n",(ans*(b^n)).a[1][1]);

}

return 0;

}

B:Garden

傻逼线段树

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int T,n,m,K;
int a[200005];
struct data{
	int l,r,mx,tag;
}t[800005];
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;t[k].mx=-inf;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void pushdown(int k)
{
	int l=t[k].l,r=t[k].r;
	if(!t[k].tag||l==r)return;
	int tag=t[k].tag;t[k].tag=0;
	t[k<<1].mx+=tag;t[k<<1].tag+=tag;
	t[k<<1|1].mx+=tag;t[k<<1|1].tag+=tag;
}
void add(int k,int x,int y,int val)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
	if(l==x&&y==r)
	{
		t[k].tag+=val;
		t[k].mx+=val;
		return;
	}
	if(x<=mid)add(k<<1,x,min(mid,y),val);
	if(y>mid)add(k<<1|1,max(mid+1,x),y,val);
	t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
}
int query(int k,int x,int y)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
	if(l==x&&y==r)
		return t[k].mx;
	int ans=-inf;
	if(x<=mid)ans=max(ans,query(k<<1,x,min(mid,y)));
	if(y>mid)ans=max(ans,query(k<<1|1,max(mid+1,x),y));
	return ans;
}
void modify(int k,int x,int val)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
	if(l==r){t[k].mx=val;return;}
	if(x<=mid)modify(k<<1,x,val);
	else modify(k<<1|1,x,val);
	t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
}
void change(int pos,int val)
{
	int l=max(1,pos-K+1),r=min(n-K+1,pos),t=a[pos];
	add(1,l,r,val-t);
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();m=read();K=read();
		for(int i=1;i<=n;i++)a[i]=read();
		build(1,1,n-K+1);
		int tmp=0;
		for(int i=n;i>=n-K+1;i--)tmp+=a[i];
		for(int i=n-K+1;i;i--)
		{
			modify(1,i,tmp);
			tmp=tmp+a[i-1]-a[i+K-1];
		}
		for(int i=1;i<=m;i++)
		{
			int p=read(),x=read(),y=read();
			if(p==0){change(x,y);a[x]=y;}
			if(p==1)
			{
				change(x,a[y]);change(y,a[x]);
				swap(a[x],a[y]);
			}
			if(p==2)
			{
				printf("%d\n",query(1,x,y-K+1));
			}
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char c=getchar();

while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

return x*f;

}

int T,n,m,K;

int a[200005];

struct data{

int l,r,mx,tag;

}t[800005];

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;t[k].mx=-inf;

if(l==r)return;

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

}

void pushdown(int k)

{

int l=t[k].l,r=t[k].r;

if(!t[k].tag||l==r)return;

int tag=t[k].tag;t[k].tag=0;

t[k<<1].mx+=tag;t[k<<1].tag+=tag;

t[k<<1|1].mx+=tag;t[k<<1|1].tag+=tag;

}

void add(int k,int x,int y,int val)

{

pushdown(k);

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==x&&y==r)

{

t[k].tag+=val;

t[k].mx+=val;

return;

}

if(x<=mid)add(k<<1,x,min(mid,y),val);

if(y>mid)add(k<<1|1,max(mid+1,x),y,val);

t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);

}

int query(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==x&&y==r)

return t[k].mx;

int ans=-inf;

if(x<=mid)ans=max(ans,query(k<<1,x,min(mid,y)));

if(y>mid)ans=max(ans,query(k<<1|1,max(mid+1,x),y));

return ans;

}

void modify(int k,int x,int val)

{

pushdown(k);

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==r){t[k].mx=val;return;}

if(x<=mid)modify(k<<1,x,val);

else modify(k<<1|1,x,val);

t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);

}

void change(int pos,int val)

{

int l=max(1,pos-K+1),r=min(n-K+1,pos),t=a[pos];

add(1,l,r,val-t);

}

int main()

{

T=read();

while(T--)

{

n=read();m=read();K=read();

for(int i=1;i<=n;i++)a[i]=read();

build(1,1,n-K+1);

int tmp=0;

for(int i=n;i>=n-K+1;i--)tmp+=a[i];

for(int i=n-K+1;i;i--)

{

modify(1,i,tmp);

tmp=tmp+a[i-1]-a[i+K-1];

}

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

{

int p=read(),x=read(),y=read();

if(p==0){change(x,y);a[x]=y;}

if(p==1)

{

change(x,a[y]);change(y,a[x]);

swap(a[x],a[y]);

}

if(p==2)

{

printf("%d\n",query(1,x,y-K+1));

}

return 0;

}

D:One-move checkmate

枚举一下皇后能一步到达的位置，然后判一下是否将死

注意细节较多具体见discuss

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int xx[]={0,0,1,1,1,-1,-1,-1},yy[]={1,-1,1,0,-1,1,0,-1};
char ans1,ans2;
char k1[2],q1[2],k2[2];
bool check1(int x,int y)
{
	return abs(x-k1[0])<=1&&abs(y-k1[1])<=1;
}
bool check2(int x,int y)
{
	return abs(x-k2[0])<=1&&abs(y-k2[1])<=1;
}
bool check(char x,char y,char nx,char ny)
{
	if(nx>'h'||nx<'a'||ny>'8'||ny<'1')return 0;
	int tx=x-nx,ty=y-ny;
	if(!tx||!ty||tx==ty||tx==-ty)return 0;
	if(check1(nx,ny))return 0;
	return 1;
}
bool move(int d,int x)
{
	char tx=q1[0]+xx[d]*x,ty=q1[1]+yy[d]*x;
	if(tx>'h'||tx<'a'||ty>'8'||ty<'1')return 0;
	if(k1[0]==tx&&k1[1]==ty)return 0;
	bool flag=0;
	if(check2(tx,ty))
		flag=!check1(tx,ty);
	flag|=check(tx,ty,k2[0],k2[1]);
	for(int i=0;i<8;i++)
		flag|=check(tx,ty,k2[0]+xx[i],k2[1]+yy[i]);
	if(!flag)
	{
		if(!ans1||tx<ans1||(tx==ans1&&ty<ans2))
			ans1=tx,ans2=ty;
	}
	return 1;
}
int main()
{
	scanf("%s",k1);scanf("%s",q1);scanf("%s",k2);
	for(int i=0;i<8;i++)
		for(int j=1;j<=8;j++)
			if(!move(i,j))break;
	if(!ans1)puts("no");
	else 
		printf("%c%c",ans1,ans2);
	return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char c=getchar();

while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

return x*f;

}

int xx[]={0,0,1,1,1,-1,-1,-1},yy[]={1,-1,1,0,-1,1,0,-1};

char ans1,ans2;

char k1[2],q1[2],k2[2];

bool check1(int x,int y)

{

return abs(x-k1[0])<=1&&abs(y-k1[1])<=1;

}

bool check2(int x,int y)

{

return abs(x-k2[0])<=1&&abs(y-k2[1])<=1;

}

bool check(char x,char y,char nx,char ny)

{

if(nx>'h'||nx<'a'||ny>'8'||ny<'1')return 0;

int tx=x-nx,ty=y-ny;

if(!tx||!ty||tx==ty||tx==-ty)return 0;

if(check1(nx,ny))return 0;

return 1;

}

bool move(int d,int x)

{

char tx=q1[0]+xx[d]*x,ty=q1[1]+yy[d]*x;

if(tx>'h'||tx<'a'||ty>'8'||ty<'1')return 0;

if(k1[0]==tx&&k1[1]==ty)return 0;

bool flag=0;

if(check2(tx,ty))

flag=!check1(tx,ty);

flag|=check(tx,ty,k2[0],k2[1]);

for(int i=0;i<8;i++)

flag|=check(tx,ty,k2[0]+xx[i],k2[1]+yy[i]);

if(!flag)

{

if(!ans1||tx<ans1||(tx==ans1&&ty<ans2))

ans1=tx,ans2=ty;

}

return 1;

}

int main()

{

scanf("%s",k1);scanf("%s",q1);scanf("%s",k2);

for(int i=0;i<8;i++)

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

if(!move(i,j))break;

if(!ans1)puts("no");

else

printf("%c%c",ans1,ans2);

return 0;

}

E:ATP

二分答案后，从比赛最后阶段往前考虑

当然是每场给每个人分配一个可以打败的最NB的人。。。贪心判解的可行性

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int n,K,x;
vector<int>q;
bool mark[5005];
bool check(int mid)
{
	memset(mark,0,sizeof(mark));
	q.clear();
	q.push_back(mid);mark[mid]=1;
	for(int p=1;p<=x;p++)
	{
		int t=q.size();
		for(int j=0;j<t;j++)
			for(int k=max(1,q[j]-K);k<=mid;k++)
				if(!mark[k])
				{
					mark[k]=1;q.push_back(k);break;
				}
	}
	for(int i=1;i<=mid;i++)
		if(!mark[i])return 0;
	return 1;
}
int main()
{
	n=read();K=read();
	x=1;int t=2;
	while(t*2<=n)t*=2,x++;
	int l=1,r=n,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char c=getchar();

while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

return x*f;

}

int n,K,x;

vector<int>q;

bool mark[5005];

bool check(int mid)

{

memset(mark,0,sizeof(mark));

q.clear();

q.push_back(mid);mark[mid]=1;

for(int p=1;p<=x;p++)

{

int t=q.size();

for(int j=0;j<t;j++)

for(int k=max(1,q[j]-K);k<=mid;k++)

if(!mark[k])

{

mark[k]=1;q.push_back(k);break;

}

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

if(!mark[i])return 0;

return 1;

}

int main()

{

n=read();K=read();

x=1;int t=2;

while(t*2<=n)t*=2,x++;

int l=1,r=n,ans=0;

while(l<=r)

{

int mid=(l+r)>>1;

if(check(mid))ans=mid,l=mid+1;

else r=mid-1;

}

printf("%d\n",ans);

return 0;

}

« usaco 刷水。。。「CF263X」Codeforces Round #161 (Div. 2) »

hzwer.com _ Home | http://hzwer.com

PKUSC 2014 #2

分类目录

热门文章

Myfriends

近期评论