这貌似是NOIP前最后一场模拟赛了，然而还是没有AK QAQ

T1 东东学奥数

题目大意：

求第n个素数，n<=100000
素数筛，我是先跑了暴力求出最大的素数，然后再用的快筛；

标准模板：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int f[1300000];
int a[1300000];
int main()
{
	freopen("prime.in","r",stdin);
	freopen("prime.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=1299709;i++)
	{
		if(a[i]==0)
		{
			f[++f[0]]=i;
		}
		if(f[0]==n)
		{
			printf("%d ",i);
			break;
		}
		for(int j=1;j<=f[0]&&i*f[j]<=1299709;j++)
		{
			if(a[i*f[j]]==0)
			{
				a[i*f[j]]=1;
			}
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
} 
//1299709

T2 东东又被困

题目描述：

东东在小黑屋里发现有N个按钮，编号为1到N。按钮的正上方有一个显示器，显示器上显示出M条信息。第i条信息由2个正整数描述：（Ai Bi），表示Ai号按钮应该在Bi号按钮前被按下。
如果东东能够打开门请输出“OK”。如果给定的信息有误，请输出有多少个按钮不能被确定按下的顺序。

正解是拓扑排序；
因为我对链表的理解还不够，无奈之下用邻接矩阵存储，只拿了60（考试时是256MB，所以实际分数比这个还要低）
赛后重新总结，加深了对链表的理解

改后AC代码：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m;
int head[100100],next[100100],to[100100],tot;
int ans[100100];
int v[100100];
void check()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		if(v[i]==0) q.push(i);
	}	
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		ans[++ans[0]]=x;
		for(int i=head[x];i!=0;i=next[i])
		{
			v[to[i]]--;
			if(v[to[i]]==0)
			{
				q.push(to[i]);
			}
		}
	}
} 
void add(int x,int y)
{ 
	tot++;
	to[tot]=y;
	next[tot]=head[x];
	head[x]=tot;
}
int main()
{
	freopen("button.in","r",stdin);
	freopen("button.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		v[y]++;
	}
	check();
	if(ans[0]==n)printf("OK");
	else printf("%d",n-ans[0]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

考试时如果数据量不算太大的话可以考虑用邻矩啊?，详见：传送门；

T3 东东去郊游

题目大意：

混合背包

当时脑子一热，不知道为什么写了二维数组，还写挂了?；
赛后改成了一维数组；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans;
int f[200100];
int w,v,bol;
void one(int a,int b)
{
	for(int i=m;i>=a;i--)
		if(f[i-a]!=0||i-a==0)f[i]=max(f[i-a]+b,f[i]);
}
void all(int a,int b)
{
	for(int i=a;i<=m;i++)
		if(f[i-a]!=0||i-a==0)f[i]=max(f[i-a]+b,f[i]);
}
void part(int a,int b,int c)
{
	int tot=1,tmp=0;
	while(tot<c)
	{
		one(a<<tmp,b<<tmp);
		++tmp;
		tot+=(1<<tmp);
	}
	tot-=1<<tmp;
	if(tot<c)
	{
		tmp=c-tot;
		one(a*tmp,b*tmp);
	}
	return;
}
int main()
{
	freopen("mix.in","r",stdin);
	freopen("mix.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&w,&v,&bol);
		if(bol==1) one(w,v);
		else if(bol==-1) all(w,v); 
		else part(w,v,bol);
	}
	for(int i=1;i<=m;i++) ans=max(ans,f[i]);
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

看来多重背包二进制优化还是还不够熟练

总结，这场考试貌似是NOIP前最后一场模拟赛了，希望在最后的一周里好好复习，保省二，冲省一，frighting!!!