10.12 正睿普及4

目录

2018.10.12 正睿普及4

时间：3.5h
期望得分：100+?+100+10
实际得分：100+45+100+10

比赛链接

A 学打字

题目链接

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=10005;

char s[N],t[N];

int main()
{
	scanf("%s%s",s+1,t+1);
	int n=strlen(s+1),m=strlen(t+1),ans=0;
	s[n+1]='!', t[n+1]='?';
	for(int i=1; i<=n; )
	{
		int ps=i,pt=1;
		while(s[ps]==t[pt]) ++ps,++pt;
		if(pt>m) i+=m, ++ans;
		else ++i, ++ans;
	}
	printf("%d
",ans);

	return 0;
}

B 减肥计划(DP 背包)

题目链接

当(sum ai)一定时，(sum bi)越大自然越优。所以令(f[i])表示(sum ai=i)时(sum bi)的最大值，转移就是个背包。
所以复杂度为(O(n^2*a_{max}))。期望得分(60)。
我们发现问题在于背包容量太大。
一个简单的性质是(max{frac{bi}{ai}}geqfrac{sum bi}{sum ai})。所以我们删去所选集合中(frac{bi}{ai})最小的那个一定不会更差。
所以在满足(sum aigeq m)时我们可以不断删元素，得到的答案一定不会更差。这样需要考虑的背包最大容量就是(m+a_{max})。
所以复杂度(O(n(m+a_{max})))。

傻了，考试的时候背包都没想到，一直在想分数规划，但是没法解啊。骗了个分。

//988ms	900kb
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+1e4+5;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
int Gcd(int x,int y)
{
	return y?Gcd(y,x%y):x;
}

int main()
{
	static int f[N];

	int n=read(),m=read(),mx=0,sum=0;
	memset(f,-0x3f,sizeof f);
	f[0]=0;
	for(int i=1,ai,bi; i<=n; ++i)
	{
		sum+=ai=read(),mx=std::max(mx,ai),bi=read();
		for(int j=std::min(m+mx,sum); j>=ai; --j)
			f[j]=std::max(f[j],f[j-ai]+bi);
	}
	if(sum<m) return puts("-1"),0;

	int A=0,B=1;
	for(int i=m+mx; i>=m; --i)
		if(1ll*A*i<1ll*B*f[i]) A=f[i], B=i;
	int g=Gcd(A,B);
	printf("%d/%d
",A/g,B/g);

	return 0;
}

C 卡常数(倍增)

题目链接

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define BIT 29
typedef long long LL;
const int N=1e5+5,M=N;

int f[N][30];
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
int Calc(int x)
{
	static int bit[66];
	int cnt=0;
	for(int v=x; v; bit[++cnt]=v%10,v/=10);
	while(cnt<5) bit[++cnt]=0;
	std::sort(bit+1,bit+1+cnt);
	int mn=0,mx=0;
	for(int i=1; i<=5; ++i) mn=mn*10+bit[i];
	for(int i=5; i; --i) mx=mx*10+bit[i];
	return mx-mn;
}
void Init()
{
	f[0][0]=0;
	const int n=99999;
	for(int i=1; i<=n; ++i) f[i][0]=Calc(i);
	for(int i=1; i<=BIT; ++i)
		for(int x=1; x<=n; ++x) f[x][i]=f[f[x][i-1]][i-1];
}
void Solve(int x,int t)
{
	static char o[66];
	if(t<=100)
		while(t--) x=f[x][0];
	else
	{
		for(int i=BIT; ~i; --i)
			if(t>>i&1) x=f[x][i];
	}
	int cnt=0;
	for(int v=x; v; o[++cnt]=v%10+'0',v/=10);
	while(cnt<5) o[++cnt]='0';
	for(int i=5; i; putchar(o[i--])); putchar('
');
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

	Init();
	for(int T=read(),c=read(); T--; Solve(read(),c));
	return 0;
}

D 造人(BFS)

题目链接

一条回文路径关于中点对称，所以我们枚举点作为路径中点BFS（一个点走的同时另一个点对称走），就可以知道，对于长为偶数的回文路径，一个点能否一次走到另一个点。
对于长为奇数的回文路径，我们从一条边开始BFS就行了。这部分复杂度(O(n^4))。
有了从一个点能一次到达哪些点，对于询问从起点BFS就可以了。复杂度也是(O(n^4))。

//288ms	8796kb
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=53,INF=0x3f3f3f3f,dx[]={-1,1,0,0},dy[]={0,0,-1,1};

bool mp[N][N],ok[N][N][N][N];
struct Node1{
	int xa,ya,xb,yb;
};
struct Node2{
	int x,y;
};

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline char Get()
{
	register char c=gc();
	for(; c!='.'&&c!='#'&&c!='F'&&c!='R'; c=gc());
	return c;
}
void BFS(int x1,int y1,int x2,int y2)
{
	static bool vis[N][N];
	static std::queue<Node1> q;

	memset(vis,0,sizeof vis);
	vis[x1][y1]=1, vis[x2][y2]=1, q.push((Node1){x1,y1,x2,y2});
	while(!q.empty())
	{
		Node1 tmp=q.front(); q.pop();
		int xa=tmp.xa,ya=tmp.ya,xb=tmp.xb,yb=tmp.yb;
		ok[xa][ya][xb][yb]=1, ok[xb][yb][xa][ya]=1;
		for(int i=0,x,y,xx,yy; i<4; ++i)
		{
			x=xa+dx[i], xx=xb+dx[i^1];
			y=ya+dy[i], yy=yb+dy[i^1];
			if(vis[x][y]||vis[xx][yy]||!mp[x][y]||!mp[xx][yy]) continue;
			vis[x][y]=1, vis[xx][yy]=1;
			q.push((Node1){x,y,xx,yy});
		}
	}
}
int BFS2(int n,int m,int sx,int sy,int ex,int ey)
{
	static int dis[N][N];
	static std::queue<Node2> q;

	while(!q.empty()) q.pop();
	memset(dis,0x3f,sizeof dis);
	dis[sx][sy]=0, q.push((Node2){sx,sy});
	while(!q.empty())//BFS
	{
		int x=q.front().x,y=q.front().y; q.pop();
		if(x==ex&&y==ey) return dis[ex][ey];
		for(int i=1; i<=n; ++i)
			for(int j=1; j<=m; ++j)
				if(dis[i][j]==INF && ok[x][y][i][j])
					dis[i][j]=dis[x][y]+1, q.push((Node2){i,j});
	}
	return dis[ex][ey]<INF?dis[ex][ey]:-1;
}

int main()
{
	for(int T=read(); T--; )
	{
		memset(ok,0,sizeof ok);
		memset(mp,0,sizeof mp);//边界得清空 
		int n=read(),m=read(),sx=0,sy=0,ex=0,ey=0;
		for(int i=1; i<=n; ++i)
			for(int j=1; j<=m; ++j)
				switch(Get())
				{
					case '.': mp[i][j]=1; break;
					case '#': mp[i][j]=0; break;
					case 'F': mp[i][j]=1,ex=i,ey=j; break;
					case 'R': mp[i][j]=1,sx=i,sy=j; break;
				}
		for(int i=1; i<=n; ++i)
			for(int j=1; j<=m; ++j)
				if(mp[i][j])
				{
					BFS(i,j,i,j);
					if(mp[i][j+1]) BFS(i,j,i,j+1);
					if(mp[i+1][j]) BFS(i,j,i+1,j);
				}
		printf("%d
",BFS2(n,m,sx,sy,ex,ey));
	}
	return 0;
}

考试代码

B

#include <cstdio>
#include <cctype>
#include <algorithm>
#define eps 1e-14
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e4+5;
//#define double long double

int n,m,A[N],B[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Frac
{
	LL x,y;
	Frac(LL x=0,LL y=0):x(x),y(y) {}

	LL Gcd(int x,int y) {return y?Gcd(y,x%y):x;}
	inline void Fix() {LL d=Gcd(std::abs(x),std::abs(y)); x/=d,y/=d;}
	friend Frac operator +(Frac a,Frac b)
	{
		Frac res=Frac{a.x*b.y+a.y*b.x,a.y*b.y};
		res.Fix(); return res;
	}
	friend Frac operator *(Frac a,Frac b)
	{
		Frac res=Frac{a.x*b.x,a.y*b.y};
		res.Fix(); return res;
	}
	friend bool operator !=(Frac a,Frac b)
	{
		a.Fix(), b.Fix(); return a.x!=b.x||a.y!=b.y;
	}
	friend bool operator ==(Frac a,Frac b)
	{
		a.Fix(), b.Fix(); return a.x==b.x&&a.y==b.y;
	}
	friend bool operator <(Frac a,Frac b)
	{
		a.Fix(), b.Fix();
		return a.x*b.y<=a.y*b.x;
	}
	inline void Print()
	{
		Fix(), printf("%lld/%lld
",x,y);
//		Fix(), printf("%I64d/%I64d
",x,y);
	}
};

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
void Spec()
{
	Frac ans(0,1);
	for(int s=1,all=1<<n; s<all; ++s)
	{
		int sa=0,sb=0;
		for(int i=0; i<n; ++i) if(s>>i&1) sa+=A[i+1],sb+=B[i+1];
		if(sa>=m && ans<Frac(sb,sa)) ans=Frac(sb,sa);
	}
	ans.Print();
}
bool Check(double mid)
{
	int sum=0;
	for(int i=1; i<=n; ++i)
		if((double)B[i]-mid*A[i]>=0) sum+=A[i];
	return sum>=m;
}
void GetAns(double x)
{
	printf("GetAns:%.10lf
",x);
	int sa=0,sb=0;
	for(int i=1; i<=n; ++i)
		if((double)B[i]-x*A[i]>=0) sa+=A[i],sb+=B[i];
	Frac(sb,sa).Print();
}

int main()
{
	freopen("a.in","r",stdin);
//	freopen(".out","w",stdout);

	n=read(),m=read(); int suma=0,sumb=0;
	for(int i=1; i<=n; ++i)
		suma+=A[i]=read(), sumb+=B[i]=read();
	if(suma<m) return puts("-1"),0;
//	if(n<=20) return Spec(),0;

	double l=0,r=sumb,mid;
	for(int T=1; T<=100; ++T)
	{
		if(Check(mid=(l+r)*0.5)) l=mid;
		else r=mid;
	}
	GetAns(l);

	return 0;
}

D

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=50;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

	char s[N];
	for(int T=read(); T--; )
	{
		int n=read(),m=read(),sx=0,sy=0,tx=0,ty=0;
		for(int i=1; i<=n; ++i)
		{
			scanf("%s",s+1);
			for(int j=1; j<=m; ++j)
				if(s[j]=='F') tx=i,ty=j;
				else if(s[j]=='R') sx=i,sy=j;
		}
		int dx=std::abs(sx-tx),dy=std::abs(sy-ty),ans=0;
		if(std::abs(dx-dy)<=1) ans=1;
		else ans=1+(std::max(dx,dy)&1);
		printf("%d
",ans);
	}
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/SovietPower/p/9793572.html