10.17 NOIP模拟赛

目录

• 2018.10.17 NOIP模拟赛
  • A 咒语curse
  • B 神光light(二分 DP)
  • C 迷宫maze(次短路)
  • 考试代码
    • B

---

2018.10.17 NOIP模拟赛

时间：1h15min(实际)
期望得分：100+100+100
实际得分：100+70+100

为什么这么困啊。。

A 咒语curse

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

int tm[N];
char s[N],ans[N];

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("curse.in","r",stdin);
	freopen("curse.out","w",stdout);

	int n=read();
	scanf("%s",s+1); int len=strlen(s+1);
	for(int j=1; j<=len; ++j) if(s[j]=='0') ++tm[j];
	for(int i=2; i<=n; ++i)
	{
		scanf("%s",s+1);
		for(int j=1; j<=len; ++j) if(s[j]=='0') ++tm[j];
	}
	for(int i=1; i<=len; ++i)
		if(tm[i]>=n-tm[i]) ans[i]='0';
		else ans[i]='1';
	ans[len+1]='', puts(ans+1);

	return 0;
}

B 神光light(二分 DP)

(f[i][j])表示用了(i)次红光(j)次绿光最远能到达哪个点。预处理之后转移即可。

考试的时候很困，很sb的写了(O(n))贪心。。

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

int n,A,B,pos[N];

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,int len)
{
	int l=x,r=n,mid,ans=l; x=pos[x];//!
	while(l<=r)
		if(pos[mid=l+r>>1]-x+1<=len) ans=mid,l=mid+1;
		else r=mid-1;
	return ans;
}
bool Check(int len)
{
	static int f[N][N],p1[N],p2[N];
	for(int i=1; i<=n; ++i)
		p1[i]=Calc(i,len), p2[i]=Calc(i,len<<1);
	memset(f,0,sizeof f);
	f[0][0]=0/*not 1...*/, p1[n+1]=p2[n+1]=n;
	for(int i=0; i<=A; ++i)
		for(int j=0; j<=B; ++j)
			f[i+1][j]=std::max(f[i+1][j],p1[f[i][j]+1]), f[i][j+1]=std::max(f[i][j+1],p2[f[i][j]+1]);
	return f[A][B]>=n;
}

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

	n=read(),A=std::min(n,read()),B=std::min(n,read());
	if(A+B>=n) return puts("1"),0;
	for(int i=1; i<=n; ++i) pos[i]=read();
	std::sort(pos+1,pos+1+n);
	int l=1,r=pos[n]-pos[1]+1,mid,ans=r;
	while(l<=r)
	{
		if(Check(mid=l+r>>1)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d
",ans);

	return 0;
}

C 迷宫maze(次短路)

枚举每一条边((u,v,w))，(次短路 = 1到u的最短路 + w + v到n的最短路)。
因为次短路与最短路相比会有一段绕路，且不会有两次绕路。

这题边可以多次走，所以不存在次短路时要多走两次最短路上边权最小的边。
忘了这个问题，但数据水过了，不改了。

辣鸡题解还是个DFS，出(n=5000)。

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define mp std::make_pair
#define pr std::pair<int,int>
#define gc() getchar()
typedef long long LL;
const int N=5005,M=2e5+5;

int Enum,H[N],nxt[M],fr[M],to[M],len[M],ds[N],dt[N];

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 void AE(int w,int u,int v)
{
	to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
	to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
void Dijkstra(int s,int *dis)
{
	static bool vis[N];
	static std::priority_queue<pr> q;
	memset(vis,0,sizeof vis);
	memset(dis,0x3f,sizeof ds);
	dis[s]=0, q.push(mp(0,s));
	while(!q.empty())
	{
		int x=q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=H[x]; i; i=nxt[i])
			if(dis[to[i]]>dis[x]+len[i]) q.push(mp(-(dis[to[i]]=dis[x]+len[i]),to[i]));
	}
}

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

	int n=read(),m=read();
	for(int i=1; i<=m; ++i) AE(read(),read(),read());
	Dijkstra(1,ds), Dijkstra(n,dt);
	int ans=2e9,Min=ds[n];
	for(int i=1,tmp; i<=Enum; ++i)
		if((tmp=ds[fr[i]]+dt[to[i]]+len[i])>Min) ans=std::min(ans,tmp);
	printf("%d
",ans);

	return 0;
}

考试代码

B

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+5;//2005;

int n,A,B,pos[N],L[N],R[N];

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;
}
bool Check(int len)
{
	int now=1,cnt=1; L[1]=pos[1];
	while(now<n)
	{
		if(pos[now+1]-L[cnt]+1>len)
			R[cnt]=pos[now], L[++cnt]=pos[++now];
		else ++now;
	}
	R[cnt]=pos[n];
	if(cnt<=A) return 1;

	int rest=cnt-A,used=0;
	for(int i=2; i<=cnt; ++i)
		if(R[i]-L[i-1]+1<=2*len)
		{
			++used, rest-=2, ++i;
			if(used>B) return 0;
			if(rest<=0) return 1;
		}
	return rest-B+used<=0;
}

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

	n=read(),A=read(),B=read();
	for(int i=1; i<=n; ++i) pos[i]=read();
	std::sort(pos+1,pos+1+n);
	int l=1,r=1e9,mid,ans=1e9;
	while(l<=r)
	{
		if(Check(mid=l+r>>1)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d
",ans);

	return 0;
}/*
7 1 2
1
3
5
7
9
11
21
*/