---

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]='\0', 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\n",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\n",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\n",ans);

	return 0;

}/*

7 1 2

1

3

5

7

9

11

21

*/